Runtime Analysis of a Simple Ant Colony Optimization Algorithm

Abstract

Ant Colony Optimization (ACO) has become quite popular in recent
years. In contrast to many successful applications, the theoretical foundation of
this randomized search heuristic is rather weak. Building up such a
theory is demanded to understand how these heuristics work as well as
to come up with better algorithms for certain problems. Up to now,
only convergence results have been achieved showing that optimal
solutions can be obtained in a finite amount of time. We present the
first runtime analysis of a simple ACO algorithm that
transfers many rigorous results with respect to the expected runtime
of a simple evolutionary algorithm to our algorithm. In addition,
we examine the choice of the evaporation factor, which is a crucial
parameter in such an algorithm, in greater detail and analyze its effect
with respect to the runtime.