基于邻域竞赛的多目标优化算法
|
摘要
传统多目标优化算法(Multi-objective evolution algorithms,MOEAs)的基本框架大致分为两部分:首先是收敛性保持,采用Pareto支配方法将种群分成若干非支配层;其次是分布性保持,在临界层中,采用分布性保持机制维持种群的分布性.然而在处理高维优化问题(Many-objective optimization problems,MOPs)(目标维数大于3)时,随着目标维数的增加,种群的收敛性和分布性的冲突加剧,Pareto支配关系比较个体优劣的能力也迅速下降,此时传统的MOEA已不再适用于高维优化问题.鉴于此,本文提出了一种基于邻域竞赛的多目标优化算法(Evolutionary algorithm based on neighborhood competition for multi-objective optimization,NCEA).NCEA首先将个体的各个目标之和作为个体的收敛性估计;然后,计算当前个体向量与收敛性最好的个体向量之间的夹角,并将其作为当前个体的邻域估计;最后,通过邻域竞赛方法将问题划分为若干个相互关联的子问题并逐步优化.为了验证NCEA的有效性,本文选取5个优秀的算法与NCEA进行对比实验.通过对比实验验证,NCEA具有较强的竞争力,能同时保持良好的收敛性和分布性.
The basic framework of traditional multi-objective evolutionary algorithms(MOEAs) can be classified into two parts: one is the convergence holding of the population, for which the fast nondominated sort approach is used to sort the population into certain nondomination layers; the other is the distribution maintenance of the population, for which diversity maintenance mechanisms are adoopted to hold the distribution of the population. However, when dealing with many-objective optimization problems(MOPs)(The number of objective dimensions is greater than 3), with the incease of objective dimensions, the conflicts between convergence and distribution will intensifys, and the Pareto dominance s ability of comparing the individuals will decline. In this case, traditional MOEAs are no longer apt. In this paper, a evolutionary algorithm is proposed based on neighborhood competition for multi-objective optimization(denoted as NCEA). Firstly,the convergence of each individual in the population is estimated by summing its objective values; then the angles between current selected solutions and the best converged solution are calculated and taken as the estimates of the distribution of the selected solutions; lastly, an MOP is divided into a number of mutually correlated sub-problems through neghorhood competition and optimizing, respectively. From the comparative experiments with other five representative MOEAs,NCEA is found to be competitive and successful in finding well-converged and well-distributed solution set.
The basic framework of traditional multi-objective evolutionary algorithms(MOEAs) can be classified into two parts: one is the convergence holding of the population, for which the fast nondominated sort approach is used to sort the population into certain nondomination layers; the other is the distribution maintenance of the population, for which diversity maintenance mechanisms are adoopted to hold the distribution of the population. However, when dealing with many-objective optimization problems(MOPs)(The number of objective dimensions is greater than 3), with the incease of objective dimensions, the conflicts between convergence and distribution will intensifys, and the Pareto dominance s ability of comparing the individuals will decline. In this case, traditional MOEAs are no longer apt. In this paper, a evolutionary algorithm is proposed based on neighborhood competition for multi-objective optimization(denoted as NCEA). Firstly,the convergence of each individual in the population is estimated by summing its objective values; then the angles between current selected solutions and the best converged solution are calculated and taken as the estimates of the distribution of the selected solutions; lastly, an MOP is divided into a number of mutually correlated sub-problems through neghorhood competition and optimizing, respectively. From the comparative experiments with other five representative MOEAs,NCEA is found to be competitive and successful in finding well-converged and well-distributed solution set.
引文
1 Guo Guan-Qi,Yin Cheng,Zeng Wen-Jing,Li Wu,Yan TaiShan.Prediction of Pareto dominance by cross similarity of equivalent components.Acta Automatica Sinica,2014,40(1):33-40(郭观七,尹呈,曾文静,李武,严太山.基于等价分量交叉相似性的Pareto支配性预测.自动化学报,2014,40(1):33-40)
2 Purshouse R C,Fleming P J.On the evolutionary optimization of many conflicting objectives.IEEE Transactions on Evolutionary Computation,2007,11(6):770-784
3 Li M Q,Yang S X,Liu X H.Shift-based density estimation for Pareto-based algorithms in many-objective optimization.IEEE Transactions on Evolutionary Computation,2014,18(3):348-365
4 Chen Zhen-Xing,Yan Xuan-Hui,Wu Kun-An,Bai Meng.Many-objective optimization integrating open angle based congestion control strategy.Acta Automatica Sinica,2015,41(6):1145-1158(陈振兴,严宣辉,吴坤安,白猛.融合张角拥挤控制策略的高维多目标优化.自动化学报,2015,41(6):1145-1158)
5 Li M Q,Yang S X,Zheng J H,Liu X H.ETEA:a euclidean minimum spanning tree-based evolutionary algorithm for multiobjective optimization.Evolutionary Computation,2014,22(2):189-230
6 Ikeda K,Kita H,Kobayashi S.Failure of Pareto-based MOEAs:Does non-dominated really mean near to optimal?In:Proceedings of the 2001 IEEE Congress on Evolutionary Computation.Seoul,South Korea:IEEE,2001.957-962
7 Li M Q,Yang S X,Liu X H.Bi-goal evolution for many-objective optimization problems.Artificial Intelligence,2015,228:45-65
8 Deb K,Mohan M,Mishra S.Evaluating the-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions.Evolutionary Computation,2005,13(4):501-525
9 Sato H,Aguirre H E,Tanaka K.Controlling dominance area of solutions and its impact on the performance of MOEAs.In:Proceedings of the 2007 International Conference on Evolutionary Multi-Criterion Optimization.Berlin:Springer,2007.5-20
10 Wang G P,Jiang H W.Fuzzy-dominance and its application in evolutionary many objective optimization.In:Proceedings of the International Conference on Computational Intelligence and Security Workshops(CISW 2007).Washington,D.C.,USA:IEEE,2007.195-198
11 Zitzler E,K¨unzli S.Indicator-based selection in multiobjective search.In:Proceedings of the 8th International Conference on Parallel Problem Solving from Nature.Birmingham,UK:Springer,2004.832-842
12 Beume N,Naujoks B,Emmerich M.SMS-EMOA:multiobjective selection based on dominated hypervolume.European Journal of Operational Research,2007,181(3):1653-1669
13 Hughes E J.Multiple single objective Pareto sampling.In:Proceedings of the 2003 IEEE Congress on Evolutionary Computation.Canberra,Australia:IEEE,2003.2678-2684
14 Zhang Q F,Li H.MOEA/D:A multiobjective evolutionary algorithm based on decomposition.IEEE Transactions on Evolutionary Computation,2007,11(6):712-731
15 Deb K,Jain H.An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach,Part I:solving problems with box constraints.IEEE Transactions on Evolutionary Computation,2014,18(4):577-601
16 Gong Dun-Wei,Liu Yi-Ping,Sun Xiao-Yan,Han Yu-Yan.Parallel Many-objective evolutionary optimization using objectives decomposition.Acta Automatica Sinica,2015,41(8):1438-1451(巩敦卫,刘益萍,孙晓燕,韩玉艳.基于目标分解的高维多目标并行进化优化方法.自动化学报,2015,41(8):1438-1451)
17 Adra S F,Fleming P J.A diversity management operator for evolutionary many-objective optimisation.In:Proceedings of the International Conference on Evolutionary MultiCriterion Optimization.Nantes,France:Springer,2009.81-94
18 Yang S X,Li M Q,Liu X H,Zheng J H.A grid-based evolutionary algorithm for many-objective optimization.IEEETransactions on Evolutionary Computation,2013,17(5):721-736
19 Deb K,Thiele L,Laumanns M,Zitzler E.Scalable test problems for evolutionary multiobjective optimization.Evolutionary Multiobjective Optimization.In:Proceedings of the Advanced Information and Knowledge Processing.Berlin,Germany:Springer,2005.105-145
20 Deb A,Pratap A,Agarwal S,Meyarivan T.A fast and elitist multiobjective genetic algorithm:NSGA-II.IEEE Transactions on Evolutionary Computation,2002,6(2):182-197
21 van Veldhuizen D A,Lamont G B.Evolutionary computation and convergence to a pareto front.In:Proceedings of the Late Breaking Papers at the Genetic Programming 1998Conference.Stanford University,California,USA:Citeseer,1998.221-228
22 Zheng J H,Li M Q.A diversity metric for MOEAs.In:Proceedings of 7th International Conference on Optimization:Techniques and Applications.Kobe,Japan,2007.451-452
23 Kung H T,Luccio F,Preparata F P.On finding the maxima of a set of vectors.Journal of the ACM(JACM),1975,22(4):469-476
24 Deb K,Jain S.Running performance metrics for evolutionary multi-objective optimization.Technical Report Kangal Report No.2002004,Indian Institute of Technology,2002
25 Bosman P A N,Thierens D.The balance between proximity and diversity in multi-objective evolutionary algorithms.IEEE Transactions on Evolutionary Computation,2003,7(2):174-188
26 Shen R M,Zheng J H,Li M Q,Zou J.Many-objective optimization based on information separation and neighbor punishment selection.Soft Computing,2015,21(5):1109-1128
27 Inselberg A.The plane with parallel coordinates.The Visual Computer,1985,1(2):69-91
28 Inselberg A,Dimsdale B.Parallel coordinates:a tool for visualizing multi-dimensional geometry.In:Proceedings of the 1st IEEE Conference on Visualization.San Francisco,California,USA:IEEE,1990.361-378
2 Purshouse R C,Fleming P J.On the evolutionary optimization of many conflicting objectives.IEEE Transactions on Evolutionary Computation,2007,11(6):770-784
3 Li M Q,Yang S X,Liu X H.Shift-based density estimation for Pareto-based algorithms in many-objective optimization.IEEE Transactions on Evolutionary Computation,2014,18(3):348-365
4 Chen Zhen-Xing,Yan Xuan-Hui,Wu Kun-An,Bai Meng.Many-objective optimization integrating open angle based congestion control strategy.Acta Automatica Sinica,2015,41(6):1145-1158(陈振兴,严宣辉,吴坤安,白猛.融合张角拥挤控制策略的高维多目标优化.自动化学报,2015,41(6):1145-1158)
5 Li M Q,Yang S X,Zheng J H,Liu X H.ETEA:a euclidean minimum spanning tree-based evolutionary algorithm for multiobjective optimization.Evolutionary Computation,2014,22(2):189-230
6 Ikeda K,Kita H,Kobayashi S.Failure of Pareto-based MOEAs:Does non-dominated really mean near to optimal?In:Proceedings of the 2001 IEEE Congress on Evolutionary Computation.Seoul,South Korea:IEEE,2001.957-962
7 Li M Q,Yang S X,Liu X H.Bi-goal evolution for many-objective optimization problems.Artificial Intelligence,2015,228:45-65
8 Deb K,Mohan M,Mishra S.Evaluating the-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions.Evolutionary Computation,2005,13(4):501-525
9 Sato H,Aguirre H E,Tanaka K.Controlling dominance area of solutions and its impact on the performance of MOEAs.In:Proceedings of the 2007 International Conference on Evolutionary Multi-Criterion Optimization.Berlin:Springer,2007.5-20
10 Wang G P,Jiang H W.Fuzzy-dominance and its application in evolutionary many objective optimization.In:Proceedings of the International Conference on Computational Intelligence and Security Workshops(CISW 2007).Washington,D.C.,USA:IEEE,2007.195-198
11 Zitzler E,K¨unzli S.Indicator-based selection in multiobjective search.In:Proceedings of the 8th International Conference on Parallel Problem Solving from Nature.Birmingham,UK:Springer,2004.832-842
12 Beume N,Naujoks B,Emmerich M.SMS-EMOA:multiobjective selection based on dominated hypervolume.European Journal of Operational Research,2007,181(3):1653-1669
13 Hughes E J.Multiple single objective Pareto sampling.In:Proceedings of the 2003 IEEE Congress on Evolutionary Computation.Canberra,Australia:IEEE,2003.2678-2684
14 Zhang Q F,Li H.MOEA/D:A multiobjective evolutionary algorithm based on decomposition.IEEE Transactions on Evolutionary Computation,2007,11(6):712-731
15 Deb K,Jain H.An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach,Part I:solving problems with box constraints.IEEE Transactions on Evolutionary Computation,2014,18(4):577-601
16 Gong Dun-Wei,Liu Yi-Ping,Sun Xiao-Yan,Han Yu-Yan.Parallel Many-objective evolutionary optimization using objectives decomposition.Acta Automatica Sinica,2015,41(8):1438-1451(巩敦卫,刘益萍,孙晓燕,韩玉艳.基于目标分解的高维多目标并行进化优化方法.自动化学报,2015,41(8):1438-1451)
17 Adra S F,Fleming P J.A diversity management operator for evolutionary many-objective optimisation.In:Proceedings of the International Conference on Evolutionary MultiCriterion Optimization.Nantes,France:Springer,2009.81-94
18 Yang S X,Li M Q,Liu X H,Zheng J H.A grid-based evolutionary algorithm for many-objective optimization.IEEETransactions on Evolutionary Computation,2013,17(5):721-736
19 Deb K,Thiele L,Laumanns M,Zitzler E.Scalable test problems for evolutionary multiobjective optimization.Evolutionary Multiobjective Optimization.In:Proceedings of the Advanced Information and Knowledge Processing.Berlin,Germany:Springer,2005.105-145
20 Deb A,Pratap A,Agarwal S,Meyarivan T.A fast and elitist multiobjective genetic algorithm:NSGA-II.IEEE Transactions on Evolutionary Computation,2002,6(2):182-197
21 van Veldhuizen D A,Lamont G B.Evolutionary computation and convergence to a pareto front.In:Proceedings of the Late Breaking Papers at the Genetic Programming 1998Conference.Stanford University,California,USA:Citeseer,1998.221-228
22 Zheng J H,Li M Q.A diversity metric for MOEAs.In:Proceedings of 7th International Conference on Optimization:Techniques and Applications.Kobe,Japan,2007.451-452
23 Kung H T,Luccio F,Preparata F P.On finding the maxima of a set of vectors.Journal of the ACM(JACM),1975,22(4):469-476
24 Deb K,Jain S.Running performance metrics for evolutionary multi-objective optimization.Technical Report Kangal Report No.2002004,Indian Institute of Technology,2002
25 Bosman P A N,Thierens D.The balance between proximity and diversity in multi-objective evolutionary algorithms.IEEE Transactions on Evolutionary Computation,2003,7(2):174-188
26 Shen R M,Zheng J H,Li M Q,Zou J.Many-objective optimization based on information separation and neighbor punishment selection.Soft Computing,2015,21(5):1109-1128
27 Inselberg A.The plane with parallel coordinates.The Visual Computer,1985,1(2):69-91
28 Inselberg A,Dimsdale B.Parallel coordinates:a tool for visualizing multi-dimensional geometry.In:Proceedings of the 1st IEEE Conference on Visualization.San Francisco,California,USA:IEEE,1990.361-378