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

摘要

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