Adaptive Ant Selection for Pheromone Update in Ant Colony Optimization

Ant selection for updating the pheromone is one most crucial operation in ant colony optimization (ACO). In this direction, this paper designs an adaptive ant selection strategy (AAS) to adaptively and dynamically select ants to update the pheromone for ACO. Therefore, a new ACO, called AAS-ACO is developed. Specifically, AAS-ACO first assigns a non-linear selection probability to each ant based on its path ranking. As a result, better ants preserve exponentially higher selection probabilities. Then, based on the selection probabilities, ants are adaptively selected for the pheromone update. By this means, on the one hand, the number of ants involved in the pheromone update is uncertain; on the other hand, relatively better ants instead of absolutely better ones are adaptively selected to update the pheromone, leading to the promotion of search diversity. Subsequently, a dynamic weighting strategy is designed to adjust the amount of the pheromone deposited by the best ant in the current iteration to enhance the search convergence. With the two schemes, AAS-ACO is expected to maintain a suitable compromise between search diversity and search convergence to seek the optimal solutions to TSP. Experiments on 10 classical TSP instances varying from 100 to 1000 cities have proven the significant superiority of AAS-ACO to 5 classic ACOs, especially on high-dimensional TSP problems.