Populations Can Be Essential in Tracking Dynamic Optima

Duc Cuong Dang, Thomas Jansen, Per Lehre

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)
110 Downloads (Pure)

Abstract

Real-world optimisation problems are often dynamic. Previously good solutions must be updated or replaced due to changes in objectives and constraints. It is often claimed that evolutionary algorithms are particularly suitable for dynamic optimisation because a large population can contain different solutions that may be useful in the future. However, rigorous theoretical demonstrations for how populations in dynamic optimisation can be essential are sparse and restricted to special cases. This paper provides theoretical explanations of how populations can be essential in evolutionary dynamic optimisation in a general and natural setting. We describe a natural class of dynamic optimisation problems where a sufficiently large population is necessary to keep track of moving optima reliably. We establish a relationship between the population-size and the probability that the algorithm loses track of the optimum.

Original languageEnglish
Pages (from-to)660-680
Number of pages21
JournalAlgorithmica
Volume78
Issue number2
Early online date26 Aug 2016
DOIs
Publication statusPublished - 1 Jun 2017

Keywords

  • Dynamic optimisation
  • Population-based algorithm
  • Runtime analysis

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Populations Can Be Essential in Tracking Dynamic Optima'. Together they form a unique fingerprint.

Cite this