Asymptotical Analysis of the $(1+(\lambda ,\lambda ))$ GA Escape Time from Local Optima on Jump Functions

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 parameters.