Optimal Parameter Choices Through Self-Adjustment: Applying the 1/5-th Rule in Discrete Settings
This work addresses the challenge of parameter tuning for algorithm designers in evolutionary computation, offering a theoretically grounded adaptive mechanism for discrete domains, though it is incremental as it extends a known rule from continuous to discrete settings.
The paper tackles the problem of dynamically adjusting parameters in evolutionary algorithms for discrete optimization, proving that applying the one-fifth success rule to the population size in the (1+(λ,λ)) GA achieves linear expected optimization time on OneMax, which is asymptotically optimal and outperforms any static parameter choice.
While evolutionary algorithms are known to be very successful for a broad range of applications, the algorithm designer is often left with many algorithmic choices, for example, the size of the population, the mutation rates, and the crossover rates of the algorithm. These parameters are known to have a crucial influence on the optimization time, and thus need to be chosen carefully, a task that often requires substantial efforts. Moreover, the optimal parameters can change during the optimization process. It is therefore of great interest to design mechanisms that dynamically choose best-possible parameters. An example for such an update mechanism is the one-fifth success rule for step-size adaption in evolutionary strategies. While in continuous domains this principle is well understood also from a mathematical point of view, no comparable theory is available for problems in discrete domains. In this work we show that the one-fifth success rule can be effective also in discrete settings. We regard the $(1+(λ,λ))$~GA proposed in [Doerr/Doerr/Ebel: From black-box complexity to designing new genetic algorithms, TCS 2015]. We prove that if its population size is chosen according to the one-fifth success rule then the expected optimization time on \textsc{OneMax} is linear. This is better than what \emph{any} static population size $λ$ can achieve and is asymptotically optimal also among all adaptive parameter choices.