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

摘要

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

关键词

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