A Tight $O(4^k/p_c)$ Runtime Bound for a ($\mu$+1) GA on Jump$_k$ for Realistic Crossover Probabilities
<|reference_start|>A Tight $O(4^k/p_c)$ Runtime Bound for a ($\mu$+1) GA on Jump$_k$ for Realistic Crossover Probabilities: The Jump$_k$ 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({\rm 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 for $p_c = \Omega(1)$ is $O((n/\chi)^{k-1})$, $\chi$ 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 \muga on Jump$_k$. We show that population diversity converges to an equilibrium of near-perfect diversity. This yields an improved and tight time bound of $O(\mu n \log(k) + 4^k/p_c)$ 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)$. Our work partially solves a problem that has been open for more than 20 years.<|reference_end|>
@article{opris2024a,
    title={A Tight $O(4^k/p_c)$ Runtime Bound for a ($\mu$+1) GA on Jump$_k$ for
  Realistic Crossover Probabilities},
    author={Andre Opris, Johannes Lengler, Dirk Sudholt},
    journal={arXiv preprint arXiv:2404.07061},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.07061},
    primaryClass={cs.NE}
}