Achieving Tight O(4^k) Runtime Bounds on Jump_k by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity

Abstract

The 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 (2002) proved an upper bound of O(poly(n) + 4^k/p_c) for the (+1) Genetic Algorithm ((+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 = (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 JUMP_k. 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 () + 4^k) function evaluations for a range of k under the mild assumptions p_c = O(1/k) and (kn). For all constant k, the restriction is satisfied for some p_c = (1) and it implies that the expected runtime for all constant k and an appropriate = (kn) is bounded by O(n^2 n), irrespective of k. For larger k, the expected time of the (+1)-_c-GA is (4^k), which is tight for a large class of unbiased black-box algorithms and faster than the original (+1) GA by a factor of (1/p_c). We also show that our analysis can be extended to other unitation functions such as JUMP_k, and HURDLE.

Tasks

Reproductions