A Simple Ant Colony Optimizer for Stochastic Shortest Path Problems

Ant Colony Optimization (ACO) is a popular optimization paradigm inspired by the capabilities of natural ant colonies of finding shortest paths between their nest and a food source. This has led to many successful applications for various combinatorial problems. The reason for the success of ACO, however, is not well understood and there is a need for a rigorous theoretical foundation. We analyze the running time of a simple ant colony optimizer for stochastic shortest path problems where edge weights are subject to noise that reflects delays and uncertainty. In particular, we consider various noise models, ranging from general, arbitrary noise with possible dependencies to more specific models such as independent gamma-distributed noise. The question is whether the ants can find or approximate shortest paths in the presence of noise. We characterize instances where the ants can discover the real shortest paths efficiently. For general instances we prove upper bounds for the time until the algorithm finds reasonable approximations. Contrariwise, for independent gamma-distributed noise we present a graph where the ant system needs exponential time to find a good approximation. The behavior of the ant system changes dramatically when the noise is perfectly correlated as then the ants find shortest paths efficiently. Our results shed light on trade-offs between the noise strength, approximation guarantees, and expected running times.