Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is Beneficial
- Submitting institution
-
The University of Sheffield
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 7394
- Type
- D - Journal article
- DOI
-
10.1007/s00453-020-00671-0
- Title of journal
- Algorithmica
- Article number
- -
- First page
- 976
- Volume
- 83
- Issue
- -
- ISSN
- 0178-4617
- Open access status
- Compliant
- Month of publication
- January
- Year of publication
- 2020
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
0
- Research group(s)
-
A - Algorithms
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper unifies 13 previous runtime analyses for different noise models on LeadingOnes test function, giving runtime bounds for arbitrary noise strengths, making it possible to locate threshold between polynomial and superpolynomial times for the first time. It further demonstrates that noise can be beneficial; it can blur the landscape, allowing a hill climber to see the underlying gradient. Recently taken up by Ecole-Polytechnique, who provided a general methodology for deriving exponential upper runtime bounds under noise (doi.org/10.1007/978-3-030-58115-2_43).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -