Running time analysis of Ant Colony Optimization for shortest path problems

Ant Colony Optimization (ACO) is a modern and very popular optimization paradigm inspired by the ability of ant colonies to find shortest paths between their nest and a food source. Despite its popularity, the theory of ACO is still in its infancy and a solid theoretical foundation is needed. We present bounds on the running time of different ACO systems for shortest path problems. First, we improve previous results by Attiratanasunthron and Fakcharoenphol [Information Processing Letters 105 (3) (2008) 88–92] for single-destination shortest paths and extend their results from DAGs to arbitrary directed graphs. Our upper bound is asymptotically tight for large evaporation factors, holds with high probability, and transfers to the all-pairs shortest paths problem. There, a simple mechanism for exchanging information between ants with different destinations yields a significant improvement. A comparison with evolutionary and genetic approaches indicates that ACO is among the best known metaheuristics for the all-pairs shortest paths problem.