Ant Local Search and its efficient adaptation to graph colouring

In this paper, we propose a new kind of ant algorithm called Ant Local Search. In most ant algorithms, the role of each ant is to build a solution in a constructive way. In contrast, we propose to consider each ant as a local search, where at each step and in concordance with all ant algorithms, each ant modifies the current solution by the use of the greedy force and the trail systems. We also propose ways to reduce the computational effort associated with each ant decision. Such a new and general ant methodology is then applied to the well-known k-colouring problem, which is NP-hard. Computational experiments give evidence that our algorithm is competitive with the best colouring methods. Journal of the Operational Research Society (2010) 61, 819-826. doi:10.1057/jors.2009.27