结合协同机制与动态调控策略的双蚁群算法

doi:10.3778/j.issn.1673-9418.2008060

摘要/Abstract

摘要：

针对蚁群算法在求解旅行商问题（TSP）时出现的收敛速度慢和多样性较差的问题，提出结合协同机制与动态调控策略的双蚁群算法。首先，将蚁群根据适应度值动态地划分为导向蚁和合作蚁，从而构成异构双蚁群。其次，异构双蚁群采用协同机制平衡算法多样性和收敛速度：导向蚁在路径构建时引入传播因子，增大蚂蚁选择新路径的概率，扩大搜索范围，提高算法多样性；合作蚁受导向蚁中最优路径的引导，当路径相似度达到阈值时，启动合作算子，加快算法收敛速度。最后，引入动态调控策略，在全局信息素更新时引入自适应调控算子，对全局最优路径的信息素进行正向激励或反向惩戒，加快收敛速度的同时避免算法陷入局部最优。求解TSP测试集的实验结果表明，该算法不仅提高了解的质量，保证了算法多样性，而且加快了算法收敛速度，尤其在大规模城市问题中效果更为明显。

关键词: 蚁群算法, 传播因子, 合作算子, 协同机制, 动态调控策略, 旅行商问题（TSP）

Abstract:

Aiming at the problem that the ant colony algorithm has slow convergence rate and poor diversity in solving traveling salesman problem (TSP), double ant colony algorithm based on collaborative mechanism and dynamic regulation strategy is proposed. Firstly, the ant colony is dynamically divided into guide ants and cooperative ants according to fitness value, so as to form a heterogeneous double ant colony. Secondly, the heterogeneous double ant colony adopts the collaborative mechanism to balance the diversity and convergence rate of the algorithm: the guide ant introduces the propagation factor in the path construction, which increases the probability of the ant choosing a new path, expands the search range, and improves the diversity of the algorithm. The cooperative ant is guided by the optimal path of the guide ant. When the path similarity reaches the threshold, the cooperative operator is started to accelerate the convergence speed. Finally, the dynamic regulation strategy is introduced, the adaptive control operator is introduced when the global pheromone is updated, and the pheromone of the global optimal path is positively stimulated or reverse-penalized, so as to accelerate the convergence speed and avoid the algorithm falling into the local optimal. The experimental results of solving the TSP test set show that the improved algorithm not only improves the quality of solutions, ensures the diversity of algorithms, but also speeds up the convergence speed of the algorithm, especially in large-scale urban problems.

Key words: ant colony algorithm, propagation factor, cooperation operator, collaborative mechanism, dynamic regulation strategy, traveling salesman problem (TSP)

孟静雯，游晓明，刘升. 结合协同机制与动态调控策略的双蚁群算法[J]. 计算机科学与探索, 2021, 15(11): 2206-2221.

MENG Jingwen, YOU Xiaoming, LIU Sheng. Double Ant Colony Algorithm Based on Collaborative Mechanism and Dynamic Regulation Strategy[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(11): 2206-2221.

参考文献

[1] DORIGO M, MANIEZZO V, COLORNI A. The ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1996, 26(1): 29-41.
[2] DORIGO M, STüTZLE T. Ant colony optimization[M]. ZHANG J, HU X M, LUO X Y, et al. Beijing: Tsinghua University Press, 2007: 68-130.
DORIGO M, STüTZLE T. 蚁群优化[M]. 张军, 胡晓敏, 罗旭耀, 等译. 北京: 清华大学出版社, 2007: 68-130.
[3] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
[4] ZHANG T , WANG X, WANG Z L. Hierarchy feedback ant colony algorithm for solving secondary delivery problem of petroleum product[J]. Computer Engineering and Applications, 2019, 55(21): 261-270.
张涛, 王昕, 王振雷. 等级反馈蚁群算法求解成品油二次配送问题[J]. 计算机工程与应用, 2019, 55(21): 261-270.
[5] WANG X Y, LUO K. LF ant colony clustering algorithm with global memory[J]. Computer Engineering and Applications, 2019, 55(20): 52-57.
王昕宇, 罗可. 具有全局记忆的LF蚁群聚类算法[J]. 计算机工程与应用, 2019, 55(20): 52-57.
[6] ZHANG Y R, WANG C Y. An improved greedy and ant colony algorithm with mutation operator for TSP[J]. Computer Integrated Manufacturing Systems, 2020, 26(3): 860-870.
张玉茹, 王晨旸. 引入变异算子的改进贪心和蚁群混合算法[J]. 计算机集成制造系统, 2020, 26(3): 860-870.
[7] ZHAO Y W, XIONG R P, QIAO Z, et al. Improved polymorphic ant colony algorithm with predatory search strategy[J]. Computer Engineering and Applications, 2019, 55(14): 115-121.
赵亚文, 熊瑞平, 乔治, 等. 应用捕食搜索策略的改进多态蚁群算法[J]. 计算机工程与应用, 2019, 55(14): 115-121.
[8] PENG Y, WANG J, XIE B F, et al. Improved overlap ant colony optimization algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2014, 8(8): 1002-1008.
彭岳, 王俊, 谢斌福, 等. 改进的重叠蚁群优化算法[J]. 计算机科学与探索, 2014, 8(8): 1002-1008.
[9] ZHOU K L, GONG D X, ZHANG Y L. Ant colony optimization algorithm for regional destructive reconstruction[J]. Computer Engineering and Applications, 2020, 56(14): 62-67.
周克良, 龚达欣, 张宇龙. 区域破坏重建的蚁群优化算法[J]. 计算机工程与应用, 2020, 56(14): 62-67.
[10] YUAN W H, YOU X M, LIU S. Dual-population ant colony algorithm on dynamic learning mechanism[J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(7): 1239-1250.
袁汪凰, 游晓明, 刘升. 动态学习机制的双种群蚁群算法[J]. 计算机科学与探索, 2019, 13(7): 1239-1250.
[11] JIANG D Y, GE H W. Continuous domain ant colony optimization algorithm based on information exchange strategy[J]. Computer Engineering and Applications, 2019, 55(11): 153-159.
姜道银, 葛洪伟. 基于信息交流策略的连续域蚁群优化算法[J]. 计算机工程与应用, 2019, 55(11): 153-159.
[12] WANG H Q, CAO C X. Research on an intelligent ant algorithm in conjuction with local O3-opt optimization[J]. Computer Application and Software, 2010, 27(10): 89-91.
王华秋, 曹长修. 一种结合O3-opt局部优化的智能蚂蚁算法研究[J]. 计算机应用与软件, 2010, 27(10): 89-91.
[13] GAO W X, LIU S, XIAO Z Y, et al. Butterfly optimization algorithm for global optimization[J]. Application Research of Computer, 2020, 37(10): 2966-2970.
高文欣, 刘升, 肖子雅, 等. 全局优化的蝴蝶优化算法[J]. 计算机应用研究, 2020, 37(10): 2966-2970.
[14] ZHANG W H, GUO M X, HE Y K, et al. An improved butterfly algorithm optimizing particle filter algorithm[J]. Journal of Xi??an University of Science and Technology, 2019, 39(1): 119-123.
张威虎, 郭明香, 贺元恺, 等. 一种改进的蝴蝶算法优化粒子滤波算法[J]. 西安科技大学学报, 2019, 39(1): 119-123.
[15] MENG X P, PIAN Z Y, SHEN Z Y, et al. Ant algorithm based on direction-coordinating[J]. Control and Decision, 2013, 28(5): 782-786.
孟祥萍, 片兆宇, 沈中玉, 等. 基于方向信息素协调的蚁群算法[J]. 控制与决策, 2013, 28(5): 782-786.
[16] JIANG K L, LI M A, ZHANG H W. Improved ant colony algorithm for travelling salesman problem[J]. Journal of Computer Applications, 2015, 35(S2): 114-117.
姜坤霖, 李美安, 张宏伟. 面向旅行商问题的蚁群算法改进[J]. 计算机应用, 2015, 35(S2): 114-117.
[17] LIU Z Q, YOU X M, LIU S. Ant colony algorithm for heuristic dynamic pheromone update strategy[J]. Computer Engineering and Applications, 2018, 54(20): 20-27.
刘中强, 游晓明, 刘升. 一种启发式动态信息素更新策略蚁群算法[J]. 计算机工程与应用, 2018, 54(20): 20-27.
[18] 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.