基于动态重组和协同交流策略的蚁群优化算法

doi:10.3778/j.issn.1673-9418.2006038

摘要/Abstract

摘要：

针对传统蚁群算法在解决旅行商问题（TSP）时所存在的收敛速度慢、易陷入局部最优等问题，提出了基于动态重组和协同交流策略的蚁群优化算法（RCACO）。首先，将蚁群划分为贪婪蚁群和探索蚁群，两类蚁群执行不同的路径构建规则和信息素更新策略，以平衡算法的收敛速度和多样性。其次，采用一种基于线索二叉树的新型动态重组算子，并根据不同的重组策略对解集进行有导向性的动态重组，以提升算法的多样性。进一步，提出一种基于相似度和潜力值的协同交流策略，从全局的角度出发，找到最有潜力成为最优解的路径，并对这些路径给予信息素奖励，以提升算法的收敛速度。最后，算法还加入了停滞规避策略，以帮助蚁群跳出局部最优，提升算法的求解精度。通过Matlab对TSPLIB中的多组案例进行仿真实验，与传统蚁群算法和其他优化算法进行对比分析，仿真结果表明，改进的蚁群算法显著提高了收敛速度和求解精度。

关键词: 旅行商问题（TSP）, 蚁群优化算法（ACO）, 动态重组, 协同交流, 停滞规避

Abstract:

Aiming at the problems of traditional ant colony algorithm in solving traveling salesman problem (TSP), such as slow convergence speed and easy to fall into local optimum, an ant colony optimization algorithm (RCACO) based on dynamic recombination and cooperative communication strategy is proposed. Firstly, the ant colony is divided into greedy ant colony and exploratory ant colony. The two ant colonies implement different path construction rules and pheromone update strategies to balance the convergence speed and diversity of the algorithm. Secondly, a new dynamic recombination operator based on the clew binary tree is adopted, and the solution set is dynamically recombined according to different strategies to improve the diversity of the algorithm. Furthermore, a collaborative communication strategy based on similarity and potential value is proposed. From a global perspective, the path with the most potential to become the optimal solution is found, and pheromone rewards are given to these paths to improve the convergence speed of the algorithm. Finally, the algorithm also adds a stagnation avoidance strategy to help the ant colony jump out of the local optimum and improve the accuracy of the algorithm. Through the Matlab simulation experiment of multiple groups of cases in TSPLIB, compared with the traditional ant colony algorithm and other optimization algorithms, the simulation results show that the improved ant colony algorithm significantly improves the convergence speed and solution accuracy.

Key words: traveling salesman problem (TSP), ant colony optimization (ACO), dynamic recombination, collaborative communication, stagnation avoidance

刘一凡, 游晓明, 刘升. 基于动态重组和协同交流策略的蚁群优化算法[J]. 计算机科学与探索, 2021, 15(8): 1511-1525.

LIU Yifan, YOU Xiaoming, LIU Sheng. Ant Colony Optimization Algorithm Based on Dynamic Recombination and Co- operative Communication Strategy[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(8): 1511-1525.

参考文献

[1] YUN X Y. Research on traveling salesman problem algorithm[J]. Advanced Materials Research, 2013, 694-697: 2901-2904.
[2] GUPTA A, KHURANA S. Study of traveling salesman pro-blem using genetic algorithm[J]. International Journal of Managment, IT and Engineering, 2012, 2(5): 575-588.
[3] SHIRDEL G H, ABDOLHOSSEINZADEH M. A simulated annealing heuristic for the online symmetric traveling sales-man problem[J]. Journal of Information and Optimization Sciences, 2018, 39(6): 1283-1296.
[4] WANG Y, XU N. A hybrid particle swarm optimization me-thod for traveling salesman problem[J]. International Journal of Applied Metaheuristic Computing, 2017, 8(3): 53-65.
[5] MAVROVOUNIOTIS M, MULLER F M, YANG S X. Ant colony optimization with local search for dynamic traveling salesman problems[J]. IEEE Transactions on Cybernetics, 2016, 47(7): 1743-1756.
[6] DORIGO M, MANIEZZO V, COLORNI A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996, 26(1): 29-41.
[7] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computa-tion, 1997, 1(1): 53-66.
[8] STUTZLE T, HOOS H H. MAX-MIN ant system[J]. Future Generation Computer Systems, 2000, 16(8): 889-914.
[9] DA FONSECA L G, CAPRILES P V S Z, BARBC H J C, et al. A stochastic rank-based ant system for discrete stru-ctural optimization[C]//Proceedings of the 2007 IEEE Swarm Intelligence Symposium, Honolulu, Apr 1-5, 2007. Piscata-way: IEEE, 2007: 68-75.
[10] ZHANG S C, PU J X, SI Y N, et al. Survey on application of ant colony algorithm in path planning of mobile robot[J]. Computer Engineering and Applications, 2020, 56(8): 10-19.
张松灿, 普杰信, 司彦娜, 等. 蚁群算法在移动机器人路径规划中的应用综述[J]. 计算机工程与应用, 2020, 56(8): 10-19.
[11] LIU X Y, TAN L M, YANG C X, et al. Self-adjustable dynamic path planning of unknown environment based on ant colony-clustering algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(5): 846-857.
刘新宇, 谭力铭, 杨春曦, 等. 未知环境下的蚁群-聚类自适应动态路径规划[J]. 计算机科学与探索, 2019, 13(5): 846-857.
[12] HU C Y, JIANG P, ZHOU G R. Application of improved ant colony algorithm in AGV path planning[J]. Computer Engineering and Applications, 2020, 56(8): 270-278.
胡春阳, 姜平, 周根荣. 改进蚁群算法在AGV路径规划中的应用[J]. 计算机工程与应用, 2020, 56(8): 270-278.
[13] JIANG H N, ZHANG X F. A hybrid artificial fish swarm and shuffled frog leaping algorithm[J]. Journal of Shanghai Dianji University, 2019, 22(6): 330-336.
姜慧楠, 张向锋. 一种人工鱼群-蛙跳混合优化算法[J]. 上海电机学院学报, 2019, 22(6): 330-336.
[14] WEI S W. A new co-evolution based genetic algorithm designed for TSP problem[J]. Intelligent Computer and App-lications, 2019, 9(5): 25-29.
魏士伟. 一种求解TSP问题的协同进化算法[J]. 智能计算机与应用, 2019, 9(5): 25-29.
[15] ZHOU N, GE H W, YUAN Y H, et al. Artificial bee colony based ant colony optimization for continuous domains[J]. Computer Engineering & Science, 2016, 38(6): 1156-1163.
周袅, 葛洪伟, 袁运浩, 等. 基于人工蜂群的连续域蚁群优化算法[J]. 计算机工程与科学, 2016, 38(6): 1156-1163.
[16] TAO L H, MA Z N, SHI P T, et al. Dynamic ant colony genetic algorithm based on TSP[J]. Machinery Design & Manufacture, 2019(12): 147-149.
陶丽华, 马振楠, 史朋涛, 等. 基于TSP问题的动态蚁群遗传算法[J]. 机械设计与制造, 2019(12): 147-149.
[17] XU J. Improvement research and application of ant colony algorithm and leapfrog algorithm[D]. Huainan: Anhui Univer-sity of Science and Technology, 2019.
许健. 蚁群算法和蛙跳算法的改进研究及其应用[D]. 淮南: 安徽理工大学, 2019.
[18] ZHANG P, XUE H Q, YUAN X W. Adaptive heterogeneous multiple ant colonies algorithm based on similarity[J]. Com-puter Engineering and Applications, 2014, 50(19): 37-41.
张鹏, 薛宏全, 原欣伟. 基于相似度的自适应异类多种群蚁群算法[J]. 计算机工程与应用, 2014, 50(19): 37-41.
[19] ZHANG D H, YOU X M, LIU S. Dynamic grouping ant colony algorithm combined with cat swarm optimization[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(5): 880-891.
张德惠, 游晓明, 刘升. 融合猫群算法的动态分组蚁群算法[J]. 计算机科学与探索, 2020, 14(5): 880-891.
[20] QIAO D P, PEI J, LI H, et al. Research on improving ant colony algorithm to solve TSP problem[J]. Machinery Design & Manufacture, 2019(10): 144-149.
乔东平, 裴杰, 李浩, 等. 改进蚁群算法求解TSP问题研究[J]. 机械设计与制造, 2019(10): 144-149.
[21] QIAO S, LYU Z M, ZHANG N. Improved particle swarm optimization algorithm based on Hamming distance for trave-ling salesman problem[J]. Journal of Computer Applications, 2017, 37(10): 2767-2772.
乔屾, 吕志民, 张楠. 基于汉明距离的改进粒子群算法求解旅行商问题[J]. 计算机应用, 2017, 37(10): 2767-2772.
[22] WANG Z, LIU R M, ZHU Y G, et al. Improved genetic algorithm for solving TSP problem[J]. Electronic Measure-ment Technology, 2019, 42(23): 91-96.
王震, 刘瑞敏, 朱阳光, 等. 一种求解TSP问题的改进遗传算法[J]. 电子测量技术, 2019, 42(23): 91-96.