关键词: 路径贡献度, 双种群, 蚁群算法, 旅行商问题, 精英蚂蚁系统, 强化子路径

Abstract: Aiming at the problem that the search space of the traveling salesman problem (TSP) grew exponentially with the increase of the number of cities, making it difficult for the algorithm to traverse all possible paths in a limited time, and was susceptible to the accumulation of pheromones during the search process, leading to premature convergence to local optimal solutions. In order to quickly converge to high-quality solutions when solving TSP, we proposed an analysis method for solving  TSP problem of  dual population ant colony algorithm based on path contribution evaluation. Firstly, we established a TSP mathematical model in the form of a weighted graph. Secondly,  two independent populations were introduced for parallel search: One population used an elite ant system to update pheromones, quickly converged using existing information, and obtained the shortest path of TSP; the other population used a strengthening  sub path evaluation mechanism to update pheromones,  jumped out of the local optimal solution by searching for new solution spaces, and  obtained the shortest path of TSP. Thirdly, by comparing and analyzing the shortest paths of the two populations, the shortest path with the smaller value was obtained as the global optimal path. Finally, introducing a path contribution evaluation mechanism to update the pheromones of the two populations again, we obtained the final TSP solution. Experimental results  show that this method can effectively solve and analyze TSPs of different scales. It can not only shorten the length of the path, but also obtain the shortest path that traverses all cities and returns to the starting point, and the data distribution effect is better.

Key words:  , path contribution, dual population, ant colony algorithm, traveling salesman problem, elite ant system, strengthening sub path