doi:

DOI: 10.3724/SP.J.1001.2009.00271

Journal of Software (软件学报) 2009/20:2 PP.271-289

Research on Evolutionary Multi-Objective Optimization Algorithms


Abstract:
Evolutionary multi-objective optimization (EMO), whose main task is to deal with multi-objective optimization problems by evolutionary computation, has become a hot topic in evolutionary computation community. After summarizing the EMO algorithms before 2003 briefly, the recent advances in EMO are discussed in details. The current research directions are concluded. On the one hand, more new evolutionary paradigms have been introduced into EMO community, such as particle swarm optimization, artificial immune systems, and estimation distribution algorithms. On the other hand, in order to deal with many-objective optimization problems, many new dominance schemes different from traditional Pareto-dominance come forth. Furthermore, the essential characteristics of multi-objective optimization problems are deeply investigated. This paper also gives experimental comparison of several representative algorithms. Finally, several viewpoints for the future research of EMO are proposed.

Key words:multi-objective optimization,evolutionary algorithm,Pareto-dominance,particle swarm optimization,artificial immune system,estimation of distribution algorithm

ReleaseDate:2014-07-21 14:29:49

Funds:Supported by the National Natural Science Foundation of China under Grant No.60703107 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z107 (国家高技术研究发展计划(863)); the National Basic Research Program of China under Grant No.2006CB705700 (国家重点基础研究发展计划(973)); the Program for Cheung Kong Scholars and Innovative Research Team in University of China under Grant No.IRT0645 (长江学者和创新团队支持计划)



[1] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. on Evolutionary Computation, 2002,6(2):182-197.

[2] Zitzler E, Thiele L. Multi-Objective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Trans. on Evolutionary Computation, 1999,3(4):257-271.

[3] Deb K. Multi-Objective Optimization Using Evolutionary Algorithms. Chichester: John Wiley Sons, 2001.

[4] Coello Coello CA, van Veldhuizen DA, Lamont GB. Evolutionary Algorithms for Solving Multi-Objective Problems. New York: Kluwer Academic Publishers, 2002.

[5] Coello Coello CA, van Veldhuizen DA, Lamont GB. Evolutionary Algorithms for Solving Multi-Objective Problems. 2nd ed., New York: Springer-Verlag, 2007.

[6] Knowles J, Corne D, Deb K. Multiobjective Problem Solving from Nature. New York: Springer-Verlag, 2008.

[7] Tan KC, Khor EF, Lee TH. Multiobjective Evolutionary Algorithms and Applications. London: Springer-Verlag, 2005.

[8] Jin YC. Multi-Objective Machine Learning. Berlin: Springer-Verlag, 2006.

[9] Schaffer JD. Multiple objective optimization with vector evaluated genetic algorithms. In: Grefenstette JJ, ed. Proc. of the Int'l Conf. on Genetic Algorithms and Their Applications. Hillsdale: L. Erlbaum Associates, Inc., 1985. 93-100.

[10] Fonseca CM, Fleming PJ. Genetic algorithm for multiobjective optimization: Formulation, discussion and generation. In: Forrest S, ed. Proc. of the 5th Int'l Conf. on Genetic Algorithms. San Mateo: Morgan Kauffman Publishers, 1993. 416-423.

[11] Srinivas N, Deb K. Multiobjective optimization using non-dominated sorting in genetic algorithms. Evolutionary Computation, 1994,2(3):221-248.

[12] Horn J, Nafpliotis N, Goldberg DE. A niched Pareto genetic algorithm for multiobjective optimization. In: Fogarty TC, ed. Proc. of the 1st IEEE Congress on Evolutionary Computation. Piscataway: IEEE, 1994. 82-87.

[13] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm. In: Giannakoglou K, Tsahalis DT, Périaux J, Papailiou KD, Fogarty T, eds. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Berlin: Springer-Verlag, 2002. 95-100.

[14] Knowles JD, Corne DW. Approximating the non-dominated front using the Pareto archived evolution strategy. Evolutionary Computation, 2000,8(2):149-172.

[15] Corne DW, Knowles JD, Oates MJ. The Pareto-envelope based selection algorithm for multi-objective optimization. In: Schoenauer M, Deb K, Rudolph G, Yao X, Lutton E, Merelo JJ, Schwefel HP, eds. Parallel Problem Solving from Nature, PPSN VI. LNCS, Berlin: Springer-Verlag, 2000. 869-878.

[16] Corne DW, Jerram NR, Knowles JD, Oates MJ. PESA-II: Region-Based selection in evolutionary multi-objective optimization. In: Spector L, Goodman ED, Wu A, Langdon WB, Voigt HM, Gen M, eds. Proc. of the Genetic and Evolutionary Computation Conf., GECCO 2001. San Francisco: Morgan Kaufmann Publishers, 2001. 283-290.

[17] Erickson M, Mayer A, Horn J. The niched Pareto genetic algorithm 2 applied to the design of groundwater remediation system. In: Zitzler E, Deb K, Thiele L, Coello Coello CA, Corne D, eds. Proc. of the 1st Int'l Conf. on Evolutionary Multi-Criterion Optimization, EMO 2001. Berlin: Springer-Verlag, 2001. 681-695.

[18] Coello Coello CA, Pulido GT. A micro-genetic algorithm for multiobjective optimization. In: Spector L, Goodman ED, Wu A, Langdon WB, Voigt HM, Gen M, eds. Proc. of the Genetic and Evolutionary Computation Conf., GECCO 2001. San Francisco: Morgan Kaufmann Publishers, 2001. 274-282.

[19] Laumanns M, Thiele L, Deb K, Zitzler E. Combining convergence and diversity in evolutionary multi-objective optimization. Evolutionary Computation, 2002,10(3):263-282.

[20] Brockoff D, Zitzler E. Are all objective necessary on dimensionality reduction in evolutionary multi-objective optimization. In: Runarsson TP, Beyer HG, Burke E, Merelo-Guervós JJ, Whitley LD, Yao X, eds. Parallel Problem Solving from Nature, PPSN IX. LNCS, Berlin: Springer-Verlag, 2006. 533-542.

[21] Hernández-Díaz AG, Santana-Quintero LV, Coello Coello CA, Molina J. Pareto-Adaptive -dominance. Evolutionary Computation, 2007,15(4): 493-517.

[22] Deb K, Saxena DK. On finding Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. Technical Report, 2005011, Kalyanmoy Deb and Dhish Kumar Saxena, Indian Institute of Technology Kanpur, 2005.

[23] Saxena DK, Deb K. Non-Linear dimensionality reduction procedure for certain large-dimensional multi-objective optimization problems: Employing correntropy and a novel maximum variance unfolding. In: Coello Coello CA, Aguirre AH, Zitzler E, eds. Proc. of the 4th Int'l Conf. on Evolutionary Multi-Criterion Optimization, EMO 2007. Berlin: Springer-Verlag, 2007. 772-787.

[24] Coello Coello CA, Pulido GT, Lechuga MS. Handing multiple objectives with particle swarm optimization. IEEE Trans. on Evolutionary Computations, 2004,8(3):256-279.

[25] Gong MG, Jiao LC, Du HF, Bo LF. Multiobjective immune algorithm with nondominated neighbor-based selection. Evolutionary Computation, 2008,16(2):225-255.

[26] Zhou AM, Zhang QF, Jin Y, Sendhoff B, Tsang E. Global multi-objective optimization via estimation of distribution algorithm with biased initialization and crossover. In: Thierens D, Beyer HG, Bongard J, Branke J, Clark JA, Cliff D, Congdon CB, Deb K, eds. Proc. of the Genetic and Evolutionary Computation Conf., GECCO 2007. New York: ACM Press, 2007. 617-622.

[27] Zhang QF, Zhou AM, Jin Y. RM-MEDA: A regularity model based multiobjective estimation of distribution algorithm. IEEE Trans. on Evolutionary Computation, 2007,12(1):41-63.

[28] Zhang QF, Li H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation, 2007,11(6):712-731.

[29] Coello Coello CA. An updated survey of evolutionary multiobjective optimization techniques: State of the art and future trends. In: Banzhaf W, Daida J, Eiben AE, Garzon MH, Honavar V, Jakiela M, Smith RE, eds. Proc. of the IEEE Congress on Evolutionary Computation, CEC 1999. Piscataway: IEEE Service Center, 1999. 3-13.

[30] Coello Coello CA. Evolutionary multiobjective optimization: current and future challenges. In: Benitez JM, Cordon O, Hoffmann F, Roy R, eds. Advances in Soft Computing- Engineering, Design and Manufacturing. Berlin: Springer-Verlag, 2003. 243-256.

[31] Coello Coello CA. Recent trends in evolutionary multi-objective optimization. In: Abraham A, Jain LC, Goldberg R, eds. Evolutionary Multi-Objective Optimization: Theoretical Advances and Applications. Berlin: Springer-Verlag, 2005. 7-32.

[32] Coello Coello CA. 20 years of evolutionary multi-objective optimization: What has been done and what remains to be done. In: Yen GY, Fogel DB, eds. Computational Intelligence: Principles and Practice. New York: IEEE Computational Intelligence Society, 2006. 73-88.

[33] Coello Coello CA. Evolutionary multi-objective optimization: A historical view of the field. IEEE Computational Intelligence Magazine, 2006,1(1):28-36.

[34] Xie T, Chen HW, Kang LS. Evolutionary algorithms of multi-objective optimization problems. Chinese Journal of Computers, 2003,26(8):997-1003 (in Chinese with English abstract).谢涛,陈火旺,康立山.多目标优化的演化算法.计算机学报,2003,26(8):997-1003.

[35] Zheng XW, Liu H. Progress of research on multi-objective evolutionary algorithms. Computer Science, 2007,34(7):187-192 (in Chinese with English abstract).郑向伟,刘弘.多目标进化算法研究进展.计算机科学,2007,34(7):187-192.

[36] Zheng JH. Multi-Objective Evolutionary Algorithms and Their Applications. Beijing: Science Press, 2007 (in Chinese).郑金华.多目标进化算法及其应用.北京:科学出版社,2007.

[37] Rosenberg RS. Simulation of genetic populations with biochemical properties [Ph.D. Thesis]. Michigan: University of Michigan, 1967.

[38] Holland JH. Adaptation in Natural and Artificial Systems. Michigan: The University of Michigan Press, 1975.

[39] Goldberg DE. Genetic algorithm for search, optimization, and machine learning. Boston: Addison-Wesley Longman Publishing Co., Inc., 1989.

[40] Goldberg DE, Richardson J. Genetic algorithms with sharing for multimodal function optimization. In: Grefenstette JJ, ed. Proc. of the 2nd Int'l Conf. on Genetic Algorithm. Hillsdale: L. Erlbaum Associates, Inc., 1987. 41-49.

[41] Veldhuizen DV, Lamont G. Multiobjective optimization with messy genetic algorithms. In: Carroll J, Damiani E, Haddad H, Oppenheim D, eds. Proc. of the 2000 ACM Symp. on Applied to Computing. New York: ACM Press, 2000. 470-476.

[42] Li X. A non-dominated sorting particle swarm optimizer for multiobjective optimization. In: Cantú-Paz E, Foster JA, Deb K, Lawrence D, Roy R, eds. Proc. of the Genetic and Evolutionary Computation Conf., GECCO 2003. Berlin: Springer-Verlag, 2003. 37-48.

[43] Fieldsend JE, Sing S. A multi-objective algorithm based upon particle swarm optimization, an efficient data structure and turbulence. In: Bullinaria JA, ed. Proc. of the 2002 UK Workshop on Computational Intelligence. Birmingham: University of Birmingham, 2002. 37-44.

[44] Reyes Sierra M, Coello Coello CA. Improving PSO-based multi-objective optimization using crowding, mutation and e-dominance. In: Coello Coello CA, Aguirre AH, Zitzler E, eds. Proc. of the 3rd Int'l Conf. Evolutionary Multi-Criterion Optimization, EMO 2005. Berlin: Springer-Verlag, 2005. 505-519.

[45] Abido MA. Two level of nondominated solutions approach to multiobjective particle swarm optimization. In: Thierens D, Beyer HG, Bongard J, Branke J, Clark JA, Cliff D, Congdon CB, Deb K, eds. Proc. of the Genetic and Evolutionary Computation Conf., GECCO 2007. New York: ACM Press, 2007. 726-733.

[46] Korudu P, Das S, Welch SM. Multi-Objective hybrid PSO using -fuzzy dominance. In: Lipson H, ed. Proc. of the Genetic and Evolutionary Computation Conf., GECCO 2007. New York: ACM Press, 2007. 853-860.

[47] Jiao LC, Du HF, Liu F, Gong MG. Immunological Computation for Optimization, Learning and Recognition. Beijing: Science Press, 2006 (in Chinese).焦李成,杜海峰,刘芳,公茂果.免疫优化计算、学习与识别.北京:科学出版社,2006.

[48] Coello Coello CA, Cortes NC. Solving multiobjective optimization problems using an artificial immune system. Genetic Programming and Evolvable Machines, 2005,6(2):163-190.

[49] Cutello V, Narzisi G, Nicosia G. A class of Pareto archived evolution strategy algorithms using immune inspired operators for ab-initio protein structure prediction. In: Rothlauf F, Branke J, Cagnoni S, Corne DW, Drechsler R, Jin YC, eds. Proc. of the3rd European Workshop on Evolutionary Computation and Bioinformatics, EvoWorkshops 2005. Berlin: Springer-Verlag, 2005. 54-63.

[50] Freschi F, Repetto M. VIS: An artificial immune network for multi-objective optimization. Engineering Optimization, 2006,38(8): 975-996.

[51] Jiao LC, Gong MG, Shang RH, Du HF, Lu B. Clonal selection with Immune dominance and energy based multi-objective optimization. In: Coello Coello CA, Aguirre AH, Zitzler E, eds. Proc. of the 3rd Int'l Conf. on Evolutionary Multi-Criterion Optimization, EMO 2005. Berlin: Springer-Verlag, 2005. 474-489.

[52] Khan N, Goldberg DE, Pelikan M. Multi-Oobjective Bayesian optimization algorithm. Technical Report, No.2002009, University of Illinois at Urbana-Champaign, 2002.

[53] Laumanns M, Ocenasek J. Bayesian optimization algorithms for multi-objective Optimization. In: Merelo JJ, Adamidis P, Beyer HG, eds. Proc. of the 7th Int'l Conf. on Parallel Problem Solving from Nature. London: Springer-Verlag, 2002. 298-307.

[54] Li H, Zhang QF. Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II. IEEE Trans. on Evolutionary Computation, 2008. doi: 10.1109/TEVC.2008.925798

[55] Lotov AV, Bushenkov VA, Lamenev GK. Interactive decision maps: Approximation and visualization of Pareto frontier. New York: Kluwer Academic Publishers, 2004.

[56] Tenenbaum JB, Silva V, Langford JC. A global geometric framework for nonlinear dimensionality reduction. Science, 2000, 290(22):2319-2323.

[57] Fry B. Visualizing Data: Exploring and Explaining Data with the Processing Environment. Sebastopol: O'Reilly Press, 2007.

[58] Khare V, Yao X, Deb K. Performance scaling of multi-objective evolutionary algorithms. In: Fonseca CM, Fleming PJ, Zitzler E, Deb K, Thiele L, eds. Proc. of the 2nd Int'l Conf. on Evolutionary Multi-Criterion Optimization, EMO 2003. Berlin: Springer-Verlag, 2003. 376-390.

[59] Hughes EJ. Multiple single objective Pareto sampling. In: Sarker R, Reynolds R, Abbass H, Tan KC, McKay B, Essam D, Gedeon T, eds. Proc. of the IEEE Congress on Evolutionary Computation, CEC 2003. Piscataway: IEEE Service Center, 2003. 2678-2684.

[60] Wagner T, Beume N, Naujoks B. Pareto-, aggregation-, and indicator-based methods in many-objective optimization. In: Obayashi S, Deb K, Poloni C, Hiroyasu T, Murata T, eds. Proc. of the 4th Int'l Conf. on Evolutionary Multi-Criterion Optimization, EMO 2007. Berlin: Springer-Verlag, 2007. 742-756.

[61] Huband S, Hingston P, Barone L, While L. A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans. on Evolutionary Computation, 2006,10(5):477-506.

[62] Zitzler E, Deb K, Thiele L. Comparison of multi-objective evolutionary algorithms: Empirical results. Evolutionary Computation, 2000,8(2):173-195.

[63] Deb K, Thiele L, Laumanns M, Zitzler E. Scalable multi-objective optimization test problems. In: Fogel DB, ed. Proc. of the IEEE Congress on Evolutionary Computation, CEC 2002. Piscataway: IEEE Service Center, 2002.825-830.

[64] Li H, Zhang QF. A multi-objective differential evolution based on decomposition for multiobjective optimization with variable linkages. In: Runarsson TP, Beyer HG, Burke E, Merelo-Guervós JJ, Whitley LD, Yao X, eds. Parallel Problem Solving from Nature, PPSN IX. LNCS, Berlin: Springer-Verlag, 2006. 583-592.

[65] Zitzler E, Thiele L, Laumanns M, Fonseca CM, da Fonseca VG. Performance assessment of multiobjective optimizers: An analysis and review. IEEE Trans. on Evolutionary Computation, 2003,7(2):117-132.

[66] Deb K. Multi-Objective genetic algorithms: Problem difficulties and construction of test problems. Evolutionary Computation, 1999,7(3):205-230.

[67] Kursawe F. A variant of evolution strategies for vector optimization. In: Schwefel HP, Männer R. Parallel Problem Solving from Nature-PPSN I. Berlin: Springer-Verlag, 1991. 193-197.

[68] Deb K, Jain S. Running performance metrics for evolutionary multi-objective optimization. Technical Report, No.2002004, Kanpur: Indian Institute of Technology Kanpur, 2002.

[69] Schott, JR. Fault tolerant design using single and multicriteria genetic algorithm optimization [MS. Thesis]. Cambridge: Massachusetts Institute of Technology, 1995.

[70] Deb K, Beyer HG. Self-Adaptive genetic algorithms with simulated binary crossover. Evolutionary Computation, 2001,9(2): 197-221.

[71] Igel C, Hansen N, Roth S. Covariance matrix adaptation for multi-objective optimization. Evolutionary Computation, 2007,15(1): 1-28.

[72] McGill R, Tukey JW, Larsen WA. Variations of boxplots. The American Statistician, 1978,32(1):12-16.

[73] Tan KC, Lee TH, Khor EF. Evolutionary algorithms with dynamic population size and local exploration for multiobjective optimization. IEEE Trans. on Evolutionary Computation, 2001,5(6):565-588.

[74] Lu HM, Yen G. Dynamic population size in multiobjective evolutionary algorithms. In: Fogel DB, ed. Proc. of IEEE Congress on Evolutionary Computation, CEC 2002. Piscataway: IEEE Service Center, 2002. 1648-1653.

[75] Giel O, Lehre PK. On the effect of populations in evolutionary multi-objective optimization. In: Keijzer M, Cattolico M, Arnold D, Babovic V, Blum C, Bosman P, eds. Proc. of the Genetic and Evolutionary Computation Conf., GECCO 2006. New York: ACM Press, 2006. 651-658.

[76] Suman B. Study of self-stopping PDMOSA and performance measure in multiobjective optimization. Computers Chemical Engineering, 2005,29(5):1131-1147.

[77] Martí L, García J, Berlanga A, Molina JM. A cumulative evidential stopping criterion for multiobjective optimization evolutionary algorithms. In: Thierens D, Beyer HG, Bongard J, Branke J, Clark JA, Cliff D, eds. Proc. of the Genetic and Evolutionary Computation Conf., GECCO 2007. New York: ACM Press, 2007. 2835-2842.

PDF