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

摘要：

传统蚁群算法在解决旅行商问题（TSP）有较大的优势，但也存在一些不足，如收敛速度慢、易陷入局部最优等。针对这些问题，提出区域破坏重建的蚁群优化算法（RDRACO）。RDRACO应用区域破坏重建算法解决因信息素积累而陷入局部最优的问题，并将蚁群算法的信息素更新规则和全局更新策略进行了调整，使之与该算法匹配。另外在蚁群路径选择中加入2-Opt算子，加快收敛速度和提高收敛精度。实验采用TSPLIB中的20个经典TSP数据集对RDRACO进行仿真实验，仿真结果表明：RDRACO算法通过较少的迭代次数就可找出数据集较小TSP的已知最优路径，并在数据集较大TSP收敛精度上有显著的优化。RDRACO在提高收敛速度的同时具有较高的精度和较好的鲁棒性。

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