2018/08/16 by Hafsteinn Einarsson, Marcelo Matheus Gauy, Einarsson, Hafsteinn +11 · 1 citation
Computer Science · Decision Sciences · #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE)
paper · pdf · doi:10.48550/arxiv.1808.05566
openalex publication_date 2018/08/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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± o(1))βn ln n, where β≈ 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± 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.