• 人工智能 •

考虑动态导向与邻域交互的双蚁型算法

1. 1. 上海工程技术大学 电子电气工程学院，上海 201620
2. 上海工程技术大学 管理学院，上海 201620
• 出版日期:2020-06-01 发布日期:2020-06-04

Double-Type Ant Colony Algorithm Considering Dynamic Guidance and Neighborhood Interaction

PAN Han, YOU Xiaoming, LIU Sheng

1. 1. School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
2. School of Management, Shanghai University of Engineering Science, Shanghai 201620, China
• Online:2020-06-01 Published:2020-06-04

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.