Back to the program.
Keeping the Ants Critical: A Fresh Look at Diversity Control
Dr. Bernd Meyer
Monash University
Dept. of Computer Science
Melbourne, Australia
bernd.meyer@acm.org

Abstract

Motivated by dynamic constraint optimization problems we study novel ways for balancing diversification and intensification in Ant Optimization algorithms. Virtually all published diversity control mechanisms in single-colony approaches can be classified as either modifications of the pheromone deposit function or modifications of the probabilistic selection function. The common idea is essentially to avoid full convergence or at least to slow it down significantly. Complementary to such methods, we suggest a surprisingly simple idea: Sufficient diversity can be achieved by using a fast converging search algorithm, which is artificially confined to the critical phase of its convergence dynamics. Secondly, we analyze the influence of a parameter that does not seem to have received sufficient attention in the literature: Alpha, the exponent on the pheromone level in the selection function. Our studies suggest that Alpha does not only determine diversity and convergence behaviour, but also that a variable Alpha can be used to render ant algorithms more robust against incorrect parameter choices. This talk is a presentation of work in progress. We discuss the underlying ideas and derive an Algorithm ccAS for which we present preliminary results on standard benchmarks. While our work is fundamentally an "in principal" investigation of the basic convergence mechanisms and no fine tuning has been performed as yet, these results appear encouraging.

Keywords

optimization, convergence dynamics, search, meta-heuristics, ACO, ant-based algorithms