John Holland, 1975 — lifting "variation + selection + recombination" out of biology and running it as a general-purpose search machine
Referenced by: Topic 26 Complex Adaptive Systems
01The Question It Poses
Some problems let you say what "good" means without giving you any route towards it. What shape should an antenna be bent into to receive best in a given band? How do you schedule three hundred flights so that every constraint holds and two fewer aircraft are needed? There is no formula to solve, and no slope to walk down — you can only try things, and the combinations run to more than you could test in the age of the universe.
Nature has solved problems of this kind, by an embarrassingly dumb method: produce a batch of slightly different offspring, let the environment discard most of them, recombine the survivors, repeat. Holland's question was: does the method survive being taken out of biology? Written as a few dozen lines of code, can it still find good solutions to a problem nobody has ever understood?
02The Rules
Encode a candidate answer as a string of symbols (classically a string of 0s and 1s). One string is an individual.
Generate a group of them at random — say 100. The group is a population.
Score every individual. The scoring function is the fitness function — the only thing you must supply, and the only channel through which "what counts as good" reaches the algorithm.
Selection: higher scores are more likely to be picked as parents. Not only the best, though — some middling ones must survive, or diversity is gone in a single round.
Crossover: take two parents, cut at a random point, swap the tails, and get two children.
Mutation: with small probability (often a fraction of a percent), flip some bits.
Replace the old population with the children and go back to step 3. Repeat for hundreds to tens of thousands of generations.
Steps 3 and 5 are worth pausing on. The fitness function says how good, never why — the algorithm knows nothing about the structure of the problem, which is exactly why it can be pointed at problems you do not understand. And crossover is what separates this from random flailing: it assumes that fragments of a good solution can be found separately and then assembled. Whether that assumption holds on your problem decides whether the method is startlingly fast or absurdly slow.
One crossover produces two children; mutation then flips a bit with small probability. Those two steps are the entire source of novelty.
03What You See When It Runs
The signature curve rises steeply and then flattens: dozens of early generations bring large gains (the improvements lying around loose), then progress slows. The shape itself carries information — it tells you roughly how much headroom is left.
The second common event is premature convergence: every individual in the population becomes nearly identical and the search sits on a mediocre solution. Crossover then produces nothing new (cutting and splicing two identical strings returns the same string), leaving only mutation to make tiny random jiggles, and the curve goes flat for good. Once diversity is spent it is hard to recover — this is the classic failure mode.
Flat curves have two quite different causes. The crude test works: measure how different the individuals still are from each other and see whether that collapsed too.
The third thing is the most interesting: the solutions often look strange. NASA's ST5 spacecraft flew an antenna designed by an evolutionary algorithm in 2006, shaped like a paperclip bent absent-mindedly out of true — no human antenna engineer would draw that, and it met the specification. That is the method's most honest advertisement: it does not understand the problem, so it is not constrained by what the answer is supposed to look like.
04What It Explains
Strictly, a genetic algorithm is a tool rather than an explanation. But it demonstrates something hard to show elsewhere: design without a designer works, and needs remarkably few parts. A batch of candidates, a score that reports only quality, and a procedure for copying and recombining — with those three, complex and effective structure appears, and nobody has to understand why it works.
That is also its place on this site: it is the minimum runnable version of adaptation. When you suspect an organisation, a market or an ecosystem is adapting, going and finding those three parts beats any metaphor.
What It Cannot Explain
It is not a model of natural selection. Here the fitness function is supplied by a person, fixed, and computable; in real evolution what counts as fit is set jointly by the environment and every other organism, and it moves constantly (Topic 31, the Red Queen, is about exactly that). Arguing biology from the behaviour of a GA needs great care.
No free lunch. Wolpert and Macready proved in 1997 that averaged over all possible problems, no optimisation algorithm beats any other — random search included. A GA's advantage is never that it is cleverer; it is that its assumption (good fragments can be found separately and assembled) happens to match the structure of a certain class of problems. Where it doesn't match, you have an expensive random search.
It guarantees no optimum and reports no distance to one. When the run ends you have a solution and a curve, and no bound on how much better things could be. Where such guarantees matter — scheduling with strict optimality requirements, combinatorial problems with provable bounds — use something else.
Expensive evaluation rules it out. Tens of thousands to millions of scorings are routine. If one scoring means running a fluid simulation, performing a physical experiment, or waiting a quarter for results, the method is out on budget alone.
The encoding decides everything, and there is no theory of encodings. The same problem under a different representation can behave completely differently, and which representation makes good fragments contiguous is currently a matter of craft and trial. Users routinely underestimate this cost.
Do not treat the schema theorem as the explanation of why it works. Holland's schema theorem and the building block hypothesis give an intuitive framework, but whether they account for actual GA performance has been contested for decades. Fine as a story; not a proof.