Self-adaptation of mutation rates in non-elitist populations

Duc Cuong Dang, Per Kristian Lehre*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

36 Citations (Scopus)


The runtime of evolutionary algorithms (EAs) depends critically on their parameter settings, which are often problem-specific. Automated schemes for parameter tuning have been developed to alleviate the high costs of manual parameter tuning. Experimental results indicate that self-adaptation, where parameter settings are encoded in the genomes of individuals, can be effective in continuous optimisation. However, results in discrete optimisation have been less conclusive. Furthermore, a rigorous runtime analysis that explains how self-adaptation can lead to asymptotic speedups has been missing. This paper provides the first such analysis for discrete, population-based EAs. We apply levelbased analysis to show how a self-adaptive EA is capable of fine-tuning its mutation rate, leading to exponential speedups over EAs using fixed mutation rates.

Original languageEnglish
Title of host publicationPPSN 2016
Subtitle of host publicationParallel Problem Solving from Nature – PPSN XIV
EditorsJulia Handl, Emma Hart, Peter R. Lewis, Manuel López-Ibáñez, Gabriela Ochoa, Ben Paechter
PublisherSpringer Verlag
Number of pages11
ISBN (Electronic)9783319458236
ISBN (Print)9783319458229
Publication statusPublished - 31 Aug 2016
Event14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 - Edinburgh, United Kingdom
Duration: 17 Sept 201621 Sept 2016

Publication series

NameLecture Notes in Computer Science (LNCS)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameTheoretical Computer Science and General Issues (LNTCS)


Conference14th International Conference on Parallel Problem Solving from Nature, PPSN 2016
Country/TerritoryUnited Kingdom

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Self-adaptation of mutation rates in non-elitist populations'. Together they form a unique fingerprint.

Cite this