Jisuanji kexue yu tansuo (Nov 2021)
Double Ant Colony Algorithm Based on Collaborative Mechanism and Dynamic Regulation Strategy
Abstract
Aiming at the problem that the ant colony algorithm has slow convergence rate and poor diversity in solving traveling salesman problem (TSP), double ant colony algorithm based on collaborative mechanism and dynamic regulation strategy is proposed. Firstly, the ant colony is dynamically divided into guide ants and cooperative ants according to fitness value, so as to form a heterogeneous double ant colony. Secondly, the heterogeneous double ant colony adopts the collaborative mechanism to balance the diversity and convergence rate of the algorithm: the guide ant introduces the propagation factor in the path construction, which increases the probability of the ant choosing a new path, expands the search range, and improves the diversity of the algorithm. The cooperative ant is guided by the optimal path of the guide ant. When the path similarity reaches the threshold, the cooperative operator is started to accelerate the convergence speed. Finally, the dynamic regulation strategy is introduced, the adaptive control operator is introduced when the global pheromone is updated, and the pheromone of the global optimal path is positively stimulated or reverse-penalized, so as to accelerate the convergence speed and avoid the algorithm falling into the local optimal. The experimental results of solving the TSP test set show that the improved algorithm not only improves the quality of solutions, ensures the diversity of algorithms, but also speeds up the convergence speed of the algorithm, especially in large-scale urban problems.
Keywords