# From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 79 references that are in the map.
- First posted on arXiv 18 Jun 2022.

## Builds on (most cited first, 19 of 19)

- [Fast Genetic Algorithms](https://mlsanity.com/paper/1703.03334/) (2017)
- [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)
- [Self-Adjusting Mutation Rates with Provably Optimal Success Rules](https://mlsanity.com/paper/1902.02588/) (2019)
- [The Runtime of the Compact Genetic Algorithm on Jump Functions](https://mlsanity.com/paper/1908.06527/) (2019)
- [Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices](https://mlsanity.com/paper/1804.05650/) (2018)
- [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)
- [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)
- [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)
- [Theory of Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/1806.05392/) (2018)
- [Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is Beneficial](https://mlsanity.com/paper/1812.00966/) (2018)
- [Choosing the Right Algorithm With Hints From Complexity Theory](https://mlsanity.com/paper/2109.06584/) (2021)
- [Upper Bounds on the Runtime of the Univariate Marginal Distribution Algorithm on OneMax](https://mlsanity.com/paper/1704.00026/) (2017)
- [From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm](https://mlsanity.com/paper/2004.07141/) (2020)
- [A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes](https://mlsanity.com/paper/2004.04978/) (2020)

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

- [Already Moderate Population Sizes Provably Yield Strong Robustness to Noise](https://mlsanity.com/paper/2404.02090/) (2024)

## Abstract (arXiv)

Estimation-of-distribution algorithms (EDAs) are optimization algorithms that learn a distribution on the search space from which good solutions can be sampled easily. A key parameter of most EDAs is the sample size (population size). If the population size is too small, the update of the probabilistic model builds on few samples, leading to the undesired effect of genetic drift. Too large population sizes avoid genetic drift, but slow down the process. Building on a recent quantitative analysis of how the population size leads to genetic drift, we design a smart-restart mechanism for EDAs. By stopping runs when the risk for genetic drift is high, it automatically runs the EDA in good parameter regimes. Via a mathematical runtime analysis, we prove a general performance guarantee for this smart-restart scheme. This in particular shows that in many situations where the optimal (problem-specific) parameter values are known, the restart scheme automatically finds these, leading to the asymptotically optimal performance. We also conduct an extensive experimental analysis. On four classic benchmark problems, we clearly observe the critical influence of the population size on the performance, and we find that the smart-restart scheme leads to a performance close to the one obtainable with optimal parameter values. Our results also show that previous theory-based suggestions for the optimal population size can be far from the optimal ones, leading to a performance clearly inferior to the one obtained via the smart-restart scheme. We also conduct experiments with PBIL (cross-entropy algorithm) on two combinatorial optimization problems from the literature, the max-cut problem and the bipartition problem. Again, we observe that the smart-restart mechanism finds much better values for the population size than those suggested in the literature, leading to a much better performance.