Projects per year
Abstract
This thesis presents new running time analyses of natureinspired 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 increasing 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 pervertex is sufficient to track some oscillations, there also exist more complex oscillations that cannot be tracked with a polynomialsize 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 finitealphabet 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 Mazelike dynamic function, demonstrating that in some cases, a lessdense 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, reproving 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 finitealphabet search space.
λMMAS on Dynamic Shortest Path Problems. We investigate how increasing 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 pervertex is sufficient to track some oscillations, there also exist more complex oscillations that cannot be tracked with a polynomialsize 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 finitealphabet 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 Mazelike dynamic function, demonstrating that in some cases, a lessdense 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, reproving 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 finitealphabet search space.
Original language  English 

Place of Publication  Kgs. Lyngby 

Publisher  DTU Transport 
Number of pages  130 
Publication status  Published  2016 
Series  DTU Compute PHD2016 

Number  404 
ISSN  09093192 
Fingerprint Dive into the research topics of 'Analysis of Ant Colony Optimization and PopulationBased Evolutionary Algorithms on Dynamic Problems'. Together they form a unique fingerprint.
Projects
 1 Finished

Exploring the boundaries of natureinspired algorithms
Lissovoi, A., Witt, C., Fischer, P., Lehre, P. K. & PrügelBennett, A.
Technical University of Denmark
01/10/2012 → 31/03/2016
Project: PhD