Abstract:

When solving a combinatorial optimization problem with the Ant Colony Optimization (ACO) metaheuristic, one usually has to find a compromise between guiding or diversifying the search. Indeed, ACO uses pheromone to attract ants. On one hand, one can increase the sensibility of ants to pheromone trails, so that they converge quicker towards a solution. However, on the other hand, one also has to favor the exploratory behaviour of ants in order to more widely explore the search space and find better solutions.

In this paper, we first study the influence of the $\alpha$ and $\rho$ parameters of ACO algorithms on the exploratory behaviour of ants. We then study the evolution of the impact of pheromone during the resolution with respect to its cost's management. We finally propose to introduce a preprocessing step that actually favors a larger exploration of the search space, at the beginning of the search, at a lower cost. We illustrate our approach with Ant-Solver, an ACO algorithm that has been designed to solve Constraint Satisfaction Problems, and we show on random binary problems that this preprocessing step allows Ant-Solver to find better solutions more quickly.
Full paper (postscript)