arXiv:2607.14278v1 Announce Type: new Abstract: The paper develops the approach to the runtime analysis of evolutionary algorithms on the basis of limit theorems from probability theory. We consider the family of Jump$_k$ benchmark functions, defined on the search space of binary strings of length $n$, parametrized by the integer $k$, which have multiple local optima at the Hamming distance $k$ from a unique global optimum. In this work, we consider the genetic algorithm $(1+(\lambda,\lambda)) GA$ from (Doerr, Doerr and Ebel, 2015) with tunable parameters of the mutation rate $p$, crossover bias $c$, and two intermediate population sizes $\lambda_M$ and $\lambda_C$, and study the time it escapes from the plateau in the case of Jump$_k$ fitness function when $np$ tends to infinity. The main result of this work is a tightened upper bound on the escape time from the work of Antipov, Doerr and Karavaev (2022). Besides that, the obtained bound applies to a wider range of algorithm parameter...
Want to discover more AI signals like this?
Explore Steek