Analysis of Ant Colony Optimization and Population-Based Evolutionary Algorithms on Dynamic Problems

This thesis presents new running time analyses of nature-inspired algorithms on various dynamic problems. It aims to identify and analyse the features of algorithms and problem classes which allow efficient optimization to occur in the presence of dynamic behaviour. We consider the following settings:

λ-MMAS on Dynamic Shortest Path Problems. We investigate how in-creasing the number of ants simulated per iteration may help an ACO algorithm to track optimum in a dynamic problem. It is shown that while a constant number of ants per-vertex is sufficient to track some oscillations, there also exist more complex oscillations that cannot be tracked with a polynomial-size colony.

MMAS and (μ+1) EA on Maze We analyse the behaviour of a (μ + 1) EA with genotype diversity on a dynamic fitness function Maze, extended to a finite-alphabet search space. We prove that the (μ + 1) EA is able to track the dynamic optimum for finite alphabets up to size μ, while MMAS is able to do so for any finite alphabet size.

Parallel Evolutionary Algorithms on Maze. We prove that while a (1 + λ) EA is unable to track the optimum of the dynamic fitness function Maze for offspring population size up to λ = O(n1-ε”), a simple island model with Ω(log n) islands is able to do so if the migration interval is chosen appropriately.

Migration Topology in Island Models. We investigate the impact of the migration topology on the performance of an island model optimizing a Maze-like dynamic function, demonstrating that in some cases, a less-dense migration topology is preferable to a complete migration topology.

(1+1) EA on Generalized Dynamic OneMax. We analyze the (1 + 1) EA on dynamically changing OneMax, re-proving known results on first hitting times using modern drift analysis, and providing a new anytime analysis showing how closely the EA can track the dynamically moving optimum over time. These results are also extended to a finite-alphabet search space.