More precise runtime analyses of non-elitist EAs in uncertain environments

Per Kristian Lehre, Xiaoyu Qin

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

Abstract

Real-world optimisation problems often involve uncertainties. In the past decade, several rigorous analysis results for evolutionary algorithms (EAs) on discrete problems show that EAs can cope with low-level uncertainties, and sometimes benefit from uncertainties. Using non-elitist EAs with large population size is a promising approach to handle higher levels of uncertainties. However, the performance of non-elitist EAs in some common fitness-uncertainty scenarios is still unknown.

We analyse the runtime of non-elitist EAs on OneMax and LeadingOnes under prior and posterior noise models, and the dynamic binary value problem (DynBV). Our analyses are more extensive and precise than previous analyses of non-elitist EAs. In several settings, we prove that the non-elitist EAs beat the current state of the art results. Previous work shows that the population size and mutation rate can dramatically impact the performance of non-elitist EAs. The optimal choices of these parameters depend on the level of uncertainties in the fitness functions. We provide more precise guidance on how to choose mutation rate and population size as a function of the level of uncertainties.
Original languageEnglish
Title of host publicationGECCO '21
Subtitle of host publicationProceedings of the 2021 Genetic and Evolutionary Computation Conference
EditorsFrancisco Chicano
Place of PublicationNew York
PublisherAssociation for Computing Machinery (ACM)
Pages1160-1168
Number of pages9
ISBN (Print)9781450383509
DOIs
Publication statusPublished - 26 Jun 2021
EventGenetic and Evolutionary Computation Conference -
Duration: 10 Jul 202114 Jul 2021

Publication series

NameGenetic and Evolutionary Computation Conference (GECCO)
PublisherACM

Conference

ConferenceGenetic and Evolutionary Computation Conference
Abbreviated titleGECCO 2021
Period10/07/2114/07/21

Bibliographical note

Funding Information:
This work was supported by a Turing AI Fellowship (EPSRC grant ref EP/V025562/1).

Publisher Copyright:
© 2021 ACM.

Keywords

  • non-elitist evolutionary algorithms
  • uncertain environments
  • noisy optimisation
  • dynamic optimisation
  • runtime analysis

Fingerprint

Dive into the research topics of 'More precise runtime analyses of non-elitist EAs in uncertain environments'. Together they form a unique fingerprint.

Cite this