# Choosing the Right Algorithm With Hints From Complexity Theory

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 130 references that are in the map.
- First posted on arXiv 14 Sep 2021.

## Builds on (most cited first, 30 of 36)

- [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)
- [Better Runtime Guarantees Via Stochastic Domination](https://mlsanity.com/paper/1801.04487/) (2018)
- [The Runtime of the Compact Genetic Algorithm on Jump Functions](https://mlsanity.com/paper/1908.06527/) (2019)
- [Stagnation Detection with Randomized Local Search](https://mlsanity.com/paper/2101.12054/) (2021)
- [Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution](https://mlsanity.com/paper/2104.06714/) (2021)
- [Runtime Analysis of a Heavy-Tailed (1+(λ,λ)) Genetic Algorithm on Jump Functions](https://mlsanity.com/paper/2006.03523/) (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)
- [A Tight Runtime Analysis for the (μ + λ) EA](https://mlsanity.com/paper/1812.11061/) (2018)
- [On the Limitations of the Univariate Marginal Distribution Algorithm to Deception and Where Bivariate EDAs might help](https://mlsanity.com/paper/1907.12438/) (2019)
- [A Rigorous Runtime Analysis of the (1 + (λ, λ)) GA on Jump Functions](https://mlsanity.com/paper/2004.06702/) (2020)
- [Runtime Analysis of the (1+(λ,λ)) Genetic Algorithm on Random Satisfiable 3-CNF Formulas](https://mlsanity.com/paper/1704.04366/) (2017)
- [Optimal Parameter Choices via Precise Black-Box Analysis](https://mlsanity.com/paper/1807.03403/) (2018)
- [Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms](https://mlsanity.com/paper/1910.14389/) (2019)
- [The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis](https://mlsanity.com/paper/2007.08277/) (2020)
- [First Steps Towards a Runtime Comparison of Natural and Artificial Evolution](https://mlsanity.com/paper/1504.06260/) (2015)
- [Significance-based Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/1807.03495/) (2018)
- [Level-Based Analysis of the Univariate Marginal Distribution Algorithm](https://mlsanity.com/paper/1807.10038/) (2018)
- [When Hypermutations and Ageing Enable Artificial Immune Systems to Outperform Evolutionary Algorithms](https://mlsanity.com/paper/1804.01314/) (2018)
- [The (1+λ) Evolutionary Algorithm with Self-Adjusting Mutation Rate](https://mlsanity.com/paper/1704.02191/) (2017)
- [Complexity Theory for Discrete Black-Box Optimization Heuristics](https://mlsanity.com/paper/1801.02037/) (2018)
- [Runtime Analysis for Self-adaptive Mutation Rates](https://mlsanity.com/paper/1811.12824/) (2018)
- [The Query Complexity of a Permutation-Based Variant of Mastermind](https://mlsanity.com/paper/1812.08480/) (2018)
- [Multiplicative Up-Drift](https://mlsanity.com/paper/1904.05682/) (2019)
- [Self-Adjusting Population Sizes for Non-Elitist Evolutionary Algorithms: Why Success Rates Matter](https://mlsanity.com/paper/2104.05624/) (2021)
- [Drift Analysis and Evolutionary Algorithms Revisited](https://mlsanity.com/paper/1608.03226/) (2016)
- [A Tight Runtime Analysis for the cGA on Jump Functions---EDAs Can Cross Fitness Valleys at No Extra Cost](https://mlsanity.com/paper/1903.10983/) (2019)

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

- [How Well Does the Metropolis Algorithm Cope With Local Optima?](https://mlsanity.com/paper/2304.10848/) (2023)
- [From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/2206.09090/) (2022)
- [Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus](https://mlsanity.com/paper/2302.08021/) (2023)
- [Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy](https://mlsanity.com/paper/2505.01647/) (2025)
- [A Fresh Look at Lamarckian Evolution and the Baldwin Effect](https://mlsanity.com/paper/2605.28703/) (2026)

## Abstract (arXiv)

Choosing a suitable algorithm from the myriads of different search heuristics is difficult when faced with a novel optimization problem. In this work, we argue that the purely academic question of what could be the best possible algorithm in a certain broad class of black-box optimizers can give fruitful indications in which direction to search for good established optimization heuristics. We demonstrate this approach on the recently proposed DLB benchmark, for which the only known results are O(n3) runtimes for several classic evolutionary algorithms and an O(n2 log n) runtime for an estimation-of-distribution algorithm. Our finding that the unary unbiased black-box complexity is only O(n2) suggests the Metropolis algorithm as an interesting candidate and we prove that it solves the DLB problem in quadratic time. Since we also prove that better runtimes cannot be obtained in the class of unary unbiased algorithms, we shift our attention to algorithms that use the information of more parents to generate new solutions. An artificial algorithm of this type having an O(n log n) runtime leads to the result that the significance-based compact genetic algorithm (sig-cGA) can solve the DLB problem also in time O(n log n) with high probability. Our experiments show a remarkably good performance of the Metropolis algorithm, clearly the best of all algorithms regarded for reasonable problem sizes.