Refined Runtime Analysis of a Basic Ant Colony Optimization Algorithm

Neumann and Witt (2006) analyzed the runtime of the basic ant colony optimization (ACO) algorithm {\sc 1-Ant} on pseudo-boolean optimization problems. For the problem {\sc OneMax} they showed how the runtime depends on the evaporation factor. In particular, they proved a phase transition from exponential to polynomial runtime. In this work, we simplify the view on this problem by an appropriate translation of the pheromone model. This results in a profound simplification of the pheromone update rule and, by that, a refinement of the results of Neumann and Witt. In particular, we show how the exponential runtime bound gradually changes to a polynomial bound inside the phase of transition