Many-Objective Evolutionary Algorithm with Vector Angle Selection and Indicator Deletion

doi:10.3778/j.issn.1673-9418.2208111

Abstract

Abstract: Given that the challenge for evolutionary algorithms when solving many-objective optimization problems lies in balancing the convergence and diversity, a many-objective evolutionary algorithm based on vector angle selection and indicator deletion (MOEA/AS-ID), is proposed. In this algorithm, a coordinated mechanism that includes two strategies is designed in the environmental selection process to delete the solutions with poor convergence and diversity one by one, retaining the elitist to participate in the evolution process for the next generation. To be specific, the former strategy based on vector angle selection is used to select a pair of solutions with a similar search direction in the objective space, and the latter indicator-based deletion strategy which uses the [ISDE+] indicator (indicator shift-based density estimation) that takes into account the convergence and diversity of a single solution, is employed to compare the selected pair of solutions and delete the solution with a smaller indicator value, then encourage the population to converge to the Pareto optimal front toward all directions. Finally, the balance between convergence and diversity of the solution set is achieved. On DTLZ (Deb-Thiele-Laumanns-Zitzler), SDTLZ (scaled DTLZ), and MaF (many-objective function) three benchmark test suites with various characteristics，MOEA/AS-ID and six recently proposed many-objective evolutionary algorithms covering all current types perform extensive comparative simulation experiments and numerical results analysis. Simulation results and numerical analysis show that MOEA/AS-ID has strong competitiveness in balancing the convergence and diversity when solving many-objective optimization problems with various characteristics.

Key words: evolutionary algorithm, many-objective optimization, vector angle selection, indicator deletion, conver-gence, diversity

摘要： 针对进化算法求解高维多目标优化问题平衡收敛性和多样性所面临的挑战，提出了向量角选择和指标删除的高维多目标进化算法（MOEA/AS-ID）。该算法在环境选择过程中设计了一种包含两种策略的协作机制逐一删除收敛性和多样性差的解以保留精英个体参与下一代的进化。前者基于向量角的选择策略用于选择一对在目标空间具有相似搜索方向的解，后者基于指标的删除策略采用同时兼顾个体收敛性和分布性的[ISDE+]指标比较被选择的这一对解，然后删除具有较小指标值的解，进而促使种群朝各个方向收敛到帕累托最优前沿，最终平衡解集的收敛性和多样性。在包含各种特征的3组标准测试系列问题DTLZ、SDTLZ、MaF上，MOEA/AS-ID与近年提出的6个涵盖了当前各种类型的高维多目标进化算法执行了广泛的对比仿真实验和数值结果分析。仿真结果和数值分析表明所提算法MOEA/AS-ID求解各种特征的高维多目标优化问题平衡收敛性和多样性的能力具有较强的竞争力。

关键词: 进化算法, 高维多目标优化, 向量角选择, 指标删除, 收敛性, 多样性

GU Qinghua, LUO Jiale, LI Xuexian. Many-Objective Evolutionary Algorithm with Vector Angle Selection and Indicator Deletion[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(2): 425-438.

顾清华, 骆家乐, 李学现. 向量角选择和指标删除的高维多目标进化算法[J]. 计算机科学与探索, 2024, 18(2): 425-438.

References

[1] 易灵芝, 林佳豪, 刘建康, 等. 改进自适应MOEA/D算法的楼宇负荷优化调度[J]. 计算机工程与应用, 2022, 58(2): 295-302.
YI L Z, LIN J H, LIU J K, et al. Improved adaptive MOEA/D algorithm for building load optimization scheduling[J]. Computer Engineering and Applications, 2022, 58(2): 295-302.
[2] 王琴, 杨信丰, 李楠, 等. 不确定环境下的危险品运输车辆路径优化[J]. 计算机工程与应用, 2022, 58(15): 309-316.
WANG Q, YANG X F, LI N, et al. Route optimization of hazardous materials transportation vehicles in uncertain environ-ment[J]. Computer Engineering and Applications, 2022, 58(15): 309-316.
[3] 顾清华, 莫明慧, 卢才武, 等. 求解约束高维多目标问题的分解约束支配NSGA-Ⅱ优化算法[J]. 控制与决策, 2020, 35(10): 9-15.
GU Q H, MO M H, LU C W, et al. Decomposition-based constrained dominance principle NSGA-II for constrained many-objective optimization problems[J]. Control and Decision, 2020, 35(10): 9-15.
[4] 栾宪超, 常健, 王聪, 等. 主动关节履带式蛇形救援机器人结构参数多目标优化设计[J]. 机器人, 2022, 44(3): 267-280.
LUAN X C, CHANG J, WANG C, et al. Multi-objective optimization design of structural parameters for a crawler type snake-like rescue robot with active joint[J]. ROBOT, 2022, 44(3): 267-280.
[5] 宋超, 周铸, 李伟斌, 等. 旋翼翼型高维多目标气动优化设计[J]. 北京航空航天大学学报, 2022, 48(1): 95-105.
SONG C, ZHOU Z, LI W B, et al. Many-objective aero-dynamic optimization design of rotor airfoil[J]. Journal of Beijing University of Aeronautics and Astronautics, 2022, 48(1): 95-105.
[6] DEB K, AGARWAL S, MEYARIVAN T. A fast elitist non-dominated sorting genetic algorithm for multi-objective op-timization NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[7] ZHANG Q, HUI L. MOEA/D: a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2008, 11(6): 712-731.
[8] LI B, LI J, TANG K, et al. Many-objective evolutionary algorithms: a survey[J]. ACM Computing Surveys, 2015, 48(1): 1-35.
[9] 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.
[10] 谢承旺, 余伟伟, 郭华, 等. DAV-MOEA: 一种采用动态角度向量支配关系的高维多目标进化算法[J]. 计算机学报, 2022, 45(2): 317-333.
XIE C W, YU W W, GUO H, et al. DAV-MOEA: a many-objective evolutionary algorithm adopting dynamic angle vector based dominance relation[J]. Chinese Journal of Computers, 2022, 45(2): 317-333.
[11] LIU Y, ZHU N, LI K, et al. An angle dominance criterion for evolutionary many-objective optimization[J]. Information Sciences, 2020, 509: 376-399.
[12] SHEN J, WANG P, WANG X. A controlled strengthened dominance relation for evolutionary many-objective optimization[J]. IEEE Transactions on Cybernetics, 2022, 52(5): 3645-3657.
[13] 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.
[14] GU Q, CHEN H, CHEN L, et al. A many-objective evolu-tionary algorithm with reference points-based strengthened dominance relation[J]. Information Sciences, 2020, 554: 236-255.
[15] ZHOU C, DAI G, WANG M. Enhanced theta dominance and density selection based evolutionary algorithm for many-objective optimization problems[J]. Applied Intelligence, 2018, 48(4): 992-1012.
[16] WANG H, JIAO L, YAO X. Two_Arch2: an improved two-archive algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(4): 524-541.
[17] HE C, TIAN Y, JIN Y, et al. A radial space division based evolutionary algorithm for many-objective optimization[J]. Applied Soft Computing, 2017, 61: 603-621.
[18] ZHOU J, ZOU J, YANG S, et al. Niche-based and angle-based selection strategies for many-objective evolutionary optimi-zation[J]. Information Sciences, 2021, 571: 133-153.
[19] CHEN H, CHENG R, PEDRYCZ W, et al. Solving many-objective optimization problems via multistage evolutionary search[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(6): 3552-3564.
[20] 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, and Cybernetics: Systems, 2022，52(10): 6222-6234.
[21] PANICHELLA A. An adaptive evolutionary algorithm based on non-Euclidean geometry for many-objective optimization[C]//Proceedings of the 2019 Genetic and Evolutionary Com-putation Conference, Prague, Jul 13-17, 2019. New York: ACM, 2019: 595-603.
[22] LIANG Z, LUO T, HU K, et al. An indicator-based many-objective evolutionary algorithm with boundary protection[J]. IEEE Transactions on Cybernetics, 2021, 51(9): 4553-4566.
[23] LI L, YEN G G, SAHOO A, et al. On the estimation of Pareto front and dimensional similarity in many-objective evolu-tionary algorithm[J]. Information Sciences, 2021, 563: 375-400.
[24] ZOU J, FU L, YANG S, et al. An adaptation reference-point-based multiobjective evolutionary algorithm[J]. Information Sciences, 2019, 488: 41-57.
[25] MZ A, LEI W A, WL B, et al. Many-objective evolutionary algorithm with adaptive reference vector[J]. Information Sciences, 2021, 563(2): 70-90.
[26] YUAN Y, XU H, WANG B, et al. Balancing convergence and diversity in decomposition-based many-objective opti-mizers[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(2): 180-198.
[27] 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.
[28] LIU R, WANG R, BIAN R, et al. A decomposition-based evolutionary algorithm with correlative selection mechanism for many-objective optimization[J]. Evolutionary Computation, 2021, 29(2): 269-304.
[29] DEB K, JAIN H. An evolutionary many-objective optimi-zation algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box cons-traints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577-601.
[30] QI Y, LIU D, LI X, et al. An adaptive penalty-based boun-dary intersection method for many-objective optimization problem[J]. Information Sciences, 2020, 509: 356-375.
[31] ZOU J, ZHANG Z, ZHENG J, et al. A many-objective evo-lutionary algorithm based on dominance and decomposi-tion with reference point adaptation[J]. Knowledge-Based Systems, 2021, 231: 912-931.
[32] SUN Y, YEN G G, YI Z. IGD indicator-based evolutionary algorithm for many-objective optimization problems[J]. IEEE Transaction on Evolutionary Computation, 2018, 23(2): 173-187.
[33] CAI X, XIAO Y, LI M, et al. A grid-based inverted genera-tional distance for multi/many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(1): 21-34.
[34] HERNáNDEZ G R, COELLO COELLO C A. Improved metaheuristic based on the R2 indicator for many-objective optimization[C]//Proceedings of the 2015 Genetic and Evolu-tionary Computation Conference, Madrid, Jul 11-15, 2015.New York: ACM, 2015: 679-686.
[35] 陈国玉, 李军华, 黎明, 等. 基于R2指标和参考向量的高维多目标进化算法[J]. 自动化学报, 2021, 47(11): 2675-2690.
CHEN G Y, LI J H, LI M, et al. An R2 indicator and reference vector based many-objective optimization evolutionary algo-rithm[J]. Acta Automatica Sinica, 2021, 47(11): 2675-2690.
[36] BADER J, ZITZLER E. HypE: an algorithm for fast hyper-volume-based many-objective optimization[J]. Evolutionary Computation, 2011, 19(1): 45-76.
[37] TRINADH, PAMULAPATI, RAMMOHAN, et al. [ISDE+]—an indicator for multi and many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(2): 346-352.
[38] AGRAWAL R B, DEB K. Simulated binary crossover for continuous search space[J]. Complex Systems, 1995, 9(3): 115-148.
[39] DEB K, GOYAL M. A combined genetic adaptive search (GeneAS) for engineering design[J]. Computer Science and Informatics, 1996, 26(4): 30-45.
[40] DEB K, THIELE L, LAUMANNS M, et al. Scalable test problems for evolutionary multi-objective optimization[J]. Evolutionary Multiobjective Optimization, 2006: 105-145.
[41] 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.
[42] YANG F, XU L, CHU X, et al. A new dominance relation based on convergence indicators and niching for many-objective op-timization[J]. Applied Intelligence, 2021, 51(8): 5525-5542.
[43] LIANG Z, LUO T, HU K, et al. An indicator-based many-objective evolutionary algorithm with boundary protection[J]. IEEE Transactions on Cybernetics, 2021, 51(9): 4553 - 4566.
[44] ZITZLER E, THIELE L, LAUMANNS M, et al. Performance assessment of multiobjective optimizers: an analysis and re-view[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(2): 117-132.
[45] DERRAC J, GARCIA S, MOLINA D, et al. A practical tutorial on the use of nonparametric statistical tests as a me-thodology for comparing evolutionary and swarm intelligence algorithms[J]. Swarm and Evolutionary Computation, 2011, 1(1): 3-18.
[46] YUAN Y, XU H, WANG B, et al. A new dominance relation-based evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(1): 16-37.