# A Tight Runtime Analysis for the cGA on Jump Functions---EDAs Can Cross Fitness Valleys at No Extra Cost

arXiv: https://arxiv.org/abs/1903.10983 · HTML: https://mlsanity.com/paper/1903.10983/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2019.

## Built on by (most cited first, 3 of 3)

- [Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution](https://mlsanity.com/paper/2104.06714/) (2021)
- [Choosing the Right Algorithm With Hints From Complexity Theory](https://mlsanity.com/paper/2109.06584/) (2021)
- [A Fresh Look at Lamarckian Evolution and the Baldwin Effect](https://mlsanity.com/paper/2605.28703/) (2026)

## Abstract (arXiv)

We prove that the compact genetic algorithm (cGA) with hypothetical population size μ = Omega(√ n log n) cap poly(n) with high probability finds the optimum of any n-dimensional jump function with jump size k < frac 1 20 ln n in O(μ √ n) iterations. Since it is known that the cGA with high probability needs at least Omega(μ √ n + n log n) iterations to optimize the unimodal OneMax function, our result shows that the cGA in contrast to most classic evolutionary algorithms here is able to cross moderate-sized valleys of low fitness at no extra cost. Our runtime guarantee improves over the recent upper bound O(μ n1.5 log n) valid for μ = Omega(n3.5+varepsilon) of Hasen"ohrl and Sutton (GECCO 2018). For the best choice of the hypothetical population size, this result gives a runtime guarantee of O(n5+varepsilon), whereas ours gives O(n log n). We also provide a simple general method based on parallel runs that, under mild conditions, (i)~overcomes the need to specify a suitable population size, but gives a performance close to the one stemming from the best-possible population size, and (ii)~transforms EDAs with high-probability performance guarantees into EDAs with similar bounds on the expected runtime.