hide
Free keywords:
-
Abstract:
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.
