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.
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 language | English |
---|---|
Title of host publication | GECCO '21 |
Subtitle of host publication | Proceedings of the 2021 Genetic and Evolutionary Computation Conference |
Editors | Francisco Chicano |
Place of Publication | New York |
Publisher | Association for Computing Machinery (ACM) |
Pages | 1160-1168 |
Number of pages | 9 |
ISBN (Print) | 9781450383509 |
DOIs | |
Publication status | Published - 26 Jun 2021 |
Event | Genetic and Evolutionary Computation Conference - Duration: 10 Jul 2021 → 14 Jul 2021 |
Publication series
Name | Genetic and Evolutionary Computation Conference (GECCO) |
---|---|
Publisher | ACM |
Conference
Conference | Genetic and Evolutionary Computation Conference |
---|---|
Abbreviated title | GECCO 2021 |
Period | 10/07/21 → 14/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