loading...
running...
How to use
Press a preset, then watch the beads climb the landscape. The white ring marks the best individual, the green cross or ring the true global optimum, the gold line the path of the best individual. Click the landscape to scatter the individuals under the cursor (a local catastrophe) and watch the population recover. Try: (1) Rugged, balanced: the population finds the green optimum; (2) Too greedy: large tournaments and tiny mutations lock onto a local peak, diversity collapses; (3) Random drift (k = 1): no improvement without selection; (4) Deceptive trap: most runs choose the wide decoy hill, raise sigma and population to find the narrow peak; (5) change the random seed to see how much a single run varies. Space pauses, R restarts.
The science
The idea. Evolutionary computation searches for good solutions the way populations evolve. Each individual is a candidate solution, here a pair of genes (x, y) in the unit square; its fitness F(x, y) says how good it is. Fitter individuals are more likely to become parents, offspring mix and perturb the parents' genes, and the process repeats generation after generation. It needs only the ability to evaluate F, not its gradient, so it works on rugged landscapes where hill climbing gets stuck.
One generation of this genetic algorithm.
1. keep the e fittest unchanged (elitism)
2. repeat until N offspring: pick two parents by tournament of size k (best of k random individuals)
3. with probability pc cross them: BLX-0.3, child gene uniform in [lo - 0.3 w, hi + 0.3 w], w = hi - lo
4. each gene mutates with probability pm: g ← g + σ N(0,1), then is clipped to [0, 1]
Selection pressure. In a tournament of size k from a population of N, the single best individual wins with probability
Pbest = 1 - (1 - 1/N)k ≈ k/N, takeover time ≈ ln N / ln k generations
Large k drives the population to the best known point quickly, but it also kills diversity: the population may converge to a local peak (premature convergence). Tournament size k = 1 is pure random drift. The readout shows Pbest and the takeover-time estimate (the estimate assumes selection alone, no variation, on a landscape where the best individual keeps its lead).
Exploration and exploitation. The mutation step σ and crossover rate set how far offspring land from their parents. Small steps refine the current best (exploitation); large steps and crossover between distant parents explore. The diversity graph (mean pairwise distance, estimated on a subsample) shows when the population has collapsed to one peak.
Landscapes. Rugged is an inverted Rastrigin function, F = 1 - [20 + u2 + v2 - 10(cos 2πu + cos 2πv)] / 80 with u = 10.24 (x - 0.5), v = 10.24 (y - 0.5): about 100 local peaks and one global peak F = 1 at (0.5, 0.5). Six hills is a maximum of Gaussian bumps, and deceptive has a broad decoy hill (height 0.8) next to a narrow true peak (height 1.0) so that gradient-following search is led astray. The global optimum of the last two is found by a 400 x 400 grid scan.
Checks (run in the page). (1) the sampled probability that the best of 20 individuals wins a size-3 tournament equals 1 - (1 - 1/20)3; (2) one round of size-2 tournaments on F = x gives mean fitness 2/3, the expected maximum of two uniform numbers; (3) the best of 9 uniform random draws averages N/(N+1) = 0.9, which tests the random generator; (4) the algorithm locates the analytic optimum of the rugged landscape.
Simplifications. Two genes only, real-valued, no noise in F, a generational (not steady-state) scheme and no speciation or niching. Results for a given seed are exactly reproducible; different seeds give different histories, so a single run is an anecdote, not a statistic. The 3D page uses the same model.js and the same random sequence as the 2D page.