The \(\textsc {Jump} _k\) benchmark was the first problem for which crossover was proven to give a speed-up over mutation-only evolutionary algorithms. Jansen and Wegener (Algorithmica 2002) proved an upper bound of \(O(\textrm{poly}(n) + 4^k/p_c)\) for the ( \(\mu \) +1) Genetic Algorithm (( \(\mu \) +1) GA), but only for unrealistically small crossover probabilities \(p_c\) . To this date, it remains an open problem to prove similar upper bounds for realistic \(p_c\) ; the best known runtime bound, in terms of function evaluations, for \(p_c = \Omega (1)\) is \(O((n/\chi )^{k-1})\) , \(\chi \) 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 ( \(\mu \) +1) GA on \(\textsc {Jump} _k\) . The ( \(\mu \) +1)- \({\lambda _c}\) -GA creates one offspring in each generation either by applying mutation to one parent or by applying crossover \({\lambda _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 ( \(\mu \) +1)- \({\lambda _c}\) -GA converges to an equilibrium of near-perfect diversity. This yields an improved time bound of \(O(\mu n \log (\mu ) + 4^k)\) function evaluations for a range of k under the mild assumptions \(p_c = O(1/k)\) and \(\mu \in \Omega (kn)\) . For all constant k, the restriction is satisfied for some \(p_c = \Omega (1)\) and it implies that the expected runtime for all constant k and an appropriate \(\mu = \Theta (kn)\) is bounded by \(O(n^2 \log n)\) , irrespective of k. For larger k, the expected time of the ( \(\mu \) +1)- \({\lambda _c}\) -GA is \(\Theta (4^k)\) , which is tight for a large class of unbiased black-box algorithms and faster than the original ( \(\mu \) +1) GA by a factor of \(\Omega (1/p_c)\) . We also show that our analysis can be extended to other unitation functions such as \(\textsc {Jump} _{k, \delta }\) and Hurdle.
