Genetic algorithms explained

Evolution has produced eyes, wings and brains without a designer, simply by keeping what works and varying it. A genetic algorithm borrows that idea to solve problems on a computer. It does not need to understand the problem, only to tell a better answer from a worse one, which makes it a powerful tool when the space of possible answers is too large and too strange to search in any other way.

Rockets flying from the bottom of a field round a wall to a green target, with the best flight drawn as a dashed line
Rockets flying from the bottom of a field round a wall to a green target, with the best flight drawn as a dashed line

The idea

In the 1960s and 1970s John Holland at the University of Michigan turned Darwin's theory into an algorithm, described in his book Adaptation in Natural and Artificial Systems of 1975. Around the same time Ingo Rechenberg and Hans-Paul Schwefel in Germany developed evolution strategies for engineering design. The common recipe: keep a population of candidate solutions, score them, let the better ones reproduce with variation, and repeat for many generations.

John Holland, who described genetic algorithms in his 1975 book Adaptation in Natural and Artificial Systems.
John Holland, who described genetic algorithms in his 1975 book Adaptation in Natural and Artificial Systems.

Genes and the population

Each candidate is described by a chromosome, a list of genes. In the playground a rocket's genes are its pushes, one for each moment of its flight; in other problems they might be the bits of a number, the order of cities on a route or the sizes of parts in a design. The first generation is random, which means it explores the space of answers widely but has almost no good ones.

The fitness function

Fitness is the single number that says how good a candidate is, and it is the only thing the algorithm knows about the problem. For the rockets it rewards arriving early most, then ending close to the target, and punishes crashing. A well-chosen fitness function guides the search smoothly towards good answers; a careless one rewards the wrong thing, and the algorithm will exploit any loophole it leaves open.

Selection

Parents are chosen so that fitter candidates have more children, but weaker ones still get a chance, because their genes may hold useful pieces. Roulette wheel selection gives each candidate a slice of a wheel in proportion to its fitness; tournament selection picks a few at random and takes the best of them. Stronger selection speeds up progress but also makes the population more alike, which can end the search too early.

Crossover and mutation

Crossover combines two parents: here a child takes the first part of its genes from one parent and the rest from the other, so the early manoeuvres of one rocket can meet the late ones of another. Mutation replaces a few genes at random. Crossover recombines what the population already has; mutation brings in what it has never had. Holland's schema theorem describes how short building blocks of good genes spread through the population under this mix of selection and recombination.

Elitism, exploration and exploitation

Copying the best few candidates unchanged into the next generation, elitism, guarantees that the best answer never gets lost. Every genetic algorithm has to balance exploration, trying new regions of the search space, against exploitation, refining what is already good. Too little variation and the population converges on one mediocre answer; too much and it never settles. Population size, mutation rate and selection pressure are the dials that set the balance.

Local optima

A genetic algorithm only follows fitness, so it can be fooled. When the path to the best answer first leads through worse ones, the population climbs the nearest hill and stays there: a local optimum. Behind the staggered walls in the playground, rockets that crash under the target score better than rockets that turn away to find the gap, so the population piles up against the wall. Remedies include larger populations, higher mutation, keeping the population diverse, and above all a better fitness function.

Explore it

Open the genetic algorithm playground to evolve rockets round one wall, a gap, pillars, staggered walls or walls you draw yourself. Change the population, the mutation rate, the lifespan and the selection method, switch elitism on and off, and follow in the chart how quickly the share of rockets reaching the target grows, or why it does not.

Frequently asked questions

Is a genetic algorithm a kind of artificial intelligence?

It belongs to the wider field of AI and machine learning, as a search and optimisation method. It does not learn from examples like a neural network; it improves candidate solutions by trial and selection. The two are often combined, for example by evolving the structure or weights of neural networks, an approach called neuroevolution.

Does a genetic algorithm always find the best answer?

No. It is a heuristic: it usually finds good answers to hard problems, but it gives no guarantee of the best one and no proof of how close it is. For problems where an exact method is fast enough, that method is better.

What is the difference between a genetic algorithm and evolution strategies?

Both are evolutionary algorithms. Classic genetic algorithms emphasise crossover on string-like chromosomes; evolution strategies work mainly with mutation on real numbers and often adapt their own mutation sizes as they go. Modern methods mix ideas from both.

Why are the rockets so clumsy at first?

Their first genes are completely random pushes, so on average they cancel out and the rockets drift. Only after selection has kept the rare rockets that happened to push roughly the right way, and crossover has combined their good stretches, do coordinated flights appear.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Open the genetic algorithm playground