The choice of the offspring population size in the (1,λ) EA

Jonathan Rowe, Dirk Sudholt

Research output: Contribution to conference (unpublished)Paperpeer-review

44 Citations (Scopus)
267 Downloads (Pure)

Abstract

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,λ) EA. We establish a sharp threshold at λ = log{\frac{e}{e-1}} n ≈5 log10 n between exponential and polynomial running times on OneMax. For any smaller value, the (1,λ) EA needs exponential time on every function that has only one global optimum. We also consider arbitrary unimodal functions and show that the threshold can shift towards larger offspring population sizes. Finally, we investigate the relationship between the offspring population size and arbitrary mutation rates on OneMax. We get sharp thresholds for λ that decrease with the mutation rate. This illustrates the balance between selection and mutation.
Original languageEnglish
Pages1349-1356
DOIs
Publication statusPublished - 2012
Event14th International Conference on Genetic and Evolutionary Computation - GECCO 12 - Philadelphia, United States
Duration: 7 Jul 201211 Jul 2012

Conference

Conference14th International Conference on Genetic and Evolutionary Computation - GECCO 12
Country/TerritoryUnited States
CityPhiladelphia
Period7/07/1211/07/12

Keywords

  • Evolutionary algorithms
  • comma strategies
  • offspring populations
  • runtime analysis
  • drift analysis
  • theory

Fingerprint

Dive into the research topics of 'The choice of the offspring population size in the (1,λ) EA'. Together they form a unique fingerprint.

Cite this