Abstract: Aiming at the issues of ant colony algorithm in solving large-scale traveling salesman problems (TSP), such as easily falling into local optima and slow convergence speed, an ant colony algorithm integrating adaptive clustering and mother ant guidance strategy (AMACS) is proposed. In the adaptive clustering process, firstly, an improved clustering method is used, which leverages the concepts of maximum-minimum distance and class density to obtain the optimal clustering results through an adaptive clustering strategy, and quickly obtains the optimized solution for each cluster. Next, the neighboring clusters are fused using a spider web fusion principle, effectively enhancing the accuracy of the initial solution. Additionally, the initial solution is optimized through the mother ant guidance strategy, which includes two components: path guidance and pheromone optimization. Path guidance sets the initial solution as the solution for the first generation, improving the stability of the algorithm; pheromone optimization involves stimulating the pheromone along the initial solution’s path, thereby enhancing the solution’s accuracy. Finally, a random recombination strategy is employed to reorganize and randomly stimulate the pheromones, helping the algorithm to escape local optima and improving the solution’s accuracy. Experimental results show that the proposed algorithm not only ensures solution accuracy when solving large-scale TSPs but also improves the stability of the algorithm.

Key words: ant colony algorithm, clustering algorithm, traveling salesman problem, pheromone optimization, mother ant guidance

摘要： 针对蚁群算法在求解较大规模旅行商问题时，容易出现陷入局部最优、收敛速度较慢的情况，提出一个融合自适应聚类与母蚁引导策略的蚁群算法（AMACS）。在自适应聚类中，使用改进的聚类方法，利用最大最小距离与类密度的思想，通过自适应聚类策略，获得最佳聚类结果，并快速获得各个类的优化解；利用近邻原则，将相邻的类进行蛛网融合，从而有效提高了初始解的精度。通过母蚁引导策略对初始解进行优化，其中母蚁引导策略包括路径诱导与信息素优化两个部分：路径诱导将初始解设定为第一代的解，提高了算法的稳定性；信息素优化通过对初始解路径进行信息素激励，提高了解的精度。使用随机重组策略对信息素进行重组以及随机激励，使算法尽量跳出局部最优，提高了算法的精度。实验结果表明，提出的算法在求解大规模旅行商问题时，不仅保证了解的精度，而且提高了算法的稳定性。

关键词: 蚁群算法, 聚类算法, 旅行商问题, 信息素优化, 母蚁引导