2015/06/19 by Benjamin Doerr, Carola Doerr, Doerr, Benjamin +1
Computer Science · #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Fuzzy Logic and Control Systems #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE) #cs.NE
paper · pdf · doi:10.48550/arxiv.1506.05937
This is a preliminary version of a paper that is to appear at Genetic and Evolutionary Computation Conference (GECCO 2015)
arxiv created 2015/06/19 · openalex publication_date 2015/06/19 · arxiv updated 2015/06/22 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
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: TCS 2015]. Using the fitness level method, the expected optimization time on general OneMax functions was analyzed and a O(max\nlog(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\nlog(n)/λ, nλloglog(λ)/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. We then present the first lower bound for this problem. It matches our upper bound for all values of λ. This allows to determine the asymptotically optimal value for the population size. It is λ= Θ(√(log(n)loglog(n)/logloglog(n))), which gives an optimization time of Θ(n √(log(n)logloglog(n)/loglog(n))). Hence the improved runtime analysis gives a better runtime guarantee along with a better suggestion for the parameter λ. We finally give a tail bound for the upper tail of the runtime distribution, which shows that the actual runtime exceeds our runtime guarantee by a factor of (1+δ) with probability O((n/λ2)-δ) only.