We consider Ant Colony Optimization (ACO) for stochastic shortest path problems where edge weights are subject to noise that reflects delays and uncertainty. The question is whether the ants can find or approximate shortest paths in the presence of noise. We first prove a general upper bound for the time until the algorithm finds an approximation for arbitrary, independent noise values. For independent gamma-distributed noise we prove lower bounds for the time until a good approximation is found. We construct a graph where the ants cannot find a reasonable approximation, even in exponential time. The last result changes when the noise is perfectly correlated as then the ants find shortest paths efficiently.
|Title of host publication||Proceedings of the 12th annual conference on Genetic and evolutionary computation|
|Number of pages||8|
|Publication status||Published - 11 Jul 2010|
|Event||Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10) - New York, United States|
Duration: 11 Jul 2010 → …
|Conference||Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10)|
|Period||11/07/10 → …|