关键词: 蚁群算法, 区域破坏重建, 2-Opt, 旅行商问题

Abstract:

The traditional ant colony algorithm has great advantages in solving the Traveling Salesman Problem（TSP）. At the same time, there are some problems such as slow convergence speed and easy to fall into local optimum. To solve these problems, an Ant Colony Optimization algorithm for Regional Damage Reconstruction（RDRACO） is proposed. RDRACO solves the problem of local optimum due to pheromone accumulation through the region destruction reconstruction algorithm, and adjusts the pheromone update rule and global update strategy of the ant colony algorithm to match the algorithm. At the same time, the 2-Opt operator is added to the ant colony path selection to speed up the convergence and improve the convergence accuracy. The experiment uses the 20 classic TSP data sets in TSPLIB to simulate RDRACO. The simulation results show that the RDRACO algorithm can find the known optimal path of the smaller TSP data set with fewer iterations, and in the larger data set TSP. There is significant optimization in convergence accuracy. RDRACO has higher accuracy and better robustness while improving convergence speed.

Key words: ant colony algorithm, regional damage reconstruction, 2-Opt, traveling salesman problem