Paper Info
Title
Runtime analysis of ant colony optimization on dynamic shortest path problems.
Abstract
A simple ACO algorithm called λ-MMAS for dynamic variants of the single-destination shortest paths problem is studied by rigorous runtime analyses. Building upon previous results for the special case of 1-MMAS, it is studied to what extent an enlarged colony using $\lambda$ ants per vertex helps in tracking an oscillating optimum. It is shown that easy cases of oscillations can be tracked by a constant number of ants. However, the paper also identifies more involved oscillations that with overwhelming probability cannot be tracked with any polynomial-size colony. Finally, parameters of dynamic shortest-path problems which make the optimum difficult to track are discussed. Experiments illustrate theoretical findings and conjectures.
Year
DOI
Venue
2013
10.1145/2463372.2463567
Theoretical Computer Science
Keywords
DocType
Volume
enlarged colony,overwhelming probability,runtime analysis,dynamic variant,previous result,ant colony optimization,easy case,polynomial-size colony,rigorous runtime analysis,dynamic shortest path problem,involved oscillation,constant number,dynamic shortest-path problem,dynamic problems
Conference
561
Issue
ISSN
Citations 
PA
0304-3975
13
PageRank 
References 
Authors
0.59
21
2
Name
Order
Citations
PageRank
Andrei Lissovoi1677.69
Carsten Witt298759.83