Abstract
This chapter presents a review of modern parallel platforms and the way in which they can be exploited to implement parallel multi-objective evolutionary algorithms. Regarding parallel platforms, a special emphasis is given to global metacomputing which is an emerging form of parallel computing with promising applications in evolutionary (both multi- and singleobjective) optimization. In addition, we present the well-known models to parallelize evolutionary algorithms (i.e., master-slave, island, diffusion and hybrid models) describing some possible strategies to incorporate these models in the context of multi-objective optimization. Since an important concern in parallel computing is performance assessment, the chapter also presents how to apply parallel performance measures in multi-objective evolutionary algorithms taking into consideration their stochastic nature. Finally, we present a selection of current parallel multi-objective evolutionary algorithms that integrate novel strategies to address multi-objective issues.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
distributed.net project home Page (1997), http://www.distributed.net
SETI@home project home Page (1999), http://setiathome.berkeley.edu
Akl, S.G., Lindon, L.F.: Paradigms admitting superunitary behaviour in parallel computation. In: Buchberger, B., Volkert, J. (eds.) CONPAR 1994 and VAPP 1994. LNCS, vol. 854, pp. 301–312. Springer, Heidelberg (1994)
Alba Torres, E.: Parallel evolutionary algorithms can achieve super-linear performance. Information Processing Letters 82(1), 7–13 (2002)
Alba Torres, E., Troya Linero, J.M.: A survey of parallel distributed genetic algorithms. Complexity 4(4), 31–51 (1999)
Alba Torres, E., Troya Linero, J.M.: Analyzing synchronous and asynchronous parallel distributed genetic algorithms. Future Generation Computer Systems 17(4), 451–465 (2001)
Amdahl, G.M.: Validity of the single processor approach to achieving large scale computing capabilities. In: Proceedings of the AFIPS 1967, spring joint computer conference, April 18-20, 1967, pp. 483–485. ACM, New York (1967), http://doi.acm.org/10.1145/1465482.1465560
August, M.C., Brost, G.M., Hsiung, C.C., Schiffleger, A.J.: Cray X-MP: The birth of a supercomputer. Computer 22(1), 45–52 (1989), http://dx.doi.org/10.1109/2.19822
Belding, T.C.: The distributed genetic algorithm revisited. In: Eshelman, L. (ed.) Proceedings of the Sixth International Conference on Genetic Algorithms, pp. 114–121. Morgan Kaufmann, San Francisco (1995)
Bell, G.: Ultracomputers: A teraflop before its time. Communications of the ACM 35(8), 27–47 (1992)
Bell, G.: Bell’s law for the birth and death of computer classes. Communications of the ACM 51(1), 86–94 (2008), http://doi.acm.org/10.1145/1327452.1327453
Blank, T.: The MasPar MP-1 architecture. In: Compcon Spring 1990. Intellectual Leverage. Digest of Papers. Thirty-Fifth IEEE Computer Society International Conference, pp. 20–24 (1990)
Branke, J., Kaußler, T., Schmeck, H.: Guidance in Evolutionary Multi-Objective Optimization. Advances in Engineering Software 32, 499–507 (2001)
Brockhoff, D., Friedrich, T., Hebbinghaus, N., Klein, C., Neumann, F., Zitzler, E.: Do Additional Objectives Make a Problem Harder? In: Thierens, D. (ed.) 2007 Genetic and Evolutionary Computation Conference (GECCO 2007), vol. 1, pp. 765–772. ACM Press, London (2007)
Cantú Paz, E.: Efficient and Accurate Parallel Genetic Algorithms. Kluwer Academic Publishers, Boston (2002)
Coello Coello, C.A., Lamont, G.B., Van Veldhuizen, D.A.: Evolutionary Algorithms for Solving Multi-Objective Problems, 2nd edn. Springer, New York (2007)
Collette, Y., Siarry, P.: Multiobjective Optimization. Principles and Case Studies. Springer, Heidelberg (2003)
Crowl, L.A.: How to measure, present, and compare parallel performance. IEEE Parallel Distrib. Technol. 2(1), 9–25 (1994), http://dx.doi.org/10.1109/88.281869
de Toro Negro, F., Ortega, J., Ros, E., Mota, S., Paechter, B., Martin, J.M.: PSFGA: Parallel Processing and Evolutionary Computation for Multiobjective Optimisation. Parallel Computing 30(5-6), 721–739 (2004)
Deb, K.: Multi-objective Evolutionary Optimization: Past, Present and Future. In: Parmee, I.C. (ed.) Proceedings of the Fourth International Conference on Adaptive Computing in Design and Manufacture (ACDM 2000), PEDC, University of Plymouth, UK, pp. 225–236. Springer, London (2000)
Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. John Wiley & Sons, Chichester (2001)
Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable Multi-Objective Optimization Test Problems. In: Congress on Evolutionary Computation (CEC 2002), vol. 1, pp. 825–830. IEEE Service Center, Piscataway (2002)
Deb, K., Mohan, M., Mishra, S.: Towards a Quick Computation of Well-Spread Pareto-Optimal Solutions. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 222–236. Springer, Heidelberg (2003)
Dongarra, J., Sterling, T., Simon, H., Strohmaier, E.: High-performance computing: Clusters, constellations, MPPs, and future directions. Computing in Science and Engineering 7(2), 51–59 (2005), http://doi.ieeecomputersociety.org/10.1109/MCSE.2005.34
Duncan, R.: A survey of parallel computer architectures. Computer 23(2), 5–16 (1990), http://dx.doi.org/10.1109/2.44904
Edgeworth, F.Y.: Mathematical Physics. P. Keagan, London (1881)
Eklund, S.E.: A massively parallel architecture for distributed genetic algorithms. Parallel Computing 30(5-6), 647–676 (2004), http://dx.doi.org/10.1016/j.parco.2003.12.009
Flynn, M.J.: Some computer organizations and their effectiveness. IEEE Transactions on Computers 21(9), 948–960 (1972)
Foster, I., Kesselman, C. (eds.): The grid: blueprint for a new computing infrastructure. Morgan Kaufmann Publishers Inc., San Francisco (1999)
Foster, I., Kesselman, C., Tuecke, S.: The anatomy of the grid: Enabling scalable virtual organizations. Int. J. High Perform. Comput. Appl. 15(3), 200–222 (2001), http://dx.doi.org/10.1177/109434200101500302
Giloi, W.K.: Towards a taxonomy of computer architecture based on the machine data type view. SIGARCH Comput. Archit. News 11(3), 6–15 (1983)
Gustafson, J.L.: Fixed time, tiered memory, and superlinear speedup. In: Proceedings of the Fifth Distributed Memory Computing Conference, DMCC5 (1990)
Helmbold, D.P., McDowell, C.E.: Modeling speedup (n) greater than n. IEEE Trans. Parallel Distrib. Syst. 1(2), 250–256 (1990), http://dx.doi.org/10.1109/71.80148
Hillis, W.D.: The Connection Machine. MIT Press, Cambridge (1989)
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: 2000 Congress on Evolutionary Computation, vol. 1, pp. 333–340. IEEE Service Center, Piscataway (2000)
Johnson, E.E.: Completing an MIMD multiprocessor taxonomy. SIGARCH Computure Architecture News 16(3), 44–47 (1988), http://doi.acm.org/10.1145/48675.48682
Karp, A.H., Flatt, H.P.: Measuring parallel processor performance. Communications of the ACM 33(5), 539–543 (1990)
Knowles, J., Corne, D.: Properties of an Adaptive Archiving Algorithm for Storing Nondominated Vectors. IEEE Transactions on Evolutionary Computation 7(2), 100–116 (2003)
Kumar, V., Ananth Grama, G.K., Gupta, A.: Introduction to Parallel Computing: design and analysis of parallel algorithms. Benjamin Cummings Publishing Company, Redwood City (1994)
León, C., Miranda, G., Segura, C.: Parallel hyperheuristic: a self-adaptive island-based model for multi-objective optimization. In: GECCO 2008: Proceedings of the 10th annual conference on Genetic and evolutionary computation, pp. 757–758. ACM, New York (2008), http://doi.acm.org/10.1145/1389095.1389241
Licklider, J.C.R., Taylor, R.W.: The computer as a communication device. Science and Technology 76, 21–31 (1968)
Lin, S.C., Punch III, W.F., Goodman, E.D.: Coarse-grain genetic algorithms, categorization and new approaches. In: Sixth IEEE Symposium on Parallel and Distributed Processing, pp. 28–37. IEEE Computer Society Press, Dallas (1994)
Lizárraga Lizárraga, G., Hernández Aguirre, A., Botello Rionda, S.: G-metric: an m-ary quality indicator for the evaluation of non-dominated sets. In: GECCO 2008: Proceedings of the 10th annual conference on Genetic and evolutionary computation, pp. 665–672. ACM, New York (2008), http://doi.acm.org/10.1145/1389095.1389227
López Jaimes, A., Coello Coello, C.A.: MRMOGA: A New Parallel Multi-Objective Evolutionary Algorithm Based on the Use of Multiple Resolutions. Concurrency and Computation: Practice and Experience 19(4), 397–441 (2007)
López Jaimes, A., Coello Coello, C.A., Chakraborty, D.: Objective Reduction Using a Feature Selection Technique. In: 2008 Genetic and Evolutionary Computation Conference (GECCO 2008), pp. 674–680. ACM Press, Atlanta (2008)
Luna, F., Nebro, A., Dorronsoro, B., Alba, E., Bouvry, P., Hogie, L.: Optimal Broadcasting in Metropolitan MANETs Using Multiobjective Scatter Search. In: Rothlauf, F., Branke, J., Cagnoni, S., Costa, E., Cotta, C., Drechsler, R., Lutton, E., Machado, P., Moore, J.H., Romero, J., Smith, G.D., Squillero, G., Takagi, H. (eds.) EvoWorkshops 2006. LNCS, vol. 3907, pp. 255–266. Springer, Heidelberg (2006)
Meuer, H.W.: The TOP500 project: Looking back over 15 years of supercomputing experience. Informatik-Spektrum 31(3), 203–222 (2008), http://dx.doi.org/10.1007/s00287-008-0240-6
Nebro, A., Luna, F., Talbi, E.G., Alba, E.: Parallel Multiobjective Optimization. In: Alba, E. (ed.) Parallel Metaheuristics, pp. 371–394. Wiley-Interscience, New Jersey (2005)
Obayashi, S., Sasaki, D.: Multiobjective Aerodynamic Design and Visualization of Supersonic Wings by Using Adaptive Range Multiobjective Genetic Algorithms. In: Coello Coello, C.A., Lamont, G.B. (eds.) Applications of Multi-Objective Evolutionary Algorithms, pp. 295–315. World Scientific, Singapore (2004)
Okuda, T., Hiroyasu, T., Miki, M., Watanabe, S.: DCMOGA: Distributed cooperation model of multi-objective genetic algorithm. In: Proceedings of the PPSN/SAB Workshop on Multiobjective Problem Solving from Nature II (MPSN-II) (2002)
Osyczka, A.: Evolutionary Algorithms for Single and Multicriteria Design Optimization. Physica Verlag, Germany (2002)
Pareto, V.: Cours D’Economie Politique, vol. I and II. F. Rouge, Lausanne (1896)
Sarmenta, L.F.G.: Volunteer computing. PhD thesis, Massachusetts Institute of Technology (2001)
Sawai, H., Adachi, S.: Parallel distributed processing of a parameter-free GA by using hierarchical migration methods. In: Banzhaf, W., Daida, J., Eiben, A.E., Garzon, M.H., Honavar, V., Jakiela, M., Smith, R.E. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999), vol. 1, pp. 579–586. Morgan Kaufmann, San Francisco (1999)
Stadler, W.: Fundamentals of multicriteria optimization. In: Stadler, W. (ed.) Multicriteria Optimization in Engineering and the Sciences, pp. 1–25. Plenum Press, New York (1988)
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., Mostaghim, S., Okabe, T., Ishibuchi, H., Rudolph, G., Coello Coello, C.A.: Parallel Approaches for Multi-objective Optimization. In: Branke, J., Deb, K., Miettinen, K., Slowinski, R. (eds.) Multiobjective Optimization. Interactive and Evolutionary Approaches. LNCS, vol. 5252, pp. 349–372. Springer, Heidelberg (2008)
Tan, K., Khor, E., Lee, T.: Multiobjective Evolutionary Algorithms and Applications. Springer, London (2005)
Tanenbaum, A.S., van Steen, M.: Distributed Systems: Principles and Paradigms. Prentice Hall, Upper Saddle River (2002)
Teich, J., Zitzler, E., Bhattacharyya, S.S.: 3D Exploration of Software schedules for DSP Algorithms. In: 7th International Workshop on Hardware/Software Codesign (CODES 1999), pp. 168–172 (1999)
Tomassini, M.: Parallel and distributed evolutionary algorithms: A review. In: Miettinen, K., Mäkelä, M., Neittaanmäki, P., Periaux, J. (eds.) Evolutionary Algorithms in Engineering and Computer Science, pp. 113–133. John Wiley and Sons, Chichester (1999)
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)
Vrugt, J.A., Robinson, B.A.: Improved evolutionary optimization from genetically adaptive multimethod search. Proceedings of the National Academy of Sciences of the United States of America 104(3), 708–711 (2007)
Vyssotsky, V.A., Corbató, F.J., Graham, R.M.: Structure of the Multics Supervisor. In: Proceedings of the AFIPS, Fall Joint Computer Conference (FJCC), Spartan Books, Las Vegas, Nevada, vol. 27, Part 1, pp. 203–212 (1965)
Zhu, Z.Y., Leung, K.S.: An Enhanced Annealing Genetic Algorithm for Multi-Objective Optimization Problems. In: Langdon, W., Cantú-Paz, E., Mathias, K., Roy, R., Davis, D., Poli, R., Balakrishnan, K., Honavar, V., Rudolph, G., Wegener, J., Bull, L., Potter, M., Schultz, A., Miller, J., Burke, E., Jonoska, N. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), pp. 658–665. Morgan Kaufmann Publishers, San Francisco (2002)
Zitzler, E., Teich, J., Bhattacharyya, S.S.: Evolutionary Algorithm Based Exploration of Software Schedules for Digital Signal Processors. In: Banzhaf, W., Daida, J., Eiben, A.E., Garzon, M.H., Honavar, V., Jakiela, M., Smith, R.E. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999), vol. 2, pp. 1762–1769. Morgan Kaufmann, San Francisco (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Jaimes, A.L., Coello, C.A.C. (2009). Applications of Parallel Platforms and Models in Evolutionary Multi-Objective Optimization. In: Lewis, A., Mostaghim, S., Randall, M. (eds) Biologically-Inspired Optimisation Methods. Studies in Computational Intelligence, vol 210. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01262-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-01262-4_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01261-7
Online ISBN: 978-3-642-01262-4
eBook Packages: EngineeringEngineering (R0)