- Flying
- Reached the target
- Crashed
- Best flight of the last generation
- Reached the target
- Crashed
Genetic algorithm playground
A genetic algorithm solves a problem the way evolution shapes living things: try many random answers, keep the better ones, mix them and change a few bits at random, and repeat. Here the answers are rockets. Each one follows a list of random pushes and nothing else, and at first they tumble about aimlessly. Press Run and watch the population improve generation by generation until most of them sweep round the walls to the target, without anyone telling them where to go. Press Run and watch a population of rockets try to reach the green target. Each rocket only follows its genes, a list of small pushes, one per moment of its flight. After every flight the rockets that got closest, and above all those that arrived, are most likely to become parents of the next generation; their genes are mixed and a few are changed at random. Next generation skips the rest of a flight. Drag on the field to draw a wall, and click a wall to remove it.
How it works
- Choose obstacles, or drag on the field to draw your own walls, and set the population, mutation rate and lifespan.
- Press Run and watch each generation fly; Next generation skips the rest of a flight.
- Follow the share that reaches the target in the tiles and the chart, and try other mutation rates and selection methods.
How the rockets evolve
Every rocket carries genes: one small push for every moment of its flight. The first generation's genes are random. After the flight each rocket gets a fitness score, highest for arriving early, then higher the closer it ended to the target, and divided by ten after a crash. Parents for the next generation are chosen at random, but fitter rockets are more likely to be chosen. Each child takes the first part of its genes from one parent and the rest from the other, and a few genes are replaced by random pushes: mutations. Over the generations good flight plans spread and improve.
What the settings change
A larger population explores more flight plans at once and is less likely to get stuck, but every generation takes longer. The mutation rate balances exploring and keeping what works: with no mutation the population quickly runs out of new ideas, with too much it forgets good flights faster than it can find them. Roulette selection chooses parents in proportion to fitness, while a tournament picks the best of three random rockets, which is less sensitive to how fitness is scaled. Elitism copies the best rocket into the next generation unchanged, so the best result never gets worse.
Frequently asked questions
Why do the rockets get stuck behind the staggered walls?
Their fitness measures the straight-line distance to the target, so a rocket that flies into the wall under the target scores better than one that flies away to find the gap. The population piles up in that dead end, a local optimum. Larger populations, more mutation or tournament selection help it escape, and a fitness that measured the real route round the walls would avoid the trap. Choosing a good fitness function is the hardest part of using a genetic algorithm.
Is this how evolution works in nature?
In outline: variation from mutation and recombination, inheritance of genes and selection of the fittest are Darwin's ingredients. The differences are large, though. Nature has no target and no fitness formula, only survival and reproduction, and real genomes build bodies through development instead of listing actions.
What are genetic algorithms used for?
For problems with a huge space of possible answers and an easy way to score a candidate: shaping antennas, wings and car parts, scheduling timetables, tuning the settings of other algorithms, designing neural networks, and creating art and game strategies. NASA's evolved antenna on the ST5 satellites of 2006 is a famous example.
Why does the best rocket sometimes fly worse in the next generation?
Without elitism, the best rocket is not copied: its genes only survive mixed with others and possibly mutated, so the next generation may lose its exact flight. With elitism switched on, the best rocket is kept unchanged and the best result never gets worse.
Is anything sent to a server?
No. The rockets fly and evolve in your browser, and the walls you draw stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor