Runtime Analysis for Self-adaptive Mutation Rates
This work addresses the challenge of parameter tuning in evolutionary computation for researchers and practitioners, showing that self-adaptation can efficiently find optimal settings, though it is incremental as it builds on prior schemes.
The paper tackles the problem of optimizing mutation rates in evolutionary algorithms by proposing a self-adaptive version where the mutation rate is part of the individual and subject to mutation, achieving an expected optimization time of O(nλ/logλ + n log n) on the OneMax benchmark, which is asymptotically optimal for λ ≥ C ln n.
We propose and analyze a self-adaptive version of the $(1,λ)$ evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis on the OneMax benchmark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time (number of fitness evaluations) of $O(nλ/\logλ+n\log n)$ when $λ$ is at least $C \ln n$ for some constant $C > 0$. For all values of $λ\ge C \ln n$, this performance is asymptotically best possible among all $λ$-parallel mutation-based unbiased black-box algorithms. Our result shows that self-adaptation in evolutionary computation can find complex optimal parameter settings on the fly. At the same time, it proves that a relatively complicated self-adjusting scheme for the mutation rate proposed by Doerr, Gießen, Witt, and Yang~(GECCO~2017) can be replaced by our simple endogenous scheme. On the technical side, the paper contributes new tools for the analysis of two-dimensional drift processes arising in the analysis of dynamic parameter choices in EAs, including bounds on occupation probabilities in processes with non-constant drift.