计算机科学与探索2019，Vol.13Issue(8)：1280-1294,15.DOI:10.3778/j.issn.1673-9418.1901022
分层递进的改进聚类蚁群算法解决TSP问题*
Hierarchical Progressive Improved Clustering Ant Colony Algorithm for Solving TSP Problems*
摘要
Abstract
As the scale of the traveling salesman problem (TSP) increases, the running time of the traditional ant colony algorithm will increase, the accuracy of the algorithm will also decrease, and the algorithm will easily fall into the local optimal situation. The idea of the hierarchical progressive algorithm proposed in this paper originates from the product line assembly process of division of labor. First, the inflection point is determined by the operation of the improved density peak clustering algorithm to elect the cluster center, and the included data points are determined according to the cluster center. Then the initial TSP problem is divided into smaller clusters, and the ant colony algorithm of the adaptive pheromone update strategy is used to find the optimal solution of each cluster. Further, the edge formed by the nodes close to the cluster is disconnected, and the nodes disconnected between the two clusters are recombined into a global optimal solution. The optimal solution is finally optimized by the local optimization strategy, so that the running time is effectively shortened under the premise of ensuring the quality of the algorithm solution. This paper selects small-scale and large-scale benchmark cases from TSPLIB, and proves that the improved algorithm has better robustness through Matlab simulation, especially in large-scale benchmark cases, which significantly reduces the running time of the algorithm.关键词
分层递进/密度峰聚类/蚁群算法/局部优化/旅行商问题(TSP)Key words
hierarchical progression/density peak clustering/ant colony algorithm/local optimization/traveling salesman problem (TSP)分类
信息技术与安全科学引用本文复制引用
冯志雨,游晓明,刘升..分层递进的改进聚类蚁群算法解决TSP问题*[J].计算机科学与探索,2019,13(8):1280-1294,15.基金项目
The National Natural Science Foundation of China under Grant Nos. 61673258, 61075115, 61403249, 61603242 (国家自然科学基金). （国家自然科学基金）
