The Benefit of Migration in Parallel Evolutionary Algorithms

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

doi:10.1145/1830483.1830687

The Benefit of Migration in Parallel Evolutionary Algorithms

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Proceedings of the 12th annual conference on Genetic and evolutionary computation
Pages	1105-1112
Number of pages	8
DOIs	https://doi.org/10.1145/1830483.1830687
Publication status	Published - 11 Jul 2010
Event	Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10) - New York, United States Duration: 11 Jul 2010 → …

Conference

Conference	Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10)
Country/Territory	United States
City	New York
Period	11/07/10 → …

Access to Document

10.1145/1830483.1830687

Cite this

@inproceedings{37470183ade9429ebb0e281f0919535b,

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",

author = "J L{\"a}ssig and Dirk Sudholt and M Pelikan and J Branke",

year = "2010",

month = jul,

day = "11",

doi = "10.1145/1830483.1830687",

language = "English",

isbn = "978-1-4503-0072-8",

pages = "1105--1112",

booktitle = "Proceedings of the 12th annual conference on Genetic and evolutionary computation",

note = "Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10) ; Conference date: 11-07-2010",

}

Lässig, J, Sudholt, D, Pelikan, M & Branke, J 2010, The Benefit of Migration in Parallel Evolutionary Algorithms. in Proceedings of the 12th annual conference on Genetic and evolutionary computation. pp. 1105-1112, Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10), New York, United States, 11/07/10. https://doi.org/10.1145/1830483.1830687

TY - GEN

T1 - The Benefit of Migration in Parallel Evolutionary Algorithms

AU - Lässig, J

AU - Sudholt, Dirk

AU - Pelikan, M

AU - Branke, J

PY - 2010/7/11

Y1 - 2010/7/11

N2 - 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

AB - 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

U2 - 10.1145/1830483.1830687

DO - 10.1145/1830483.1830687

M3 - Conference contribution

SN - 978-1-4503-0072-8

SP - 1105

EP - 1112

BT - Proceedings of the 12th annual conference on Genetic and evolutionary computation

T2 - Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10)

Y2 - 11 July 2010

ER -

The Benefit of Migration in Parallel Evolutionary Algorithms

Abstract

Conference

Access to Document

Fingerprint

Cite this