Genetic Algorithms: Evolution as Computation

Nature's most powerful optimisation process is evolution. Over billions of years, natural selection has produced organisms exquisitely adapted to their environments - from the aerodynamic shape of a peregrine falcon to the light-harvesting efficiency of photosynthetic pigments. Genetic algorithms (GAs) borrow this logic and apply it to computational problems, turning Darwinian evolution into a general-purpose search and optimisation engine.

The Biological Inspiration

In biological evolution, a population of organisms reproduces with variation. Offspring inherit traits from their parents, sometimes with mutations. Those individuals best suited to the environment survive and reproduce more successfully - a process Darwin called natural selection. Over many generations, the population adapts. No central planner is needed; adaptation emerges from the interplay of variation, inheritance, and selection.

This insight - that complex, well-adapted solutions can arise from simple evolutionary mechanisms - is the foundation of evolutionary computation. John Holland formalised genetic algorithms in the 1970s, showing that populations of candidate solutions can evolve toward optimal or near-optimal answers through analogues of biological processes [1].

How Genetic Algorithms Work

A genetic algorithm maintains a population of candidate solutions, each encoded as a string (often binary, but any representation works). The algorithm repeatedly applies three operators inspired by biology:

Selection - individuals are chosen for reproduction based on their fitness. Fitter individuals are more likely to be selected, mimicking survival of the fittest. Common methods include tournament selection and roulette-wheel (fitness-proportionate) selection.

Crossover - selected parents exchange segments of their genetic material to produce offspring. This recombination allows useful building blocks from different parents to be combined, just as sexual reproduction shuffles alleles in biology [1].

Mutation - small random changes are introduced into offspring, maintaining genetic diversity and preventing the population from converging prematurely on a suboptimal solution. In a binary GA, this might mean flipping a single bit.

Each cycle of selection, crossover, and mutation constitutes one generation. Over successive generations, average fitness tends to increase - the population evolves.

One Generation, Traced by Hand

The loop is easier to believe once you have watched it turn once. Take the task used by the simulation on this site: evolve a population of random character strings towards a target phrase. Say the target is HELLO and fitness is simply the number of positions that match, so the maximum score is 5.

Start with four random individuals:

individual   genes    matches   fitness
A            HXLLP    H _ L L _      3
B            QELDO    _ E L _ O      3
C            ZBRTV    _ _ _ _ _      0
D            HEQQO    H E _ _ O      3

Selection. C never gets to reproduce - not because anything examined it and judged it hopeless, but because a fitness-weighted draw almost never picks a zero. A, B and D enter the mating pool.

Crossover. Pair A with D and cut after position 2. A contributes HX, D contributes QQO, giving HXQQO - fitness 2, worse than either parent. Cut the same pair after position 3 instead and you get HXLQO, fitness 3. Now pair B with D after position 1: Q + EQQO gives fitness 2, but D with B gives H + ELDO = HELDO, fitness 4. That last child is better than anything in the starting population, and no individual invented it: D supplied a correct H, B supplied a correct EL and O, and crossover merely put the two halves in the same string. That is the building block hypothesis in one move.

Mutation. Flip one random character in HELDO. Most flips make it worse and those offspring quietly lose the next selection round. But the D in position 4 can only become an L by mutation - no parent in the pool has one, so crossover can never supply it. Crossover recombines what already exists; mutation is the only source of genuinely new material.

Repeat a few hundred times and the population converges on HELLO. Nothing in the loop knows what a word is, that position 4 is wrong, or which direction is better. It only ever compares whole candidates by score.

The Broader Family: Evolutionary Algorithms

Genetic algorithms are part of a larger family called evolutionary algorithms (EAs), which includes evolution strategies, evolutionary programming, and genetic programming. Evolution strategies, developed by Rechenberg and Schwefel in the 1960s, focus on continuous parameter optimisation and use self-adaptive mutation step sizes [2]. Genetic programming, pioneered by Koza, evolves entire computer programs represented as tree structures [3].

All evolutionary algorithms share the same Darwinian loop: a population of varied individuals undergoes selection based on fitness, produces offspring through recombination and mutation, and iterates over generations. The differences lie in representation, operator design, and selection pressure.

Schema Theory and Building Blocks

Holland's Schema Theorem provides a theoretical underpinning for why GAs work. A schema is a template describing a subset of strings that share certain fixed positions. The theorem shows that short, low-order schemata with above-average fitness receive exponentially increasing representation in the population over time - the building block hypothesis [1]. This means GAs implicitly sample a vast number of candidate building blocks in parallel.

It is worth being careful with this argument. The schema theorem is a useful intuition rather than a performance guarantee: it describes how schema representation changes over one generation under idealised assumptions, and it says nothing about whether the building blocks a given encoding exposes are the ones the problem is actually made of. Choose a poor representation and crossover will happily shred the structure you were hoping it would preserve. The no-free-lunch results make the boundary explicit - averaged over all possible problems, no search algorithm beats any other, so a GA's advantage always comes from a match between its operators and the structure of the specific problem in front of it.

Real-World Applications

Genetic algorithms have been applied across an extraordinary range of domains. In engineering, they optimise the topology of structures and the shapes of turbine blades. In scheduling, they solve timetabling and job-shop problems. In machine learning, they tune hyperparameters and evolve neural network architectures - a technique called neuroevolution [4].

The most quietly remarkable example flew. For NASA's Space Technology 5 mission, an evolutionary algorithm was used to design the spacecraft's X-band antenna, searching over wire geometries against a simulated radiation pattern [5]. The result looks like a bent paperclip: a few centimetres of wire folded at angles no antenna engineer would draw, because no design convention produced it and none of it is decorative. It met the specification, it was manufactured, and in 2006 it launched - making it one of the first computer-evolved objects to fly in space. It is a good illustration of the central trade: the search had no theory of antennas, and in exchange it was not limited by one either.

A landmark demonstration was Karl Sims' 1994 work on evolving virtual creatures with morphologies and behaviours simultaneously co-optimised through artificial evolution - showing that complex body plans and locomotion strategies can emerge purely from evolutionary pressure [6].

Where Genetic Algorithms Struggle

The freedom from problem structure is real, but it is bought, not given, and it is worth being precise about the price.

Premature convergence is the classic failure. A population that finds one decent solution early tends to fill up with its descendants, at which point crossover is recombining near-identical parents and produces nothing new. The search is still running and has effectively stopped. Mutation rates, selection pressure and diversity-preserving schemes such as niching and fitness sharing all exist to hold this off. A GA does not escape local optima for free - it has to be tuned to keep exploring.

Designing the fitness function is the actual work. "You only need to measure how good a solution is" hides the difficulty rather than removing it. A fitness function that is nearly flat gives selection nothing to act on; one that rewards a proxy rather than the goal gets optimised exactly as written, which is how evolved solutions end up exploiting bugs in the simulator instead of solving the problem. Evolution is a very literal reader of specifications.

Encoding decides what crossover can do. The building block argument only holds if related genes sit near each other on the chromosome, because a single cut point separates things that are far apart. Under a poor encoding, crossover reliably destroys the structure it is supposed to preserve, and the algorithm degenerates into an expensive random search.

And when a gradient exists, use it. A GA's indifference to problem structure is also a refusal to exploit it. On a smooth differentiable objective, gradient descent will reach a better answer in a tiny fraction of the evaluations, because it knows which way is downhill and the GA is guessing. Genetic algorithms earn their place where the landscape is discontinuous, combinatorial, noisy or simply has no derivative to take.

Why It Matters

Genetic algorithms demonstrate that you do not need to understand the structure of a problem to solve it - you only need to measure how good a candidate solution is. This makes GAs applicable to problems where the search space is vast, discontinuous, or poorly understood. They are inherently parallel and require no gradient information, and maintaining a diverse population gives them more than one foothold in the search space at a time. You can explore this process yourself in the Genetic Algorithm simulation, where a population of strings evolves toward a target phrase through selection, crossover, and mutation.