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

高 宏(辽宁科技大学计算机科学与技术学院,中国)
李 迎春(辽宁科技大学计算机科学与技术学院,中国)

DOI: http://dx.doi.org/10.12349/tie.v3i3.10036

Article ID: 10036

摘要


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

关键词


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

参考


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

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.

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

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

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.

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.

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

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

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.


Refbacks

  • 当前没有refback。


版权所有(c)2026 高 宏, 李 迎春

Creative Commons License
此作品已接受知识共享署名-非商业性使用 4.0国际许可协议的许可。