Key points are not available for this paper at this time.
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/) ^k-1), 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 (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.
Opris et al. (Wed,) studied this question.