Dynamic Hierarchical Ant Colony Optimization Based on Reward and Punishment Learning Strategy

doi:10.3778/j.issn.1673-9418.2006084

Abstract

Abstract:

In order to solve the problems of low precision and premature convergence of traditional ant colony system in solving traveling salesman problem (TSP), this paper proposes a dynamic hierarchical ant colony system which integrates reward and punishment learning strategy (DHL-ACS). Firstly, the ant colony is dynamically divided into empire ants, colony ants and king ant, in which empire ants and colony ants perform local pheromone update, and king ant performs global pheromone update. In local pheromone update, the empire ants perform larger weight coefficient, which is responsible for the development of better solution to enhance the guidance of algorithm, and the colony ants perform small weight coefficient to explore the suboptimal solution and to ensure the diversity of algorithm. In addition, the method of exchanging high-quality solutions between empire ants and colony ants is used to improve the accuracy of the solutions. Secondly, an improved learning strategy is proposed, which realizes the assimilation of the better solution by rewarding the common path of empire ants and colony ants, and improves the convergence speed of the algorithm. Furthermore, when the algorithm stops, the feedback operator is introduced to reduce the pheromone concentration on the path of king ant, which can punish the path of higher pheromone, so as to improve the diversity of the population and enhance the ability of the algorithm to jump out of the local optimum. Through the experiments of several sets of TSP instances, it is shown that the improved algorithm balances the relationship between convergence rate and diversity, especially for large-scale TSP problems, which can effectively improve the accuracy of solutions.

Key words: ant colony optimization (ACO), learning strategy, feedback operator, dynamic hierarchical, traveling salesman problem (TSP)

摘要：

为应对传统蚁群算法在解决旅行商问题（TSP）中求解精度不高、算法易早熟等问题，提出融合奖惩学习策略的动态分级蚁群算法（DHL-ACS）。首先将蚁群动态划分为帝国蚁、殖民蚁及国王蚁，其中帝国蚁与殖民蚁执行局部信息素更新，国王蚁执行全局信息素更新，在局部信息素更新中帝国蚁执行较大权重系数，负责对较优解的开发增强算法导向性，殖民蚁执行较小权重系数，负责对次优解的探索保证算法多样性，并利用帝国蚁与殖民蚁交换优质解的方式提高解的精度。其次提出一种改进的学习策略，通过奖励帝国蚁与殖民蚁的公共路径以实现较优解的同化作用，进而提高算法收敛速度；进一步当算法停滞时，引入反馈算子来减少国王蚁路径上的信息素，以达到对较高信息素路径的惩罚作用，从而提高种群多样性，增强算法跳出局部最优能力。通过对多组TSP数据集实验对比分析，实验结果表明改进后的算法很好地平衡了收敛速度与多样性之间的关系，尤其应对大规模TSP问题，能有效改善解的精度。

关键词: 蚁群算法（ACO）, 学习策略, 反馈算子, 动态分级, 旅行商问题（TSP）

MO Yadong, YOU Xiaoming, LIU Sheng. Dynamic Hierarchical Ant Colony Optimization Based on Reward and Punishment Learning Strategy[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(9): 1703-1716.

莫亚东, 游晓明, 刘升. 融合奖惩学习策略的动态分级蚁群算法[J]. 计算机科学与探索, 2021, 15(9): 1703-1716.

References

[1] ZHOU Y Q, HUANG Z X. Artificial glow worm swarm optimization algorithm for TSP[J]. Control and Decision, 2012, 27(12): 1816-1821.
周永权, 黄正新. 求解TSP的人工萤火虫群优化算法[J]. 控制与决策, 2012, 27(12): 1816-1821.
[2] QIAO S, LV Z M, ZHANG N. Improved particle swarm optimization algorithm based on Hamming distance for travel-ing salesman problem[J]. Journal of Computer Applications, 2017, 37(10): 2767-2772.
乔屾, 吕志民, 张楠. 基于汉明距离的改进粒子群算法求解旅行商问题[J]. 计算机应用, 2017, 37(10): 2767-2772.
[3] ZHANG X L, CHEN X W, XIAO H, et al. A new imperia-list competitive algorithm for solving TSP problem[J]. Con-trol and Decision, 2016, 31(4): 586-596.
张鑫龙, 陈秀万, 肖汉, 等. 一种求解旅行商问题的新型帝国竞争算法[J]. 控制与决策, 2016, 31(4): 586-596.
[4] DORIGO M, MANIEZZO V, COLORNI A. Ant system: op-timization by a colony of cooperating agents[J]. IEEE Tran-sactions on Systems, Man, and Cybernetics: Part B, 1996, 26(1): 29-41.
[5] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman pro-blem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
[6] STUTZLE T, HOOS H H. MAX-MIN, ant system[M]. New York: Elsevier Science Inc., 2000.
[7] LIU X Y, TAN L M, YANG C X, et al. Self-adjustable dy-namic path planning of unknown environment based on ant colony-clustering algorithm[J]. Journal of Frontiers of Com-puter Science and Technology, 2019, 13(5): 846-857.
刘新宇, 谭力铭, 杨春曦, 等. 未知环境下的蚁群-聚类自适应动态路径规划[J]. 计算机科学与探索, 2019, 13(5): 846-857.
[8] WEI J, WANG J J, WANG J, et al. Three dimensional path planning based on improved ant colony algorithm[J]. Com-puter Engineering and Applications, 2020, 56(17): 217-223.
魏江, 王建军, 王健, 等. 基于改进蚁群算法的三维航迹规划[J]. 计算机工程与应用, 2020, 56(17): 217-223.
[9] YOU X M, LIU S, LV J Q. Ant colony algorithm based on dynamic search strategy and its application on path plann-ing of robot[J]. Control and Decision, 2017, 32(3): 552-556.
游晓明, 刘升, 吕金秋. 一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J]. 控制与决策, 2017, 32(3): 552-556.
[10] GANGADHARAN M M, SALGAONKAR A. Ant colony optimization and firefly algorithms for robotic motion plann-ing in dynamic environments[J]. Engineering Reports, 2020, 2(3).
[11] ZHAO Q C, YANG Y W, XIE S Y, et al. Research on im-provement of ant colony optimization algorithm for MPR under dense MANET[J]. Computer Engineering, 2021, 47(4): 135-140.
赵启超, 杨余旺, 谢勇盛, 等. 密集MANET下MPR的蚁群优化算法改进研究[J]. 计算机工程, 2021, 47(4): 135-140.
[12] LIU X F, ZHAN Z H, DENG J D, et al. An energy efficient ant colony system for virtual machine placement in cloud computing[J]. IEEE Transactions on Evolutionary Comput-ation, 2018, 22(1): 113-128.
[13] 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.
[14] ZHANG M X, ZHANG D M, YANG J Q, et al. Ant colony optimization algorithm based on Tabu search[J]. Communi-cations Technology, 2017, 50(8): 1658-1663.
张慕雪, 张达敏, 杨菊蜻, 等. 基于禁忌搜索的蚁群优化算法[J]. 通信技术, 2017, 50(8): 1658-1663.
[15] LI J, TONG Z, WANG Z. Approach to solve TSP with par-allel ACS-2-opt[J]. Computer Science, 2018, 45(S2): 138-142.
李俊, 童钊, 王政. 一种并行ACS-2-opt算法处理TSP问题的方法[J]. 计算机科学, 2018, 45(S2): 138-142.
[16] HUANG Y Q, YANG S L, LIANG C Y. Improved inter-active ant colony algorithm and its application[J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(12): 1720-1728.
黄永青, 杨善林, 梁昌勇. 改进交互式蚁群算法及其应用 [J]. 计算机科学与探索, 2016, 10(12): 1720-1728.
[17] DU P Z, TANG Z M, SUN Y. An object-oriented multi-role ant colony optimization algorithm for solving TSP problem[J]. Control and Decision, 2014, 29(10): 1729-1736.
杜鹏桢, 唐振民, 孙研. 一种面向对象的多角色蚁群算法及其TSP问题求解[J]. 控制与决策, 2014, 29(10): 1729-1736.
[18] XU K B, LU H Y, CHENG B Y, et al. Ant colony optimi-zation algorithm based on improved pheromones double updating and local optimization for solving TSP[J]. Journal of Computer Applications, 2017, 37(6): 1686-1691.
许凯波, 鲁海燕, 程毕芸, 等. 求解TSP的改进信息素二次更新与局部优化蚁群算法[J]. 计算机应用, 2017, 37(6): 1686-1691.
[19] WU H F, CHEN X Q, MAO Q H, et al. Improved ant colony algorithm based on natural selection strategy for solving TSP problem[J]. Journal on Communications, 2013, 34(4): 165-170.
吴华锋, 陈信强, 毛奇凰, 等. 基于自然选择策略的蚁群算法求解TSP问题[J]. 通信学报, 2013, 34(4): 165-170.
[20] ZHANG Y, QUAN H, WEN J F. Mobile robot path plann-ing based on the wolf ant colony hybrid algorithm[J]. Jour-nal of Huazhong University of Science and Technology(Nature Science Edition), 2020, 48(1): 127-132.
张毅, 权浩, 文家富. 基于独狼蚁群混合算法的移动机器人路径规划[J]. 华中科技大学学报(自然科学版), 2020, 48(1): 127-132.