Achieving Tight $O(4^k)$ Runtime Bounds on Jump${}_k$ by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity

Andre Opris, Johannes Lengler, Dirk Sudholt

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…