基于小生境的多目标进化算法

doi:10.3778/j.issn.1002-8331.2207-0006

摘要/Abstract

摘要： 进化算法求解多目标优化问题平衡收敛性和多样性面临的主要挑战在两个方面：增强对帕累托最优前沿的选择压力和获得多样性良好的解集。然而，随着目标维数的增加，基于帕累托支配关系的选择标准无法有效地解决以上问题。因此，设计了一种基于小生境的多目标进化算法。基于小生境，提出了一种新的支配关系，其中，设计了一个聚合函数和一种采用目标向量角的密度估计方法分别度量候选解的收敛度和分布性。为了保证解集的收敛性，在同一个小生境内，仅仅收敛度最好的解是非支配解。为了维护解集的多样性，在任何两个不同的小生境内，一个小生境内兼具收敛度和分布性良好的解支配另一个小生境内收敛性和分布性均差的解，将提出的支配关系嵌入VaEA取代帕累托支配关系，设计了一种多目标进化算法VaEA-SDN。VaEA-SDN与NSGA-III、VaEA、MSEA、NSGAII-CSDR、RPS-NSGAII以及CDR-MOEA等先进的算法在DTLZ（Deb-Thiele-Laumanns-Zitzler）和MaF（many-objective function）基准测试系列问题上进行了广泛的对比仿真实验。仿真结果表明，VaEA-SDN平衡收敛收敛性和多样性的能力分别比被比较的6个算法平均高37.7%、32.9%、31.8%、22.2%、43.5%、30.2%。

关键词: 进化算法, 多目标优化, 小生境, 目标向量角

Abstract: The main challenges for evolutionary algorithms to balance convergence and diversity in solving many-objective optimization problems are in two aspects：strengthening selection pressure towards the Pareto optimal front and achieving a good diversity of the obtained solution set. However, the Pareto dominance-based selection criteria cannot effectively solve the above problems with the increase of the objective number. Therefore, an evolutionary algorithm based on niche is designed. Firstly, based on the niche, a new dominance relation is proposed, where an aggregation function and an objective vector angle-based density estimation method are used to measure the convergence and distribution of candidate solutions respectively. Then, in the same niche, only the solution with the best convergence degree is identified as the non-dominated solution to ensure the convergence of a solution set. At the same time, to improve the diversity of a solution set, in any two different niches, the solution with good convergence and distribution in one niche will dominate the solution with poor convergence and distribution in the other niche. Finally, the proposed dominance relation is embedded into VaEA instead of Pareto dominance relation to design an improved many-objective evolutionary algorithm（VaEA-SDN）. VaEA-SDN and six state-of-the-art algorithms NSGA-III, VaEA, MSEA, NSGAII-CSDR, RPS-NSGAII and CDR-MOEA are conducted in simulation experiments on the DTLZ（Deb-Thiele-Laumanns-Zitzler） and MaF（many-objective function） benchmark suites. The results show that the ability of VaEA-SDN in keeping a balance between the convergence and diversity has an average improvement of 37.7%, 32.9%, 31.8%, 22.2%, 43.5%, 30.2% over the compared six algorithms in terms of the quality of obtained solutions.

Key words: evolutionary algorithms, multi-objective optimization, niche, objective vector angle

顾清华, 骆家乐, 李学现. 基于小生境的多目标进化算法[J]. 计算机工程与应用, 2023, 59(1): 126-139.

GU Qinghua, LUO Jiale, LI Xuexian. Evolutionary Algorithm Based on Niche for Multi-Objective Optimization[J]. Computer Engineering and Applications, 2023, 59(1): 126-139.

参考文献

[1] 顾清华，李学现，卢才武，等.求解高维复杂函数的遗传-灰狼混合算法[J].控制与决策，2020，35（5）：1191-1198.
GU Q H，LI X X，LU C W，et al.Hybrid grey wolf genetic algorithm for high dimensional complex function optimization[J].Control and Decision，2020，35（5）：1191-1198.
[2] ZHU S，XU L，GOODMAN E D，et al.A new many-objective evolutionary algorithm based on generalized pareto dominance[J].IEEE Transactions on Cybernetics，2022，52（8）：7776-7790.
[3] LIU Y，ZHU N，LI K，et al.An angle dominance criterion for evolutionary many-objective optimization[J].Information Sciences，2019，509：376-399.
[4] KHAN B，HANOUN S，JOHNSTONE M，et al.A scalarization-based dominance evolutionary algorithm for many-objective optimization[J].Information Sciences，2019，474：236-252.
[5] GU Q，CHEN H，CHEN L，et al.A many-objective evolutionary algorithm with reference points-based strengthened dominance relation[J].Information Sciences，2020，554：236-255.
[6] TIAN Y，CHENG R，ZHANG X，et al.A strengthened dominance relation considering convergence and diversity for evolutionary many-objective optimization[J].IEEE Transactions on Evolutionary Computation，2019，23（2）：331-345.
[7] YANG F，XU L，CHU X，et al.A new dominance relation based on convergence indicators and niching for many-objective optimization[J].Applied Intelligence，2021，51（8）：5525-5542.
[8] SHEN J，WANG P，WANG X.A controlled strengthened dominance relation for evolutionary many-objective optimization[J].IEEE Transactions on Cybernetics，2022，99：1-13.
[9] YI X，ZHOU Y，LI M，et al.A vector angle-based evolutionary algorithm for unconstrained many-objective optimization[J].IEEE Transactions on Evolutionary Computation，2017，21（1）：131-152.
[10] 顾清华，徐青松，李学现.基于距离优势关系的高维多目标进化算法[J].计算机科学与探索，2022，16（11）：2642-2652.
GU Q H，XU Q S，LI X X.Many-objective evolutionary algorithm based on distance dominance relation[J].Journal of Frontiers of Computer Science and Technology，2022，16（11）：2642-2652.
[11] TIAN Y，CHENG H，CHENG R，et al.A multi-stage evolutionary algorithm for better diversity preservation in multi-objective optimization[J].IEEE Transactions on Systems，Man，and Cybernetics：Systems，2019，51（9）：5880-5894.
[12] CHEN H，CHENG R，PEDRYCZ W，et al.Solving many-objective optimization problems via multistage evolutionary search[J].IEEE Transactions on Systems Man Cybernetics：Systems，2021，51（6）：3552-3564.
[13] MING F，GONG W，WANG L.A two-stage evolutionary algorithm with balanced convergence and diversity for many-objective optimization[J].IEEE Transactions on Systems Man Cybernetics：Systems，2022，52（10）：6222-6234.
[14] ZHAO L，REN Y，ZENG Y，et al.A knee point-driven many-objective pigeon-inspired optimization algorithm[J].Complex & Intelligent Systems，2022，8（5）：4277-4299.
[15] QI Y，LIU D，LI X，et al.An adaptive penalty-based boundary intersection method for many-objective optimization problem[J].Information Sciences，2020，509：356-375.
[16] LIU S，LIN Q，WONG K C，et al.A self-guided reference vector strategy for many-objective optimization[J].IEEE Transactions on Cybernetics，2022，52（2）：1164-1178.
[17] ZHANG Q，HUI L.MOEA/D：A multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation，2008，11（6）：712-731.
[18] YUAN Y，XU H，WANG B，et al.Balancing convergence and diversity in decomposition-based many-objective optimizers[J].IEEE Transactions on Evolutionary Computation，2016，20（2）：180-198.
[19] CHEN J，DING J，TAN K C，et al.A decomposition-based evolutionary algorithm for scalable multi/many-objective optimization[J].Memetic Computing，2021，13（3）：413-432.
[20] ZHAO C，ZHOU Y，CHEN Z.Decomposition-based evolutionary algorithm with automatic estimation to handle many-objective optimization problem[J].Information Sciences，2021，546：1030-1046.
[21] 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.
[22] ZOU J，ZHANG Z，ZHENG J，et al.A many-objective evolutionary algorithm based on dominance and decomposition with reference point adaptation[J].Knowledge-Based Systems，2021，231：912-931.
[23] HAN D，DU W，DU W，et al.An adaptive decomposition-based evolutionary algorithm for many-objective optimization[J].Information Sciences，2019，491：204-222.
[24] YI J，ZHANG W，BAI J，et al.Multifactorial evolutionary algorithm based on improved dynamical decomposition for many-objective optimization problems[J].IEEE Transactions on Evolutionary Computation，2022，26（2）：334-348.
[25] BISWAS S，KUNDU S，DAS S.Inducing niching behavior in differential evolution through local information sharing[J].IEEE Transactions on Evolutionary Computation，2015，19（2）：246-263.
[26] BECHIKH S，CHAABANI A，BEN SAID L.An efficient chemical reaction optimization algorithm for multiobjective optimization[J].IEEE Transactions on Cybernetics，2015，45（10）：2051-2064.
[27] TIAN Y，XIANG X，ZHANG X，et al.Sampling reference points on the pareto fronts of benchmark multi-objective optimization problems[C]//Proceedings of the IEEE Congress on Evolutionary Computation（CEC），2018：1-6.
[28] DEB K，THIELE L，LAUMANNS M，et al.Scalable test problems for evolutionary multi-objective optimization[J].Evolutionary Multiobjective Optimization，2005（1）：105-145.
[29] CHENG R，LI M，TIAN Y，et al.A benchmark test suite for evolutionary many-objective optimization[J].Complex & Intelligent Systems，2017，3（1）：67-81.
[30] TIAN Y，CHENG R，ZHANG X Y，et al.Diversity assessment of multi-Objective evolutionary algorithms：Performance metric and benchmark problems[J].IEEE Computational Intelligence Magazine，2019，14（3）：61-74.
[31] ZITZLER E，THIELE L，LAUMANNS M，et al.Performance assessment of multiobjective optimizers：An analysis and review[J].IEEE Transactions on Evolutionary Computation，2003，7（2）：117-132.
[32] TIAN Y，CHENG R，ZHANG X，et al.PlatEMO：A MATLAB platform for evolutionary multi-objective optimization[J].IEEE Computational Intelligence Magazine，2017，12（4）：73-87.
[33] DERRAC J，GARCIA S，MOLINA D，et al.A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J].Swarm and Evolutionary Computation，2011，1（1）：3-18.
[34] LIAO X，LI Q，YANG X，et al.Multiobjective optimization for crash safety design of vehicles using stepwise regression model[J].Structural and Multidisciplinary Optimization，2007，35（6）：561-569.
[35] 顾清华，周煜丰，李学现，等.基于径向空间划分的昂贵多目标进化算法[J].自动化学报，2022，48（10）：2564?2584.
GU Q H，ZHOU Y F，LI X X，et al.Expensive many-objective evolutionary algorithm based on radial space division[J].Acta Automatica Sinica，2022，48（10）：2564-2584.
[36] YUE C T，QU B Y，LIANG J.A multiobjective particle swarm optimizer using ring topology for solving multimodal multiobjective problems[J].IEEE Transactions on Evolutionary Computation，2018，22（5）：805-817.
[37] YUE C T，LIANG J，QU B Y，et al.Multimodal multiobjective optimization in feature selection[C]//Proceedings of the IEEE Congress on Evolutionary Computation，2019：302-309.
[38] YU V F，HU K J，CHANG A Y.An interactive approach for the multi-objective transportation problem with interval parameters[J].International Journal of Production Research，2015，53（4）：1051-1064.