Article Details

Abstract

In response to the problems of premature convergence and insufficient global exploration ability of traditional grey wolf optimization algorithm in solving the traveling salesman problem, this paper proposes an improved grey wolf optimization algorithm based on dual adaptive mechanism (DAMGWO). Firstly, the algorithm introduces three complementary neighborhood search operators and designs an adaptive selection strategy based on the search process, dynamically adjusting the usage probability of each operator to enable the algorithm to intelligently adopt the most effective search method during the exploration and exploitation stages, balancing the breadth and depth of the search. Secondly, in order to effectively avoid the population falling into local optima, an adaptive chaotic perturbation strategy was designed. When the algorithm falls into local optima, this mutation mode is triggered to expand the diversity of the population in a targeted manner and enhance the algorithm's ability to escape from local optima. Finally, simulation experiments were conducted on the proposed method using six instances of TSPLIB, and compared with other known methods. The results showed that the proposed algorithm has certain advantages in solving stability, accuracy, and convergence speed.

Keywords

traveling salesman problem; dual adaptive mechanism; grey wolf optimization algorithm; adaptive chaotic perturbation strategy

References

1. [1] Ao Hongrui, Zhang Jihui, Chen Shengzong Improved Adaptive Large Neighborhood Search Algorithm and Its Application in Traveling Salesman Problem [J]. Computer Application Research, 2025, 42 (6): 1713-1718
2. [2] Li Yiming, Li Yi, Zhou Tomorrow Research on Distributed Parallelization of Branch and Bound Algorithm [J]. Computer Applications, 2006 (3): 723-726
3. [3] But open, Duan Longzhen Dynamic Programming Algorithm for Traveling Salesman Problem Based on Optimal Insertion Subset [J]. Computer Applications and Software, 2022, 39 (12): 260-265297
4. [4] Xu Jia, Han Fengqing, Liu Qixin, etc A bioinformatics heuristic genetic algorithm for solving TSP [J]. Journal of System Simulation, 2022, 34 (8): 1811-1819
5. [5] Chen Shengzong, Zhang Jihui, Yu Shoushui, etc Simulated Annealing Algorithm for Wave Temperature Control in Solving Traveling Salesman Problems [J]. Control and Decision, 2023, 38 (4): 911-920
6. [6] Ding Zengliang, Chen Jue, Qiu Xihe A Levy Flight Transfer Rule Ant Colony Optimization Algorithm Applied to the Traveling Salesman Problem [J]. Computer Application Research, 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] Zhang Zicheng, Han Wei, Mao Bo Adaptive discrete cuckoo algorithm based on simulated annealing for solving traveling salesman problem [J]. Acta Sinica, 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.

Funding

"Big Data Management and Application" Project of Mount Taishan University of Science and Technology in 2024 (2024120108T)

About the authors

Shen Xiaokai (1997-), male, Han nationality, from Linyi, Shandong, teaching assistant, master's student, research direction: intelligent optimization algorithm, path optimization; Qin Qin (1998-), female, Han nationality, from Rizhao, Shandong, teaching assistant, master's student, research direction: machine learning, recommendation algorithm; Sun Fengxiao (1997-), male, Han nationality, from Tai'an, Shandong, lecturer, master's student, research direction: deep learning, natural language processing; Zhang Wei (2000-), male, Han nationality, born in Yancheng, Jiangsu Province, engineer, master's degree candidate, research interests: scheduling problems, edge computing.