More Precise Runtime Analyses of Non-elitist EAs in Uncertain Environments

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

Authors

Colleges, School and Institutes

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 \textsc{OneMax} and \textsc{LeadingOnes} under prior and posterior noise models, and the dynamic binary value problem (\textsc{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.

Details

Original languageEnglish
Title of host publicationProceedings of the 2021 Genetic and Evolutionary Computation Conference
Publication statusAccepted/In press - 2021

Keywords

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