The idea: evolve a population
A genetic algorithm (GA) searches for a good solution the way breeding improves a herd. It keeps a population of candidate solutions, each written as a string of bits called a chromosome. Each generation it scores every chromosome with a fitness function, picks fitter ones as parents more often, mixes the parents' bits into children, flips a few bits at random, and lets the children replace the old population. Nothing in the loop knows how the problem works; it only needs the fitness score.
The animation uses 6 chromosomes of 12 bits. The left panel is the current population, the middle panel is where two parents make two children, and the right panel fills up with the next generation. The chart below plots the best and the average fitness of every generation. All random numbers come from a seeded generator: the same seed and settings always give the same run, and New Population moves to the next seed.
Fitness: the OneMax problem
The problem here is OneMax: the fitness of a chromosome is the number of 1 bits, so the best possible string is 111111111111 with fitness 12. The 1 bits are drawn green and each row has a fitness bar. OneMax is a toy, but the loop is the same for real problems: for a knapsack, bit i means "take item i" and the fitness is the total value (zero if the weight is over the limit); for a schedule or a circuit layout, the bits encode the choices and the fitness is the score of the result.
Selection: tournament or roulette wheel
Selection is where the pressure towards better solutions comes from: fitter chromosomes become parents more often, but weaker ones still get a chance, which keeps some variety.
| Method | How a parent is picked | Notes |
|---|---|---|
| Tournament (k = 2) | Pick 2 chromosomes at random; the fitter one wins. | Only the order of fitness matters. A larger k means stronger pressure. |
| Roulette wheel | Each chromosome gets a slice of a wheel in proportion to its fitness; a random spin r in [0, Σf) picks one. | Fitness 8 vs 6 is only 8 : 6, so the pressure is weak when all fitness values are close. |
In the middle panel, a tournament shows both contests (A: #2 (f 4) vs #5 (f 3) → #2); the roulette wheel is drawn as a strip with one slice per chromosome and the two spins marked ▼A and ▼B. (Demo: one generation, step by step and Demo: roulette-wheel selection, step by step.) The same chromosome can be picked as both parents.
Single-point crossover
Crossover mixes two parents. Single-point crossover picks a random cut between two bits; child 1 keeps parent A's head and takes parent B's tail, and child 2 the other way round. Good pieces (a run of 1 bits in A's head, another in B's tail) can end up together in one child. The page always applies crossover (crossover rate 1.0). Parent A's bits are blue and parent B's are orange, so each child shows where its bits came from.
Mutation: too little, too much
Mutation flips each bit of a child with a small probability pm. The usual choice is about 1/L, one flipped bit per child on average; here 1/12 ≈ 0.08. Flipped bits are drawn red.
- pm = 0. Selection and crossover only reshuffle bits that are already in the population. If some bit position is 0 in every chromosome, no crossover can put a 1 there again. Selection keeps copying the best strings, the population turns into copies of one string, and the search stops short of the optimum. This is premature convergence. (Demo: mutation rate 0 gets stuck: with seed 4 the six chromosomes become identical
001010100101at fitness 5, while the same seed with pm 0.08 reaches 12.) - pm = 0.5. Every bit is a coin flip, so a child has nothing to do with its parents. The average fitness stays near 6 (half of 12) and the best only improves by luck: a random search. (Demo: mutation rate 0.5 is a random search.)
Elitism
Without care, the best chromosome can be lost: it may not be selected, or crossover and mutation may break it. Elitism copies the best one (or the best few) unchanged into the next generation, so the best fitness never goes down. The copy is drawn with a gold tag in slot #1. (Demo: elitism off vs on: with seed 6 and elitism off the best reaches 11 and then falls back to 7; with elitism on it only climbs, to 12 by generation 19.) Elitism also has a cost: one copy of the best takes a slot, which speeds up the loss of variety.
Where GAs fit
A GA is a black-box search: it needs no gradient, so it works on discrete, noisy or oddly shaped problems (scheduling, layouts, feature selection, tuning settings, evolving antenna shapes). It is not guaranteed to find the optimum and usually needs many fitness evaluations, so a method that knows the problem (dynamic programming for an exact knapsack, gradient descent for a smooth loss) wins when one exists. Compared with hill climbing and simulated annealing, which move one solution, a GA moves a whole population and combines parts of different solutions through crossover.
What the page leaves out
Real GAs use larger populations (50–1000) and run for hundreds of generations. The page always crosses over (rate 1.0) and keeps exactly one elite. It leaves out other encodings (real numbers, permutations with order crossover for the travelling salesman), two-point and uniform crossover, rank selection and fitness scaling, constraint handling with penalties, diversity tricks such as niching and island models, and the related methods of evolution strategies and genetic programming.