Self-adjusting Population Sizes for Non-elitist Evolutionary Algorithms: Why Success Rates Matter

Mario Alejandro Hevia Fajardo, Dirk Sudholt*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

66 Downloads (Pure)

Abstract

Evolutionary algorithms (EAs) are general-purpose optimisers that come with several parameters like the sizes of parent and offspring populations or the mutation rate. It is well known that the performance of EAs may depend drastically on these parameters. Recent theoretical studies have shown that self-adjusting parameter control mechanisms that tune parameters during the algorithm run can provably outperform the best static parameters in EAs on discrete problems. However, the majority of these studies concerned elitist EAs and we do not have a clear answer on whether the same mechanisms can be applied for non-elitist EAs. We study one of the best-known parameter control mechanisms, the one-fifth success rule, to control the offspring population size λ in the non-elitist (1,λ) EA. It is known that the (1,λ) EA has a sharp threshold with respect to the choice of λ where the expected runtime on the benchmark function ONEMAX changes from polynomial to exponential time. Hence, it is not clear whether parameter control mechanisms are able to find and maintain suitable values of λ . For ONEMAX we show that the answer crucially depends on the success rate s (i. e. a one-(s+1) -th success rule). We prove that, if the success rate is appropriately small, the self-adjusting (1,λ) EA optimises ONEMAX in O(n) expected generations and O(nlogn) expected evaluations, the best possible runtime for any unary unbiased black-box algorithm. A small success rate is crucial: we also show that if the success rate is too large, the algorithm has an exponential runtime on ONEMAX and other functions with similar characteristics.
Original languageEnglish
Pages (from-to)526–565
Number of pages40
JournalAlgorithmica
Volume86
Issue number2
Early online date24 Jul 2023
DOIs
Publication statusPublished - Feb 2024

Keywords

  • Evolutionary algorithms
  • Parameter control
  • Theory
  • Runtime analysis
  • Non-elitism

Fingerprint

Dive into the research topics of 'Self-adjusting Population Sizes for Non-elitist Evolutionary Algorithms: Why Success Rates Matter'. Together they form a unique fingerprint.

Cite this