Projects per year
Abstract
Real-world applications often involve “uncertain” objectives, i.e., where optimisation algorithms observe objective values as a random variables with positive variance. In the past decade, several rigorous analysis results for evolutionary algorithms (EAs) on discrete problems show that EAs can cope with low-level uncertainties, i.e. when the variance of the uncertain objective value is small, and sometimes even benefit from uncertainty. Previous work showed that a large population combined with a non-elitist selection mechanism is a promising approach to handle high levels of uncertainty. However, the population size and the mutation rate can dramatically impact the performance of non-elitist EAs, and the optimal choices of these parameters depend on the level of uncertainty in the objective function. The performance and the required parameter settings for non-elitist EAs in some common objective-uncertainty scenarios are still unknown. We analyse the runtime of non-elitist EAs on two classical benchmark problems OneMax and LeadingOnes in in the one-bit, the bitwise, the Gaussian, and the symmetric 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 outperform the current state-of-the-art results. Furthermore, we provide more precise guidance on how to choose the mutation rate, the selective pressure, and the population size as a function of the level of uncertainty.
Original language | English |
---|---|
Journal | Algorithmica |
Early online date | 2 Oct 2022 |
DOIs | |
Publication status | E-pub ahead of print - 2 Oct 2022 |
Bibliographical note
Funding Information:This work was supported by a Turing AI Fellowship (EPSRC grant ref EP/V025562/1).
Publisher Copyright:
© 2022, The Author(s).
Keywords
- Dynamic optimisation
- Noisy optimisation
- Non-elitist evolutionary algorithms
- Runtime analysis
- Uncertain environments
ASJC Scopus subject areas
- General Computer Science
- Computer Science Applications
- Applied Mathematics
Fingerprint
Dive into the research topics of 'More precise runtime analyses of non-elitist evolutionary algorithms in uncertain environments'. Together they form a unique fingerprint.Projects
- 1 Active
-
Turing AI Fellowship: Rigorous time-complexity analysis of co-evolutionary algorithms
Engineering & Physical Science Research Council
1/01/21 → 31/12/25
Project: Research Councils