On the Benefits of Populations for the Exploitation Speed of Standard Steady-State Genetic Algorithms
- Submitting institution
-
The University of Sheffield
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 7858
- Type
- D - Journal article
- DOI
-
10.1007/s00453-020-00743-1
- Title of journal
- Algorithmica
- Article number
- -
- First page
- 3676
- Volume
- 82
- Issue
- -
- ISSN
- 0178-4617
- Open access status
- Compliant
- Month of publication
- July
- 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
-
1
- Research group(s)
-
A - Algorithms
- Citation count
- 1
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This work, a main achievement of EPSRC Fellowship (EP/M004252/1), proves that GAs can hillclimb faster than any unary (mutation-only) unbiased search heuristic - crossover makes the algorithm faster. Providing bounds on the expected runtime that decrease with the population size, it led to the surprising hypothesis that populations are beneficial also for hillclimbing, not only for escaping local optima (doi.org/10.1109/TEVC.2017.2724201), considerably improving upon the state-of-the-art (doi.org/10.1109/TEVC.2017.2745715) where the bounds do not depend on the population size. A formal proof was recently provided (doi.org/10.1145/3377930.3390212) by building upon this work.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -