# Significance-based Estimation-of-Distribution Algorithms

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2018.

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

- [Choosing the Right Algorithm With Hints From Complexity Theory](https://mlsanity.com/paper/2109.06584/) (2021)
- [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)
- [Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noise](https://mlsanity.com/paper/2305.04553/) (2023)
- [A Fresh Look at Lamarckian Evolution and the Baldwin Effect](https://mlsanity.com/paper/2605.28703/) (2026)
- [On the Runtime Analysis of Reinforcement Learning Hyper-Heuristics](https://mlsanity.com/paper/2607.22036/) (2026)

## Abstract (arXiv)

Estimation-of-distribution algorithms (EDAs) are randomized search heuristics that create a probabilistic model of the solution space, which is updated iteratively, based on the quality of the solutions sampled according to the model. As previous works show, this iteration-based perspective can lead to erratic updates of the model, in particular, to bit-frequencies approaching a random boundary value. In order to overcome this problem, we propose a new EDA based on the classic compact genetic algorithm (cGA) that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significance-based compact genetic algorithm (sig-cGA) optimizes the commonly regarded benchmark functions OneMax, LeadingOnes, and BinVal all in quasilinear time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed scGA -- an EDA that tries to prevent erratic model updates by imposing a bias to the uniformly distributed model -- we prove that it optimizes OneMax only in a time exponential in its hypothetical population size. Similarly, we show that the convex search algorithm cannot optimize OneMax in polynomial time.