Skip to Main content Skip to Navigation
Journal articles

Self-Adjusting Mutation Rates with Provably Optimal Success Rules

Abstract : The one-fifth success rule is one of the best-known and most widely accepted techniques to control the parameters of evolutionary algorithms. While it is often applied in the literal sense, a common interpretation sees the one-fifth success rule as a family of success-based updated rules that are determined by an update strength F and a success rate. We analyze in this work how the performance of the (1+1) Evolutionary Algorithm on LeadingOnes depends on these two hyper-parameters. Our main result shows that the best performance is obtained for small update strengths F = 1 + o(1) and success rate 1/e. We also prove that the running time obtained by this parameter setting is, apart from lower order terms, the same that is achieved with the best fitness-dependent mutation rate. We show similar results for the resampling variant of the (1+1) Evolutionary Algorithm, which enforces to flip at least one bit per iteration.
Document type :
Journal articles
Complete list of metadata

https://hal.sorbonne-universite.fr/hal-03377092
Contributor : Carola Doerr Connect in order to contact the contributor
Submitted on : Thursday, October 14, 2021 - 7:20:01 AM
Last modification on : Saturday, October 16, 2021 - 3:50:42 AM

File

2019-SelfAdjustingLO-arxiv-v3-...
Files produced by the author(s)

Identifiers

Citation

Benjamin Doerr, Carola Doerr, Johannes Lengler. Self-Adjusting Mutation Rates with Provably Optimal Success Rules. Algorithmica, Springer Verlag, 2021, 83 (10), pp.3108-3147. ⟨10.1007/s00453-021-00854-3⟩. ⟨hal-03377092⟩

Share

Metrics

Record views

42

Files downloads

11