A Runtime Analysis of Parallel Evolutionary Algorithms in Dynamic Optimization

Andrei Lissovoi, Carsten Witt

Research output: Contribution to journalJournal articleResearchpeer-review

392 Downloads (Pure)

Abstract

A simple island model with (Formula presented.) islands and migration occurring after every (Formula presented.) iterations is studied on the dynamic fitness function Maze. This model is equivalent to a (Formula presented.) EA if (Formula presented.), i. e., migration occurs during every iteration. It is proved that even for an increased offspring population size up to (Formula presented.), the (Formula presented.) 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 presented.). The relationship of (Formula presented.), 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.
Original languageEnglish
JournalAlgorithmica
Volume78
Issue number2
Pages (from-to)641–659
ISSN0178-4617
DOIs
Publication statusPublished - 2017

Bibliographical note

© The Author(s) 2016. This article is published with open access at Springerlink.com

Keywords

  • Dynamic problems
  • Evolutionary algorithms
  • Island models
  • Populations
  • Runtime analysis

Fingerprint Dive into the research topics of 'A Runtime Analysis of Parallel Evolutionary Algorithms in Dynamic Optimization'. Together they form a unique fingerprint.

Cite this