A tight runtime analysis for the (1 + (λ, λ)) GA on leadingones
Denis Antipov, Benjamin Doerr, Vitalii Karavaev · 2019
We conduct a rigorous runtime analysis of the (1 + (λ, λ)) evolutionary algorithm with standard parameter settings, that is, a mutation rate of p = λ/n and a crossover bias of c = 1/λ when optimizing the classic LeadingOnes benchmark function. We show that, for all λ ∈ [1..n/2], the runtime is Θ(n2/λ) iterations and Θ(n2) fitness evaluations. This is, asymptotically, the same number of iterations as for the (1 + λ) EA and the same number of fitness evaluations as for the (1 + λ) EA for any value of λ = O(n). We also extend our results to parameter control techniques and prove that for any dynamic choice of λ the bound of Θ(n2) fitness evaluations still holds.