基于聚类集成的蚁群算法求解大规模TSP问题

摘要：

ACA(Ant Colony Algorithm)是一种可以有效求解组合优化的TSP(Travelling Salesman Problem)问题的方法.然而,当TSP问题的规模较大时,该算法的求解性能将会明显减弱.本文针对大规模TSP问题提出一种基于聚类集成的蚁群算法IAPACA(Improved AP Ant Colony Algorithm)的求解方法.利用AP(Affinity Propagation)聚类对大规模旅行商问题进行处理,将大规模旅行商问题分为若干子问题,并对每个子问题用蚁群算法进行寻优.然后用改进的集成方案对子问题进行组合,得到问题的结果.最后进行TSPLIB标准库测试算例的实验仿真,实验结果表明,基于聚类集成的蚁群算法具有更好的求解效果.

关键词：大规模TSP问题、蚁群算法、AP聚类、集成方案、求解质量

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金面上项目;浙江省大学生新苗人才计划项目;国家大学生创新创业训练计划支持项目

在线出版日期：2020-04-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：31-35