Self-Adjusting Mutation Rates with Provably Optimal Success Rules
This work provides theoretical insights for optimizing evolutionary algorithms, but it is incremental as it builds on the well-known one-fifth success rule.
The paper analyzes how hyper-parameters (update strength and success rate) affect the performance of the (1+1) Evolutionary Algorithm on the LeadingOnes problem, finding optimal settings at small update strengths and a success rate of 1/e, with running time matching the best fitness-dependent mutation rate.
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.