Fast non-elitist evolutionary algorithms with power-law ranking selection

Duc-Cuong Dang, Anton Eremeev, Per Kristian Lehre, Xiaoyu Qin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

116 Downloads (Pure)


Theoretical evidence suggests that non-elitist evolutionary algorithms (EAs) with non-linear selection mechanisms can efficiently overcome broad classes of local optima where elitist EAs fail. However, the analysis assumes a weak selective pressure and mutation rates carefully chosen close to the "error threshold", above which they cease to be efficient. On problems easier for hill-climbing, the populations may slow down these algorithms, leading to worse runtime compared with variants of the elitist (1+1) EA.

Here, we show that a non-elitist EA with power-law ranking selection leads to fast runtime on easy benchmark problems, while maintaining the capability of escaping certain local optima where the elitist EAs spend exponential time in the expectation.

We derive a variant of the level-based theorem which accounts for power-law distributions. For classical theoretical benchmarks, the expected runtime is stated with small leading constants. For complex, multi-modal fitness landscapes, we provide sufficient conditions for polynomial optimisation, formulated in terms of deceptive regions sparsity and fitness valleys density. We derive the error threshold and show extreme tolerance to high mutation rates. Experiments on NK-Landscape functions, generated according to the Kauffman's model, show that the algorithm outperforms the (1+1) EA and the univariate marginal distribution algorithm (UMDA).

Original languageEnglish
Title of host publicationGECCO '22
Subtitle of host publicationProceedings of the Genetic and Evolutionary Computation Conference
EditorsJonathan E. Fieldsend
Place of PublicationNew York
PublisherAssociation for Computing Machinery (ACM)
Number of pages9
ISBN (Electronic)9781450392372
Publication statusPublished - 8 Jul 2022
EventGECCO '22: Genetic and Evolutionary Computation Conference - Boston, United States
Duration: 9 Jul 202213 Jul 2022

Publication series

NameGECCO: Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery (ACM)


ConferenceGECCO '22: Genetic and Evolutionary Computation Conference
Abbreviated titleGECCO 2022
Country/TerritoryUnited States

Bibliographical note

Funding Information:
Lehre was supported by a Turing AI Fellowship (EPSRC grant ref EP/V025562/1). Eremeev was funded within the state task of the IM SB RAS, project FWNF-2022-0020.

Publisher Copyright:
© 2022 ACM.


  • Local optima
  • Power-law ranking
  • Runtime Analysis
  • Selection
  • Runtime analysis

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence
  • Theoretical Computer Science


Dive into the research topics of 'Fast non-elitist evolutionary algorithms with power-law ranking selection'. Together they form a unique fingerprint.

Cite this