A4.3.7 · Machine learning approaches
Genetic algorithms
By the end you can
Describe how selection, crossover and mutation evolve a good answer over generations, and where this is used, for example in route planning.
Some problems have more possible answers than there are atoms to try them on. Find the shortest route that visits 50 towns and there are more orders than you could ever test. But given any one route, it is easy to measure how long it is. A uses this: it does not solve the problem directly but evolves good answers, borrowing the ideas of natural selection.
The evolutionary loop#
- Population. Create a of candidate solutions, often at random. Each is stored as a string of genes (bits, numbers, or a list of towns).
- Fitness. Score every candidate with a : for a route, perhaps 1 ÷ its length.
- Selection. Choose parents, favouring the fit. Roulette wheel selection gives each candidate a slice of a wheel in proportion to its fitness and spins it. Tournament selection picks a few candidates at random and takes the fittest of them.
- Crossover. Combine two parents into a child, for example the first part of one and the rest of the other.
- Mutation. Make a small random change in the child, such as flipping a bit or swapping two towns.
- Evaluate, replace and repeat. Score the children with the same fitness function; they replace the weaker members of the population (or the whole population) as the next generation. This repeats until a termination condition is met: a fixed number of generations, a good enough fitness, or no real improvement for a number of generations.
Many versions also use elitism: the best one or two candidates are copied into the next generation unchanged, so the best answer found is never lost.
| Step | What it does | Why it matters |
|---|---|---|
| Scores how good each candidate is. | It defines what “good” means: a badly designed fitness function evolves the wrong thing. | |
| Picks parents, fitter ones more often. | Pushes the population towards better answers. | |
| Mixes parts of two parents. | Can combine good features from different candidates. | |
| Randomly changes a child slightly. | Adds variety so the search does not get stuck. |
Each row is one individual: 16 bits. Its fitness is how many bits match the target pattern in the top row. A green cell matches; a red one does not.
| Target | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| #1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 10/16 |
| #2 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 9/16 |
| #3 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 9/16 |
| #4 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 9/16 |
| #5 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 8/16 |
| #6 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 8/16 |
| #7 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 8/16 |
| #8 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 7/16 |
| #9 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 7/16 |
| #10 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 7/16 |
| #11 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 7/16 |
| #12 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 7/16 |
Generation
0
Best fitness
10 / 16
Average fitness
8.0
Solid line: the best individual. Dashed line: the average. Each generation keeps the best individual, then fills the rest by choosing parents (fitter ones are more likely), swapping parts of their bit strings (crossover) and occasionally flipping a bit (mutation).
Example: the travelling salesperson#
A van must visit every town once and return to the start by the shortest route. A candidate is an order of the towns. Fitness is 1 ÷ total distance. Mutation swaps two towns. Crossover is trickier, because a child must still visit every town exactly once. A common method keeps the first part of one parent and then adds the remaining towns in the order they appear in the other:
- Parent 1: 0, 4, 5, 1, 3, 2. Parent 2: 4, 2, 0, 3, 5, 1.
- Keep the first three towns of parent 1: 0, 4, 5.
- Add the rest in parent 2's order, skipping towns already used: 2, 3, 1.
- Child: 0, 4, 5, 2, 3, 1, a valid route that mixes both parents.
Over many generations, routes with long detours are less likely to be chosen as parents, short stretches are passed on, and the population converges on short routes. Typical runs show the best distance falling quickly at first and then slowly.
Uses and limits#
- Logistics: delivery routes, vehicle scheduling.
- Scheduling: timetables, factory shifts, exam rooms.
- Design: shapes of antennas, wings and circuits, found by evolving thousands of variants. For a wind farm, a candidate is a layout of turbines, its fitness is the energy produced minus the cost, and mutation moves one turbine.
- Machine learning: choosing features or hyperparameters, or evolving the structure of a neural network.
- Games and robots: evolving strategies or controllers.
A genetic algorithm does not promise the best answer, only a good one found reasonably quickly. It may stall on a mediocre solution (a local optimum) if variety is lost, and it needs many fitness evaluations, so it is slow when scoring a candidate is expensive.
Check yourself
Genetic algorithms
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
6 questions · 19 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Describe how a genetic algorithm works.
[5]Describe: A detailed account: say what happens, step by step if it is a process.
2.Two parents are the bit strings 11001100 and 00110011. Construct the child produced by single-point crossover after the 3rd bit, taking the first part from the first parent.
[2]Construct: Draw or write it out (a table, a diagram, a program).
3.Explain why mutation is included in a genetic algorithm.
[2]Explain: Give reasons: say what happens AND why, or how one thing causes another.
4.Four towns are at (0, 0), (0, 3), (4, 3) and (4, 0). A delivery van visits them and returns to the start. Route A visits them in the order (0,0), (0,3), (4,3), (4,0). Route B visits them in the order (0,0), (4,3), (0,3), (4,0). The fitness of a route is 1 ÷ its total length. Calculate which route is fitter.
[3]Calculate: Work out the number, showing the working.
5.Explain how a genetic algorithm could be used to plan a delivery route that visits 50 towns.
[4]Explain: Give reasons: say what happens AND why, or how one thing causes another.
6.Outline three real-world problems that genetic algorithms can be used to solve.
[3]Outline: A brief account: the main points, without much detail.
In a nutshell
- A genetic algorithm searches for a good solution by evolving a population of candidates, copying natural selection.
- Loop: score every candidate with a fitness function; select fitter parents; crossover (mix two parents); mutation (small random change); form the next generation; repeat until good enough.
- Elitism keeps the best candidates unchanged. Mutation preserves variety so the search does not get stuck.
- It suits problems with huge numbers of possible answers that are easy to score but hard to solve directly: routes, timetables, designs, tuning settings.
- It finds a good answer, not always the best one, and needs a well-designed fitness function.