The Benefit of Migration in Parallel Evolutionary Algorithms

J Lässig, Dirk Sudholt, M Pelikan, J Branke

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Citations (Scopus)

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
Original languageEnglish
Title of host publicationProceedings of the 12th annual conference on Genetic and evolutionary computation
Pages1105-1112
Number of pages8
DOIs
Publication statusPublished - 11 Jul 2010
EventProceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10) - New York, United States
Duration: 11 Jul 2010 → …

Conference

ConferenceProceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10)
Country/TerritoryUnited States
CityNew York
Period11/07/10 → …

Fingerprint

Dive into the research topics of 'The Benefit of Migration in Parallel Evolutionary Algorithms'. Together they form a unique fingerprint.

Cite this