Ant colony optimization for stochastic shortest path problems

Autor:	Christian Horoba, Dirk Sudholt
Rok vydání:	2010
Předmět:	Euclidean shortest path Mathematical optimization Shortest Path Faster Algorithm Computer Science::Neural and Evolutionary Computation Shortest path problem Applied mathematics K shortest path routing Canadian traveller problem Yen's algorithm Constrained Shortest Path First Distance Mathematics
Zdroj:	GECCO
DOI:	10.1145/1830483.1830750
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::ceba49293ab24cbf07b70a6c50936ae7 https://doi.org/10.1145/1830483.1830750 Zobrazit plný text záznamu