求解TSP问题的快速蚁群算法

申铉京，刘阳阳，黄永平，徐 铁，何习文

（1.吉林大学计算机科学与技术学院，长春130012；2.吉林大学符号计算与知识工程教育部重点实验室，长春130012；3.吉林石油集团有限责任公司洮河农场，吉林松原138000）

TSP是著名的NP难问题，在电路板布局、VLSI芯片设计、车辆调度等组合优化问题中有着广泛的应用。蚁群算法是由意大利学者Dorigo等［1］首先提出的一种基于种群模拟进化智能启发式算法，并已经成功应用于TSP等多个NP难的组合优化问题求解，但基本蚁群算法也存在着易出现早熟、停滞的缺陷。针对蚁群算法的这些缺点，人们提出了许多改进的算法，如结合Q-Learning提出的Ant-Q算法［2］、MMAS算法［3］，基于负反馈的蚁群算法［4］等。在逐渐认识到蚁群有组织、有分工的特性，人们又提出多态蚁群算法，在一定程度上改善了蚁群算法的性能，也是提高TSP求解效率的一个发展方向。但现有方法在收敛速度和求解精度上未达到一个很好的平衡。

本文算法通过采用信息素挥发因子自适应调整机制，保证算法的全局搜索能力，有效地避免算法陷入局部最优解。另外，通过加强公共路径的选择引导算法寻找更优路径，使得在算法停滞前易于发现更好的路径，并趋向最优路径解。该算法可以有效防止陷入局部最优解，同时提高收敛的速度。

1 算法策略

1.1 蚂蚁群体移动规则

该算法中，第k只蚂蚁由城市i选择到下一个城市j的规则是：

当q≤q0时，

当q＞q0时，蚂蚁根据转移概率公式（2）选择下一个点：

式中：q0是一个给定的位于（0，1）之间的常数；……