Dynamic Hierarchical Ant Colony Optimization Based on Reward and Punishment Learning Strategy

Abstract

In order to solve the problems of low precision and premature convergence of traditional ant colony system in solving traveling salesman problem (TSP), this paper proposes a dynamic hierarchical ant colony system which integrates reward and punishment learning strategy (DHL-ACS). Firstly, the ant colony is dynamically divided into empire ants, colony ants and king ant, in which empire ants and colony ants perform local pheromone update, and king ant performs global pheromone update. In local pheromone update, the empire ants perform larger weight coefficient, which is responsible for the development of better solution to enhance the guidance of algorithm, and the colony ants perform small weight coefficient to explore the suboptimal solution and to ensure the diversity of algorithm. In addition, the method of exchanging high-quality solutions between empire ants and colony ants is used to improve the accuracy of the solutions. Secondly, an improved learning strategy is proposed, which realizes the assimilation of the better solution by rewarding the common path of empire ants and colony ants, and improves the convergence speed of the algorithm. Furthermore, when the algorithm stops, the feedback operator is introduced to reduce the pheromone concentration on the path of king ant, which can punish the path of higher pheromone, so as to improve the diversity of the population and enhance the ability of the algorithm to jump out of the local optimum. Through the experiments of several sets of TSP instances, it is shown that the improved algorithm balances the relationship between convergence rate and diversity, especially for large-scale TSP problems, which can effectively improve the accuracy of solutions.

Keywords

• ant colony optimization (aco)
• learning strategy
• feedback operator
• dynamic hierarchical
• traveling salesman problem (tsp)