# Fixed-Target Runtime Analysis

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Apr 2020.

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

- [Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution](https://mlsanity.com/paper/2104.06714/) (2021)
- [Lower Bounds from Fitness Levels Made Easy](https://mlsanity.com/paper/2104.03372/) (2021)
- [An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics](https://mlsanity.com/paper/2105.03090/) (2021)
- [The (1+(λ,λ)) Global SEMO Algorithm](https://mlsanity.com/paper/2210.03618/) (2022)
- [Towards a Stronger Theory for Permutation-based Evolutionary Algorithms](https://mlsanity.com/paper/2204.07637/) (2022)
- [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)
- [Frequency Fitness Assignment: Optimization without Bias for Good Solutions can be Efficient](https://mlsanity.com/paper/2112.00229/) (2021)
- [Local Optima in Diversity Optimization: Non-trivial Offspring Population is Essential](https://mlsanity.com/paper/2407.08963/) (2024)

## Abstract (arXiv)

Runtime analysis aims at contributing to our understanding of evolutionary algorithms through mathematical analyses of their runtimes. In the context of discrete optimization problems, runtime analysis classically studies the time needed to find an optimal solution. However, both from a practical and from a theoretical viewpoint, more fine-grained performance measures are needed to gain a more detailed understanding of the main working principles and their resulting performance implications. Two complementary approaches have been suggested: fixed-budget analyses and fixed-target analyses. In this work, we conduct an in-depth study on the advantages and the limitations of fixed-target analyses. We show that, different from fixed-budget analyses, many classical methods from the runtime analysis of discrete evolutionary algorithms yield fixed-target results without greater effort. We use this to conduct a number of new fixed-target analyses. However, we also point out examples where an extension of existing runtime results to fixed-target results is highly non-trivial.