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

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