分层递进的改进聚类蚁群算法解决TSP问题*

摘要：

随着旅行商问题(TSP)规模的增大,传统蚁群算法的运行时间会增大,算法的解精度也会降低,并且算法很容易陷入局部最优的情况.提出的分层递进算法的思想源于分工合作的产品线组装流程,首先利用改进的密度峰聚类算法确定拐点,从而选举出聚类中心,根据聚类中心确定包含的数据点;其次将初始的TSP问题分割成较小的簇,这些簇称为二类TSP问题;再经自适应信息素更新策略的蚁群算法运算,找出每个簇的最优解,进一步将簇与簇之间相近的节点构成的边断开;然后两簇之间断开的节点重组成全局最优解;最终通过局部优化策略对重组的优化解进一步优化,从而在保证算法解质量的前提下有效地缩短了运行时间.从TSPLIB中选取小规模、大规模基准案例,通过Matlab仿真验证了改进算法具有更好的鲁棒性,特别是在大规模基准案例中显著地减少了算法运行时间.

关键词：分层递进、密度峰聚类、蚁群算法、局部优化、旅行商问题(TSP)

所属期刊栏目：13

分类号：TP18(自动化基础理论)

资助基金：The National Natural Science Foundation of China under Grant Nos. 61673258, 61075115, 61403249, 61603242

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

页数：共15页

页码：1280-1294