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

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