Optimal mutation rates for the (1+λ) EA on OneMax

Christian Gießen, Carsten Witt

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

Abstract

We study the (1 + λ) EA with mutation probability c/n, where c > 0 is a constant, on the ONEMAX problem. Using an improved variable drift theorem, we show that upper and lower bounds on the expected runtime of the (1+λ) EA obtained from variable drift theorems are at most apart by a small lower order term if the exact drift is known. This reduces the analysis of expected optimization time to finding an exact expression for the drift.

We then give an exact closed-form expression for the drift and develop a method to approximate it very efficiently, enabling us to determine approximate optimal mutation rates for the (1+λ) EA for various parameter settings of c and λ and also for moderate sizes of n. This makes the need for potentially lengthy and costly experiments in order to optimize the parameters unnecessary.

Interestingly, even for moderate n and not too small λ it turns out that mutation rates up to 10% larger than the asymptotically optimal rate 1/n minimize the expected runtime. However, in absolute terms the expected runtime does not change by much when replacing 1/n with the optimal mutation rate.
Original languageEnglish
Title of host publicationProceedings of the Genetic and Evolutionary Computation Conference (GECCO '16)
PublisherAssociation for Computing Machinery
Publication date2016
Pages1147-1154
ISBN (Print)978-1-4503-4206-3
DOIs
Publication statusPublished - 2016
Event2016 Genetic and Evolutionary Computation Conference - Denver, United States
Duration: 20 Jul 201624 Jul 2016
http://gecco-2016.sigevo.org/index.html/HomePage#&panel1-1

Conference

Conference2016 Genetic and Evolutionary Computation Conference
CountryUnited States
CityDenver
Period20/07/201624/07/2016
Internet address

Keywords

  • Runtime Analysis
  • Populations
  • Mutation

Fingerprint Dive into the research topics of 'Optimal mutation rates for the (1+λ) EA on OneMax'. Together they form a unique fingerprint.

Cite this