# Solving Problems with Unknown Solution Length at (Almost) No Extra Cost

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2015.

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

- [Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution](https://mlsanity.com/paper/2104.06714/) (2021)
- [An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics](https://mlsanity.com/paper/2105.03090/) (2021)

## Abstract (arXiv)

Most research in the theory of evolutionary computation assumes that the problem at hand has a fixed problem size. This assumption does not always apply to real-world optimization challenges, where the length of an optimal solution may be unknown a priori. Following up on previous work of Cathabard, Lehre, and Yao [FOGA 2011] we analyze variants of the (1+1) evolutionary algorithm for problems with unknown solution length. For their setting, in which the solution length is sampled from a geometric distribution, we provide mutation rates that yield an expected optimization time that is of the same order as that of the (1+1) EA knowing the solution length. We then show that almost the same run times can be achieved even if no a priori information on the solution length is available. Finally, we provide mutation rates suitable for settings in which neither the solution length nor the positions of the relevant bits are known. Again we obtain almost optimal run times for the textscOneMax and textscLeadingOnes test functions, thus solving an open problem from Cathabard et al.