动态信息素更新和路径奖惩的蚁群算法  

Ant Colony Algorithm Based on Dynamic Pheromone Update and Path Rewards and Punishments

作　　者：马世轩 游晓明[1] 刘升[2] MA Shixuan;YOU Xiaoming;LIU Sheng(School of Electronic and Electrical Engineering,Shanghai University of Engineering Science,Shanghai 201620,China;School of Management,Shanghai University of Engineering Science,Shanghai 201620,China)

机构地区：[1]上海工程技术大学电子电气工程学院,上海201620 [2]上海工程技术大学管理学院,上海201620

出　　处：《计算机工程与应用》2023年第4期64-76,共13页Computer Engineering and Applications

基　　金：国家自然科学基金(61673258,61075115);上海市自然科学基金(19ZR1421600)。

摘　　要：针对蚁群算法容易陷入局部最优,收敛速度慢,难以解决大规模问题的情况,提出依据信息熵和停滞次数的动态信息素的更新策略和基于最优路径集合的奖惩策略的蚁群算法,在动态信息素更新策略中,利用收敛系数来动态调节信息素,从而有效地平衡算法的多样性和收敛性。在搜索过程中,通过持续增大收敛系数,加快了收敛速度;当信息熵降低或者停滞次数达到一定数值时,通过降低收敛系数,跳出局部最优。同时基于最优路径集合,对较优路径进行奖励,对其他路径进行惩罚,通过减少蚂蚁每一步可选城市的数量,加快了收敛速度。并且使用三种局部优化方法,从而进一步提高解的精度。经过实验测试,该算法用于解决旅行商问题(traveling salesman problem,TSP),具有较高的求解精度,并能有效平衡解的精度和收敛速度的矛盾。Aiming at the fact that the ant colony algorithm is prone to fall into local optimum,the convergence speed is slow,and it is difficult to solve large-scale problems,this paper proposes an ant colony algorithm based on dynamic pheromone update strategy dependent on the information entropy and the number of stagnation and the reward and punishment strategy based on the optimal path set.In the dynamic pheromone update strategy,the convergence coefficient is used to dynamically adjust the pheromone,so as to effectively balance the diversity and convergence of the algorithm.During the search process,the convergence speed is accelerated by continuously increasing the convergence coefficient.When the information entropy decreases or the number of stagnation reaches a certain value,the local optimum can be jumped out by reducing the convergence coefficient.At the same time,based on the optimal path set,the optimal path is rewarded and other paths are penalized,thereby reducing the number of cities that ants can choose at each step,and speeding up the convergence speed.And three local optimization methods are used to further improve the accuracy of the solution.After experimental tests,the algorithm is used to solve the traveling salesman problem(TSP),which has a high solution accuracy and can effectively balance the contradiction between the solution accuracy and the convergence speed.

关 键 词：蚁群算法 信息熵 旅行商人问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]