许凯波, 鲁海燕，程毕芸，黄 洋

(江南大学 理学院，江苏 无锡 214122)

求解TSP的改进信息素二次更新与局部优化蚁群算法

许凯波, 鲁海燕*，程毕芸，黄 洋

(江南大学 理学院，江苏 无锡 214122)

(*通信作者电子邮箱luhaiyan@jiangnan.edu.cn)

针对蚁群(ACO)算法收敛速度慢、容易陷入局部最优的缺陷，提出了一种改进信息素二次更新局部优化蚁群算法(IPDULACO)。该算法对蚁群搜索到的当前全局最优解中路径贡献度大于给定的路径贡献阈值的子路径信息素进行二次更新，以提高构成潜在最优解的子路径被选择的概率，从而加快算法的收敛。然后，在搜索过程中，当蚁群陷入局部最优时，使用随机插入法对局部最优解中城市的排序进行调整，以增强算法跳出局部最优解的能力。将改进算法应用于若干经典的旅行售货商问题(TSP)进行仿真实验，实验结果表明，对于小规模的TSP, IPDULACO可以在较少的迭代次数内获得已知最优解；对于较大规模的TSP, IPDULACO可以在较少的迭代次数内获得更精确的解。因此，IPDULACO具有更强的搜索全局最优解的能力和更快的收敛速度，可以高效求解TSP。

旅行售货商问题；蚁群算法；信息素二次更新；局部优化

0 引言

旅行售货商问题(Traveling Salesman Problem, TSP)是经典的组合优化问题[1]，现实生活中的许多问题都可以归结为TSP，如邮路问题、装配线上的螺母问题和产品的生产安排问题等。因此，TSP的有效求解在降低运输成本、提高生产效率等方面具有重要意义。由于TSP是NP难(Non-deterministic Polynomial hard, NP-hard)问题[2]，随着问题规模的扩大，问题解的数量呈指数式增长，目前尚无求解该问题的有效算法。……