The choice of the offspring population size in the (1,λ) evolutionary algorithm
- Submitting institution
-
The University of Birmingham
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 30646372
- Type
- D - Journal article
- DOI
-
10.1016/j.tcs.2013.09.036
- Title of journal
- Theoretical Computer Science
- Article number
- -
- First page
- 20
- Volume
- 545
- Issue
- -
- ISSN
- 0304-3975
- Open access status
- Out of scope for open access requirements
- Month of publication
- August
- Year of publication
- 2014
- 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)
-
-
- Citation count
- 43
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper introduces significant extensions to methods of drift analysis for determining run times of randomised
algorithms. These allow critical parameter thresholds to be determined, distinguishing between polynomial and
exponential run-times, by considering the balance of expected progress towards or away from a finishing state. This
allowed an open problem in understanding a certain class of evolutionary algorithm to be solved. The methods have been taken up in a variety of run-time analysis papers, especially in determining optimal parameter settings, and studying the trade-offs between parameter choices. There is also a cool inequality (Lemma 8) which has found multiple applications.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -