求解TSP问题的自适应模拟退火蚁群算法

袁汪凰　游晓明*　刘　升　朱　艳

1(上海工程技术大学电子电气学院　上海 201620) 2(上海工程技术大学管理学院　上海 201620)

0　引　言

旅行商问题TSP(Traveling Salesman Problem)是一个属于NP-Hard的组合优化问题。旅行商从所有城市列表中任选一个城市作为起点，不重复地遍历完所有城市，最后回到原起始点，从而形成一个最短路径的Hamilton回路。目前解决TSP问题的算法有最近邻点[1]、贪心算法[2]、遗传算法[3]、模拟退火算法[2]、粒子群优化算法[4]、蚁群算法[5]等。而蚁群算法是一个全局搜索策略的群智能算法，具有很好的自组织性、鲁棒性、正反馈性、并行性和易与其他算法结合解决实际问题等优点。但是蚁群算法同时也存在收敛速度慢、易陷入局部最优、容易陷入早熟、停滞的缺点。

蚁群算法最早由意大利学者M.Dorigo受到自然界中蚂蚁群体的觅食行为的启发首次提出，并将其应用于经典的TSP问题。其后专家学者对蚁群算法进行了改进：1996年M.Dorigo等在此基础上，提出了蚂蚁系统AS(Ant System)[5]，该算法采用随机比例规则构建路径，当所有蚂蚁路径构建结束之后，进行信息素更新；1997年M.Dorigo和M.Gambardella将蚁群算法中加入Q-Learning算法，提出了一种具有全新机制的蚁群系统ACS (Ant Colony System)[6];此后T.Stutzle等在AS基础上进行改进，提出了最大-最小蚁群算法MMAS (Max-Min Ant System)[7]。在这些改进算法中，MMAS是对AS完善的典型代表之一，在解决TSP问题上具有的良好性能。

MMAS在一定程度上有效地避免了算法的停滞，但仍存在解质量不高、收敛速度较慢等不足，因此专家学者在此基础上进行了改进。文献[8]提出一种动态的最大最小蚁群算法DMAS,通过构造与当前迭代过程中信息素最大值相关的函数，动态更新信息素的下限阈值，增大蚂蚁的探索能力，使得多样性增加；……