The (1+λ) evolutionary algorithm with self-adjusting mutation rate

Benjamin Doerr, Carsten Witt, Christian Gießen, Jing Yang

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

307 Downloads (Pure)

Abstract

We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring. We analyze how the (1 + A) evolutionary algorithm with this self-adjusting mutation rate optimizes the OneMax test function. We prove that this dynamic version of the (1 + A) EA finds the optimum in an expected optimization time (number of fitness evaluations) of O(nA/log A + n log n). This time is asymptotically smaller than the optimization time of the classic (1 + A) EA. Previous work shows that this performance is best-possible among all A-parallel mutation-based unbiased black-box algorithms. This result shows that the new way of adjusting the mutation rate can find optimal dynamic parameter values on the fly. Since our adjustment mechanism is simpler than the ones previously used for adjusting the mutation rate and does not have parameters itself, we are optimistic that it will find other applications.
Original languageEnglish
Title of host publicationProceedings of 2017 Genetic and Evolutionary Computation Conference
Number of pages8
PublisherAssociation for Computing Machinery
Publication date2017
Pages1351-1358
ISBN (Print)9781450349208
DOIs
Publication statusPublished - 2017
Event2017 Genetic and Evolutionary Computation Conference - VIENNA HOUSE ANDEL'S BERLIN Landsberger Allee 106, Berlin, Germany
Duration: 15 Jul 201719 Jul 2017
http://gecco-2017.sigevo.org/index.html/HomePage

Conference

Conference2017 Genetic and Evolutionary Computation Conference
LocationVIENNA HOUSE ANDEL'S BERLIN Landsberger Allee 106
CountryGermany
CityBerlin
Period15/07/201719/07/2017
SponsorAssociation for Computing Machinery, Evolv Technologies, Uber AI Labs
Internet address

Keywords

  • Dynamic parameter control
  • Mutation
  • Runtime analysis
  • Optimization Techniques
  • Optimization
  • Adjustment mechanisms
  • Black box algorithms
  • Current mutations
  • Expected optimization time
  • Fitness evaluations
  • Run-time analysis
  • Evolutionary algorithms

Fingerprint Dive into the research topics of 'The (1+λ) evolutionary algorithm with self-adjusting mutation rate'. Together they form a unique fingerprint.

Cite this