| 分层递进的改进聚类蚁群算法解决TSP问题* |
| |
| 引用本文： | 冯志雨,游晓明,刘升. 分层递进的改进聚类蚁群算法解决TSP问题*[J]. 计算机科学与探索, 2019, 13(8): 1280-1294 |
| |
| 作者姓名： | 冯志雨 游晓明 刘升 |
| |
| 作者单位： | 上海工程技术大学 电子电气工程学院,上海,201620;上海工程技术大学 管理学院,上海,201620 |
| |
| 摘 要： | 随着旅行商问题(TSP)规模的增大,传统蚁群算法的运行时间会增大,算法的解精度也会降低,并且算法很容易陷入局部最优的情况。提出的分层递进算法的思想源于分工合作的产品线组装流程,首先利用改进的密度峰聚类算法确定拐点,从而选举出聚类中心,根据聚类中心确定包含的数据点;其次将初始的TSP问题分割成较小的簇,这些簇称为二类TSP问题;再经自适应信息素更新策略的蚁群算法运算,找出每个簇的最优解,进一步将簇与簇之间相近的节点构成的边断开;然后两簇之间断开的节点重组成全局最优解;最终通过局部优化策略对重组的优化解进一步优化,从而在保证算法解质量的前提下有效地缩短了运行时间。从TSPLIB中选取小规模、大规模基准案例,通过Matlab仿真验证了改进算法具有更好的鲁棒性,特别是在大规模基准案例中显著地减少了算法运行时间。
|
| 关 键 词： | 分层递进 密度峰聚类 蚁群算法 局部优化 旅行商问题(TSP) |
Hierarchical Progressive Improved Clustering Ant Colony Algorithm for Solving TSP Problems |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
