计算机科学与探索

作者：冯志雨，游晓明，刘升

单位：1.上海工程技术大学 电子电气工程学院，上海 2016202.上海工程技术大学 管理学院，上海 201620

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

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

来源：2019年第8期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2019年第8期