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 s. We analyze in this work how the performance of the (1+1) Evolutionary Algorithm (EA) 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 runtime obtained by this parameter setting is asymptotically optimal among all dynamic choices of the mutation rate for the (1+1) EA, up to lower order error terms. We show similar results for the resampling variant of the (1+1) EA, which enforces to flip at least one bit per iteration.
Document type :
Conference papers
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.sorbonne-universite.fr/hal-02175768
Contributor : Carola Doerr <>
Submitted on : Tuesday, January 14, 2020 - 3:42:03 PM
Last modification on : Saturday, February 1, 2020 - 1:51:46 AM

File

bl pap162s3-file1 (1).pdf
Files produced by the author(s)

Identifiers

Citation

Benjamin Doerr, Carola Doerr, Johannes Lengler. Self-adjusting mutation rates with provably optimal success rules. GECCO 2019 - The Genetic and Evolutionary Computation Conference, Jul 2019, Prague, Czech Republic. pp.1479-1487, ⟨10.1145/3321707.3321733⟩. ⟨hal-02175768⟩

Share

Metrics

Record views

93

Files downloads

37