Session:

LBP - Late Breaking Papers

Title:

Convergence Control in ACO

Authors:

Bernd Meyer

Abstract:

Ant Colony Optimization (ACO) is a recent stochastic meta-heuristic inspired by the foraging behaviour of real ants. As for all meta-heuristics the balance between learning based on previous solutions (intensification) and exploration of the search space (diversification) is of crucial importance. The present paper explores a novel approach to diversity control in ACO. The common idea of most diversity control mechanisms is to avoid or slow down full convergence. We suggest to instead use a fast converging search algorithm that is artificially confined to the critical phase of its convergence dynamics. We also analyze the influence of an ACO parameter that does not seem to have received sufficient attention in the ACO literature: alpha, the exponent on the pheromone level in the probabilistic choice function. Our studies suggest that $\alpha$ does not only qualitatively determine diversity and convergence behaviour, but also that a variable alpha can be used to render ant algorithms more robust. Based on these ideas we construct an Algorithm ccAS for which we present some encouraging results on standard benchmarks.