2024/04/10 by Andre Opris, Johannes Lengler, Opris, Andre +3
Computer Science · Decision Sciences · Mathematics · #68Q25 #68Q87 #68W20 #68W40 #68W50 #Bayesian Modeling and Causal Inference #F.2.2 #FOS: Computer and information sciences #G.3 #Mathematical Approximation and Integration #Neural and Evolutionary Computing (cs.NE) #Probability and Risk Models
paper · pdf · doi:10.48550/arxiv.2404.07061
openalex publication_date 2024/04/10 · openalex created_date 2024/04/12 · openalex updated_date 2026/07/28
The JUMPk benchmark was the first problem for which crossover was proven to give a speed-up over mutation-only evolutionary algorithms. Jansen and Wegener (2002) proved an upper bound of O(poly(n) + 4k/pc) for the (μ+1) Genetic Algorithm ((μ+1) GA), but only for unrealistically small crossover probabilities pc. To this date, it remains an open problem to prove similar upper bounds for realistic pc; the best known runtime bound, in terms of function evaluations, for pc = Ω(1) is O((n/χ)k-1), χ a positive constant. We provide a novel approach and analyse the evolution of the population diversity, measured as sum of pairwise Hamming distances, for a variant of the (μ+1) GA on JUMPk. The (μ+1)-λc-GA creates one offspring in each generation either by applying mutation to one parent or by applying crossover λc times to the same two parents (followed by mutation), to amplify the probability of creating an accepted offspring in generations with crossover. We show that population diversity in the (μ+1)-λc-GA converges to an equilibrium of near-perfect diversity. This yields an improved time bound of O(μn log(μ) + 4k) function evaluations for a range of k under the mild assumptions pc = O(1/k) and μ∈ Ω(kn). For all constant k, the restriction is satisfied for some pc = Ω(1) and it implies that the expected runtime for all constant k and an appropriate μ= Θ(kn) is bounded by O(n2 log n), irrespective of k. For larger k, the expected time of the (μ+1)-λc-GA is Θ(4k), which is tight for a large class of unbiased black-box algorithms and faster than the original (μ+1) GA by a factor of Ω(1/pc). We also show that our analysis can be extended to other unitation functions such as JUMPk, δ and HURDLE.