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

Abstract

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 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
PublisherAssociation for Computing Machinery (ACM)
Publication statusAccepted/In press - 25 Mar 2022
EventGECCO '22: Genetic and Evolutionary Computation Conference - Boston, United States
Duration: 9 Jul 202213 Jul 2022

Conference

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

Bibliographical note

Not yet published as of 13/05/2022.

Keywords

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

Fingerprint

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

Cite this