基于记忆引导重启的蚁群算法求解TSP问题

A Memory-Guided Ant Colony Algorithm for TSP Problem

摘要

针对蚁群算法（ACO）容易陷入局部最优的问题，本文提出一种记忆引导的自适应重启蚁群算法求解旅行商问题（TSP）。该算法通过存储优秀解并采用智能重启策略来跳出局部最优。实验结果表明，所提算法显著提高了求解质量和最优解命中率，加快了ACO算法的前期收敛速度，具有广阔的应用潜力。

Abstract

To address the problem of ant colony optimization (ACO) easily falling into local optima, this paper proposes a memory-guided adaptive restart ant colony algorithm to solve the traveling salesman problem (TSP). The algorithm stores excellent solutions and employs an intelligent restart strategy to escape local optima. Experimental results show that the proposed algorithm significantly improves solution quality and the hit rate of optimal solutions, accelerates the early convergence speed of the ACO algorithm, and has broad application potential.

关键词

记忆引导自适应重启 / 蚁群算法 / 旅行商问题

Key words

Memory-Guided Adaptive Restart / Ant Colony Optimization / Traveling Salesman Problem

参考文献

[1] Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2006). The traveling salesman problem: a computational study. Princeton university press.

[2] Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1), 29-41.

[3] Dorigo, M., & Stützle, T. (2004). Ant colony optimization. MIT press.

[4] Stützle, T., & Hoos, H. H. (2000). MAX-MIN ant system. Future generation computer systems, 16(8), 889-914.

[5] Ouyang, X., & D. L. (2013). A novel hybrid algorithm based on ant colony optimization and Nelder-Mead simplex search for traveling salesman problem. Journal of Computational Information Systems, 9(5), 1867-1874.

[6] de O. Campos, P. R. A., & Nascimento, M. Z. (2017). A restart strategy for enhancing the performance of population-based metaheuristics. Applied Soft Computing, 61, 1142-1154.

[7] Lü Z., & Hao, J. K. (2010). Adaptive tabu search for the traveling salesman problem. Computers & Operations Research, 37(7), 1225-1232.

[8] Dorigo, M. (1992). Optimization, Learning and Natural Algorithms (Ph.D. thesis). Politecnico di Milano, Italy.

[9] Rios, L. H., & Sahinidis, N. V. (2013). Derivative-free optimization: a review of algorithms and comparison of software implementations. Journal of Global Optimization, 56(3), 1247-1293.

基金资助

2025年辽宁科技大学校级大学生创新创业训练计划项目