一种基于多样性指标排序的多模态多目标算法

摘要/Abstract

摘要： 多模态多目标优化问题中决策空间与目标空间的多样性都会对算法的性能产生重要的影响,为更好地平衡两个空间的多样性,提出一种基于多样性指标排序的多模态多目标优化算法 (D-DNEAL).D-DNEAL首先将K-近邻密度估计方法构造为一个多样性指标,并将其引入快速非支配排序中对个体进行排序,保证收敛性差但分布性好的个体仍有机会被选中进入下一代,从而提高了种群的搜索能力.然后通过多前沿存档机制保存多样性更好的个体,使得算法能够定位更多的局部最优解.为验证D-DNEAL在多模态多目标优化问题上的性能,将其与6种最新的多模态多目标优化算法在28个多模态多目标优化测试函数上进行对比,实验结果证明了D-DNEAL在求解多模态多目标问题上是有效的.

关键词: 多模态多目标优化, 多样性指标, 多前沿存档, 双小生境适应度共享函数, 非支配排序

Abstract: In multi-modal multi-objective optimization, the diversity in both the decision space and the objective space plays a critical role in the impact on the performance of the algorithm. To better balance the diversity between the two, proposes a multi-modal multi-objective optimization algorithm based on diversity index ranking (D-DNEAL) is proposed in this paper. First, D-DNEAL constructs a diversity indicator using the K-nearest neighbor density estimation method, which is then integrated into the fast non-dominated sorting process to rank individuals. This ensures that individuals with poor convergence but good distribution still have a chance to be selected for the next generation, thereby improving the search ability of the population. Additionally, multi-frontier archiving mechanism is introduced to preserve the individuals with better diversity, so that the algorithm can obtain more local optimal solutions. To verify the performance of D-DNEAL on multi-modal multi-objective optimization problems, six state-of-the-art algorithms are used to make a comparison on 28 multi-modal multi-objective optimization test problems. The results show that the D-DNEAL is effective in solving multi-modal multi-objective problems.

Key words: multi-modal multi-objective optimization, diversity indicator, multiple frontier archives, double niche fitness sharing function, non-dominant sort

中图分类号:

TP18

曹洁, 齐志, 陈作汉, 张建林. 一种基于多样性指标排序的多模态多目标算法[J]. 兰州理工大学学报, 2025, 51(5): 81-91.

CAO Jie, QI Zhi, CHEN Zuo-han, ZHANG Jian-lin. A multi-modal multi-objective algorithm based on diversity indicator ranking[J]. Journal of Lanzhou University of Technology, 2025, 51(5): 81-91.

参考文献

[1] 岳彩通,梁静,瞿博阳,等.多模态多目标优化综述 [J].控制与决策,2021,36(11):2577-2588.
[2] LI Z,ZOU J,YANG S,et al.A two-archive algorithm with decomposition and fitness allocation for multi-modal multi-objective optimization [J].Information Sciences,2021,574:413-430.
[3] 蔡雨岑,杜鹏桢.基于平衡鲸鱼优化算法的无人车路径规划 [J].控制与决策,2021,36(11):2647-2655.
[4] KAMYAB S,EFTEKHARI M.Feature selection using multimodal optimization techniques [J].Neurocomputing,2016,171:586-597.
[5] WANG W,LI G,WANG Y,et al.Clearing-based multimodal multi-objective evolutionary optimization with layer-to-layer strategy [J].Swarm and Evolutionary Computation,2022,68:100976.
[6] ZHANG W,LI G,ZHANG W,et al.A cluster based PSO with leader updating mechanism and ring-topology for multimodal multi-objective optimization [J].Swarm and Evolutionary Computation,2019,50:100569.
[7] LIANG J,QIAO K J,YUE C T,et al.A clustering-based differential evolution algorithm for solving multimodal multi-objective optimization problems [J].Swarm and Evolutionary Computation,2021,60:100788.
[8] LIU Y P,ISHIBUCHI H,NOJIMA Y,et al.A double-niched evolutionary algorithm and its behavior on polygon-based problems [C]//15th International Conference on Parallel Problem Solving from Nature (PPSN).Coimbra,Portugal:[s.n.],2018:262-273.
[9] LIU Y P,ISHIBUCHI H,NOJIMA Y,et al.Searching for local pareto optimal solutions:a case study on polygon-based problems[C]//IEEE Congress on Evolutionary Computation (IEEE CEC).Wellington:IEEE,2019:896-903.
[10] LIANG J J,YUE C T,QU B Y.Multimodal multi-objective optimization:a preliminary study [C]//IEEE Congress on Evolutionary Computation.Piscataway:IEEE,2016:2454-2461.
[11] YUE C T,QU B Y,LIANG J 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.
[12] LIU Y P,YEN G G,GONG D W.A multimodal multiobjective evolutionary algorithm using two-archive and recombination strategies [J].IEEE Transactions on Evolutionary Computation,2019,23(4):660-674.
[13] YUE C T,SUGANTHAN P N,LIANG J J,et al.Differential evolution using improved crowding distance for multimodal multiobjective optimization [J].Swarm and Evolutionary Computation,2021,62:100849.
[14] ISHIBUCHI H,AKEDO N,NOJIMA Y.A many-objective test problem for visually examining diversity maintenance behavior in a decision space [C]//13th Annual Genetic and Evolutionary Computation Conference (GECCO).Dublin:[s.n.],2011:649-656.
[15] 公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究 [J].软件学报,2009,20(2):271-289.
[16] LIU Y P,ISHIBUCHI H,YEN G G,et al.Handling imbalance between convergence and diversity in the decision space in evolutionary multimodal multiobjectiveoptimization [J].IEEE Transactions on Evolutionary Computation,2020,24(3):551-565.
[17] 刘若辰,焦李成,雷七峰,等.一种新的差分进化约束优化算法 [J].西安电子科技大学学报,2011,38(1):47-53.
[18] 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.
[19] DEB K,SINDHYA K,OKABE T.Self-adaptive simulated binary crossover for real-parameter optimization [C]//Proceedings of the 9th Annual Conference onGenetic and Evolutionary Computation.London:[s.n.],2007:1187-1194.
[20] DEB K,GOYAL M.A combined genetic adaptive search (GeneAS) for engineering design [J].Journal of Computer Science and Informatics,1996,26:30-45.
[21] LIANG J J,QU B Y,GONG D W,et al.Problem definitions and evaluation criteria for the CEC 2019 special session on multimodal multiobjective optimization[R].Zhengzhou:Computational Intelligence Laboratory,Zhengzhou University,2019.
[22] ZHOU A,ZHANG Q,JIN Y.Approximating the set of pareto-optimal solutions in both the decision and objective spaces by an estimation of distribution algorithm [J].IEEE Transactions on Evolutionary Computation,2009,13(5):1167-1189.
[23] 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.