Evolutionary Algorithms
Borrowing the one idea that built every living thing, survival of the fittest, and turning it into a way to evolve solutions to hard problems.
In local search, week 5, you climbed a hill one step at a time and hoped you did not get stuck. Evolutionary algorithms take a bolder idea: instead of improving one solution, keep a whole population of them, let the best ones survive and breed, add a little random mutation, and repeat. Over many generations, good solutions emerge on their own, the same way nature designs living things without any designer. This page shows you exactly how that works, and lets you watch it happen.
The core idea
Some problems are too big to solve by checking every option and too bumpy for hill climbing to work reliably. Designing a delivery route, tuning a set of parameters, or packing a container can have millions of possible answers with no obvious way to improve step by step. Evolutionary algorithms attack exactly this kind of problem, and they do it by copying biology.
The insight is that evolution is a search algorithm. Nature never sat down and designed the eye. Instead, many slightly different creatures existed, the ones better suited to their environment survived and had offspring, those offspring varied a little, and over enormous time this produced astonishing designs. Strip that down and you get a recipe a computer can follow.
- Keep a population of candidate solutions, not just one.
- Score each by a fitness measure: how good a solution is it?
- Let fitter candidates survive and reproduce more often.
- Combine parents (crossover) and add small random changes (mutation) to make offspring.
- Repeat for many generations, and the population drifts toward better solutions.
The genetic algorithm loop
The most common evolutionary algorithm is the genetic algorithm, or GA. Everything else on this page is a detail inside this one loop, so learn the loop first and the rest slots into place.
- Initialise: create a random population of candidate solutions.
- Evaluate: score every candidate with the fitness function.
- Select: pick parents, favouring fitter ones.
- Crossover: combine pairs of parents to create offspring.
- Mutate: randomly tweak some offspring a little.
- Replace: the offspring form the next generation.
- Repeat from step 2 until a solution is good enough or you run out of generations.
Rather than trace this on paper, watch it. Below is a live genetic algorithm with one job: evolve a random jumble of characters into a target phrase. It starts from pure noise and uses only selection, crossover, and mutation. Press play.
A population of 200 random strings evolves toward the target. The best candidate each generation is shown, with matched characters in green.
Representation and chromosomes
Before a GA can breed solutions, you must decide how to write a solution down as data. This is called the representation or encoding, and getting it right is half the battle. A single candidate solution is called a chromosome, and each piece of it is a gene.
- Binary encoding: a string of bits, like
10110010. Classic and flexible. - Character encoding: a string of letters, as in the demo above.
- Permutation encoding: an ordering, like a sequence of cities for a travelling-salesman route.
- Real-valued encoding: a list of numbers, for tuning continuous parameters.
The encoding decides what crossover and mutation even mean, so it is the first design choice you make and the one exams most often ask you to justify.
The fitness function
The fitness function is the heart of a GA. It takes a chromosome and returns a number saying how good that solution is. The entire algorithm is steered by this one score, so if the fitness function is wrong, the GA cheerfully evolves the wrong thing.
Fitness is problem-specific. A few examples:
| Problem | A chromosome is | Fitness is |
|---|---|---|
| Evolve a target phrase | A string of characters | Number of characters that match the target |
| Travelling salesman | An order of cities | The negative of the total route distance (shorter is fitter) |
| Timetabling | An assignment of classes to slots | Fewer clashes means higher fitness |
Selection
Selection decides which candidates get to be parents. The goal is to favour fitter candidates so good genes spread, while not being so ruthless that the population loses variety and gets stuck. Three common methods:
- Roulette-wheel (fitness-proportionate): imagine a roulette wheel where each candidate gets a slice sized by its fitness. Spin it to pick a parent. Fitter candidates have bigger slices, so they are picked more often, but weaker ones still have a chance.
- Tournament selection: pick a few candidates at random and let the fittest of that small group become a parent. Simple, fast, and easy to tune by changing the tournament size.
- Elitism: copy the very best one or two candidates straight into the next generation, untouched. This guarantees the best solution is never lost to unlucky breeding.
Crossover
Crossover, also called recombination, is how two parents produce a child. The idea is that if two decent solutions each got some things right, combining them might produce a child that inherits the best of both.
- Single-point crossover: choose one cut point. The child takes everything before the cut from parent A and everything after from parent B.
- Two-point crossover: two cuts, and the middle section comes from the other parent.
- Uniform crossover: for each gene, flip a coin to decide which parent it comes from.
Try single-point crossover yourself. Drag the slider to move the cut point and watch how the child is assembled from the two parents.
Parent A is blue, parent B is amber. The child takes genes before the cut from A and after the cut from B.
Mutation
Mutation randomly changes a gene with some small probability, for example flipping a bit or replacing a character. It sounds like it would just add noise, and if you turn it up too high it does exactly that. But at a low rate it does something crossover alone cannot.
Crossover can only shuffle genes that already exist in the population. If every candidate happens to have a 0 in one position, no amount of crossover will ever produce a 1 there. Mutation is the only operator that can introduce genuinely new genetic material, which is what lets a GA escape a rut.
| Mutation rate | Effect |
|---|---|
| Too low (near zero) | Little new variety, the population can stagnate and get stuck |
| Well chosen (small) | Enough fresh variation to keep exploring, without destroying good solutions |
| Too high | Good solutions are constantly broken, the search becomes little better than random |
Convergence and diversity
Run a GA long enough and the population starts to look similar: it has converged. Convergence is what you want if it settles on a great solution, but there is a failure mode with a name examiners love.
Premature convergence happens when the population becomes too similar too early, before finding a truly good solution. One decent-but-not-great candidate takes over, everything starts to look like it, diversity collapses, and the GA gets stuck, much like local search trapped on a small hill. The cures are the tools you have already met:
- Enough mutation to keep introducing new genes.
- Selection that is not too greedy, so weaker candidates still occasionally breed.
- A large enough population to hold variety.
- Elitism to protect the best, balanced against diversity so it does not dominate.
Uses and comparisons
Genetic algorithms shine on large, bumpy problems where you can score a solution but cannot easily compute the best one directly: route and schedule optimisation, engineering design, tuning parameters, game strategies, and antenna or circuit layout. They do not need the problem to be smooth or differentiable, which is their big advantage.
How they relate to what you already know
| Method | Keeps | Explores by | Main weakness |
|---|---|---|---|
| Local search (week 5) | One solution | Small moves to neighbours | Gets stuck in local optima |
| Genetic algorithm (this week) | A population | Crossover and mutation | Slow, many parameters to tune |
| Swarm intelligence (week 7) | A population (a swarm) | Sharing information between agents | Also parameter-sensitive |
Local search, genetic algorithms, and swarm intelligence are all members of the same family: optimisation by trial, feedback, and improvement. The GA's distinctive trick is keeping a whole population and breeding it. Next week, week 7, swarm intelligence keeps a population too, but coordinates it in a completely different way.
Key points and practice
- A GA keeps a population of candidate solutions, not one.
- The loop is: evaluate, select, crossover, mutate, replace, repeat.
- The representation defines a chromosome and its genes, and everything else depends on it.
- The fitness function steers the whole search, so design it with care.
- Selection favours the fit, crossover combines them, mutation adds novelty.
- Watch out for premature convergence: keep enough diversity alive.
Target 1111. Fitness is the number of 1s. Start with a tiny population of four:
Initialise a random population of candidate solutions. Evaluate each with a fitness function. Select parents, favouring fitter candidates. Apply crossover to combine parents into offspring. Apply mutation to add small random changes. Replace the old generation with the offspring, and repeat until a solution is good enough or a generation limit is reached.
Crossover combines genes from two parents, so it recombines existing genetic material. Mutation randomly changes a gene, introducing new material that may not exist anywhere in the population. Both are needed because crossover alone can only shuffle what is already present, while mutation alone lacks the power to combine good building blocks. Together they balance exploiting known good genes and exploring new ones.
Premature convergence is when the population becomes too similar too early and settles on a suboptimal solution, losing the diversity needed to improve. It can be reduced by increasing the mutation rate, using less greedy selection so weaker candidates still breed, using a larger population, and limiting how strongly elitism dominates, all of which preserve diversity.
