A Runtime Analysis of Parallel Evolutionary Algorithms in Dynamic Optimization

A simple island model with [Formula: see text] islands and migration occurring after every [Formula: see text] iterations is studied on the dynamic fitness function Maze. This model is equivalent to a [Formula: see text] EA if [Formula: see text] , i. e., migration occurs during every iteration. It is proved that even for an increased offspring population size up to [Formula: see text] , the [Formula: see text] EA is still not able to track the optimum of Maze. If the migration interval is chosen carefully, the algorithm is able to track the optimum even for logarithmic [Formula: see text] . The relationship of [Formula: see text] , and the ability of the island model to track the optimum is then investigated more closely. Finally, experiments are performed to supplement the asymptotic results, and investigate the impact of the migration topology.