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 finite
time. We present the first runtime analysis of an ACO algorithm,
which transfers many rigorous results with respect to the runtime of
a simple evolutionary algorithm to our algorithm. Moreover, we
examine the choice of the evaporation factor, a crucial parameter in
ACO algorithms, in detail. By deriving new lower bounds on the tails
of sums of independent Poisson trials, we determine the effect of
the evaporation factor almost completely and prove a phase
transition from exponential to polynomial runtime.