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.
Proceeding of the Fifteenth Annual Conference on Genetic and Evolutionary Computation, 2013, p. 1605-1612
Ant Colony Optimization; Shortest Paths; Dynamic Problems; Runtime Analysis
Main Research Area:
Genetic and Evolutionary Computation Conference (GECCO 2013)Genetic and Evolutionary Computation Conference