Paper Info
Title
The benefit of migration in parallel evolutionary algorithms
Abstract
Parallelization is becoming a more and more important issue for solving difficult optimization problems. Various implementations of parallel evolutionary algorithms (EAs) have been applied in the past decades. Island models combine phases of independent evolution with migration where genetic information is spread out to neighbored islands. Compared to panmictic models, this mechanism can lead to an increased diversity within the population. We perform a first rigorous runtime analysis for island models and construct a function where phases of independent evolution as well as communication among the islands is essential. A simple island model with migration finds a global optimum in polynomial time, while panmictic populations as well as island models without migration need exponential time, with very high probability. Our results lead to new insights on the usefulness of migration and contribute to the theoretical foundation of parallel EAs
Year
DOI
Venue
2010
10.1145/1830483.1830687
GECCO
Keywords
Field
DocType
difficult optimization problem,parallel eas,simple island model,neighbored island,parallel evolutionary algorithm,panmictic population,polynomial time,migration need exponential time,island model,independent evolution,migration,optimization problem,genetics
Population,Mathematical optimization,Evolutionary algorithm,Computer science,Global optimum,Island model,Time complexity,Optimization problem
Conference
Citations 
PageRank 
References 
18
1.18
10
Authors
2
Name
Order
Citations
PageRank
Jörg Lässig117522.53
Dirk Sudholt2106364.62