随机游走和特殊拥挤距离更新的多模态多目标狼群算法

doi:10.3778/j.issn.1002-8331.2408-0091

摘要/Abstract

摘要： 针对多模态多目标优化中种群多样性较差和搜索能力不足的问题，提出随机游走和特殊拥挤距离更新的多模态多目标狼群算法（MMOWPA-RSCD）。在游走行为中融入莱维飞行，提出随机游走策略，生成多个随机突变的游走位置，使种群快速跳出局部最优，增强算法的全局搜索能力；设计基于特殊拥挤距离的种群更新机制，利用k-means算法将待更新种群划分为多个子种群以降低整体搜索难度，通过计算各个子种群个体的特殊拥挤距离，保留决策空间和目标空间综合拥挤度较好的解，维持种群的多样性；引入环境选择策略，通过特殊拥挤距离非支配排序筛选优良种群，进一步提升算法的多样性。将MMOWPA-RSCD算法和8种经典以及新近多模态多目标优化算法在13个多模态多目标测试函数进行实验对比及秩均值检验，实验结果表明：MMOWPA-RSCD的总体性能优于对比算法。将算法用于栅格地图路径规划问题，进一步验证了算法的有效性。

关键词: 多模态多目标优化, 多目标狼群算法, 随机游走, 特殊拥挤距离更新, 环境选择, 栅格地图路径规划

Abstract: To address the issues of low population diversity and inadequate search capability in multi-modal multi-objective optimization, multi-modal multi-objective wolf pack algorithm with random wandering and special crowding distance (MMOWPA-RSCD) is proposed. By integrating Lévy’s flights into the wandering behavior, a random walk strategy is introduced to generate multiple randomly mutated positions, allowing the population to rapidly escape local optima and enhancing the global search capability of the algorithm. Population update mechanism based on special crowding distance is designed, the k-means algorithm is used to partition the population into several subpopulations to reduce overall search difficulty. By calculating the special crowding distance of individuals within each subpopulation, solutions with better comprehensive crowding degrees in both decision and objective spaces are retained, maintaining population diversity. Finally, an environmental selection strategy is introduced, using special crowding distance non-dominated sorting to select superior populations, further enhancing the diversity of the algorithm. The MMOWPA-RSCD algorithm is experimentally compared with eight recent multi-modal multi-objective optimization algorithms across 13 multi-modal multi-objective test functions, including rank mean value testing. Experimental results indicate that the overall performance of MMOWPA-RSCD surpasses that of the comparison algorithms. Lastly, the algorithm is applied to a grid map path planning problem to further validate its effectiveness.

Key words: multi-modal multi-objective optimization, multi-objective wolf pack algorithm, random wandering, special crowding distance update, environmental selection, grid map path planning

赵嘉, 钟劲文, 肖人彬, 王晖, 潘正祥. 随机游走和特殊拥挤距离更新的多模态多目标狼群算法[J]. 计算机工程与应用, 2025, 61(12): 93-106.

ZHAO Jia, ZHONG Jinwen, XIAO Renbin, WANG Hui, PAN Jeng-shyang. Multi-Modal Multi-Objective Wolf Pack Algorithm with Random Wandering and Special Crowding Distance[J]. Computer Engineering and Applications, 2025, 61(12): 93-106.

参考文献

[1] 赵嘉, 赖智臻, 吴润秀, 等. 层级引导的增强型多目标萤火虫算法[J]. 系统仿真学报, 2024, 36(5): 1152-1164.
ZHAO J, LAI Z Z, WU R X, et al. Hierarchical guided enhanced multi-objective firefly algorithm[J]. Journal of System Simulation, 2024, 36(5): 1152-1164.
[2] DEB K, TIWARI S. Omni-optimizer: a procedure for single and multi-objective optimization[C]//Proceedings of the International Confereren on Evolutionary Multi-Criterion Optimization. Berlin, Heidelberg: Springer, 2005: 47-61.
[3] PéREZ E, POSADA M, HERRERA F. Analysis of new niching genetic algorithms for finding multiple solutions in the job shop scheduling[J]. Journal of Intelligent Manufacturing, 2012, 23(3): 341-356.
[4] MIAO Z H, HUANG W T, JIANG Q C, et al. A novel multimodal multi-objective optimization algorithm for multi-robot task allocation[J]. Transactions of the Institute of Measurement and Control, 2023: 01423312231183588.
[5] ZHANG W Z, LI G Q, ZHANG W 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.
[6] TIAN Y, LIU R C, ZHANG X Y, et al. A multipopulation evolutionary algorithm for solving large?scale multimodal multiobjective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(3): 405-418.
[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] QU B Y, SUGANTHAN P N, DAS S. A distance-based locally informed particle swarm model for multimodal optimization[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(3): 387-402.
[9] LIANG J J, YUE C T, QU B Y. Multimodal multi-objective optimization: a preliminary study[C]//Proceedings of the 2016 IEEE Congress on Evolutionary Computation. Piscataway: IEEE, 2016: 2454-2461.
[10] YUE C T, QU B Y, LIANG 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.
[11] 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.
[12] LIANG J, XU W W, YUE C T, et al. Multimodal multiobjective optimization with differential evolution[J]. Swarm and Evolutionary Computation, 2019, 44: 1028-1059.
[13] WU H S, ZHANG F M. Wolf pack algorithm for unconstrained global optimization[J]. Mathematical Problems in Engineering, 2014, 2014(1): 465082.
[14] XIAO R B. Four development stages of collective intelligence[J]. Frontiers of Information Technology & Electronic Engineering, 2024, 25(7): 903-916.
[15] XIU-WU Y U, HAO Y U, LIU Y, et al. A clustering routing algorithm based on wolf pack algorithm for heterogeneous wireless sensor networks[J]. Computer Networks, 2020, 167: 106994.
[16] ZHANG L Y, ZHANG L, LIU S, et al. Three-dimensional underwater path planning based on modified wolf pack algorithm[J]. IEEE Access, 2017, 5: 22783-22795.
[17] 李昌响, 赵嘉, 韩龙哲, 等. 多通道CNN-BiLSTM的短时温度预测[J]. 江西师范大学学报 (自然科学版), 2023, 47(3): 325-330.
LI C X, ZHAO J, HAN L Z, et al. The short-time temperature prediction for multi-channel CNN-BiLSTM[J]. Journal of Jiangxi Normal University (Natural Science Edition), 2023, 47(3): 325-330.
[18] 颜学龙, 丁鹏, 马峻. 基于狼群算法的RBF神经网络模拟电路故障诊断[J]. 计算机工程与应用, 2017, 53(19): 152-156.
YAN X L, DING P, MA J. Analog circuit diagnosis based on wolf pack algorithm radical basis function network[J]. Computer Engineering and Applications, 2017, 53(19): 152-156.
[19] 谢锐强, 张惠珍. 求解柔性作业车间调度问题的两段式狼群算法[J]. 计算机工程与应用, 2021, 57(7): 251-256.
XIE R Q, ZHANG H Z. Two-vector wolf pack algorithm for flexible job shop scheduling problem[J]. Computer Engineering and Applications, 2021, 57(7): 251-256.
[20] 荀洪凯, 陶翼飞, 张源, 等. 多目标启发式狼群算法求解不相关并行机分批调度问题[J]. 信息与控制, 2023, 52(1): 93-103.
XUN H K, TAO Y F, ZHANG Y, et al. Multi-objective heuristic wolf pack algorithm for unrelated parallel machine batch scheduling problem[J]. Information and Control, 2023, 52(1): 93-103.
[21] 陶翼飞, 丁小鹏, 罗俊斌, 等. 基于多目标狼群算法的机场行李导入系统仿真优化研究[J]. 系统仿真学报, 2024, 36(7): 1655-1669.
TAO Y F, DING X P, LUO J B, et al. Simulation optimization of airport baggage import system based on multi-objective wolf pack algorithm[J]. Journal of System Simulation, 2024, 36(7): 1655-1669.
[22] 赵嘉,吕丰,肖人彬, 等.自适应分组和拥挤距离更新的多目标狼群算法[J].控制与决策, 2024,39(11):3772-3780.
ZHAO J, LV F, XIAO R B, et al. Multi-objective wolf pack algorithm based on adaptive grouping strategy and crowding distance [J]. Control and Decision, 2024,39(11):3772-3780.
[23] 丁瑞成, 周玉成. 引入莱维飞行与动态权重的改进灰狼算法[J]. 计算机工程与应用, 2022, 58(23): 74-82.
DING R C, ZHOU Y C. Improved grey wolf optimization algorithm based on levy flight and dynamic weight strategy[J]. Computer Engineering and Applications, 2022, 58(23): 74-82.
[24] 潘成胜, 张斌, 吕亚娜, 等. 改进灰狼优化算法的K-Means文本聚类[J]. 计算机工程与应用, 2021, 57(1): 188-193.
PAN C S, ZHANG B, LYU Y N, et al. K-means text clustering based on improved gray wolf optimization algorithm[J]. Computer Engineering and Applications, 2021, 57(1): 188-193.
[25] ZITZLER E, LAUMANNS M, THIELE L. SPEA2: improving the strength Pareto evolutionary algorithm[R]. TIK Report 103, 2001.
[26] RUDOLPH G, NAUJOKS B, PREUSS M. Capabilities of EMOA to detect and preserve equivalent Pareto subsets[C]//Proceedings of the International Conference on Evolutionary Multi-Criterion Optimization. Berlin, Heidelberg: Springer, 2007: 36-50.
[27] 岳彩通, 梁静, 瞿博阳, 等. 多模态多目标优化综述[J]. 控制与决策, 2021, 36(11): 2577-2588.
YUE C T, LIANG J, QU B Y, et al. A survey on multimodal multiobjective optimization[J]. Control and Decision, 2021, 36(11): 2577-2588.
[28] 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.
[29] LI W H, ZHANG T, WANG R, et al. Weighted indicator-based evolutionary algorithm for multimodal multiobjective optimization[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(6): 1064-1078.
[30] LI W H, YAO X Y, ZHANG T, et al. Hierarchy ranking method for multimodal multiobjective optimization with local Pareto fronts[J]. IEEE Transactions on Evolutionary Computation, 2023, 27(1): 98-110.
[31] MING F, GONG W Y, WANG L, et al. Balancing convergence and diversity in objective and decision spaces for multimodal multi-objective optimization[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2023, 7(2): 474-486.
[32] LI W H, YAO X Y, LI K W, et al. Coevolutionary framework for generalized multimodal multi-objective optimization[J]. IEEE/CAA Journal of Automatica Sinica, 2023, 10(7): 1544-1556.
[33] MING F, GONG W Y, JIN Y C. Growing neural gas network-based surrogate-assisted Pareto set learning for multimodal multi-objective optimization[J]. Swarm and Evolutionary Computation, 2024, 87: 101541.
[34] 吕莉, 陈威, 肖人彬, 等. 面向密度分布不均数据的加权逆近邻密度峰值聚类算法[J]. 智能系统学报, 2024, 19(1): 165-175.
LYU L, CHEN W, XIAO R B, et al. Density peak clustering algorithm based on weighted reverse nearest neighbor for uneven density datasets[J]. CAAI Transactions on Intelligent Systems, 2024, 19(1): 165-175.
[35] 赵嘉, 谢智峰, 吕莉, 等. 深度学习萤火虫算法[J]. 电子学报, 2018, 46(11): 2633-2641.
ZHAO J, XIE Z F, Lü L, et al. Firefly algorithm with deep learning[J]. Acta Electronica Sinica, 2018, 46(11): 2633-2641.