关键词: 蚁群算法, 最大生成树, 最小生成树, 吸引因子, 旅行商问题（TSP）

Abstract:

When solving traveling salesman problem (TSP), the ant colony algorithm is easy to fall into local optimum and convergence speed is slow, a double-type ant colony algorithm considering dynamic guidance and neighborhood interaction is proposed. Firstly, the algorithm combines the dynamic guidance strategy to increase the dynamic pheromone belonging to the path of the largest spanning tree in the early iteration, thereby effectively increasing the diversity of the population; adding the dynamic pheromone belonging to the path of the minimum spanning tree in the late iteration to accelerate the convergence speed. Furthermore, the ants are divided into two categories, which are integrated into the neighborhood interaction strategy, and the second type of ants improve the state transition and the local pheromone update formula through the attraction factors, and use the MMAS (max-min ant system) pheromone restriction strategy, which not only improves the convergence, but also prevents the algorithm from early stagnation. The experimental results of solving the TSP test set and compared with other improved ant colony algorithms show that the improved algorithm can effectively accelerate the convergence speed and avoid falling into local optimum, thus obtaining a more accurate solution, especially in the case of large-scale TSP problems, the effect is more significant.

Key words: ant colony algorithm, maximal spanning tree, minimum spanning tree, attraction factor, traveling salesman problem (TSP)