1 Department of Applied Mathematics and Computer Science, Technical University of Denmark2 Algorithms and Logic, Department of Applied Mathematics and Computer Science, Technical University of Denmark
A simple ACO algorithm called lambda-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.
Theoretical Computer Science, 2015, Vol 561, Issue Part A, p. 73-85
COMPUTER; Ant colony optimization; Shortest paths; Dynamic problems; Runtime analysis