求解TSP问题的改进蚁群算法

An Improved Ant Colony Algorithm on TSP Problem

在带精英策略的最大最小蚁群算法的基础上,提出了一种对所找到的最短路径较为敏感,能快速收敛,并能跳出局部最短路径的用于求解TSP问题的改进蚁群算法。它以节约算法找到的路径作为初始最短路径,使得该改进的蚁群算法在一个高起点上进行优化;为了抓住最优路径的某些局部特征,为蚂蚁的概率选择公式提供更全面的先验知识;通过加强找到的最短路径上的信息素的相对引导作用来提高算法向最短路径收敛的速度;对局部最短路径应用禁忌策略来避免算法陷入局部最优。在求解TSP问题上,将该算法与带精英策略的最大最小蚁群算法进行了比较,发现该算法的收敛速度更快,解的质量更高。

Based on the Max-Min Ant Colony Algorithm with the elite strategy,an improved ant colony algorithm was proposed,which was more sensitive to the best route found.It can converge in a short time,and can jump out the local best route.The route found by Saving Algorithm is made to be its initial best route,which makes the improved ant algorithm be optimized in a high starting point.To grasp some local characteristics of the best route,more complete transcendental knowledge for probability choosing formula was provided.The convergence of the improved ant colony algorithm was accelerated through strengthening the relative guiding effect of the best route found in the last iterations.The algorithm was avoided to fall into the local best route through the application of the local best route strategy.The algorithm was compared to the Max-Min Ant Colony Algorithm with the elite strategy.The results show that the improved algorithm can converge faster,and the quality of the solutions is higher.