高维多目标优化算法分析研究

摘要/Abstract

摘要： 目前,大部分多目标进化算法MOEA(Multi-Objective Evolutionary Algorithms)是针对2到3个目标问题而设计,并且已经取得良好的优化效果,而对于目标个数大于或远大于3个的高维多目标问题,用MOEA逼近Pareto前沿和保持较低的计算复杂度都十分困难。通过讨论分析目标个数对高维优化算法带来的困扰,总结针对这些困扰引入的一些算法和策略。介绍了已有的高维多目标算法对占优机制进行的改善,并着重对现存的高维多目标减少算法做了系统的分类综述,对比分析验证了各类算法的优化效果,并给出进一步可研究的方向。

关键词: 高维目标,多目标优化,目标减少算法,冗余目标中图法分类号TP18文献标识码A

Abstract: At present,most multi-objective evolutionary algorithms MOEA (Multi-Objective Evolutionary Algorithms) are designed for the problems of 2～3goals with good optimization results．But for 4or more goals, approximating Pareto front by MOEA and maintaining a low computational complexity are very difficult．This article analyzed the problems caused by the number of objectives in Many-objective optimization algorithm．To solve the problems,some of strategies and algorithms were introduced．This paper introduced the improvement of dominant mechanism in existing many-objective optimization algorithm and focused on a systematic review of many-objective reduction algorithm,comparative analysis of the effectiveness of various algorithms,and gave the directions for further research．

Key words: Many-objective,Multi-objective optimization,Multi-objective reduction algorithm,Redundancy objective

周草臣,陈自郁,何中市. 高维多目标优化算法分析研究[J]. 计算机科学, 2014, 41(Z6): 57-60. https://doi.org/

ZHOU Cao-chen,CHEN Zi-yu and HE Zhong-shi. Survey of Many-objective Optimization Algorithms[J]. Computer Science, 2014, 41(Z6): 57-60. https://doi.org/

参考文献

[1] Goldberg D E.Genetic algorithms for search,optimization,and machine learning[M]．Reading,MA:Addison-Wesley,1989:100-150
[2] 郑金华.多目标进化算法及其应用[M].北京:科学出版社,2007:2-276
[3] Paechter B,Rankin R C,Cumming A．Timetabling the classes of an entire university with an evolutionary algorithm[M]∥PPSN V Proceedings．Springer,1998:865-874
[4] Coello C A C,Vanveldhuizen D A,Lamont G.Evolutionary Algorithms For Solving MultiObjective Problems[M]．Boston,MA:Kluwer Academic Publishers,2002:123-179
[5] Coello C C A,Hern′andez Aguirre A．Design of Combinational Logic Circuits through an Evolutionary Multiobjective Optimization Approach[J]．Artificial Intelligence for Engineering,Design,Analysis and Manufacture,2002,6(1):39-53
[6] Purshouse R C,Fleming P J．Evolutionary many-objective optimization:An exploratory analysis[C]∥Proc of 2003IEEE Congress on Evolutionary Computation．Canberra:IEEE Service Center,2003:2066-2073
[7] Brockhoff D,Zitzler E．Are All objectives Necessary on Dimen-sionality Reduction in Evolutionary Multi-objective Optimization[M]．Parallel Problem Solving from Nature．Springer,2006:533-542
[8] Jones D,Schonlau M,Welch W．Efficient global optimization of expensive black-box function[J]．Journal of Global Optimization,1998,3(4):455-492
[9] Ishibuchi H,Tsukamoto N,Nojima Y．Evolutionary many-objective optimization:A short review[C]∥Proc of IEEE Congress on Evolutionary Computation．Hong Kong:IEEE Service Center,2008:2424-2431
[10] Sinha D A,Korhonen P,Wallenius J．An interactive evolutionary multi-objective optimization method based on progressively approximated value functions[J]．Evolutionary Computation,IEEE Transactions,2010,4:723-739
[11] Knowles J D,Corne D W,Fleischer M．Bounded archiving using the Lebesgue measure[C]∥Proc of 2003Congress on Evolutionary Computation．Canberra:IEEE Service Center,2003:2490-2497
[12] Zitzler E,Künzli S．Indicator-based selection in multi-objectivesearch [C]∥Lecture Notes in Computer Science 3242:Parallel Problem Solving from Nature-PPSN VIII．Berlin:Springer-Verlag,2004:832-842
[13] Deb K,Sundar J．Reference point based multi-objective optimization using evolutionary algorithms[C]∥Proc of 2006Genetic and Evolutionary Computation Conf．New York:ACM,2006:635-642
[14] 孔维健,丁进良,柴天佑.高维多目标进化算法研究综述[J].控制与决策,2010,5(3):321-326
[15] 郭思涵,龚小胜．正交设计的E占优策略求解高维多目标优化问题研究[J].计算机科学,2012,9(2):276-310
[16] Fleming P J,Purshouse R C,Lygoe R J．Many-objective optimization:An engineering design perspective[C]∥Evolutionary Multi-Criterion Optimization．Berlin:Springer-Verlag,2005:14-32
[17] Obayashi S,Sasaki D．Visualization and data mining of Pareto solutions using self-organizing map[C]∥Lecture Notes in Computer Science 2632:Evolutionary Multi-Criterion Optimization -EMO 2003．Berlin:Springer-Verlag,2003:796-809
[18] NaudA,Duch W．Interactive data exploration using MDS mapping[C]∥The 5th Conf Neural Networks and Soft Computing．New York:Physica-Verlag,2000:255-260
[19] Li X J．Visualization of high-dimensional data with relationalperspective map [J]．Information Visualization,2004,3(1):49-59
[20] Tanaka M,Tanino T．Global optimization by the genetic algo-rithm in a multi-objective decision support system[C]∥Proc of the 10th Int Conf on Multiple Criteria Decision Making．Berlin:Springer-Verlag,1992:261-270
[21] Horn J．Multicriterion decision making[C]∥Handbook of Evolutionary Computation．IOP Publishing Ltd．and Oxford University Press,1997:1-15
[22] Wierzbicki A P．The use of reference objectives in multi-objective optimization[C]∥Multiple Criteria Decision Making Theory and Applications．Berlin:Springer-Verlag,1980:468-486
[23] Deb K,Sundar J．Reference point based multi-objective optimization using evolutionary algorithms[C]∥Proc of 2006Genetic and Evolutionary Computation Conf．New York:ACM,2006:635-642
[24] Drechsler D,Drechsler R,Becher B．Multi-objective optimization based on relation favour [C]∥Proc 1st Evolutionary Multi-Criterion Optimization．Berlin:Springer-Verlag,2001:154-166
[25] Ikeda K,Kita H,Kobayashi S．Failure of Pareto-based MOEAs:Does non-dominated really mean near to optimal[C]∥Proc of 2001IEEE Congress on Evolutionary Computation．Seoul:IEEE Service Center,2001:957-962
[26] Di Pierro F,Djordjevic S,Khu S-T,et al．Automatic calibration of urban drainage model using a novel multi-objective GA[J]．Water Science and Technology,2004,52(5):41-52
[27] Laumanns M,Thiele L,Deb K,et al．Combining convergenceand diversity in evolutionary multi-objective optimization[J]．Evolutionary Computation,2002,10(3):263-282
[28] Brockhoff D,Zitzler E．Are all objectives necessary on dimensionality reduction in evolutionary multiobjective optimization [C]∥Parallel Problem Solving from Nature．Berlin:Springer-Verlag,2006:533-542
[29] Zitzler Z,Künzli S．Indicator-based selection in multi-objectivesearch [C]∥Lecture Notes in Computer Science 3242:Parallel Problem Solving from Nature -PPSN VIII．Berlin:Springer-Verlag,2004:832-842
[30] Hughes E J．Multiple single objective pareto sampling[C]∥Congress on Evolutionary Computation (CEC 03)．Piscataway NJ:IEEE Press,2003:2678-2684
[31] Saxena D K,Deb K．Dimensionality Reduction of Objectives and constraints in MultiObjective Optimization Problems [C]∥A System Design Perspective．In Congress on Evolutionary Computation (CEC 2008)．IEEE Press,2008:3203-3210
[32] Deb K,Saxena D K．Searching for Pareto optimal Solutionsthrough Dimensionality Reduction for Certain Large Dimensional MultiObjective Optimization Problem [C]∥Congress on Evolutionary Computation (CEC 2006)．IEEE Press,2006:3352-3360
[33] Saxena D K,Deb K．Non-Linear dimensionality reduction procedure for certain large-dimensional multi-objective optimization problems:Employing correntropy and a novel maximum variance unfolding[C]∥Proc．of the 4th Int’l Conf．on Evolutionary Multi-Criterion Optimization,EMO 2007．Berlin:Springer-Verlag,2007:272-787
[34] Deb K,Saxena D K．On Finding Pareto-Optimal SolutionsThrough Dimensionality Reduction for Certain Large-Dimensional Multi-Objective Optimization Problems [R]．KanGAL,2005
[35] Deb K,Pratap A,Agrawal S,et al.A Fast and Elitist Multi-objective Genetic Algorithm:NSGA-II[J]．IEEE Transactions on Evolutionary Computation,2002,6(2):182-197
[36] Brockhoff D,Zitzler E．Dimensionality Reduction in Multi-Ob-jective Optimization,the Minimum Objective Subject problem [C]∥Operations Research Proceedings．[S.l.]:Springer,2007:423-429
[37] Jaimes A L,Coello C A C,Chakraborty D．Objective Reduction Using a feature Selection Technique [C]∥GECCO 08．2008:673-680
[38] 陈静,周聪,李珂,等．高维目标减少算法[J].计算机工程与应用,2010,6(11):38-41
[39] Deb K,Thiele L,Laumanns M,et al．Scalable multi-objective optimization test problems[C]∥Proc．of the IEEE Congress on Evolutionary Computation．CEC 2002．2002:825-830
[40] Knowles J,Come D.The Pareto Archived Evolution Strategy:A New Baseline Algorithm for Pareto Multiobjective Optimisation[C]∥Congress on Evolutionary Computation．1999:98-105
[41] 刘磊,杨仕友．高维多目标优化设计的改进多重单目标Pareto采样算法研究[J]．电工电能新技术,2013,2(1):89-93
[42] Knowles J．ParEGO:a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems[J]．IEEE Transactions on Evolutionary Computation,2006,0(1):50-66
[43] Zhang Q,Liu W,Tsang E,et al.Expensive multiobjective optimization By MOEA/D with Gaussian process model[J]．IEEE Transactions on Evolutionary Computation,2010,4(3):456-474
[44] Srinivas N,Deb K．Multiobjective Optimization Using Non-dominated Sorting in Genetic Algorithms[J].Evolutionary Computation,1994,2(3):221-248
[45] Zitzler E,Thiele L．Multiobjective Evolutionary Algorithms:AComparative Case Study and the Strength Pareto Approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271
[46] Emmerich M T M,Giannakoglou K,Naujoks B．Single-and multiobjective evolutionary optimization assisted by Gaussian random field meta models[J]．IEEE Transactions on Evolutionary Computation,2006,10(4):421-439

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed