Evolution, Live: Genetic Algorithms
A while ago I set an ant colony foraging in your browser. Watching an optimiser work beats reading about one, by a mile, so here is the sequel, for the algorithm that is even more watchable, because it is even more alive. This post evolves a solution in front of you, out of a population that breeds, mutates, and dies, generation by generation, on your CPU.
Quick jargon guide
- Genetic algorithm (GA): an optimiser that keeps a population of candidate solutions and improves it by imitating natural selection: the fittest breed, the rest die.
- Individual / genome: one candidate solution, encoded as a string of "genes" the algorithm can cut and mutate.
- Fitness function: the score that decides who breeds.
- Selection: picking parents, biased toward the fit. Turn the bias up and evolution speeds toward whatever's currently best, at the cost of variety.
- Crossover: combining two parents' genomes into a child, the "sexual" recombination step.
- Mutation: random tweaks to a genome. The source of new material; too little and you stagnate, too much and you get a lot of noise.
- Elitism: carrying the best individuals into the next generation untouched, so the best score never gets worse.
- Premature convergence: the population collapsing to near-copies of one decent solution too early, killing the diversity needed to find a great one.
The whole algorithm on a napkin
The entire loop:
- Make a population of random candidate solutions.
- Score each one with the fitness function.
- Select parents, biased toward the fitter ones.
- Cross them over to make children, mutate the children a little.
- Replace the old population with the new one (keeping a few elites).
- Go to step 2. Repeat until bored or converged.
Watch it evolve
Below, a population is evolving toward a target. Each little picture is one individual; the big one is the current champion. Press play and watch the champion sharpen out of noise, generation by generation. Play with the parameters in the sliders to see how they effect the outcome.
The big picture is the champion: the best painting of the target letter the population has produced so far, built from fifty translucent triangles. The inset beside it is the target (K by default; pick any letter and the population starts over, because a new target is a new fitness landscape), and every cell in the grid below is one individual (the champion's cell is ringed in green). In the chart, best and average match climb while diversity falls as the population agrees with itself; with elitism on, the best score can never drop. Diversity crashing to the floor while best stops moving is premature convergence.
Break it on purpose
Three experiments to try:
Crank selection pressure to maximum. The population will rocket toward the best early solution and then stop improving, sometimes far from a good answer. You've just caused premature convergence: everyone became a copy of one lucky ancestor, and with no diversity left, crossover has nothing to recombine and mutation alone can't dig out.
Set mutation to zero. Evolution grinds to a halt the moment the population homogenises, because crossover can only ever remix genes that already exist. No new material, no progress. Then push mutation to maximum and watch the opposite disaster: the champion thrashes randomly and never settles, because you've turned evolution into a random search.
Shrink the population to a handful. Small populations converge fast and badly; they're a tiny gene pool, prone to the same fragility as any small, inbred group. This happens in real life often when a natural disaster strikes, or a small number of a species is separated (e.g. a pond splits in two, or high winds migrate some animals across distance).
The thesis
Gradient descent, the engine under modern AI, needs a smooth, differentiable landscape to roll down. The genetic algorithm in your browser needs no such thing. It will happily optimise a target you can only score, never differentiate: a timetable, a circuit layout, a wing shape evaluated by a physics simulator. Whole classes of real problems have no gradient to descend, and on those, evolution isn't a quaint biological metaphor, nor a glorified random number generator, it's the only tool that works.
And the fitness function, the thing you were choosing every time you moved a slider, is where all the meaning lives. Change what you reward and you change what evolves, completely. I've watched evolutionary systems find gleeful, alien loopholes in a fitness function, technically-correct solutions no human would ever propose, and every one of them was a small lesson in being careful what you optimise for. It's the same lesson the paperclip thought-experiment provides.
So play with it. Melt it, starve it, inbreed it, and get a better feel for the importance of parameter selection and genetic algorithms.
Download the standalone demo
The algorithm (JavaScript, 406 lines)
/* ============================================================
Evolution, Live — the interactive demo for this post.
No dependencies. A genetic algorithm evolves paintings of a target letter
(K by default, any of A-Z from the toolbar select):
each individual is 50 translucent triangles (10 genes apiece: six vertex
coordinates, rgb, alpha), fitness is one minus the mean per-pixel
difference from a 48x48 target render. Tournament selection, per-triangle
crossover, per-gene mutation, optional two-slot elitism. Chart colours
come from the CSS custom properties on .evo-viz, so the site's light/dark
toggle restyles the widget live; the paintings themselves keep fixed
colours because the target never changes.
============================================================ */
(function () {
'use strict';
var wrap = document.getElementById('evo-demo');
if (!wrap) return;
var cv = document.getElementById('evoCanvas');
var chart = document.getElementById('evoChart');
function mulberry32(seed) {
var a = seed >>> 0;
return function () {
a |= 0; a = (a + 0x6D2B79F5) | 0;
var t = Math.imul(a ^ (a >>> 15), 1 | a);
t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
function vizColors(el) {
var cs = getComputedStyle(el);
function v(n) { return cs.getPropertyValue(n).trim(); }
return { s1: v('--viz-s1'), s2: v('--viz-s2'), s3: v('--viz-s3'), s4: v('--viz-s4'),
ink: v('--viz-ink'), muted: v('--viz-muted'), grid: v('--viz-grid'), surface: v('--viz-surface') };
}
var W = 0, H = 0, ctx = null, WC = 0, HC = 0, ctxC = null;
function fitOne(canvas, h) {
var dpr = window.devicePixelRatio || 1;
var w = canvas.clientWidth || 600;
canvas.style.height = h + 'px';
canvas.width = Math.round(w * dpr); canvas.height = Math.round(h * dpr);
var g = canvas.getContext('2d'); g.setTransform(dpr, 0, 0, dpr, 0, 0);
return { g: g, w: w, h: h };
}
function fitCanvas() {
// height tracks width: champion beside the grid on desktop, champion
// above the grid (and a taller canvas) on phones
var w = cv.clientWidth || 600;
var mainH = w < 480 ? Math.round(Math.min(600, w * 1.30))
: Math.round(Math.max(260, Math.min(340, w * 0.5)));
var m = fitOne(cv, mainH); ctx = m.g; W = m.w; H = m.h;
var c = fitOne(chart, w < 480 ? 170 : 120); ctxC = c.g; WC = c.w; HC = c.h;
}
// ---- tunables ----
var TRIS = 50, GENES = TRIS * 10, EVAL = 48; // genome + fitness render size
var EVAL_BUDGET = 120, MAX_GENS_FRAME = 2; // work per animation frame; low
// enough that the sharpening is
// watchable rather than instant
var ELITES = 2;
var BG = '#1e1e21', TARGET_INK = '#fc6060'; // fixed painting colours
// ---- state ----
var seedBase = 20260718, reseeds = 0, rng = mulberry32(seedBase);
var pop = []; // [{genes, fit, cv}], eval canvas per individual
var gen = 0, evals = 0, bestEver = 0, bestIdx = 0;
var hist = [], stride = 1, sinceSample = 0; // chart history, decimated as it grows
var running = true, raf = null;
var target = null, targetData = null;
// control refs
var runBtn = document.getElementById('evoRun');
var reseedBtn = document.getElementById('evoReseed');
var popS = document.getElementById('evoPop'), popV = document.getElementById('evoPopVal');
var mutS = document.getElementById('evoMut'), mutV = document.getElementById('evoMutVal');
var pressS = document.getElementById('evoPress'), pressV = document.getElementById('evoPressVal');
var eliteC = document.getElementById('evoElite');
var letterSel = document.getElementById('evoLetter');
var statusEl = document.getElementById('evoStatus');
var genEl = document.getElementById('evoGen'), bestEl = document.getElementById('evoBest');
var avgEl = document.getElementById('evoAvg'), divEl = document.getElementById('evoDiv');
var evalsEl = document.getElementById('evoEvals');
// ---- the target: one bold letter (K by default), re-rendered on change ----
function makeTarget(letter) {
target = document.createElement('canvas');
target.width = EVAL; target.height = EVAL;
var g = target.getContext('2d', { willReadFrequently: true });
g.fillStyle = BG; g.fillRect(0, 0, EVAL, EVAL);
g.fillStyle = TARGET_INK;
var size = 46;
g.font = '900 ' + size + 'px Arial, sans-serif';
var w = g.measureText(letter).width; // shrink-to-fit so W and M don't clip
if (w > EVAL - 6) {
size = Math.floor(size * (EVAL - 6) / w);
g.font = '900 ' + size + 'px Arial, sans-serif';
}
g.textAlign = 'center'; g.textBaseline = 'middle';
g.fillText(letter, EVAL / 2, EVAL / 2 + 2);
targetData = g.getImageData(0, 0, EVAL, EVAL).data;
}
// ---- genome plumbing ----
function renderGenome(genes, g, size) {
g.fillStyle = BG; g.fillRect(0, 0, size, size);
for (var t = 0; t < TRIS; t++) {
var i = t * 10;
g.fillStyle = 'rgba(' + (genes[i + 6] * 255 | 0) + ',' + (genes[i + 7] * 255 | 0) + ',' +
(genes[i + 8] * 255 | 0) + ',' + (genes[i + 9] * 0.85).toFixed(3) + ')';
g.beginPath();
g.moveTo(genes[i] * size, genes[i + 1] * size);
g.lineTo(genes[i + 2] * size, genes[i + 3] * size);
g.lineTo(genes[i + 4] * size, genes[i + 5] * size);
g.closePath(); g.fill();
}
}
function evaluate(ind) {
var g = ind.cv.getContext('2d', { willReadFrequently: true });
renderGenome(ind.genes, g, EVAL);
var d = g.getImageData(0, 0, EVAL, EVAL).data, sum = 0;
for (var p = 0; p < d.length; p += 4) {
sum += Math.abs(d[p] - targetData[p]) + Math.abs(d[p + 1] - targetData[p + 1]) +
Math.abs(d[p + 2] - targetData[p + 2]);
}
ind.fit = 1 - sum / (EVAL * EVAL * 3 * 255);
evals++;
}
function newIndividual(genes) {
var c = document.createElement('canvas');
c.width = EVAL; c.height = EVAL;
var ind = { genes: genes, fit: 0, cv: c };
evaluate(ind);
return ind;
}
function randomGenes() {
var g = new Float32Array(GENES);
for (var i = 0; i < GENES; i++) g[i] = rng();
return g;
}
// ---- the algorithm ----
function tournament(T) {
var bi = (rng() * pop.length) | 0;
for (var k = 1; k < T; k++) {
var j = (rng() * pop.length) | 0;
if (pop[j].fit > pop[bi].fit) bi = j;
}
return pop[bi];
}
function breed(pa, pb, pMut, dMut) {
var g = new Float32Array(GENES);
for (var t = 0; t < TRIS; t++) { // crossover: whole triangles from either parent
var src = rng() < 0.5 ? pa.genes : pb.genes;
for (var k = 0; k < 10; k++) g[t * 10 + k] = src[t * 10 + k];
}
for (var i = 0; i < GENES; i++) { // mutation: per-gene nudge, clamped to [0,1]
if (rng() < pMut) {
var v = g[i] + (rng() * 2 - 1) * dMut;
g[i] = v < 0 ? 0 : v > 1 ? 1 : v;
}
}
return g;
}
function stepGeneration() {
var n = pop.length;
// slider mappings: pressure 1 = uniform random parents (pure drift),
// 10 = the whole population in every tournament (winner takes all)
var s = +pressS.value;
var T = Math.max(1, Math.round(1 + (n - 1) * Math.pow((s - 1) / 9, 2)));
var mv = +mutS.value / 100;
var pMut = Math.pow(mv, 1.5) * 0.35;
var dMut = 0.05 + 0.45 * mv;
var elite = eliteC.checked ? Math.min(ELITES, n) : 0;
pop.sort(function (a, b) { return b.fit - a.fit; });
var next = pop.slice(0, elite);
while (next.length < n) next.push(newIndividual(breed(tournament(T), tournament(T), pMut, dMut)));
pop = next;
gen++;
sample();
}
function generationCost() {
return Math.max(1, pop.length - (eliteC.checked ? Math.min(ELITES, pop.length) : 0));
}
function runBudget() {
var spent = 0, gens = 0;
while (gens < MAX_GENS_FRAME && spent + generationCost() <= EVAL_BUDGET) {
stepGeneration();
spent += generationCost(); gens++;
}
}
// ---- stats + chart history ----
function popStats() {
var n = pop.length, sum = 0, best = -1, bi = 0;
for (var i = 0; i < n; i++) {
sum += pop[i].fit;
if (pop[i].fit > best) { best = pop[i].fit; bi = i; }
}
bestIdx = bi;
// diversity: mean per-gene standard deviation, normalised so a fully
// random population reads ~100% (std of uniform [0,1] is 1/sqrt(12))
var m, m2, gsum = 0;
for (var gI = 0; gI < GENES; gI++) {
m = 0; m2 = 0;
for (var j = 0; j < n; j++) { var v = pop[j].genes[gI]; m += v; m2 += v * v; }
m /= n;
gsum += Math.sqrt(Math.max(0, m2 / n - m * m));
}
var div = Math.min(1, (gsum / GENES) / 0.2887);
return { best: best, avg: sum / n, div: div };
}
function sample() {
if (++sinceSample < stride) return;
sinceSample = 0;
var st = popStats();
if (st.best > bestEver) bestEver = st.best;
hist.push({ g: gen, best: st.best, avg: st.avg, div: st.div });
if (hist.length >= 480) { // decimate so the chart array stays bounded
hist = hist.filter(function (_, i) { return i % 2 === 0; });
stride *= 2;
}
}
// ---- drawing ----
function layout() {
var pad = 10, lab = 16;
if (W < 480) {
var s = Math.round(Math.min(W - 2 * pad, H * 0.55));
var gy = pad + lab + s + pad + lab;
return { champ: { x: (W - s) / 2, y: pad + lab, s: s },
grid: { x: pad, y: gy, w: W - 2 * pad, h: H - gy - pad } };
}
var side = H - 2 * pad - lab;
var gx = pad + side + pad + 8;
return { champ: { x: pad, y: pad + lab, s: side },
grid: { x: gx, y: pad + lab, w: W - gx - pad, h: side } };
}
function label(text, x, y, c, align) {
ctx.fillStyle = c;
ctx.font = '600 10px Poppins, sans-serif';
ctx.textAlign = align || 'start'; ctx.textBaseline = 'alphabetic';
ctx.fillText(text, x, y);
ctx.textAlign = 'start';
}
function draw() {
var c = vizColors(wrap);
var L = layout();
var st = popStats(); // refreshes bestIdx so the champion pane never lags
ctx.clearRect(0, 0, W, H);
ctx.fillStyle = c.surface; ctx.fillRect(0, 0, W, H);
// champion pane: the best individual, rendered as vectors so it stays crisp
label('CHAMPION', L.champ.x, L.champ.y - 5, c.muted);
ctx.save();
ctx.translate(L.champ.x, L.champ.y);
renderGenome(pop[bestIdx].genes, ctx, L.champ.s);
ctx.restore();
ctx.strokeStyle = c.grid; ctx.lineWidth = 1;
ctx.strokeRect(L.champ.x + 0.5, L.champ.y + 0.5, L.champ.s - 1, L.champ.s - 1);
// target inset, top-right corner of the champion pane
var ts = Math.max(34, Math.round(L.champ.s * 0.24));
var tx = L.champ.x + L.champ.s - ts - 6, ty = L.champ.y + 6;
ctx.drawImage(target, tx, ty, ts, ts);
ctx.strokeStyle = c.muted; ctx.strokeRect(tx + 0.5, ty + 0.5, ts - 1, ts - 1);
label('TARGET', L.champ.x + L.champ.s, L.champ.y - 5, c.muted, 'right');
// population grid: every individual's evaluation render, champion ringed
label('POPULATION', L.grid.x, L.grid.y - 5, c.muted);
var n = pop.length;
var cols = Math.max(1, Math.ceil(Math.sqrt(n * L.grid.w / Math.max(1, L.grid.h))));
var rows = Math.ceil(n / cols);
var cell = Math.floor(Math.min(L.grid.w / cols, L.grid.h / rows));
for (var i = 0; i < n; i++) {
var x = L.grid.x + (i % cols) * cell, y = L.grid.y + ((i / cols) | 0) * cell;
ctx.drawImage(pop[i].cv, x + 1, y + 1, cell - 2, cell - 2);
if (i === bestIdx) {
ctx.strokeStyle = c.s2; ctx.lineWidth = 2;
ctx.strokeRect(x + 1.5, y + 1.5, cell - 3, cell - 3);
ctx.lineWidth = 1;
}
}
drawChart(c);
updateStats(st);
}
function drawChart(c) {
ctxC.clearRect(0, 0, WC, HC);
ctxC.fillStyle = c.surface; ctxC.fillRect(0, 0, WC, HC);
var x0 = 34, x1 = WC - 62, y0 = 8, y1 = HC - 16;
ctxC.font = '9px Poppins, sans-serif';
[0, 0.5, 1].forEach(function (p) {
var y = y1 - (y1 - y0) * p;
ctxC.strokeStyle = c.grid; ctxC.lineWidth = 1;
ctxC.beginPath(); ctxC.moveTo(x0, y + 0.5); ctxC.lineTo(x1, y + 0.5); ctxC.stroke();
ctxC.fillStyle = c.muted; ctxC.textAlign = 'right';
ctxC.fillText(Math.round(p * 100) + '%', x0 - 5, y + 3);
});
ctxC.textAlign = 'center';
ctxC.fillStyle = c.muted;
ctxC.fillText('generations', (x0 + x1) / 2, HC - 4);
ctxC.textAlign = 'start';
if (hist.length < 2) return;
var g0 = hist[0].g, g1 = hist[hist.length - 1].g;
function X(gi) { return x0 + (x1 - x0) * ((gi - g0) / Math.max(1, g1 - g0)); }
function Y(v) { return y1 - (y1 - y0) * v; }
var series = [ { k: 'best', col: c.s2, name: 'best' },
{ k: 'avg', col: c.s1, name: 'average' },
{ k: 'div', col: c.s3, name: 'diversity' } ];
// series lines, labelled at their right-hand ends (labels nudged apart)
var ends = [];
series.forEach(function (s) {
ctxC.beginPath();
for (var i = 0; i < hist.length; i++) {
var x = X(hist[i].g), y = Y(hist[i][s.k]);
if (i === 0) ctxC.moveTo(x, y); else ctxC.lineTo(x, y);
}
ctxC.strokeStyle = s.col; ctxC.lineWidth = 1.6; ctxC.stroke();
ends.push({ y: Y(hist[hist.length - 1][s.k]), col: s.col, name: s.name });
});
ends.sort(function (a, b) { return a.y - b.y; });
for (var e = 1; e < ends.length; e++) {
if (ends[e].y - ends[e - 1].y < 10) ends[e].y = ends[e - 1].y + 10;
}
ends.forEach(function (e2) {
ctxC.fillStyle = e2.col;
ctxC.fillText(e2.name, x1 + 5, Math.max(y0 + 6, Math.min(y1, e2.y)) + 3);
});
}
function fmtPct(v) { return (v * 100).toFixed(1) + '%'; }
function updateStats(st) {
genEl.textContent = gen;
bestEl.textContent = fmtPct(Math.max(bestEver, st.best));
avgEl.textContent = fmtPct(st.avg);
divEl.textContent = Math.round(st.div * 100) + '%';
evalsEl.textContent = evals >= 10000 ? (evals / 1000).toFixed(0) + 'k' : evals;
}
// ---- run control ----
function loop() {
if (!running) return;
runBudget();
draw();
raf = requestAnimationFrame(loop);
}
function start() { if (running) raf = requestAnimationFrame(loop); }
function resetSim() {
rng = mulberry32(seedBase + reseeds * 9973);
evals = 0; gen = 0; bestEver = 0; bestIdx = 0;
hist = []; stride = 1; sinceSample = 0;
pop = [];
var n = +popS.value;
for (var i = 0; i < n; i++) pop.push(newIndividual(randomGenes()));
sample();
}
runBtn.addEventListener('click', function () {
running = !running;
runBtn.textContent = running ? 'Pause' : 'Play';
statusEl.textContent = running ? '' : 'Paused.';
if (running) start(); else if (raf) cancelAnimationFrame(raf);
});
reseedBtn.addEventListener('click', function () {
reseeds++; resetSim();
if (!running) draw();
});
function setPop() {
popV.textContent = popS.value;
var n = +popS.value;
if (n === pop.length) return;
pop.sort(function (a, b) { return b.fit - a.fit; });
if (n < pop.length) pop = pop.slice(0, n);
else while (pop.length < n) { // grow with mutated copies of survivors
var p = pop[(rng() * pop.length) | 0];
pop.push(newIndividual(breed(p, p, 0.1, 0.3)));
}
if (!running) draw();
}
function setMut() { mutV.textContent = mutS.value + '%'; }
function setPress() { pressV.textContent = pressS.value; }
popS.addEventListener('input', setPop);
mutS.addEventListener('input', setMut);
pressS.addEventListener('input', setPress);
letterSel.addEventListener('change', function () {
// a new target is a new fitness landscape: re-render it and start over
makeTarget(letterSel.value);
resetSim();
if (!running) draw();
});
window.addEventListener('resize', function () { fitCanvas(); if (!running) draw(); });
new MutationObserver(function () { draw(); }).observe(document.documentElement, { attributes: true, attributeFilter: ['data-theme'] });
// ---- init ----
for (var li = 0; li < 26; li++) {
var opt = document.createElement('option');
opt.value = opt.textContent = String.fromCharCode(65 + li);
if (opt.value === 'K') opt.selected = true;
letterSel.appendChild(opt);
}
makeTarget('K');
fitCanvas();
setMut(); setPress(); popV.textContent = popS.value;
resetSim();
draw();
start();
})();
Common questions
Is this how real biological evolution works?
Ish. This is a metaphor. Real evolution has no fitness function written down anywhere (fitness just is reproductive success), no fixed population size, no clean generations, and no goal. The GA borrows the process (variation plus selection) and bolts on an explicit target because we want something specific, while nature just wants a mix of equilibrium of an ecosystem and successful species.
Why would I use this instead of a neural network?
When the thing you're optimising isn't differentiable and can only be scored: discrete layouts, schedules, structures evaluated by a simulator, or strategies. Gradient-based methods (which power neural nets) need a smooth slope to follow; evolution doesn't. They're also not rivals: evolutionary methods are increasingly used to tune, prune, and search neural architectures, so the two often ride together.
Doesn't this waste a lot of computation on bad candidates?
Yes: the population is insurance against getting stuck, paid for in extra evaluations. On easy, smooth problems it's wasteful and a hill climber wins. On hard, rugged, deceptive ones, the wasted evaluations are what keeps evolution from committing early to a bad answer. No algorithm wins everywhere; that's the No Free Lunch theorem.
