Estimation of Distribution Algorithms

Classical genetic algorithms evolve a population by randomly cutting two parent solutions apart and swapping halves (crossover), then randomly flipping bits (mutation). The metaphor fits biology, but there is a deeper question: does the algorithm actually understand what makes a solution good?

Estimation of Distribution Algorithms (EDAs) answer that question head-on. Instead of breeding solutions together, an EDA stops each generation, looks at the best candidates in the population, and asks: what is the probability distribution over solutions that best explains why these are winners? Then it throws the old population away and samples an entirely new one from that distribution.

The result is evolution by learning. Every generation tightens the model around what seems to work, and samples spread out from that tightened center — a feedback loop between statistics and search. The approach was formalized in the 1990s by researchers including Shumeet Baluja (PBIL, 1994) and Heinz Mühlenbein (UMDA, 1996), though the idea traces back to population-based learning earlier in the decade.

EDAs are not a single algorithm but a family defined by how complex a probability model they maintain — from a simple independent-bit model to full Bayesian networks encoding dependencies between variables.

The demo below runs a simple Univariate Marginal Distribution Algorithm (UMDA) on a toy one-dimensional problem: maximize the function f(x) = −(x − target)². Each candidate is a real number drawn from a Gaussian. Each generation the best half are kept, the Gaussian is refit to those winners, and the next generation is sampled from the updated distribution.

<div class="controls">
  <label>{{label_target}} <strong id="targetDisplay">0.70</strong>
    <input type="range" id="targetSlider" min="0.10" max="0.90" step="0.05" value="0.70">
  </label>
  <div class="btn-row">
    <button id="stepBtn" type="button">{{btn_step}}</button>
    <button id="runBtn" type="button">{{btn_run}}</button>
    <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<canvas id="canvas" width="560" height="220"></canvas>
<div class="stats" id="stats">{{stats_initial}}</div>
<div class="log" id="log">{{log_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.controls { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .6rem; }
label { font-size: .88rem; color: #444; display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; }
input[type=range] { width: 160px; accent-color: #1d3557; }
.btn-row { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border: 1px solid #dde3ea; border-radius: 8px;
         width: 100%; max-width: 560px; height: auto; }
.stats { font-size: .88rem; color: #1d3557; font-weight: 600; margin: .4rem 0 .2rem; }
.log { font-size: .83rem; color: #555; min-height: 1.3em; }

// Code not found

Notice how the mean (vertical line) drifts toward the optimum and the standard deviation (shaded band) shrinks. After enough generations the distribution has essentially collapsed onto the answer — not because any single solution was mutated there, but because the model learned where good solutions live. Hit Reset and try a different target to see the process from scratch.

EDAs appear to sidestep the blind thrashing of mutation, but they face a different kind of hardness rooted in model complexity.

• Simple models (UMDA, PBIL): assume all variables are independent. Fitting is cheap — just compute a marginal probability per variable. But if the optimum lives at an interaction of variables (e.g., both $x_{1}$ and $x_{2}$ must be 1 together), an independent model may never capture it and the algorithm converges to the wrong place.
• Pairwise models (MIMIC, COMIT): model dependencies between pairs of variables, capturing more structure but at $O(n^{2})$ estimation cost.
• Full Bayesian networks (BOA, hBOA): learn a full Bayesian network over variables each generation. These can capture any structure that exists, but learning the best network is itself an NP-hard problem — so heuristic structure learning is used. The Bayesian Optimization Algorithm (BOA), introduced by Pelikan, Goldberg & Cantú-Paz in 1999, is the flagship here.
• The fitness landscape matters: on problems with strong variable interactions (called epistasis), simple EDAs fail while complex ones succeed — but complex models are expensive to fit. Choosing the right model for the problem is an open question in practice.

EDAs also share a classic evolutionary trap: premature convergence. Once the distribution collapses to a narrow region, diversity is lost and the algorithm can't escape local optima. The interaction between population size, selection pressure, and model complexity determines how long diversity survives — a topic closely related to non-convex optimization and the difficulty of escaping local minima.

The EDA framework shines wherever the structure of good solutions is learnable and the fitness landscape is too rugged for gradient methods:

• Combinatorial optimization: EDAs have been applied to the Traveling Salesman Problem, bin packing, and scheduling problems — anywhere variable interactions define what makes a solution good.
• Bioinformatics: protein structure prediction and gene network inference both require searching large discrete spaces; the model-building step helps EDAs exploit biological structure.
• Hyperparameter optimization: modern machine learning often needs to search over dozens of interacting hyperparameters. EDAs offer a principled alternative to random search and grid search by modeling which configurations work together.
• Electronic design automation: chip placement and routing problems have precise dependency structures that Bayesian EDAs can capture explicitly.
• Finance: portfolio optimization under complex covariance structures maps naturally to the graphical model at the heart of BOA-style algorithms.

Across all these domains, the key insight is the same: if you can learn why a solution is good, you can sample better candidates next time — the core promise of statistical learning applied to search.

Estimation of Distribution Algorithms reframe evolutionary search as a learning problem: each generation produces a dataset of winners, the algorithm fits a probability model to that dataset, and the next generation is sampled from the model. Crossover and mutation disappear; in their place stands the quality of statistical inference.

The elegance comes with a price. Simple models are fast but blind to interactions. Rich models capture structure but are expensive to learn — and learning the best Bayesian network is itself NP-hard. Premature convergence lurks whenever the distribution narrows too fast.

But when the model fits the problem, EDAs converge in far fewer evaluations than blind mutation, making them a compelling tool wherever evaluations are expensive. If you understand genetic algorithms and want to know what happens when evolution stops guessing and starts learning, EDAs are the answer.