Multi-objective evolutionary algorithm using decomposition method and polynomial mutation operator
-
摘要:
MOEA/D-M2M算法将一个多目标优化问题同时转换为若干个多目标优化子问题，分别求得这些子问题的Pareto解，最终得到原多目标优化问题的Pareto解，保证了种群的多样性，比MOEA/D具有更好的算法性能.多项式变异算子具有强化局部搜索和加强收敛的作用，但是在多目标进化算法中应用多项式变异算子的成果不多.将多项式变异算子和MOEA/D-M2M中提出的多目标优化问题的新的分解方法相结合，提出了一种新的采用多项式变异策略和分解方法的多目标进化算法(MOEA/PmD).考虑到非均匀变异算子通过动态调整步长获得自适应性的特点，尝试通过将非均匀变异算子替换MOEA/PmD中的多项式变异算子而构造采用非均匀变异算子和分解方法的多目标进化算法(MOEA/NumD).实验表明MOEA/PmD算法比MOEA/NumD算法和MOEA/D-M2M算法具有更好的性能.
Abstract:The algorithm ofMOEA/D-M2Mcan transform multi-objective optimization problem into a number of multi-objective optimization sub-problems and obtains the Pareto solutions of these sub-problems separately, and finally obtains the Pareto solution of the multi-objective optimization problem, which ensures the diversity of population and has better algorithm performance than MOEA/D. Polynomialmutation operator has the function of strengthening local search and convergence, but there is less work on the application of themutation operator in the multi-objective evolutionary algorithm.A new multi-objective evolution algorithm using decomposition methods and polynomial mutation operators (MOEA/PmD) is proposedby combining the polynomial mutation operator and the new decomposition method of multi-objective optimization problem proposed in MOEA/D-M2M. Non-uniform mutation operator obtains the adaptability by dynamically adjusting the step size, an attempt is done to replace the polynomial mutation operator in MOEA/PmD with the non-uniform mutation operator, and multi-objectiveevolutionary algorithm using non-uniform mutation operator and decomposition method (MOEA/NumD) is devised. Experiments show MOEA/PmD algorithmhas better performance than MOEA/NumD and MOEA/D-M2M.
-
表 1 MOEA/PmD、MOEA/NumD和MOEA/D-M2M在ZDT系列测试函数上的逆世代距离IGD
测试函数 算法 最大值 最小值 平均值 标准差 MOEA/ PmD 0.004 9 0.004 9 0.004 90 8.67E-19 ZDT1 MOEA/NumD 0.009 1 0.006 0 0.006 49 8.73E-04 MOEA/D-M2M 0.006 3 0.006 1 0.006 21 5.39E-05 MOEA/ PmD 0.003 8 0.003 8 0.003 80 0.00E+00 ZDT2 MOEA/NumD 0.004 0 0.003 9 0.003 91 3.00E-05 MOEA/D-M2M 0.003 9 0.003 8 0.003 83 4.58E-05 MOEA/ PmD 0.534 0 0.361 5 0.470 57 6.31E-02 ZDT3 MOEA/NumD 0.595 6 0.588 4 0.593 16 2.39E-03 MOEA/D-M2M 0.595 7 0.505 3 0.569 56 3.23E-02 MOEA/ PmD 0.004 9 0.004 9 0.004 9 8.70E-19 ZDT4 MOEA/NumD 0.523 5 0.121 7 0.477 15 1.19E-01 MOEA/D-M2M 0.006 3 0.006 2 0.006 22 4.00E-05 MOEA/ PmD 0.003 3 0.003 2 0.003 23 4.58E-05 ZDT6 MOEA/NumD 0.042 0 0.003 2 0.008 88 1.17E-02 MOEA/D-M2M 0.003 3 0.003 2 0.003 23 4.58E-05 
下载: 导出CSV
表 2 MOEA/PmD、MOEA/NumD和MOEA/D-M2M在ZDT系列测试函数上的超体积HV
测试函数 算法 最大值 最小值 平均值 标准差 MOEA/ PmD 0.661 5 0.661 4 0.661 48 4.00E-05 ZDT1 MOEA/NumD 0.661 5 0.653 1 0.660 20 2.44E-03 MOEA/D-M2M 0.661 5 0.661 4 0.661 47 4.58E-05 MOEA/ PmD 0.328 4 0.328 1 0.328 29 8.31E-05 ZDT2 MOEA/NumD 0.328 4 0.327 8 0.328 25 1.80E-04 MOEA/D-M2M 0.328 4 0.328 3 0.328 39 3.00E-05 MOEA/ PmD 1.627 1.613 2 1.623 02 4.80E -03 ZDT3 MOEA/NumD 1.610 5 1.606 1 1.609 00 1.68E-03 MOEA/D-M2M 1.610 9 1.610 6 1.610 69 1.22E-04 MOEA/ PmD 0.661 6 0.661 4 0.661 5 4.47E-05 ZDT4 MOEA/NumD 0.493 8 0.102 4 0.145 3 1.16E-01 MOEA/D-M2M 0.661 5 0.661 4 0.661 49 3.00E-05 MOEA/ PmD 0.282 2 0.281 5 0.281 95 2.06E-04 ZDT6 MOEA/NumD 0.282 2 0.228 6 0.273 41 1.60E-02 MOEA/D-M2M 0.282 3 0.281 5 0.282 1 2.32E-04
下载: 导出CSV
表 3 MOEA/PmD、MOEA/NumD和MOEA/D-M2M在测试函数DTLZ1-4上的逆世代距离IGD
测试函数 算法 最大值 最小值 平均值 标准差 MOEA/PmD 0.028 0 0.018 6 0.022 41 3.08E-03 DTLZ 1 MOEA/NumD 0.038 0 0.018 5 0.028 08 4.76E-03 MOEA/D-M2M 0.037 2 0.018 3 0.022 69 5.18E-03 MOEA/PmD 0.047 8 0.038 5 0.041 68 2.64E-03 DTLZ 2 MOEA/NumD 0.043 4 0.039 5 0.041 29 1.18E-03 MOEA/D-M2M 0.042 6 0.039 5 0.040 74 9.98E-04 MOEA/PmD 0.058 3 0.042 5 0.049 91 5.44E-03 DTLZ 3 MOEA/NumD 0.112 3 0.045 9 0.076 43 2.13E-02 MOEA/D-M2M 0.164 5 0.040 5 0.067 25 4.05E-02 MOEA/PmD 0.071 8 0.036 3 0.055 25 1.02E-02 DTLZ 4 MOEA/NumD 0.099 1 0.038 2 0.063 85 2.06E-02 MOEA/D-M2M 0.077 2 0.043 4 0.055 61 1.14E-02
下载: 导出CSV
表 4 MOEA/PmD、MOEA/NumD和MOEA/D-M2M在测试函数DTLZ1-4上的超体积HV
测试函数 算法 最大值 最小值 平均值 标准差 MOEA/PmD 0.094 4 0.089 7 0.092 99 1.39E-03 DTLZ 1 MOEA/NumD 0.093 9 0.086 4 0.090 00 1.82E-03 MOEA/D-M2M 0.094 4 0.087 9 0.093 12 1.94E-03 MOEA/PmD 0.432 5 0.427 6 0.429 83 1.30E-03 DTLZ 2 MOEA/NumD 0.431 4 0.423 9 0.429 10 1.99E-03 MOEA/D-M2M 0.432 0 0.427 6 0.429 78 1.25E-03 MOEA/PmD 0.423 0 0.376 4 0.399 18 1.62E-02 DTLZ 3 MOEA/NumD 0.407 4 0.288 9 0.347 18 3.86E-02 MOEA/D-M2M 0.425 1 0.270 0 0.383 59 5.37E-02 MOEA/PmD 0.412 8 0.408 3 0.410 55 1.21E-03 DTLZ 4 MOEA/NumD 0.407 9 0.400 6 0.404 48 2.44E-03 MOEA/D-M2M 0.411 5 0.406 9 0.409 83 1.32E-03
下载: 导出CSV
-
[1] QIAN S Q, YE Y Q, LIU Y M, et al. An improved binary differential evolution algorithm for optimizing PWM control laws of power inverters[J]. Optimization and Engineering, 2018, 19(2): 271-296. DOI: 10.1007/s11081-017-9354-5. [2] MORADI B. Multi-objective mobile robot path planning problem through learnable evolution model[J]. Journal of Experimental & Theoretical Artificial Intelligence, 2019, 31(2): 325-348. DOI: 10.1080/0952813X.2018.1549107. [3] RAHUL K. Robot mission planning using Co-evolutionary optimization[J]. Robotica, 2020, 38(3): 512-530. DOI: 10.1017/S026357471900081X. [4] 樊田田, 许蕾, 陈林.基于多目标优化算法NSGA-Ⅱ推荐相似缺陷报告[J].计算机学报, 2018, 42(10): 2175-2189. DOI: 10.11897/SP.J.1016.2019.02175.FAN T T, XU L, CHEN L. Recommending similar bug reports based on multi-targets optimization algorithm NSGA-Ⅱ[J]. Chinese Journal of Computers, 2018, 42(10): 2175-2189. DOI: 10.11897/SP.J.1016.2019.02175. [5] JANGIR P, TRIVEDⅡ N. Non-dominated sorting moth flame optimizer: a novel multi-objective optimization algorithm for solving engineering design problems[J]. Engineering Technology Open Access Journal, 2018, 2(1): 555579. DOI: 10.19080/ETOAJ.2018.02.555579. [6] LIN L, GEN M. Hybrid evolutionary optimisation with learning for production scheduling: state-of-the-art survey on algorithms and applications[J]. International Journal of Production Research, 2018, 56(1-2): 193-223. DOI: 10.1080/00207543.2018.1437288. [7] HOLLAND J H. Adaptation in natural and artificial systems[M]. Ann Arbor: University of Michigan Press, 1975. [8] TRIPATHY A. Numerical optimization of computer models[J]. Journal of the Operational Research Society, 1982, 33(12): 1166. DOI: 10.1057/jors.1982.238. [9] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J].IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. DOI: 10.1109/4235.996017. [10] ZHANG Q F, LI H.MOEA/D: a multi-objective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731. DOI: 10.1109/TEVC.2007.892759. [11] LIU H L, GU F Q, ZHANG Q F.Decomposition of a multiobjective optimization problem into a number of simple multiobjectivesubproblems[J].IEEE Transactions on Evolutionary Computation, 2014, 18(3): 450-455. DOI: 10.1109/TEVC.2013.2281533. [12] WANG Y P, LIU H Y, WEI F, et al.Cooperative coevolution with formula-based variable grouping for large-scale global optimization[J].Evolutionary Computation, 2018, 26(4): 569-596. DOI: 10.1162/evco_a_00214. [13] LI H C, WANG Z C. An evolutionary algorithm using parameter space searching for interval linear fractional bilevel programming problems[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2016, 30(4): 1659011. DOI: 10.1142/S0218001416590114. [14] WANG H B, WANG J, ZHEN XX, et al. Oriented multi-mutation strategy in a many-objective evolutionary algorithm[J]. Information Sciences, 2019, 478: 391-407. DOI: 10.1016/j.ins.2018.11.042. [15] ZHANG Q, ZOU D X, DUAN N, et al. An adaptive differential evolutionary algorithm incorporating multiple mutation strategies for the economic load dispatch problem[J]. Applied Soft Computing, 2019, 78: 641-669. DOI: 10.1016/j.asoc.2019.03.019. -
下载:
点击查看大图
计量
- 文章访问数: 371
- HTML全文浏览量: 366
- PDF下载量: 31
- 被引次数: 0
