Introduction

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.

Try It: Distribution Tightens Each Generation

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>Target optimum: <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">Step (1 generation)</button>
    <button id="runBtn" type="button">Run to convergence</button>
    <button id="resetBtn" type="button" class="ghost">Reset</button>
  </div>
</div>
<canvas id="canvas" width="560" height="220"></canvas>
<div class="stats" id="stats">Generation 0 โ€” Mean: 0.50 &nbsp; SD: 0.20</div>
<div class="log" id="log">Press Step or Run to start.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Univariate Marginal Distribution Algorithm (UMDA) on f(x) = -(x-target)^2
// Population of real values drawn from Gaussian(mean, sd).
// Each generation: keep top 50%, refit Gaussian to survivors, sample next gen.
const POP = 60;      // population size
const KEEP = 30;     // survivors per generation
const SD_INIT = 0.22;
const SD_MIN  = 0.005;
const MAX_GEN = 80;

let target, mean, sd, gen, running, rafId, history;

function init() {
  target = parseFloat(document.getElementById('targetSlider').value);
  mean = 0.5;
  sd   = SD_INIT;
  gen  = 0;
  running = false;
  history = [{ gen: 0, mean: mean, sd: sd }];
  clearInterval(rafId);
  updateDisplay();
  document.getElementById('log').textContent = 'Press Step or Run to start.';
  document.getElementById('runBtn').textContent = 'Run to convergence';
}

function fitness(x) { return -(x - target) * (x - target); }

// Box-Muller transform โ€” produces standard normal samples
function randn() {
  let u = 0, v = 0;
  while (u === 0) u = Math.random();
  while (v === 0) v = Math.random();
  return Math.sqrt(-2 * Math.log(u)) * Math.cos(2 * Math.PI * v);
}

function samplePop(m, s, n) {
  const arr = [];
  for (let i = 0; i < n; i++) arr.push(Math.max(0, Math.min(1, m + s * randn())));
  return arr;
}

function step() {
  if (gen >= MAX_GEN) { stop(); return false; }
  // Sample population
  const pop = samplePop(mean, sd, POP);
  // Sort by fitness descending, keep top KEEP
  pop.sort((a, b) => fitness(b) - fitness(a));
  const survivors = pop.slice(0, KEEP);
  // Refit Gaussian to survivors
  const newMean = survivors.reduce((s, x) => s + x, 0) / KEEP;
  const variance = survivors.reduce((s, x) => s + (x - newMean) ** 2, 0) / KEEP;
  const newSd = Math.max(SD_MIN, Math.sqrt(variance));
  mean = newMean;
  sd   = newSd;
  gen++;
  history.push({ gen, mean, sd });
  updateDisplay();
  const converged = sd <= SD_MIN * 1.5;
  if (converged) {
    document.getElementById('log').textContent =
      fmt('Converged at generation %gen%: mean=%mean%, target=%target%', { gen: gen, mean: mean.toFixed(4), target: target.toFixed(2) });
    stop();
    return false;
  }
  return true;
}

function stop() {
  running = false;
  clearInterval(rafId);
  document.getElementById('runBtn').textContent = 'Run to convergence';
}

function run() {
  if (running) { stop(); return; }
  if (gen >= MAX_GEN || sd <= SD_MIN * 1.5) { init(); }
  running = true;
  document.getElementById('runBtn').textContent = 'Stop';
  rafId = setInterval(() => { if (!step()) stop(); }, 80);
}

function updateDisplay() {
  document.getElementById('stats').innerHTML =
    fmt('Generation %gen% โ€” Mean: <b>%mean%</b> &nbsp; SD: <b>%sd%</b>', { gen: gen, mean: mean.toFixed(4), sd: sd.toFixed(4) });
  draw();
}

// โ”€โ”€ Drawing โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function draw() {
  const canvas = document.getElementById('canvas');
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  const PAD = { l: 8, r: 8, t: 30, b: 30 };
  const plotW = W - PAD.l - PAD.r;
  const plotH = H - PAD.t - PAD.b;

  ctx.clearRect(0, 0, W, H);

  // Background
  ctx.fillStyle = '#f8fafc';
  ctx.fillRect(PAD.l, PAD.t, plotW, plotH);

  // Target line (dashed, gold)
  const tx = PAD.l + target * plotW;
  ctx.save();
  ctx.strokeStyle = '#e6a817';
  ctx.lineWidth = 2;
  ctx.setLineDash([5, 4]);
  ctx.beginPath(); ctx.moveTo(tx, PAD.t); ctx.lineTo(tx, PAD.t + plotH);
  ctx.stroke();
  ctx.restore();

  // History trace of mean (thin blue path)
  if (history.length > 1) {
    ctx.save();
    ctx.strokeStyle = '#1d3557';
    ctx.lineWidth = 1.2;
    ctx.globalAlpha = 0.35;
    ctx.beginPath();
    history.forEach((h, i) => {
      const x = PAD.l + h.mean * plotW;
      const y = PAD.t + plotH * (1 - h.gen / MAX_GEN);
      if (i === 0) ctx.moveTo(x, y); else ctx.lineTo(x, y);
    });
    ctx.stroke();
    ctx.restore();
  }

  // Gaussian PDF curve (scaled to fit plot height)
  const gaussPDF = (x) =>
    (1 / (sd * Math.sqrt(2 * Math.PI))) * Math.exp(-0.5 * ((x - mean) / sd) ** 2);
  const peakPDF  = gaussPDF(mean);
  const SCALE    = peakPDF > 0 ? plotH * 0.85 / peakPDF : 1;

  // Shaded ยฑ1ฯƒ band
  ctx.save();
  ctx.fillStyle = 'rgba(29, 53, 87, 0.12)';
  ctx.beginPath();
  const lo = Math.max(0, mean - sd), hi = Math.min(1, mean + sd);
  const loX = PAD.l + lo * plotW, hiX = PAD.l + hi * plotW;
  // bottom edge
  ctx.moveTo(loX, PAD.t + plotH);
  for (let i = 0; i <= 120; i++) {
    const xi = lo + (hi - lo) * (i / 120);
    const y  = PAD.t + plotH - gaussPDF(xi) * SCALE;
    ctx.lineTo(PAD.l + xi * plotW, y);
  }
  ctx.lineTo(hiX, PAD.t + plotH);
  ctx.closePath();
  ctx.fill();
  ctx.restore();

  // PDF curve
  ctx.save();
  ctx.strokeStyle = '#1d3557';
  ctx.lineWidth = 2.2;
  ctx.beginPath();
  for (let i = 0; i <= 300; i++) {
    const xi = i / 300;
    const y  = PAD.t + plotH - gaussPDF(xi) * SCALE;
    if (i === 0) ctx.moveTo(PAD.l + xi * plotW, y);
    else ctx.lineTo(PAD.l + xi * plotW, y);
  }
  ctx.stroke();
  ctx.restore();

  // Mean vertical line
  const mx = PAD.l + mean * plotW;
  ctx.save();
  ctx.strokeStyle = '#457b9d';
  ctx.lineWidth = 2;
  ctx.beginPath(); ctx.moveTo(mx, PAD.t); ctx.lineTo(mx, PAD.t + plotH);
  ctx.stroke();
  ctx.restore();

  // Labels
  ctx.fillStyle = '#e6a817';
  ctx.font = '11px system-ui, sans-serif';
  ctx.fillText(fmt('target %target%', { target: target.toFixed(2) }), Math.min(tx + 4, W - 72), PAD.t + 14);

  ctx.fillStyle = '#457b9d';
  ctx.fillText(fmt('mean %mean%', { mean: mean.toFixed(3) }), Math.max(mx - 38, PAD.l), PAD.t + 28);

  // x-axis ticks
  ctx.fillStyle = '#888';
  ctx.font = '10px system-ui, sans-serif';
  for (let v = 0; v <= 1; v += 0.25) {
    const x = PAD.l + v * plotW;
    ctx.fillText(v.toFixed(2), x - 8, PAD.t + plotH + 14);
    ctx.fillStyle = '#ccc';
    ctx.fillRect(x, PAD.t + plotH, 1, 4);
    ctx.fillStyle = '#888';
  }
}

// โ”€โ”€ Event wiring โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
document.getElementById('targetSlider').addEventListener('input', function () {
  document.getElementById('targetDisplay').textContent = parseFloat(this.value).toFixed(2);
  init();
});
document.getElementById('stepBtn').addEventListener('click', () => {
  if (running) stop();
  step();
});
document.getElementById('runBtn').addEventListener('click', run);
document.getElementById('resetBtn').addEventListener('click', init);

init();

// โ”€โ”€ Node.js verification (runs only outside browser) โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// Verify that UMDA converges to the target within MAX_GEN generations.
if (typeof window === 'undefined') {
  const targets = [0.1, 0.3, 0.5, 0.7, 0.9];
  let allPass = true;
  targets.forEach(t => {
    // Run 5 trials; require โ‰ฅ4 to converge within 0.06 of target
    let passes = 0;
    for (let trial = 0; trial < 5; trial++) {
      target = t; mean = 0.5; sd = SD_INIT; gen = 0; history = [{ gen: 0, mean: 0.5, sd: SD_INIT }];
      while (gen < MAX_GEN && sd > SD_MIN * 1.5) step();
      if (Math.abs(mean - t) < 0.06) passes++;
    }
    const ok = passes >= 4;
    console.log(`target=${t.toFixed(2)} -> passes=${passes}/5 OK=${ok}`);
    if (!ok) allPass = false;
  });
  if (!allPass) throw new Error('UMDA failed to converge for some targets');
  console.log('All targets passed.');
}
Result
Console

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.

The Real Complexity

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 x1x_{1} and x2x_{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(n2)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/estimation-of-distribution/Content licensed under CC BY-NC 4.0.