刘一凡，游晓明+，刘 升

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

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

旅行商问题[1]（traveling salesman problem，TSP）是一类经典的组合优化问题，可以描述为：旅行商从一个城市出发，不重复地遍历完所有城市并最终回到起始城市，需要在所有满足以上条件的路径中找出最短路径的问题。国内外学者采用多种算法来研究此问题，目前主要有遗传算法[2]、模拟退火法[3]、粒子群算法[4]和蚁群算法[5]等。其中，蚁群算法具有较强的鲁棒性、良好的并行性和易与其他算法结合等特点，在求解TSP 问题中取得很好的效果，并被广泛应用于车辆调度、图像处理和多目标组合优化等诸多优化领域。

蚁群算法是一种新兴智能仿生优化算法，最初于20 世纪90 年代由意大利学者Dorigo 等人提出。1996 年，Dorigo 等人在蚂蚁系统（ant system，AS）[6]的基础上，采用信息素全局更新和局部更新两种信息素更新方式，提出蚁群系统（ant colony system，ACS）[7]算法，加快了算法收敛速度。2000年，Stutzle等人提出了最大最小蚂蚁系统（max-min ant system，MMAS）[8]，为每条路径上信息素浓度设定了上、下限阈值，避免信息素浓度无限累加而停滞，提高了算法的多样性。以上基本蚁群算法具有高效的搜索能力，但仍存在着易陷入局部最优、收敛速度慢等问题。

蚁群优化算法（ant colony optimization，ACO）是对基本蚁群算法进行改进的一系列优化算法，为了提高基本蚁群算法的性能，国内外学者主要在路径选择、信息素更新、添加局部优化算子和与其他算法结合等方面进行改进。文献[9]引入精英策略思想，提出一种基于排序加权的信息素更新策略，通过强化较优路径信息对蚂蚁的反馈作用，提高了算法收敛速度和求解质量。……