2018/11/30 by Benjamin Doerr, Doerr, Benjamin, Carsten Witt +3 · 1 citation
Computer Science · #Advanced Multi-Objective Optimization Algorithms #Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE)
paper · doi:10.48550/arxiv.1811.12824
openalex publication_date 2018/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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λ+nlog n) when λ is at least C ln n for some constant C > 0. For all values of λ≥ 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.