An immigrants scheme based on environmental information for ant colony optimization for the dynamic travelling salesman problem

Abstract

Ant colony optimization (ACO) algorithms have proved to be powerful methods to address dynamic optimization problems. However, once the population converges to a solution and a dynamic change occurs, it is difficult for the population to adapt to the new environment since high levels of pheromone will be generated to a single trail and force the ants to follow it even after a dynamic change. A good solution is to maintain the diversity via transferring knowledge to the pheromone trails. Hence, we propose an immigrants scheme based on environmental information for ACO to address the dynamic travelling salesman problem (DTSP) with traffic factor. The immigrants are generated using a probabilistic distribution based on the frequency of cities, constructed from a number of ants of the previous iteration, and replace the worst ants in the current population. Experimental results based on different DTSP test cases show that the proposed immigrants scheme enhances the performance of ACO by the knowledge transferred from the previous environment and the generation of guided diversity. © 2012 Springer-Verlag.