# First Steps Towards a Runtime Analysis When Starting With a Good Solution

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

## Key facts

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

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

- [A First Runtime Analysis of the NSGA-II on a Multimodal Problem](https://mlsanity.com/paper/2204.13750/) (2022)
- [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)
- [Choosing the Right Algorithm With Hints From Complexity Theory](https://mlsanity.com/paper/2109.06584/) (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)
- [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)

## Abstract (arXiv)

The mathematical runtime analysis of evolutionary algorithms traditionally regards the time an algorithm needs to find a solution of a certain quality when initialized with a random population. In practical applications it may be possible to guess solutions that are better than random ones. We start a mathematical runtime analysis for such situations. We observe that different algorithms profit to a very different degree from a better initialization. We also show that the optimal parameterization of the algorithm can depend strongly on the quality of the initial solutions. To overcome this difficulty, self-adjusting and randomized heavy-tailed parameter choices can be profitable. Finally, we observe a larger gap between the performance of the best evolutionary algorithm we found and the corresponding black-box complexity. This could suggest that evolutionary algorithms better exploiting good initial solutions are still to be found. These first findings stem from analyzing the performance of the (1+1) evolutionary algorithm and the static, self-adjusting, and heavy-tailed (1 + (λ,λ)) GA on the OneMax benchmark. We are optimistic that the question how to profit from good initial solutions is interesting beyond these first examples.