Abstract
This chapter presents a general overview of parallel approaches for multiobjective optimization. For this purpose, we propose a taxonomy for parallel metaheuristics and exact methods. This chapter covers the design aspect of the algorithms as well as the implementation aspects on different parallel and distributed architectures.
Reviewed by: Heinrich Braun, SAP AG, Walldorf, Germany
Jürgen Branke, University of Karlsruhe, Germany
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Adamidis, P.: Review of Parallel Genetic Algorithms Bibliography. Technical Report, Aristotle University of Thessaloniki (1994)
Antunes, C., Tsoukiás, A.: Against fashion: A travel survival kit in ”modern” MCDA. In: Multicriteria Analysis:International Conference on Multiple Criteria Decision Making, pp. 378–389. Springer, Berlin (1997)
Baita, F., Mason, F., Poloni, C., Ukovich, W.: Genetic Algorithm with Redundancies for the Vehicle Scheduling Problem. In: Biethahn, J., Nissen, V. (eds.) Evolutionary Algorithms in Management Applications, pp. 341–353. Springer, Berlin (1995)
Basseur, M., Lemesre, J., Dhaenens, C., Talbi, E.-G.: Cooperation between branch and bound and evolutionary approaches to solve a bi-objective flow shop problem. In: Ribeiro, C.C., Martins, S.L. (eds.) WEA 2004. LNCS, vol. 3059, pp. 72–86. Springer, Heidelberg (2004)
Bethke, A.D.: Comparison of Genetic Algorithms and Gradient-based Optimizers on Parallel Processors: Efficiency of Use of Processing Capacity. Logic of Computers Group Technical Report 197, University of Michigan (1976)
Branke, J., Schmeck, H., Deb, K., Reddy, M.: Parallelizing Multi-Objective Evolutionary Algorithms: Cone Separation. In: IEEE Congress on Evolutionary Computation, pp. 1952–1957 (2004)
Bui, L.T., Abbass, H.A., Essam, D.: Local models - an approach to distributed multiobjective optimization. Technical Report TR-ALAR-200601002, The Artificial Life and Adaptive Robotics Laboratory, University of New South Wales, Australia (2006)
Cahon, S., Melab, N., Talbi, E.-G.: ParadisEO: A framework for the reusable design of parallel and distributed metaheuristics. Journal of Heuristics 10(3), 357–380 (2004)
Cantu-Paz, E.: A Survey of Parallel Genetic Algorithms. IlliGAL Report 97003, University of Illinois (1997a)
Cantu-Paz, E.: Designing Efficient Master-slave Parallel Genetic Algorithms. IlliGAL Report 97004, University of Illinois (1997b)
Coello Coello, C.A., Reyes Sierra, M.: A study of the parallelization of a coevolutionary multi-objective evolutionary algorithm. In: Monroy, R., Arroyo-Figueroa, G., Sucar, L.E., Sossa, H. (eds.) MICAI 2004. LNCS (LNAI), vol. 2972, pp. 688–697. Springer, Heidelberg (2004)
Coello Coello, C.A., Van Veldhuizen, D.A., Lamont, G.B.: Evolutionary Algorithms for Solving Multi-Objective Problems. Kluwer Academic Publishers, New York (2002)
Costa, J.P., Climaco, J.N.: A multiple reference point parallel approach in MCDM. In: International Conference on Multiple Criteria Decision Making, pp. 255–263. Springer, New York (1994)
de Toro Negro, F., Ortega, J., Fernandez, J., Diaz, A.: PSFGA: a parallel genetic algorithm for multiobjective optimization. In: Euromicro Workshop on Parallel, Distributed and Network-based Processing, pp. 384–391 (2002)
de Toro Negro, F., Ortega, J., Ros, E., Mota, S., Paechter, B., Martín, J.M.: PSFGA: Parallel Processing and Evolutionary Computation for Multiobjective Optimisation. Parallel Computing 30(5–6), 721–739 (2004)
Deb, K., Zope, P., Jain, S.: Distributed computing of Pareto-optimal solutions with evolutionary algorithms. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 534–549. Springer, Heidelberg (2003)
Dhaenens, C., Lemesre, J., Melab, N., Mezmaz, M., Talbi, E.-G.: Parallel exact methods for multi-objective combinatorial optimization. In: Parallel Combinatorial Optimization, John Wiley and Sons, Berlin (2006)
Dias, L.C., Costa, J.P., Climaco, J.N.: Conflicting criteria, cooperating processors—some experiments on implementing a multicriteria support method on a parallel computer. Computers and Operations Research 24(9), 805–817 (1997)
Dias, L.C., Costa, J.P., Climaco, J.N.: A parallel implementation of the PROMETHEE method. European Journal of Operational Research 104(3), 521–531 (1998)
Dubreuil, M., Gagne, C., Parizeau, M.: Analysis of a Master-slave Architecture for Distributed Evolutionary Computations. IEEE Transactions on Systems, Man, and Cybernetics 36(1), 229–235 (2006)
Elleighy, W.M., Tanaka, M.: Domain Decomposition Coupling of FEM and BEM. Transactions of the Japan Society for Computational Engineering and Science 4, 107–111 (2001)
Galperin, E.A.: Nonscalarized multiobjective global optimization. Journal of Optimization Theory and Applications 75(1), 69–85 (1992)
Grauer, M., Boden, H.: OpTiX-II: A software environment for MCDM based on distributed and parallel computing. In: Multicriteria Analysis: International Conference on Multiple Criteria Decision Making, pp. 199–208. Springer, Berlin (1997)
Hiroyasu, T., Miki, M., Watanabe, S.: The New Model of Parallel Genetic Algorithm in Multi-Objective Optimization Problems—Divided Range Multi-Objective Genetic Algorithm—. In: IEEE Congress on Evolutionary Computation, July 2000, vol. 1, pp. 333–340. IEEE Computer Society Press, Piscataway (2000)
Jones, B.R., Crossley, W.A., Lyrintzis, A.S.: Aerodynamic and Aeroacoustic Optimization of Airfoils via a Parallel Genetic Algorithm. In: AIAA 98-4811 (1998)
Jozefowiez, N., Semet, F., Talbi, E.-G.: Parallel and hybrid models for multi-objective optimization: Application to the vehicle routing problem. In: Guervós, J.J.M., Adamidis, P.A., Beyer, H.-G., Fernández-Villacañas, J.-L., Schwefel, H.-P. (eds.) PPSN 2002. LNCS, vol. 2439, pp. 271–280. Springer, Heidelberg (2002)
Jozefowiez, N., Semet, F., Talbi, E.-G.: Enhancements of nsga ii and its application to the vehicle routing problem with route balancing. In: Talbi, E.-G., Liardet, P., Collet, P., Lutton, E., Schoenauer, M. (eds.) EA 2005. LNCS, vol. 3871, pp. 131–142. Springer, Heidelberg (2006)
Jozefowiez, N., Semet, F., Talbi, E.-G.: Target aiming pareto search and its application to the vehicle routing problem with route balancing. Journal of Heuristics 13(5), 455–469 (2007)
Köksalan, M., Zionts, S.: International Conference on Multiple Criteria Decision Making. Springer, Berlin (2001)
Lemesre, J., Dhaenens, C., Talbi, E.-G.: An exact parallel method for a bi-objective permutation flowshop problem. European Journal of Operational Research 177(3), 1641–1655 (2007a)
Lemesre, J., Dhaenens, C., Talbi, E.-G.: Parallel partitioning method (PPM): A new exact method to solve bi-objective problems. Computers and Operations Research 34(8), 2450–2462 (2007b)
Liefooghe, A., Jourdan, L., Talbi, E.-G.: Paradiseo-MOEO: A framework for evolutionary multi-objective optimization. In: Evolutionary Multi-objective Optimization, Japan, pp. 457–471 (2007)
López-Jaimes, A., Coello Coello, C.A.: MRMOGA: Parallel Evolutionary Multiobjective Optimization using Multiple Resolutions. In: IEEE Congress on Evolutionary Computation, Edinburgh, Scotland, September 2005, vol. 3, pp. 2294–2301. IEEE Computer Society Press, Los Alamitos (2005)
Mehnen, J., Michelitsch, T., Schmitt, K., Kohlen, T.: pMOHypEA: Parallel evolutionary multiobjective optimization using hypergraphs. Technical Report of the SFB Project 531 Computational Intelligence CI–189/04, University of Dortmund (2004)
Melab, N., Cahon, S., Talbi, E.-G.: Grid computing for parallel bioinspired algorithms. Journal of Parallel and Distributed Computing (JPDC) 66(8), 1052–1061 (2006a)
Melab, N., Mezmaz, M., Talbi, E.-G.: Parallel cooperative metaheuristics on the computational grid: A case study - the biobjective flow-shop problem. Parallel computing 32(9), 643–659 (2006b)
Meunier, H., Talbi, E.-G., Reininger, P.: A multiobjective genetic algorithm for radio network design. In: IEEE Congress on Evolutionary Computation, Orlando, USA, pp. 317–324 (2000)
Mezmaz, M., Melab, N., Talbi, E.-G.: Using the multi-start and island models for parallel multi-objective optimization on the computational grid. In: IEEE International Conference on e-Science and Grid Computing (e-Science’06), pp. 112–120 (2006)
Mezmaz, M., Melab, N., Talbi, E.-G.: An efficient load balancing strategy for grid-based branch and bound. Parallel computing 33(4-5), 302–313 (2007)
Mostaghim, S., Branke, J., Schmeck, H.: Multi-objective particle swarm optimization on computer grids. In: The Genetic and Evolutionary Computation Conference, vol. 1, pp. 869–875 (2007)
Okabe, T.: Evolutionary Multi-objective Optimization -On the Distribution of Offspring in Parameter and Fitness Space-. Shaker Verlag, Aachen (2004)
Okabe, T., Foli, K., Olhofer, M., Jin, Y., Sendhoff, B.: Comparative Studies on Micro Heat Exchanger Optimization. In: IEEE Congress on Evolutionary Computation, pp. 647–654 (2003)
Parmee, I.C., Vekeria, H.D.: Co-operative Evolutionary Strategies for Single Component Design. In: Bäck, T. (ed.) International Conference on Genetic Algorithms, pp. 529–536. Morgan Kaufmann, San Francisco (1997)
Poloni, C.: Hybrid GA for Multi-Objective Aerodynamic Shape Optimization. In: Winter, G., Periaux, J., Galan, M., Cuesta, P. (eds.) Genetic Algorithms in Engineering and Computer Science, pp. 397–416. Wiley & Sons, Chichester (1995)
Sasaki, D., Obayashi, S., Sawada, K., Himeno, R.: Multiobjective Aerodynamic Optimization of Supersonic Wings Using Navier-Stokes Equations. In: European Congress on Computational Methods in Applied Sciences and Engineering (2000)
Schaffer, D.J.: Multiple objective optimization with vector evaluated genetic algorithms. In: International Conference on Genetic Algorithms and Their Applications, pp. 93–100 (1985)
Schmeck, H., Kohlmorgen, U., Branke, J.: Parallel Implementations of Evolutionary Algorithms. In: Solutions to Parallel and Distributed Computing Problems, pp. 47–68 (2001)
Stanley, T.J., Mudge, T.: A Parallel Genetic Algorithm for Multiobjective Microprocessor Design. In: The Sixth International Conference on Genetic Algorithms, pp. 597–604 (1995)
Streichert, F., Ulmer, H., Zell, A.: Parallelization of multi-objective evolutionary algorithms using clustering algorithms. In: Coello Coello, C.A., Hernández Aguirre, A., Zitzler, E. (eds.) EMO 2005. LNCS, vol. 3410, pp. 92–107. Springer, Heidelberg (2005)
Talbi, E.-G.: Parallel combinatorial optimization. Wiley, Chichester (2006)
Talbi, E.-G., Meunier, H.: Hierarchical parallel approach for gsm mobile network design. Journal of Parallel and Distributed Computing 66(2), 274–290 (2006)
Van Veldhuizen, D.A., Zydallis, J.B., Lamont, G.B.: Considerations in Engineering Parallel Multiobjective Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation 7(2), 144–173 (2003)
Volkovich, V.L.: Distributed multiobjective optimization problems and methods for their solution. In: International Conference on Multiple Criteria Decision Making, pp. 222–232. Springer, Berlin (1997)
Watanabe, S., Hiroyasu, T., Miki, M.: Parallel Evolutionary Multi-Criterion Optimization for Mobile Telecommunication Networks Optimization. In: Evolutionary Methods for Design, Optimization and Control, pp. 162–172 (2002)
Wiecek, M.M., Zhang, H.: A parallel algorithm for multiple objective linear programs. Computational Optimization and Applications 8(1), 41–56 (1997)
Xiao, N., Armstrong, M.P.: A specialized island model and its application in multiobjective optimization. In: Cantú-Paz, E., Foster, J.A., Deb, K., Davis, L., Roy, R., O’Reilly, U.-M., Beyer, H.-G., Kendall, G., Wilson, S.W., Harman, M., Wegener, J., Dasgupta, D., Potter, M.A., Schultz, A., Dowsland, K.A., Jonoska, N., Miller, J., Standish, R.K. (eds.) GECCO 2003. LNCS, vol. 2724, pp. 1530–1540. Springer, Heidelberg (2003)
Zhu, Z.-Y.: An Evolutionary Approach to Multi-Objective Optimization Problems. Ph.D. thesis, The Chinese University of Hong Kong (2002)
Zhu, Z.-Y., Leung, K.-S.: Asynchronous Self-Adjustable Island Genetic Algorithm for Multi-Objective Optimization Problems. In: IEEE Congress on Evolutionary Computation, Piscataway, New Jersey, May 2002, vol. 1, pp. 837–842 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Talbi, EG., Mostaghim, S., Okabe, T., Ishibuchi, H., Rudolph, G., Coello Coello, C.A. (2008). Parallel Approaches for Multiobjective Optimization . In: Branke, J., Deb, K., Miettinen, K., Słowiński, R. (eds) Multiobjective Optimization. Lecture Notes in Computer Science, vol 5252. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88908-3_13
Download citation
DOI: https://doi.org/10.1007/978-3-540-88908-3_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-88907-6
Online ISBN: 978-3-540-88908-3
eBook Packages: Computer ScienceComputer Science (R0)