Skip to content
Computational Lab.

Genetic Algorithm

Selection, crossover, mutation - repeat.

Intermediate / optimization / evolution / search

A population of candidates lives on a rugged fitness landscape. Each generation brings tournament selection, blend crossover, gaussian mutation, and a few elites carried through unchanged. No gradient exists here - the algorithm only ever compares fitness values, which is exactly what makes GAs fit landscapes that break gradient methods.

Tagged: tournament selection, crossover, mutation, elitism

Live simulation

The dots are the population climbing the landscape; accent marks the current best.

Speed

The dots are the population climbing the landscape; accent marks the current best.

Mathematics

A genetic algorithm searches by evolving a population: candidates with higher fitness are selected as parents, traits are blended by crossover, and mutation perturbs the result. No derivatives - selection pressure is the only gradient-like signal.

selection: k-way tournament (pick k random, keep the fittest)

crossover: child = alpha * parent_a + (1 - alpha) * parent_b

mutation: child += N(0, sigma_mutation); elites carried unchanged

Elitism guarantees the best fitness never decreases, which the history strip shows as a monotone ceiling over a noisy population mean. Raising the mutation sigma explores more but commits less - the classic exploration-exploitation trade-off, one slider wide.

How it works

The landscape is a fixed sum of four Gaussian peaks plus a mild ripple, evaluated at each candidate's (x, y). Each tick runs a configurable number of generations: rank, copy elites, breed the rest by tournament and blend crossover, mutate, clamp to the unit square.

The heatmap is the landscape itself; the population dots are drawn on top, with the current best highlighted in accent.

Implementation

src/engine/experiments/genetic-algorithm.ts · 204 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ParameterDef, ThemeColors } from "../core/types";
3
4/**
5 * Genetic algorithm optimizing over a rugged 2-D landscape:
6 * tournament selection, blend crossover, gaussian mutation, elitism.
7 * The population dots on the heatmap ARE the algorithm's state.
8 */
9export class GeneticAlgorithmExperiment extends BaseExperiment {
10 readonly id = "genetic-algorithm";
11
12 private popX = new Float64Array(0);
13 private popY = new Float64Array(0);
14 private fitness = new Float64Array(0);
15 private popSize = 0;
16 private generation = 0;
17 private bestFitness = 0;
18 private meanFitness = 0;
19 private history: number[] = [];
20
21 protected params(): ParameterDef[] {
22 return [
23 { key: "population", label: "Population", min: 20, max: 200, step: 10, defaultValue: 80 },
24 { key: "mutation", label: "Mutation sigma", min: 0.005, max: 0.15, step: 0.005, defaultValue: 0.04 },
25 { key: "elitism", label: "Elites kept", min: 1, max: 10, step: 1, defaultValue: 3 },
26 { key: "generations", label: "Generations per tick", min: 1, max: 10, step: 1, defaultValue: 1 },
27 ];
28 }
29
30 /** Rugged multi-peak landscape in [0,1]^2. */
31 private landscape(x: number, y: number): number {
32 const peak = (cx: number, cy: number, s: number, amp: number) =>
33 amp * Math.exp(-(((x - cx) ** 2 + (y - cy) ** 2) / (2 * s * s)));
34 return (
35 peak(0.28, 0.3, 0.09, 1) +
36 peak(0.72, 0.62, 0.12, 0.86) +
37 peak(0.6, 0.2, 0.05, 0.6) +
38 peak(0.2, 0.78, 0.07, 0.5) +
39 0.12 * Math.sin(x * 21) * Math.cos(y * 18)
40 );
41 }
42
43 protected onReset(): void {
44 this.popSize = this.num("population");
45 this.popX = new Float64Array(this.popSize);
46 this.popY = new Float64Array(this.popSize);
47 this.fitness = new Float64Array(this.popSize);
48 for (let i = 0; i < this.popSize; i++) {
49 this.popX[i] = this.rng();
50 this.popY[i] = this.rng();
51 this.fitness[i] = this.landscape(this.popX[i], this.popY[i]);
52 }
53 this.generation = 0;
54 this.history = [];
55 this.evaluate();
56 }
57
58 protected onParameterChange(key: string): void {
59 if (key !== "generations") this.reset();
60 }
61
62 resize(width: number, height: number): void {
63 this.width = width;
64 this.height = height;
65 }
66
67 private evaluate(): void {
68 let best = -Infinity;
69 let sum = 0;
70 for (let i = 0; i < this.popSize; i++) {
71 this.fitness[i] = this.landscape(this.popX[i], this.popY[i]);
72 best = Math.max(best, this.fitness[i]);
73 sum += this.fitness[i];
74 }
75 this.bestFitness = best;
76 this.meanFitness = sum / this.popSize;
77 }
78
79 private tournament(k = 3): number {
80 let best = Math.floor(this.rng() * this.popSize);
81 for (let i = 1; i < k; i++) {
82 const challenger = Math.floor(this.rng() * this.popSize);
83 if (this.fitness[challenger] > this.fitness[best]) best = challenger;
84 }
85 return best;
86 }
87
88 protected onUpdate(): void {
89 const elites = Math.min(this.num("elitism"), this.popSize - 1);
90 const sigma = this.num("mutation");
91 const generations = this.num("generations");
92 for (let g = 0; g < generations; g++) {
93 // Rank indices by fitness.
94 const order = Array.from({ length: this.popSize }, (_, i) => i);
95 order.sort((a, b) => this.fitness[b] - this.fitness[a]);
96 const nextX = new Float64Array(this.popSize);
97 const nextY = new Float64Array(this.popSize);
98 // Elitism: carry the best unchanged.
99 for (let e = 0; e < elites; e++) {
100 nextX[e] = this.popX[order[e]];
101 nextY[e] = this.popY[order[e]];
102 }
103 for (let i = elites; i < this.popSize; i++) {
104 const pa = this.tournament();
105 const pb = this.tournament();
106 // Blend crossover.
107 const alpha = this.rng();
108 let x = alpha * this.popX[pa] + (1 - alpha) * this.popX[pb];
109 let y = alpha * this.popY[pa] + (1 - alpha) * this.popY[pb];
110 // Gaussian mutation.
111 x += (this.rng() + this.rng() + this.rng() - 1.5) * sigma;
112 y += (this.rng() + this.rng() + this.rng() - 1.5) * sigma;
113 nextX[i] = Math.min(1, Math.max(0, x));
114 nextY[i] = Math.min(1, Math.max(0, y));
115 }
116 this.popX = nextX;
117 this.popY = nextY;
118 this.generation += 1;
119 this.evaluate();
120 this.history.push(this.bestFitness);
121 if (this.history.length > 400) this.history.shift();
122 }
123 }
124
125 onPointer(): void {}
126
127 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
128 ctx.fillStyle = theme.bg;
129 ctx.fillRect(0, 0, this.width, this.height);
130 // Landscape heatmap (low-res blocks)
131 const cells = 44;
132 const cw = this.width / cells;
133 const ch = this.height / cells;
134 let min = Infinity;
135 let max = -Infinity;
136 const grid = new Float64Array(cells * cells);
137 for (let gy = 0; gy < cells; gy++) {
138 for (let gx = 0; gx < cells; gx++) {
139 const value = this.landscape((gx + 0.5) / cells, (gy + 0.5) / cells);
140 grid[gy * cells + gx] = value;
141 min = Math.min(min, value);
142 max = Math.max(max, value);
143 }
144 }
145 for (let gy = 0; gy < cells; gy++) {
146 for (let gx = 0; gx < cells; gx++) {
147 const t = (grid[gy * cells + gx] - min) / (max - min);
148 const alpha = 0.06 + t * 0.3;
149 ctx.fillStyle = t > 0.72 ? theme.accent : theme.fgSecondary;
150 ctx.globalAlpha = alpha;
151 ctx.fillRect(gx * cw, gy * ch, cw + 0.5, ch + 0.5);
152 }
153 }
154 ctx.globalAlpha = 1;
155 // Population
156 for (let i = 0; i < this.popSize; i++) {
157 const rank = this.fitness[i] >= this.bestFitness - 1e-9;
158 ctx.fillStyle = rank ? theme.accent : theme.fg;
159 ctx.beginPath();
160 ctx.arc(this.popX[i] * this.width, this.popY[i] * this.height, rank ? 3.6 : 2.2, 0, Math.PI * 2);
161 ctx.fill();
162 }
163 // Best-fitness history (bottom strip)
164 if (this.history.length > 2) {
165 ctx.strokeStyle = theme.viz[1];
166 ctx.lineWidth = 1.5;
167 ctx.globalAlpha = 0.8;
168 ctx.beginPath();
169 let lo = Infinity;
170 let hi = -Infinity;
171 for (const h of this.history) {
172 lo = Math.min(lo, h);
173 hi = Math.max(hi, h);
174 }
175 const span = Math.max(1e-6, hi - lo);
176 for (let i = 0; i < this.history.length; i++) {
177 const x = (i / (this.history.length - 1)) * this.width;
178 const y = this.height - 8 - ((this.history[i] - lo) / span) * 26;
179 if (i === 0) ctx.moveTo(x, y);
180 else ctx.lineTo(x, y);
181 }
182 ctx.stroke();
183 ctx.globalAlpha = 1;
184 }
185 }
186
187 getMetrics() {
188 return {
189 generation: this.generation,
190 best: this.bestFitness.toFixed(4),
191 mean: this.meanFitness.toFixed(4),
192 mutation: this.num("mutation").toFixed(3),
193 };
194 }
195
196 describe(): string {
197 return `Generation ${this.generation}: the best of ${this.popSize} candidates reaches fitness ${this.bestFitness.toFixed(3)} on the rugged landscape.`;
198 }
199
200 entities(): number {
201 return this.popSize;
202 }
203}
204

Performance

Time per tick
O(population) fitness evaluations per generation
Space
Two population arrays plus a history buffer
Notes
Drop mutation to zero after a few generations and the population collapses onto its elites - premature convergence, live.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.