# On the Limitations of the Univariate Marginal Distribution Algorithm to Deception and Where Bivariate EDAs might help

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jul 2019.

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

- [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)
- [How Well Does the Metropolis Algorithm Cope With Local Optima?](https://mlsanity.com/paper/2304.10848/) (2023)
- [When Non-Elitism Meets Time-Linkage Problems](https://mlsanity.com/paper/2104.06831/) (2021)
- [From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/2206.09090/) (2022)
- [General Univariate Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/2206.11198/) (2022)
- [Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus](https://mlsanity.com/paper/2302.08021/) (2023)
- [A Fresh Look at Lamarckian Evolution and the Baldwin Effect](https://mlsanity.com/paper/2605.28703/) (2026)

## Abstract (arXiv)

We introduce a new benchmark problem called Deceptive Leading Blocks (DLB) to rigorously study the runtime of the Univariate Marginal Distribution Algorithm (UMDA) in the presence of epistasis and deception. We show that simple Evolutionary Algorithms (EAs) outperform the UMDA unless the selective pressure μ/λ is extremely high, where μ and λ are the parent and offspring population sizes, respectively. More precisely, we show that the UMDA with a parent population size of μ=Omega(log n) has an expected runtime of eOmega(μ) on the DLB problem assuming any selective pressure fracμλ ≥ frac141000, as opposed to the expected runtime of O(nλlog λ+n3) for the non-elitist (μ,λ)~EA with μ/λ≤ 1/e. These results illustrate inherent limitations of univariate EDAs against deception and epistasis, which are common characteristics of real-world problems. In contrast, empirical evidence reveals the efficiency of the bi-variate MIMIC algorithm on the DLB problem. Our results suggest that one should consider EDAs with more complex probabilistic models when optimising problems with some degree of epistasis and deception.