Paper Info
Title
The Impact of Migration Topology on the Runtime of Island Models in Dynamic Optimization.
Abstract
We introduce a simplified island model with behavior similar to the λ (1+1) islands optimizing the Maze fitness function, and investigate the effects of the migration topology on the ability of the simplified island model to track the optimum of a dynamic fitness function. More specifically, we prove that there exist choices of model parameters for which using a unidirectional ring as the migration topology allows the model to track the oscillating optimum through n Maze-like phases with high probability, while using a complete graph as the migration topology results in the island model losing track of the optimum with overwhelming probability. Additionally, we prove that if migration occurs only rarely, denser migration topologies may be advantageous. This serves to illustrate that while a less-dense migration topology may be useful when optimizing dynamic functions with oscillating behavior, and requires less problem-specific knowledge to determine when migration may be allowed to occur, care must be taken to ensure that a sufficient amount of migration occurs during the optimization process.
Year
DOI
Venue
2016
10.1145/2908812.2908843
GECCO
Field
DocType
Citations 
Complete graph,Topology,Mathematical optimization,Evolutionary algorithm,Computer science,Island model,Fitness function,Network topology,Dynamic problem
Conference
2
PageRank 
References 
Authors
0.37
16
2
Name
Order
Citations
PageRank
Andrei Lissovoi1677.69
Carsten Witt239424.26