摘要 为了使多目标进化算法在收敛性和分布性之间保持平衡,该文提出一种基于角度惩罚距离的高维多目标进化算法(Many-Objective Evolutionary Algorithm based on Angle Penalized Distance, MaOEA-APD)。首先,综合考虑收敛性和分布性在进化不同阶段的重要性,构造一种角度惩罚距离,使两者随进化进程动态平衡;其次,开发基于删除劣质个体的环境选择策略,在提高种群分布性的同时提高收敛性;最后,根据环境选择的原理,设计与之相协调且互补的匹配选择过程,提高算法的整体进化效率。将所提算法与目前国内外性能优异的3种高维多目标进化算法进行对比,实验结果表明在WFG标准测试函数集上,该文算法相对于其他算法,综合性能有了较大的提升。
Abstract:In order to balance between convergence and distribution in Multi-Objective Evolutionary Algorithms (MOEAs), a Many-Objective Evolutionary Algorithm based on Angle Penalized Distance (MaOEA-APD) is proposed. Firstly, considering the importance of convergence and diversity in the different stages of the evolutionary process, an angle penalized distance is constructed to dynamically balance between them. Then, the environmental selection based on removing the worse individual is designed to maintain the distribution and improve the convergence. Finally, the mating selection is designed based on the principle of the environmental selection. Both are complement and coordinated to each other for improving the evolutionary efficiency of the algorithm. Compared with three state-of-the-art many-objective evolutionary algorithms (MaOEAs), the experimental results on WFG test suite show that MaOEA-APD has more advantage than other algorithms in terms of the overall performance.
毕晓君, 王朝. 一种基于角度惩罚距离的高维多目标进化算法[J]. 电子与信息学报, 2018, 40(2): 314-322.
BI Xiaojun, WANG Chao. A Many-objective Evolutionary Algorithm Based on Angle Penalized Distance. JEIT, 2018, 40(2): 314-322.
GONG Dunwei, JI Xinfang, and SUN Xiaoyan. Solving many-objective optimization problems using set-based evolutionary algorithms[J]. Acta Electronica Sinica, 2014, 42(1): 77-83. doi: 10.3969/j.issn.0372-2112.2014.01.012.
CHEN Xiaohong, LI Xia, and WANG Na. Objective reduction with sparse feature selection for many objective optimization problem[J]. Acta Electronica Sinica, 2015, 43(7): 1300-1307. doi: 10.3969/j.issn.0372-2112.2015.07.008.
[3]
HUGHES E J. Radar waveform optimisation as a many- objective application benchmark[C]. International Conference on Evolutionary Multi-Criterion Optimization, Springer-Verlag, 2007: 700-714. doi: 10.1007/978-3-540- 70928-2_53.
[4]
REED P M and KOLLAT J B. Save now, pay later? Multi- period many-objective groundwater monitoring design given systematic model errors and uncertainty[J]. Advances in Water Resources, 2012, 35: 55-68. doi: 10.1016/j.advwatres. 2011.10.011.
[5]
LYGOE R J, CARY M, and FLEMING P J. A Real-World Application Of A Many-Objective Optimisation Complexity Reduction Process[M]. Evolutionary Multi-Criterion Optimization, Springer Berlin Heidelberg, 2013: 641-655.
KONG Weijian, DING Jinliang, and CHAI Tianyou. Survey on large-dimensional multi-objective evolutionary algorithms [J]. Control & Decision, 2010, 25(3): 321-326. doi: 10.13195 /j.cd.2010.03.4.kongwj.008.
[7]
LI Ke, DEB K, ZHANG Q, et al. An evolutionary many- objective optimization algorithm based on dominance and decomposition[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(5): 694-716. doi: 10.1109/TEVC.2014. 2373386.
[8]
CHENG Jixiang, YEN G G, and ZHANG G. A many- objective evolutionary algorithm with enhanced mating and environmental selections[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(4): 592-605. doi: 10.1109 /TEVC.2015.2424921.
[9]
ZHANG Xingyi, TIAN Ye, and JIN Yaochu. A knee point-driven evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(6): 761-776. doi: 10.1109/TEVC. 2014.2378512.
CHEN Zhenxing, YAN Xuanhui, WU Kunan, et al. Many- objective optimization integrating open angle based congestion control strategy[J]. Acta Automatica Sinica, 2015, 41(6): 1145-1158. doi: 10.16383/j.aas.2015.c140555.
[11]
CHENG Ran, JIN Yaochu, 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.
[12]
HE Zhenan and YEN G G. Many-objective evolutionary algorithms based on coordinated selection strategy[J]. IEEE Transactions on Evolutionary Computation, 2017, 21(2): 220-233. doi: 10.1109/TEVC.2016.2598687.
[13]
XIANG Yi, ZHOU Yuren, LI Miqing, 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.
[14]
LI Miqing, YANG Shengxiang, and LIU Xiaohui. Bi-goal evolution for many-objective optimization problems[J]. Artificial Intelligence, 2015, 228: 45-65.
ZHENG Jinhua, SHEN Ruimin, LI Miqing, et al. Evolutionary algorithm based on information separation for many-objective optimization[J]. Journal of Software, 2015, 26(5): 1013-1036. doi: 10.13328/j.cnki.jos.004676.
[16]
DEB K and 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.
[17]
HUBAND S, HINGSTON P, BARONE L, et al. A review of multiobjective test problems and a scalable test problem toolkit[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(5): 477-506. doi: 10.1109/TEVC.2005.861417.
[18]
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. doi: 10.1109/TEVC.2003.810758.