Dynamic evolutionary optimisation: An analysis of frequency and magnitude of change

Philipp ROHLFSHAGEN, Per Kristian LEHRE, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

62 Citations (Scopus)

Abstract

In this paper, we rigorously analyse how the magnitude and frequency of change may affect the performance of the algorithm (1+1) EAdyn on a set of artificially designed pseudo-Boolean functions, given a simple but well-defined dynamic framework. We demonstrate some counter-intuitive scenarios that allow us to gain a better understanding of how the dynamics of a function may affect the runtime of an algorithm. In particular, we present the function Magnitude, where the time it takes for the (1+1) EAdyn to relocate the global optimum is less than n2log n (i.e., efficient) with overwhelming probability if the magnitude of change is large. For small changes of magnitude, on the other hand, the expected time to relocate the global optimum is eΩ(n) (i.e., highly inefficient). Similarly, the expected runtime of the (1+1) EAdyn on the function Balance is O(n2) (efficient) for a high frequencies of change and n Ω(√n) (highly inefficient) for low frequencies of change. These results contribute towards a better understanding of dynamic optimisation problems in general and show how traditional analytical methods may be applied in the dynamic case. Copyright 2009 ACM.
Original languageEnglish
Title of host publicationProceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009
Pages1713-1720
Number of pages8
DOIs
Publication statusPublished - 8 Jul 2009
Externally publishedYes

Keywords

  • Dynamic evolutionary computation
  • Evolutionary algorithms
  • Runtime analysis

Fingerprint

Dive into the research topics of 'Dynamic evolutionary optimisation: An analysis of frequency and magnitude of change'. Together they form a unique fingerprint.

Cite this