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

2026/07/15 by Anton V. Eremeev, Valentin A. Topchii
Computer Science · #cs.NE

paper · pdf

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+(λ,λ)) GA from (Doerr, Doerr and Ebel, 2015) with tunable parameters of the mutation rate p, crossover bias c, and two intermediate population sizes λ_M and λ_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.

Related

• Hitting times of local and global optima in genetic algorithms with very high selection pressure
• Achieving Tight O(4^k) Runtime Bounds on Jump_k by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity
• Runtime Analysis of a Heavy-Tailed (1+(λ,λ)) Genetic Algorithm on Jump Functions
• Lasting Diversity and Superior Runtime Guarantees for the (μ+1) Genetic Algorithm
• Escaping Local Optima using Crossover with Emergent or Reinforced Diversity