A Tight Runtime Analysis of the (1+(λ, λ)) Genetic Algorithm on OneMax
Benjamin Doerr, Carola Doerr · 2015
Understanding how crossover works is still one of the big challenges in evolutionary computation research, and making our understanding precise and proven by mathematical means might be an even bigger one. As one of few examples where crossover provably is useful, the (1+(λ, λ)) Genetic Algorithm (GA) was proposed recently in [Doerr, Doerr, Ebel. Lessons From the Black-Box: Fast Crossover-Based Genetic Algorithms. TCS 2015]. Using the fitness level method, the expected optimization time on general OneMax functions was analyzed and a O(max{n log(n) / λ, λ n}) bound was proven for any offspring population size λ ∈ [1..n]. We improve this work in several ways, leading to sharper bounds and a better understanding of how the use of crossover speeds up the runtime in this algorithm. We first improve the upper bound on the runtime to O(max{n log(n) / λ, n λ log log(λ)/log(λ)}). This improvement is made possible from observing that in the parallel generation of λ offspring via crossover (but not mutation), the best of these often is better than the expected value, and hence several fitness levels can be gained in one iteration.