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

• 作者: 冯志雨 刘升 游晓明
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 分层递进 密度峰聚类 蚁群算法 局部优化 旅行商问题(TSP)
• 年，卷（期）: 2019,（8）
• 所属期刊栏目: 学术研究
• 页码范围: 1280-1294
• 页数: 15页
• 分类号: TP18
• 字数: 10595字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1901022

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	游晓明	上海工程技术大学电子电气工程学院	65	380	11.0	17.0
2	刘升	上海工程技术大学管理学院	89	467	10.0	19.0
3	冯志雨	上海工程技术大学电子电气工程学院	2	3	1.0	1.0