Population Size vs. Mutation Strength for the (1+λ) EA on OneMax

Christian Gießen, Carsten Witt

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

Abstract

The (1+1) EA with mutation probability c/n, where c>0 is an arbitrary constant, is studied for the classical OneMax function. Its expected optimization time is analyzed exactly (up to lower order terms) as a function of c and λ. It turns out that 1/n is the only optimal mutation probability if λ=o(ln n ln ln n/ln ln ln n), which is the cut-off point for linear mnspeed-up. However, if λ is above this cut-off point then the standard mutation probability 1/n is no longer the only optimal choice. Instead, the expected number of generations is (up to lower order terms) independent of c, irrespectively of it being less than 1 or greater. The results are obtained by a careful study of order statistics of the binomial distribution and variable drift theorems for upper and lower bounds.
Original languageEnglish
Title of host publicationProceedings of the Genetic and Evolutionary Computation Conference (GECCO '15)
PublisherAssociation for Computing Machinery
Publication date2015
Pages1439-1446
ISBN (Print)978-1-4503-3472-3
DOIs
Publication statusPublished - 2015
EventGenetic and Evolutionary Computation Conference (GECCO 2015) - Madrid, Spain
Duration: 11 Jul 201515 Jul 2015
Conference number: 24
http://www.sigevo.org/gecco-2015/

Conference

ConferenceGenetic and Evolutionary Computation Conference (GECCO 2015)
Number24
CountrySpain
CityMadrid
Period11/07/201515/07/2015
Internet address

Keywords

  • Runtime Analysis
  • Populations
  • Mutation

Cite this