Runtime analysis for self-adaptive mutation rates

Benjamin Doerr, Carsten Witt, Jing Yang

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

342 Downloads (Pure)

Abstract

We propose and analyze a self-adaptive version of the (1,) evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis on the OneMax benchmark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time (number of fitness evaluations) of O(n /log + n log n). This time is asymptotically smaller than the optimization time of the classic (1,) EA and (1 +) EA for all static mutation rates and best possible among all -parallel mutation-based unbiased black-box algorithms. Our result shows that self-adaptation in evolutionary computation can find complex optimal parameter settings on the fly. At the same time, it proves that a relatively complicated self-adjusting scheme for the mutation rate proposed by Doerr et al. (GECCO 2017) can be replaced by our simple endogenous scheme. Moreover, the paper contributes new tools for the analysis of the two-dimensional drift processes arising in self-adaptive EAs, including bounds on occupation probabilities in processes with non-constant drift.
Original languageEnglish
Title of host publication2018 Proceedings of the Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery
Publication date2018
Pages1475-1482
ISBN (Print)978-1-4503-5618-3
DOIs
Publication statusPublished - 2018
Event2018 Genetic and Evolutionary Computation Conference - Kyoto Terrsa, Kyoto, Japan
Duration: 15 Jul 201819 Jul 2018

Conference

Conference2018 Genetic and Evolutionary Computation Conference
LocationKyoto Terrsa
Country/TerritoryJapan
CityKyoto
Period15/07/201819/07/2018

Keywords

  • Self-adaptive evolutionary algorithms
  • Theory
  • Run-time analysis

Fingerprint

Dive into the research topics of 'Runtime analysis for self-adaptive mutation rates'. Together they form a unique fingerprint.

Cite this