Pareto支配关系下两阶段进化高维多目标优化算法
|
摘要
工程应用和现实生活中广泛存在着高维多目标优化问题。基于Pareto支配的多目标演化算法在处理高维多目标优化问题时会面临收敛压力丧失的缺点,基于分解的多目标优化算法在处理Pareto前沿不规则的问题时鲁棒性较差。为了提高基于支配的多目标优化算法的选择压力同时保留基于支配算法多样性保持的灵活性,提出一种基于Pareto支配关系的两阶段进化高维多目标优化算法。在算法的第一阶段,集中计算资源搜索优化问题的极值点,通过优先选择内部空间的解来提高基于支配算法的收敛性能。在算法的第二阶段,利用动态最小距离法改善算法的多样性,使得算法获得一组均匀分布的精英解。实验表明,该算法在PF形状不规则的问题上显著优于与之比较的其他算法,且在PF形状规则的问题上性能良好,这表明该算法具有较好的鲁棒性。
People often need to optimize many conflicting objectives at the same time both in engineering application and real life. These optimization problems are called many-objective optimization problems(Ma OPs). The evolutionary algorithms based on Pareto dominance will lose the convergence pressure when dealing with Ma OPs. The decomposition based algorithm needs a set of preset reference vectors in objective space, which make the poor robustness when dealing with Ma OPs with irregular PFs. In order to improve the convergence and maintain the flexible diversity strategy in dominance based algorithms, this paper proposes a two phase many-objective optimization algorithm based on Pareto dominance. The proposed algorithm centralizes computing resources to search the nadir point of optimization problems in the first phase. Then the inner and outward space can be divided according to the nadir point, and the convergence of algorithms can be improved by selecting the solutions in the inner space. In thesecond phase, the dynamic minimal distance method is proposed to improve the diversity of the algorithm. Compared with four state-of-art many-objective optimization algorithms, the experimental results show that the performance of the proposed algorithm is significantly better than that of compared algorithms on the Ma OPs with irregular PFs. Meanwhile, the proposed algorithm also obtains competitive results on Ma OPs with regular PFs. In a word,these experimental results indicate that the proposed algorithm has better robustness.
People often need to optimize many conflicting objectives at the same time both in engineering application and real life. These optimization problems are called many-objective optimization problems(Ma OPs). The evolutionary algorithms based on Pareto dominance will lose the convergence pressure when dealing with Ma OPs. The decomposition based algorithm needs a set of preset reference vectors in objective space, which make the poor robustness when dealing with Ma OPs with irregular PFs. In order to improve the convergence and maintain the flexible diversity strategy in dominance based algorithms, this paper proposes a two phase many-objective optimization algorithm based on Pareto dominance. The proposed algorithm centralizes computing resources to search the nadir point of optimization problems in the first phase. Then the inner and outward space can be divided according to the nadir point, and the convergence of algorithms can be improved by selecting the solutions in the inner space. In thesecond phase, the dynamic minimal distance method is proposed to improve the diversity of the algorithm. Compared with four state-of-art many-objective optimization algorithms, the experimental results show that the performance of the proposed algorithm is significantly better than that of compared algorithms on the Ma OPs with irregular PFs. Meanwhile, the proposed algorithm also obtains competitive results on Ma OPs with regular PFs. In a word,these experimental results indicate that the proposed algorithm has better robustness.
引文
[1]Li Bingdong,Li Jinlong,Tang Ke,et al.Many-objective evolutionary algorithms:a survey[J].ACM Computing Surveys,2015,48(1):13.
[2]Yoshimoto T,Yajima H,Yu Qiang,et al.Multi-objective optimization for crash safety design of vehicles[C]//Proceedings of the International Body Engineering Conference&Exposition,Detroit,Sep 28-30,1999.
[3]Deb K,Gupta S,Daum D,et al.Reliability-based optimization using evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation,2009,13(5):1054-1074.
[4]Zhou Aimin,Qu Boyang,Li Hui,et al.Multiobjective evolutionary algorithms:a survey of the state of the art[J].Swarm and Evolutionary Computation,2011,1(1):32-49.
[5]Fleming P,Purshouse R,Lygoe R.Many-objective optimization:an engineering design perspective[C]//LNCS 3410:Proceedings of the 3rd International Conference on Evolutionary Multi-Criterion Optimization,Guanajuato,Mar 9-11,2005.Berlin,Heidelberg:Springer,2005:14-32.
[6]Jin Yaochu,Sendhoff B.Connectedness,regularity and the success of local search in evolutionary multi-objective optimization[C]//Proceedings of the 2003 IEEE Congress on Evolutionary Computation,Canberra,Dec 8-12,2003.Piscataway:IEEE,2003:1910-1917.
[7]Zhang Qingfu,Zhou Aimin,Jin Yaochu.RM-MEDA:a regularity model-based multiobjective estimation of distribution algorithm[J].IEEE Transactions on Evolutionary Computation,2008,12(1):41-63.
[8]Purshouse R,Fleming P.On the evolutionary optimization of many conflicting objectives[J].IEEE Transactions on Evolutionary Computation,2007,11(6):770-784.
[9]Adra S,Fleming P.Diversity management in evolutionary many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2011,15(2):183-195.
[10]Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[11]Ishibuchi H,Tsukamoto N,Nojima Y.Evolutionary manyobjective optimization:a short review[C]//Proceedings of the2008 IEEE Congress on Evolutionary Computation,Hong Kong,China,Jun 1-6,2008.Piscataway:IEEE,2008:2419-2426.
[12]He Zhenan,Yen G.Ranking many-objective evolutionary algorithms using performance metrics ensemble[C]//Proceedings of the 2013 IEEE Congress on Evolutionary Computation,Cancun,Jun 20-23,2013.Piscataway:IEEE,2013:2480-2487.
[13]Laumanns M,Thiele L,Deb K,et al.Combining convergence and diversity in evolutionary multiobjective optimization[J].Evolutionary Computation,2002,10(3):263-282.
[14]Zou Xiufen,Chen Yu,Liu Minzhong,et al.A new evolutionary algorithm for solving many-objective optimization problems[J].IEEE Transactions on Systems,Man,and Cybernetics:Part B Cybernetics,2008,38(5):1402-1412.
[15]Wang Gaoping,Jiang Huawei.Fuzzy-dominance and its application in evolutionary many objective optimization[C]//Proceedings of the 2007 International Conference on Computational Intelligence and Security Workshops,Harbin,Dec 15-19,2007.Washington:IEEE Computer Society,2007:195-198.
[16]Yang Shengxiang,Li Miqing,Liu Xiaohui,et al.A gridbased evolutionary algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2013,17(5):721-736.
[17]Li Hui,Zhang Qingfu.Multiobjective optimization problems with complicated Pareto sets,MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation,2009,13(2):284-302.
[18]Zhang Qingfu,Li Hui.MOEA/D:a multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.
[19]Zitzler E,Künzli S.Indicator-based selection in multiobjective search[C]//LNCS 3242:Proceedings of the 8th International Conference on Parallel Problem Solving from Nature,Birmingham,Sep 18-22,2004.Berlin,Heidelberg:Springer,2004:832-842.
[20]Beume N,Naujoks B,Emmerich M.SMS-EMOA:multiobjective selection based on dominated hypervolume[J].European Journal of Operational Research,2007,181(3):1653-1669.
[21]Bader J,Zitzler E.Hyp E:an algorithm for fast hypervolumebased many-objective optimization[J].Evolutionary Computation,2011,19(1):45-76.
[22]Deb K,Thiele L,Laumanns M,et al.Scalable test problems for evolutionary multiobjective optimization[M]//Abraham A,Jain L,Goldberg R.Evolutionary Multiobjective Optimization,Theoretical Advances and Applications.Berlin,Heidelberg:Springer,2006:105-145.
[23]Li Ke,Deb K,Zhang Qingfu,et al.An evolutionary manyobjective optimization algorithm based on dominance and decomposition[J].IEEE Transactions on Evolutionary Computation,2015,19(5):694-716.
[24]Deb K,Jain H.An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach,part I:solving problems with box constraints[J].IEEE Transactions on Evolutionary Computation,2014,18(4):577-601.
[25]Ishibuchi H,Setoguchi Y,Masuda H,et al.Performance of decomposition-based many-objective algorithms strongly depends on Pareto front shapes[J].IEEE Transactions on Evolutionary Computation,2017,21(2):169-190.
[26]While L,Hingston P,Barone L,et al.A faster algorithm for calculating hypervolume[J].IEEE Transactions on Evolutionary Computation,2006,10(1):29-38.
[27]Singh H K,Isaacs A,Ray T.A Pareto corner search evolutionary algorithm and dimensionality reduction in manyobjective optimization problems[J].IEEE Transactions on Evolutionary Computation,2011,15(4):539-556.
[28]He Zhenan,Yen G G.Many objective evolutionary algorithm:objective space reduction and diversity improvement[J].IEEE Transactions on Evolutionary Computation,2016,20(1):145-160.
[29]Wang Handing,Yao Xin.Corner sort for Pareto-based manyobjective optimization[J].IEEE Transactions on Cybernetics,2014,44(1):92-102.
[30]Zhu Chunyang,Cai Xinye,Fan Zhun,et al.A two-phase many-objective evolutionary algorithm with penalty based adjustment for reference lines[C]//Proceedings of the 2016IEEE Congress on Evolutionary Computation,Vancouver,Jul 24-29,2016.Piscataway:IEEE,2016:2161-2168.
1)在搜索极值点的过程中,需要给极值点一定的搜索次数,计算最大变化率的频率过高可能会导致极值点还没有被搜索到就切换到了第二阶段。反之,如果最大变化率的频率过低,会导致算法有可能一直停留在第一阶段从而失去了切换机制的应有的作用。通过在不同的测试问题上的实验表明在整个演化过程中判断5至10次比较合适。在实验阶段,选取的是30万次的函数评估,结合不同目标数时的种群规模,基本上每个目标数的问题都需要迭代1 000多次,在这种情况下,将计算最大变化率的频率统一设定为200代,从而确保每个问题基本上都能进行5~10次的最大变化率判断。
[2]Yoshimoto T,Yajima H,Yu Qiang,et al.Multi-objective optimization for crash safety design of vehicles[C]//Proceedings of the International Body Engineering Conference&Exposition,Detroit,Sep 28-30,1999.
[3]Deb K,Gupta S,Daum D,et al.Reliability-based optimization using evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation,2009,13(5):1054-1074.
[4]Zhou Aimin,Qu Boyang,Li Hui,et al.Multiobjective evolutionary algorithms:a survey of the state of the art[J].Swarm and Evolutionary Computation,2011,1(1):32-49.
[5]Fleming P,Purshouse R,Lygoe R.Many-objective optimization:an engineering design perspective[C]//LNCS 3410:Proceedings of the 3rd International Conference on Evolutionary Multi-Criterion Optimization,Guanajuato,Mar 9-11,2005.Berlin,Heidelberg:Springer,2005:14-32.
[6]Jin Yaochu,Sendhoff B.Connectedness,regularity and the success of local search in evolutionary multi-objective optimization[C]//Proceedings of the 2003 IEEE Congress on Evolutionary Computation,Canberra,Dec 8-12,2003.Piscataway:IEEE,2003:1910-1917.
[7]Zhang Qingfu,Zhou Aimin,Jin Yaochu.RM-MEDA:a regularity model-based multiobjective estimation of distribution algorithm[J].IEEE Transactions on Evolutionary Computation,2008,12(1):41-63.
[8]Purshouse R,Fleming P.On the evolutionary optimization of many conflicting objectives[J].IEEE Transactions on Evolutionary Computation,2007,11(6):770-784.
[9]Adra S,Fleming P.Diversity management in evolutionary many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2011,15(2):183-195.
[10]Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[11]Ishibuchi H,Tsukamoto N,Nojima Y.Evolutionary manyobjective optimization:a short review[C]//Proceedings of the2008 IEEE Congress on Evolutionary Computation,Hong Kong,China,Jun 1-6,2008.Piscataway:IEEE,2008:2419-2426.
[12]He Zhenan,Yen G.Ranking many-objective evolutionary algorithms using performance metrics ensemble[C]//Proceedings of the 2013 IEEE Congress on Evolutionary Computation,Cancun,Jun 20-23,2013.Piscataway:IEEE,2013:2480-2487.
[13]Laumanns M,Thiele L,Deb K,et al.Combining convergence and diversity in evolutionary multiobjective optimization[J].Evolutionary Computation,2002,10(3):263-282.
[14]Zou Xiufen,Chen Yu,Liu Minzhong,et al.A new evolutionary algorithm for solving many-objective optimization problems[J].IEEE Transactions on Systems,Man,and Cybernetics:Part B Cybernetics,2008,38(5):1402-1412.
[15]Wang Gaoping,Jiang Huawei.Fuzzy-dominance and its application in evolutionary many objective optimization[C]//Proceedings of the 2007 International Conference on Computational Intelligence and Security Workshops,Harbin,Dec 15-19,2007.Washington:IEEE Computer Society,2007:195-198.
[16]Yang Shengxiang,Li Miqing,Liu Xiaohui,et al.A gridbased evolutionary algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2013,17(5):721-736.
[17]Li Hui,Zhang Qingfu.Multiobjective optimization problems with complicated Pareto sets,MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation,2009,13(2):284-302.
[18]Zhang Qingfu,Li Hui.MOEA/D:a multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.
[19]Zitzler E,Künzli S.Indicator-based selection in multiobjective search[C]//LNCS 3242:Proceedings of the 8th International Conference on Parallel Problem Solving from Nature,Birmingham,Sep 18-22,2004.Berlin,Heidelberg:Springer,2004:832-842.
[20]Beume N,Naujoks B,Emmerich M.SMS-EMOA:multiobjective selection based on dominated hypervolume[J].European Journal of Operational Research,2007,181(3):1653-1669.
[21]Bader J,Zitzler E.Hyp E:an algorithm for fast hypervolumebased many-objective optimization[J].Evolutionary Computation,2011,19(1):45-76.
[22]Deb K,Thiele L,Laumanns M,et al.Scalable test problems for evolutionary multiobjective optimization[M]//Abraham A,Jain L,Goldberg R.Evolutionary Multiobjective Optimization,Theoretical Advances and Applications.Berlin,Heidelberg:Springer,2006:105-145.
[23]Li Ke,Deb K,Zhang Qingfu,et al.An evolutionary manyobjective optimization algorithm based on dominance and decomposition[J].IEEE Transactions on Evolutionary Computation,2015,19(5):694-716.
[24]Deb K,Jain H.An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach,part I:solving problems with box constraints[J].IEEE Transactions on Evolutionary Computation,2014,18(4):577-601.
[25]Ishibuchi H,Setoguchi Y,Masuda H,et al.Performance of decomposition-based many-objective algorithms strongly depends on Pareto front shapes[J].IEEE Transactions on Evolutionary Computation,2017,21(2):169-190.
[26]While L,Hingston P,Barone L,et al.A faster algorithm for calculating hypervolume[J].IEEE Transactions on Evolutionary Computation,2006,10(1):29-38.
[27]Singh H K,Isaacs A,Ray T.A Pareto corner search evolutionary algorithm and dimensionality reduction in manyobjective optimization problems[J].IEEE Transactions on Evolutionary Computation,2011,15(4):539-556.
[28]He Zhenan,Yen G G.Many objective evolutionary algorithm:objective space reduction and diversity improvement[J].IEEE Transactions on Evolutionary Computation,2016,20(1):145-160.
[29]Wang Handing,Yao Xin.Corner sort for Pareto-based manyobjective optimization[J].IEEE Transactions on Cybernetics,2014,44(1):92-102.
[30]Zhu Chunyang,Cai Xinye,Fan Zhun,et al.A two-phase many-objective evolutionary algorithm with penalty based adjustment for reference lines[C]//Proceedings of the 2016IEEE Congress on Evolutionary Computation,Vancouver,Jul 24-29,2016.Piscataway:IEEE,2016:2161-2168.
1)在搜索极值点的过程中,需要给极值点一定的搜索次数,计算最大变化率的频率过高可能会导致极值点还没有被搜索到就切换到了第二阶段。反之,如果最大变化率的频率过低,会导致算法有可能一直停留在第一阶段从而失去了切换机制的应有的作用。通过在不同的测试问题上的实验表明在整个演化过程中判断5至10次比较合适。在实验阶段,选取的是30万次的函数评估,结合不同目标数时的种群规模,基本上每个目标数的问题都需要迭代1 000多次,在这种情况下,将计算最大变化率的频率统一设定为200代,从而确保每个问题基本上都能进行5~10次的最大变化率判断。