文章详情

摘要

针对传统灰狼优化算法在求解旅行商问题时易早熟收敛、全局探索能力不足的问题，文章提出一种基于双重自适应机制的改进灰狼优化算法（DAMGWO）。首先，算法引入了3种性能互补的邻域搜索算子，并设计了基于搜索进程的自适应选择策略，动态调整各算子的使用概率，使算法在探索与开发阶段能更有效地选择适宜的搜索方式，平衡搜索的广度与深度。其次，为有效避免种群陷入局部最优，设计了自适应混乱扰动策略，当算法陷入局部最优时，触发该变异方式，有针对性地扩大种群多样性，增强算法跳出局部极值的能力。最后，采用TSPLIB的6个实例对所提出的方法进行了仿真实验，并将其与其他已知方法进行了比较，结果表明，所提算法在求解稳定性、精度和收敛速度等方面都具有一定的优势。

关键词

旅行商问题；双重自适应机制；灰狼优化算法；自适应混乱扰动策略

参考文献

1. [1] 敖弘瑞，张纪会，陈晟宗.改进自适应大邻域搜索算法及其在旅行商问题中的应用 [J].计算机应用研究，2025，42（6）：1713-1718.
2. [2] 李一明，李毅，周明天.分支定界算法的分布并行化研究 [J].计算机应用，2006（3）：723-726.
3. [3] 但开，段隆振.基于最优插入子集的动态规划算法求解旅行商问题 [J].计算机应用与软件，2022，39（12）：260-265，297.
4. [4] 徐佳，韩逢庆，刘奇鑫，等.一种求解TSP的生物信息启发式遗传算法 [J].系统仿真学报，2022，34（8）：1811-1819.
5. [5] 陈晟宗，张纪会，于守水，等.求解旅行商问题的波动温控模拟退火算法 [J].控制与决策，2023，38（4）：911-920.
6. [6] 丁增良，陈珏，邱禧荷.一种应用于旅行商问题的莱维飞行转移规则蚁群优化算法 [J].计算机应用研究，2024，41（5）：1420-1427.
7. [7] Karuna P，Deep K. Transformation Operators Based Grey Wolf Optimizer for Travelling Salesman Problem [J/OL].Journal of Computational Science，2021，55：101454. https://doi.org/10.1016/j.jocs.2021.101454.
8. [8] Saji Y，Mohammed B. A Discrete Bat Algorithm Based on Lévy Flights for Euclidean Traveling Salesman Problem [J/OL].Expert Systems With Applications，2021，172：114639.https://www.sciencedirect.com/science/article/abs/pii/S0957417421000804.
9. [9] 张子成，韩伟，毛波.基于模拟退火的自适应离散型布谷鸟算法求解旅行商问题 [J].电子学报，2018，46（8）：1849-1857.
10. [10] Akhand M，Ayon S I，Shahriyar S，et al. Discrete Spider Monkey Optimization for Travelling Salesman Problem [J/OL].Applied Soft Computing Journal，2020，86：105887.https://doi.org/10.1016/j.asoc.2019.105887.
11. [11] Zhang N，Lyu Z M，Qiao S，et al. An Improved Unordered Pair Bat Algorithm for Solving the Symmetrical Traveling Salesman Problem [J].Foundations of Computing and Decision Sciences，2022，47（1）：87-103.
12. [12] Karuna P，Deep K. Discrete Grey Wolf Optimizer for Symmetric Travelling Salesman Problem [J/OL].Applied Soft Computing Journal，2021，105：107298.https://doi.org/10.1016/j.asoc.2021.107298.
13. [13] Mostafa M，Ömer K B，Halife K. A New Hybrid Method based on Particle Swarm Optimization, Ant Colony Optimization and 3-Opt Algorithms for Traveling Salesman Problem [J].Applied Soft Computing Journal，2015，30：484-490.
14. [14] Deng W，Chen R，He B，et al. A Novel Two-stage Hybrid Swarm Intelligence Optimization Algorithm and Application [J].Soft computing: A Fusion of Foundations, Methodologies and Applications，2012，16（10）：1707-1722.
15. [15] Liu G J G，Xu X P，Wang F，et al. Solving Traveling Salesman Problems Based on Artificial Cooperative Search Algorithm [J/OL].Computational Intelligence and Neuroscience，2022，2022：1008617.https://onlinelibrary.wiley.com/doi/10.1155/2022/1008617.
16. [16] Mesut G，Mustafa S K，Eren Ö. A Hierarchic Approach Based on Swarm Intelligence to Solve the Traveling Salesman Problem [J].Turkish Journal of Electrical Engineering & Computer Sciences，2015，23（1）：103-117.
17. [17] Ahmet C C，Sedat K，Mustafa S K. A Discrete tree-seed Algorithm for Solving Symmetric Traveling Salesman Problem [J].Engineering Science and Technology，an International Journal，2020，23（4）：879-890.

基金项目

泰山科技学院2024年度校级一流本科专业“大数据管理与应用”项目（2024120108T）

作者简介

沈孝凯（1997—），男，汉族，山东临沂人，助教，硕士研究生，研究方向：智能优化算法、路径优化；秦琴（1998—），女，汉族，山东日照人，助教，硕士研究生，研究方向：机器学习、推荐算法；孙凤霄（1997—），男，汉族，山东泰安人，讲师，硕士研究生，研究方向：深度学习、自然语言处理；张巍（2000—），男，汉族，江苏盐城人，工程师，硕士研究生，研究方向：调度问题、边缘计算。