The linear hidden subset problem for the (1+1) EA with scheduled and adaptive mutation rates
This work addresses runtime optimization for evolutionary algorithms in theoretical computer science, providing incremental improvements over static methods.
The paper tackles the problem of optimizing runtime for unbiased (1+1) evolutionary algorithms on linear functions with an unknown number of non-zero bits, showing that dynamic mutation rate policies can improve performance. It achieves runtimes of (1±o(1))βn ln n with a fixed schedule and (1±o(1))e n ln n with adaptive rates, matching algorithms that know n in advance.
We study unbiased $(1+1)$ evolutionary algorithms on linear functions with an unknown number $n$ of bits with non-zero weight. Static algorithms achieve an optimal runtime of $O(n (\ln n)^{2+ε})$, however, it remained unclear whether more dynamic parameter policies could yield better runtime guarantees. We consider two setups: one where the mutation rate follows a fixed schedule, and one where it may be adapted depending on the history of the run. For the first setup, we give a schedule that achieves a runtime of $(1\pm o(1))βn \ln n$, where $β\approx 3.552$, which is an asymptotic improvement over the runtime of the static setup. Moreover, we show that no schedule admits a better runtime guarantee and that the optimal schedule is essentially unique. For the second setup, we show that the runtime can be further improved to $(1\pm o(1)) e n \ln n$, which matches the performance of algorithms that know $n$ in advance. Finally, we study the related model of initial segment uncertainty with static position-dependent mutation rates, and derive asymptotically optimal lower bounds. This answers a question by Doerr, Doerr, and Kötzing.