# Lower Bounds from Fitness Levels Made Easy

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 69 references that are in the map.
- First posted on arXiv 7 Apr 2021.

## Builds on (most cited first, 15 of 15)

- [Fast Genetic Algorithms](https://mlsanity.com/paper/1703.03334/) (2017)
- [Probabilistic Tools for the Analysis of Randomized Optimization Heuristics](https://mlsanity.com/paper/1801.06733/) (2018)
- [Does Comma Selection Help To Cope With Local Optima](https://mlsanity.com/paper/2004.01274/) (2020)
- [Self-Adjusting Evolutionary Algorithms for Multimodal Optimization](https://mlsanity.com/paper/2004.03266/) (2020)
- [Stagnation Detection with Randomized Local Search](https://mlsanity.com/paper/2101.12054/) (2021)
- [Runtime Analysis of a Heavy-Tailed (1+(λ,λ)) Genetic Algorithm on Jump Functions](https://mlsanity.com/paper/2006.03523/) (2020)
- [Fixed-Target Runtime Analysis](https://mlsanity.com/paper/2004.09613/) (2020)
- [First Steps Towards a Runtime Analysis When Starting With a Good Solution](https://mlsanity.com/paper/2006.12161/) (2020)
- [Level-based Analysis of Genetic Algorithms and other Search Processes](https://mlsanity.com/paper/1407.7663/) (2014)
- [Optimal Parameter Choices via Precise Black-Box Analysis](https://mlsanity.com/paper/1807.03403/) (2018)
- [Fast Artificial Immune Systems](https://mlsanity.com/paper/1806.00299/) (2018)
- [Multiplicative Up-Drift](https://mlsanity.com/paper/1904.05682/) (2019)
- [Optimal Mutation Rates for the (1+λ) EA on OneMax](https://mlsanity.com/paper/2006.11457/) (2020)
- [Probabilistic analysis of the (1+1)-evolutionary algorithm](https://mlsanity.com/paper/1409.4955/) (2014)
- [Sharp Bounds on the Runtime of the (1+1) EA via Drift Analysis and Analytic Combinatorial Tools](https://mlsanity.com/paper/1906.09047/) (2019)

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

- [An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics](https://mlsanity.com/paper/2105.03090/) (2021)
- [Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus](https://mlsanity.com/paper/2302.08021/) (2023)
- [When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection](https://mlsanity.com/paper/2604.07473/) (2026)
- [Runtime Analysis for Permutation-based Evolutionary Algorithms](https://mlsanity.com/paper/2207.04045/) (2022)
- [A Fresh Look at Lamarckian Evolution and the Baldwin Effect](https://mlsanity.com/paper/2605.28703/) (2026)

## Abstract (arXiv)

One of the first and easy to use techniques for proving run time bounds for evolutionary algorithms is the so-called method of fitness levels by Wegener. It uses a partition of the search space into a sequence of levels which are traversed by the algorithm in increasing order, possibly skipping levels. An easy, but often strong upper bound for the run time can then be derived by adding the reciprocals of the probabilities to leave the levels (or upper bounds for these). Unfortunately, a similarly effective method for proving lower bounds has not yet been established. The strongest such method, proposed by Sudholt (2013), requires a careful choice of the viscosity parameters γi,j, 0 ≤ i < j ≤ n. In this paper we present two new variants of the method, one for upper and one for lower bounds. Besides the level leaving probabilities, they only rely on the probabilities that levels are visited at all. We show that these can be computed or estimated without greater difficulties and apply our method to reprove the following known results in an easy and natural way. (i) The precise run time of the (1+1) EA on textscLeadingOnes. (ii) A lower bound for the run time of the (1+1) EA on textscOneMax, tight apart from an O(n) term. (iii) A lower bound for the run time of the (1+1) EA on long k-paths. We also prove a tighter lower bound for the run time of the (1+1) EA on jump functions by showing that, regardless of the jump size, only with probability O(2-n) the algorithm can avoid to jump over the valley of low fitness.