莫亚东，游晓明+，刘 升

1.上海工程技术大学 电子电气学院，上海201620

2.上海工程技术大学 管理学院，上海201620

旅行商问题（traveling salesman problem，TSP）是经典的组合优化问题。该问题主要描述为：一位旅行商人从任意起始城市出发，由一个城市移动到另一城市，要求能够不重复遍历整个国家的所有城市最终回到起始出发点，且构成的回路之和最小，即构成最小哈密顿回路。目前解决TSP问题有很多方法[1-3]，研究表明蚁群算法由于其自身正反馈性及分布式运行等优点是最有效的方法之一。

蚁群算法[4]（ant colony optimization，ACO）是意大利学者Dorigo等人受自然界中蚂蚁觅食的启发而提出的群智能算法，主要思想是蚂蚁能够利用自身信息素更新机制有效地往返食物源与巢穴之间。其算法提出之后引起了人们的很大关注，并开启了探讨蚁群算法的性能应用等方面的研究。针对传统蚁群算法收敛速度慢，求解精度不高等缺点，Dorigo 等人[5]又提出了蚁群系统（ant colony system，ACS），它通过每次迭代中对最优蚂蚁所生成的路径上的信息素进行更新，加强了最优信息的正反馈作用，进一步提高了算法的收敛速度，但由于对最优解的强化，易使算法陷入局部最优。Stutzle 等人[6]提出了最大-最小蚂蚁系统（max-min ant system，MMAS），该方式将信息素的取值设定在固定区间内，限制了信息素的累加及挥发，在一定程度上避免了算法停滞，提高了种群多样性，但当解的分布较为分散时，算法的收敛速度将会降低。后来众多学者结合自身领域需求对该算法进行了更进一步的改进与研究，例如，在算法应用方面，利用蚁群算法求解路径规划[7-10]、密集型网络及云计算虚拟机布局[11-12]等问题；……