基于路径贡献度评判的双种群蚁群算法TSP问题求解分析方法

来源：吉林大学学报·理学版杂志2025年第6期北京时间：

作者：蒋成, 郭向坤

单位：1. 湖北工程学院 计算机与信息科学学院, 湖北 孝感 432000; 2. 沈阳理工大学 信息科学与工程学院, 沈阳 110159

摘要：针对旅行商问题（traveling salesman problem, TSP）的搜索空间随城市数量的增加而呈指数级增长, 使算法在有限时间内难以遍历所有可能的路径, 且在搜索过程中易受信息素累积的影响, 导致算法过早收敛到局部最优解的问题, 为在求解TSP时可以快速收敛到高质量的解, 提出一种基于路径贡献度评判的双种群蚁群算法TSP问题求解分析方法.首先, 以赋权图的形式建立TSP数学模型. 其次, 引入两个独立的种群进行并行搜索: 一个种群采用精英蚂蚁系统更新信息素, 利用已有信息快速收敛, 得到TSP的最短路径； 另一个种群采用强化子路径评判机制更新信息素, 通过探索新的解空间的方式跳出局部最优解, 得到TSP的最短路径. 再次, 以对比分析两个种群最短路径的方式, 得到较小值的最短路径, 作为全局最优路径. 最后, 引入路径贡献度评判机制再次更新两个种群的信息素, 得到最终的TSP解. 实验结果表明, 该方法可有效求解分析不同规模的TSP, 不仅可缩短路径长度, 得到一条遍历全部城市并返回起点的最短路径, 且数据分布效果较佳.

关键词：路径贡献度,双种群,蚁群算法,旅行商问题,精英蚂蚁系统,强化子路径