A Tight O(4ᵏ/pc) Runtime Bound for a (μ+1) GA on Jumpₖ for Realistic Crossover Probabilities

The Jumpₖ benchmark was the first problem for which crossover was proven to give a speedup over mutation-only evolutionary algorithms. Jansen and Wegener (2002) proved an upper bound of O( poly(n) + 4ᵏ/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 for pc = Ω(1) is O((n/χ)ᵏ⁻¹), χ a positive constant. Using recently developed techniques, we analyse the evolution of the population diversity, measured as sum of pairwise Hamming distances, for a variant of the on Jumpₖ. We show that population diversity converges to an equilibrium of near-perfect diversity. This yields an improved and tight time bound of O(μ n log(k) + 4ᵏ/pc) 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). Our work partially solves a problem that has been open for more than 20 years.