Two Stage Multi-Objective Optimization Algorithm Based on Pareto Dominance
-
摘要: 针对二维和三维的多目标优化问题,提出了一种基于Pareto支配的两阶段多目标优化算法(MOEA-PT)。全局搜索阶段根据Pareto支配关系将种群进行排序,依据临界层子集的排序等级进行相应的选择策略。局部调整阶段对种群中的个体进行微调,将新产生的个体与其距离最近的个体进行支配关系以及分布性与收敛性的对比,替换较差的个体。分析了两个阶段对算法性能的影响,同时对引入局部调整后的种群进行了对比,结果表明局部调整策略能有效增强算法性能。通过对标准测试函数的求解,并与其他经典的多目标算法进行对比,验证了本文算法在收敛性和分布性等方面具有一定的优越性。Abstract: A two-stage multi-objective optimization algorithm based on Pareto dominance is proposed for 2-dimensional and 3-dimensional multi-objective problems. In the global search stage, the population is sorted according to the Pareto dominance relation, and the corresponding selection strategy is carried out according to the ranking level of the critical layer subset. In the local adjustment stage, the individuals in the population are fine tuned, and the new individuals are compared with the nearest individuals in terms of dominance, distribution and convergence, so as to replace the poor individuals. The influence of the two stages on the performance of the algorithm is analyzed, and the population with local adjustment is compared, the results show that the local adjustment strategy can effectively enhance the performance of the algorithm. By solving the standard test function and comparing with other classical multi-objective algorithms, this algorithm has some advantages in convergence and distribution.
-
Key words:
- multi-objective optimization /
- Pareto dominance /
- global search /
- local adjustment
-
表 1 ZDT、WFG、DTLZ决策变量维数
Table 1. Dimensions of decision variables in ZDT, WFG and DTLZ
Function Dim Function Dim ZDT1 30 DTLZ1 7 ZDT2 30 DTLZ2 12 ZDT3 30 DTLZ3 12 ZDT4 10 DTLZ4 12 WFG1 11 DTLZ5 12 WFG2 11 DTLZ6 12 WFG3 11 DTLZ7 22 WFG4 11 表 2 7种算法的IGD均值
Table 2. Mean value of IGD for seven algorithms
Function IGDm SPEA2 NSGA-II MOEAD NSGA-III VaEA CMOPSO MOEA-PT ZDT1 3.7486x10-3 4.6298 x10-3 5.3983 x10-3 3.7055 x10-3 4.7170 x10-3 3.9516 x10-3 3.5750 x10-3 ZDT2 3.7129 x10-3 4.6126 x10-3 7.0048 x10-3 3.6258 x10-3 3.9918 x10-3 3.8848 x10-3 3.6024 x10-3 ZDT3 4.6665 x10-3 8.0422 x10-3 2.1363e-2 5.8561 x10-3 5.5649 x10-3 4.3996 x10-3 4.3498 x10-3 ZDT4 4.4296 x10-3 4.6305 x10-3 9.2547 x10-3 4.4577 x10-3 1.8066e-2 4.5945e-2 3.9975 x10-3 WFG1 9.7079 x10-2 6.2713 x10-2 1.2723 x10-1 1.2298 x10-1 1.5381 x10-1 4.8207 x10-1 1.1397 x10-1 WFG2 1.0669 x10-2 1.2412 x10-2 6.0552 x10-2 1.3588 x10-2 1.1857 x10-2 1.0853 x10-2 1.0500 x10-2 WFG3 1.1988 x10-2 1.4409 x10-2 1.6908 x10-2 1.1341 x10-2 1.3098 x10-2 1.2996 x10-2 1.1312 x10-2 WFG4 1.2494 x10-2 1.4797 x10-2 2.5448 x10-2 1.2033 x10-2 1.3578 x10-2 4.1252 x10-2 1.1951 x10-2 DTLZ1 1.9783 x10-2 2.6299 x10-2 1.9140 x10-2 1.9092 x10-2 2.7322 x10-2 3.0359e+0 1.9506 x10-2 DTLZ2 5.3045 x10-2 6.6641 x10-2 5.0302 x10-2 5.0319 x10-2 5.3536 x10-2 5.6453 x10-2 5.1166 x10-2 DTLZ3 5.2299 x10-2 6.9070 x10-2 5.1012 x10-2 5.1122 x10-2 5.6145 x10-2 4.6293 x10 5.2565 x10-2 DTLZ4 1.7099 x10-1 6.7540 x10-2 3.4109 x10-1 1.2399 x10-1 5.4068 x10-2 1.4857 x10-1 5.1218 x10-2 DTLZ5 4.2392 x10-3 5.4852 x10-3 3.1219e-2 1.2310 x10-2 4.7674 x10-3 5.8662e-3 3.9716 x10-3 DTLZ6 7.3207 x10-1 7.3214 x10-1 7.3553 x10-1 7.3541 x10-1 7.3207 x10-1 7.3208 x10-1 7.3208 x10-1 DTLZ7 5.8928 x10-2 7.5279 x10-2 1.3621 x10-1 6.9999 x10-2 7.4099 x10-2 1.5743e-1 5.3782 x10-2 表 3 7种算法的HV均值
Table 3. Mean value of HV for seven algorithms
Function HVm SPEA2 NSGA-II MOEAD NSGA-III VaEA CMOPSO MOEA-PT ZDT1 7.2051 x10-1 7.1937 x10-1 7.1706 x10-1 7.2047 x10-1 7.1884 x10-1 7.1969 x10-1 7.2082 x10-1 ZDT2 4.4514 x10-1 4.4420 x10-1 4.3720 x10-1 4.4518 x10-1 4.4479 x10-1 4.4438 x10-1 4.4534 x10-1 ZDT3 5.9968 x10-1 6.0837 x10-1 6.1394 x10-1 5.9891 x10-1 5.9963 x10-1 5.9977 x10-1 5.9987 x10-1 ZDT4 7.1847 x10-1 7.1867 x10-1 7.1000 x10-1 7.1829 x10-1 7.0784 x10-1 6.6665 x10-1 7.1921 x10-1 WFG1 6.6374 x10-1 6.7648 x10-1 6.4713 x10-1 6.4673 x10-1 6.3454 x10-1 4.2887 x10-1 6.5373 x10-1 WFG2 6.3279 x10-1 6.3265 x10-1 6.1852 x10-1 6.3192 x10-1 6.3208 x10-1 6.3271 x10-1 6.3283 x10-1 WFG3 5.8112 x10-1 5.8004 x10-1 5.7736 x10-1 5.8147 x10-1 5.8082 x10-1 5.8028 x10-1 5.8167 x10-1 WFG4 3.4681 x10-1 3.4636 x10-1 3.4010 x10-1 3.4686 x10-1 3.4651 x10-1 3.3085 x10-1 3.4743 x10-1 DTLZ1 8.4170 x10-1 8.2334 x10-1 8.4268 x10-1 8.4312 x10-1 8.1981 x10-1 4.4139 x10-2 8.4271 x10-1 DTLZ2 5.5612 x10-1 5.3519 x10-1 5.6296 x10-1 5.6297 x10-1 5.5864 x10-1 5.4277 x10-1 5.6298 x10-1 DTLZ3 5.5828 x10-1 5.2753 x10-1 5.5581 x10-1 5.5667 x10-1 5.4995 x10-1 0 5.5656 x10-1 DTLZ4 5.0098 x10-1 5.3430 x10-1 4.2857 x10-1 5.2952 x10-1 5.5725 x10-1 4.9077 x10-1 5.6319 x10-1 DTLZ5 1.9971 x10-1 1.9928 x10-1 1.8334 x10-1 1.9444 x10-1 1.9957 x10-1 1.9813 x10-1 2.0027 x10-1 DTLZ6 3.2990 x10-1 3.2915 x10-1 3.1146 x10-1 3.2022 x10-1 3.2954 x10-1 3.2995 x10-1 3.2998 x10-1 DTLZ7 2.7690 x10-1 2.6907 x10-1 2.5927 x10-1 2.7101 x10-1 2.7565 x10-1 2.6059 x10-1 2.8054 x10-1 表 4 局部调整前后的IGD均值
Table 4. IGDm before and after local adjustment
Function IGDm Without LA With LA ZDT1 3.7592 x10-3 3.5750 x10-3 ZDT2 3.7311 x10-3 3.6024 x10-3 ZDT3 4.4525 x10-3 4.3498 x10-3 ZDT4 3.9753 x10-3 3.9663 x10-3 WFG1 1.0235 x10-1 1.1397 x10-1 WFG2 1.0717 x10-2 1.0500 x10-2 WFG3 1.2135 x10-2 1.1312 x10-2 WFG4 1.2437 x10-2 1.1951 x10-2 DTLZ1 1.9702 x10-2 1.9506 x10-2 DTLZ2 5.2933 x10-2 5.1166 x10-2 DTLZ3 5.5054 x10-2 5.2565 x10-2 DTLZ4 5.3013 x10-2 5.1218 x10-2 DTLZ5 4.3730 x10-3 3.9716 x10-3 DTLZ6 7.3208 x10-1 7.3208 x10-1 DTLZ7 5.8760 x10-2 5.3782 x10-2 表 5 局部调整前后的HV均值
Table 5. HVm before and after local adjustment
Function HVm Without LA With LA ZDT1 7.2049 x10-1 7.2082 x10-1 ZDT2 4.4516 x10-1 4.4534 x10-1 ZDT3 5.9977 x10-1 5.9987 x10-1 ZDT4 7.1944 x10-1 7.1945 x10-1 WFG1 6.6014 x10-1 6.5373 x10-1 WFG2 6.3277 x10-1 6.3283 x10-1 WFG3 5.8100 x10-1 5.8167 x10-1 WFG4 3.4704 x10-1 3.4743 x10-1 DTLZ1 8.4222 x10-1 8.4271 x10-1 DTLZ2 5.5707 x10-1 5.6298 x10-1 DTLZ3 5.5819 x10-1 5.5656 x10-1 DTLZ4 5.5740 x10-1 5.6319 x10-1 DTLZ5 1.9978 x10-1 2.0027 x10-1 DTLZ6 3.2993 x10-1 3.2998 x10-1 DTLZ7 2.7713 x10-1 2.8054 x10-1 -
[1] ZHANG Q F, LI H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731. doi: 10.1109/TEVC.2007.892759 [2] 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. doi: 10.1109/TEVC.2013.2281535 [3] 王学武, 魏建斌, 周昕, 等. 一种基于超体积指标的多目标进化算法[J]. 华东理工大学学报(自然科学版), 2020, 46(6): 780-791. [4] WANG H D, JIAO L C, YAO X. Two_Arch2: An improved two-archive algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(4): 524-541. doi: 10.1109/TEVC.2014.2350987 [5] XIANG Y, ZHOU Y R, LI M Q, et al. A vector angle-based evolutionary algorithm for unconstrained many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2017, 21(1): 131-152. doi: 10.1109/TEVC.2016.2587808 [6] CHENG R, JIN Y C, OLHOFER M, et al. A reference vector guided evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 773-791. doi: 10.1109/TEVC.2016.2519378 [7] 刘元, 郑金华, 邹娟, 等. 基于邻域竞赛的多目标优化算法[J]. 自动化学报, 2018, 44(7): 1304-1320. [8] QI Y T, MA X L, LIU F, et al. MOEA/D with adaptive weight adjustment[J]. Evolutionary Computation, 2014, 22(2): 231-264. doi: 10.1162/EVCO_a_00109 [9] JAIN H, DEB K. An evolutionary y-objective optimization algorithm using reference-point based nondominated sorting approach, part II: Handling constraints manand extending to an adaptive approach[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 602-622. doi: 10.1109/TEVC.2013.2281534 [10] 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. doi: 10.1109/TEVC.2015.2420112 [11] LIANG Z P, HU K F, MA X L, et al. A many-objective evolutionary algorithm based on a two-round selection strategy[J]. IEEE Transactions on Cybernetics, 2021, 51(3): 1417-1429. doi: 10.1109/TCYB.2019.2918087 [12] XIANG Y, ZHOU Y R, YANG X W, et al. A many-objective evolutionary algorithm with Pareto-adaptive reference points[J]. IEEE Transactions on Evolutionary Computation, 2020, 24(1): 99-113. doi: 10.1109/TEVC.2019.2909636 [13] ZITZLER E, LAUMANNS M, THIELE L. SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization[C]//Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Athens, Greece: [s. n. ], 2001: 95-100. [14] LIU Y P, GONG D W, SUN J, et al. A many-objective evolutionary algorithm using a one-by-one selection strategy[J]. IEEE Transactions on Cybernetics, 2017, 47(9): 2689-2702. doi: 10.1109/TCYB.2016.2638902 [15] 郑金华, 邹娟. 多目标进化优化[M]. 北京: 科学出版社, 2018: 98-99. [16] TIAN Y, CHENG R, ZHANG X, et al. PlatEMO: A MATLAB platform for evolutionary multi-objective optimization [educational forum][J]. IEEE Computational Intelligence Magazine, 2017, 12(4): 73-87. doi: 10.1109/MCI.2017.2742868 [17] 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. doi: 10.1109/4235.996017 [18] ZHANG X, ZHENG X, CHENG R, et al. A competitive mechanism based multi-objective particle swarm optimizer with fast convergence[J]. Information Sciences, 2018, 427: 63-76. doi: 10.1016/j.ins.2017.10.037 [19] COELLO C A C, CORTÉS N C. Solving multiobjective optimization problems using an artificial immune system[J]. Genetic Programming and Evolvable Machines, 2005, 6(2): 163-190. doi: 10.1007/s10710-005-6164-x [20] ZITZLER E, THIELE L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257-271. doi: 10.1109/4235.797969 [21] 王学武, 夏泽龙, 顾幸生. 基于DMOEA/D-ET算法的焊接机器人多目标路径规划[J]. 华南理工大学学报(自然科学版), 2019, 47(4): 99-106. -