Ant Colony Optimization for Stochastic Shortest Path Problems

C Horoba, Dirk Sudholt, M Pelikan, J Branke

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publication Proceedings of the 12th annual conference on Genetic and evolutionary computation
Pages1465-1472
Number of pages8
DOIs
Publication statusPublished - 11 Jul 2010
EventProceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10) - New York, United States
Duration: 11 Jul 2010 → …

Conference

ConferenceProceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10)
Country/TerritoryUnited States
CityNew York
Period11/07/10 → …

Fingerprint

Dive into the research topics of 'Ant Colony Optimization for Stochastic Shortest Path Problems'. Together they form a unique fingerprint.

Cite this