On the impact of mutation-selection balance on the runtime of evolutionary algorithms

Per Kristian LEHRE, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

58 Citations (Scopus)

Abstract

The interplay between mutation and selection plays a fundamental role in the behavior of evolutionary algorithms (EAs). However, this interplay is still not completely understood. This paper presents a rigorous runtime analysis of a non-elitist population-based EA that uses the linear ranking selection mechanism. The analysis focuses on how the balance between parameter η, controlling the selection pressure in linear ranking, and parameter χ controlling the bit-wise mutation rate, impacts the runtime of the algorithm. The results point out situations where a correct balance between selection pressure and mutation rate is essential for finding the optimal solution in polynomial time. In particular, it is shown that there exist fitness functions which can only be solved in polynomial time if the ratio between parameters η and χ is within a narrow critical interval, and where a small change in this ratio can increase the runtime exponentially. Furthermore, it is shown quantitatively how the appropriate parameter choice depends on the characteristics of the fitness function. In addition to the original results on the runtime of EAs, this paper also introduces a very useful analytical tool, i.e., multi-type branching processes, to the runtime analysis of non-elitist population-based EAs. © 2011 IEEE.
Original languageEnglish
Article number5910379
Pages (from-to)225-241
Number of pages17
JournalIEEE Transactions on Evolutionary Computation
Volume16
Issue number2
Early online date28 Jun 2011
DOIs
Publication statusPublished - Apr 2012
Externally publishedYes

Bibliographical note

This work was supported by EPSRC, under Grant EP/D052785/1, and by Deutsche Forschungsgemeinschaft, under Grant WI 3552/1-1. This work is based on earlier work in [18], available at http://doi.acm.org/10.1145/1527125.1527133.

Keywords

  • Computational complexity
  • evolutionary computation
  • randomized heuristics
  • runtime analysis of evolutionary algorithms
  • selection pressure

Fingerprint

Dive into the research topics of 'On the impact of mutation-selection balance on the runtime of evolutionary algorithms'. Together they form a unique fingerprint.

Cite this