K-Means聚类下的改进蚁群算法优化TSP问题

作者：张硕航; 郭改枝^*; 张朋

来源：内蒙古大学学报(自然科学版), 2021, 52(06): 609-616.

DOI：10.13484/j.nmgdxxbzk.20210607

• 旅行商问题
• K-均值算法
• 蚁群算法
• 最优路径
• 算法优化

在解决旅行商问题(Traveling Salesman Problem, TSP)上,提出了一种新的求解思路即基于K-means聚类思想下的改进型蚁群算法,目的是优化TSP最短路径。先将整体TSP中分布的全部节点利用K-means聚类思想将其分成若干子TSP,再通过对基础蚁群算法(Ant Colony Algorithm, ACA)中信息素更新策略的改进,解决传统蚁群算法在面对大规模TSP问题时有迭代时间长、收敛速度慢和易陷入局部最优解的缺陷。在对每一个子TSP求解最优路径后再将各部分连接,使其融合成为一条完整TSP的最优路径。经验证该算法不仅优化了最短路径降低了误差率,同时大大缩短运算时间,提高了运算效率。

• 出版日期2021
• 单位内蒙古师范大学