微信服务号

微信订阅号

2025年4月7日 4:11 星期一
首页 > 过刊浏览>2009年第20卷第2期 >271-289
PDF HTML阅读 XML下载 导出引用 引用提醒
进化多目标优化算法研究
作者:
基金项目:

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 (长江学者和创新团队支持计划)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [81]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    进化多目标优化主要研究如何利用进化计算方法求解多目标优化问题,已经成为进化计算领域的研究热点之一.在简要总结2003年以前的主要算法后,着重对进化多目标优化的最新进展进行了详细讨论.归纳出当前多目标优化的研究趋势,一方面,粒子群优化、人工免疫系统、分布估计算法等越来越多的进化范例被引入多目标优化领域,一些新颖的受自然系统启发的多目标优化算法相继提出;另一方面,为了更有效的求解高维多目标优化问题,一些区别于传统Pareto占优的新型占优机制相继涌现;同时,对多目标优化问题本身性质的研究也在逐步深入.对公认的代表性算法进行了实验对比.最后,对进化多目标优化的进一步发展提出了自己的看法.

    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.

    参考文献
    [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).
    [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).
    [36] Zheng JH. Multi-Objective Evolutionary Algorithms and Their Applications. Beijing: Science Press, 2007 (in Chinese).
    [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 andturbulence. 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).
    [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. 附中文参考文献:
    [34] 谢涛,陈火旺,康立山.多目标优化的演化算法.计算机学报,2003,26(8):997-1003.
    [35] 郑向伟,刘弘.多目标进化算法研究进展.计算机科学,2007,34(7):187-192.
    [36] 郑金华.多目标进化算法及其应用.北京:科学出版社,2007.
    [47] 焦李成,杜海峰,刘芳,公茂果.免疫优化计算、学习与识别.北京:科学出版社,2006.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

公茂果,焦李成,杨咚咚,马文萍.进化多目标优化算法研究.软件学报,2009,20(2):271-289

复制
分享
文章指标
  • 点击次数:27553
  • 下载次数: 46984
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2008-07-22
  • 最后修改日期:2008-10-09
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19796114位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号