Evolve an Answer
Nobody draws the picture. A crowd of random scribbles is bred over and over, and the best ones have the most babies.
There is a secret 8 by 8 picture. My scribbles start totally random. Press Run and watch them evolve!
Best scribble
Little red dots on the left show pixels that are still wrong.
Challenges
Evolve it: get all 64 pixels right.
Speedy: solve it in 40 generations or fewer (right after Start over).
Tiny crowd: solve it with a crowd of 20 or fewer. Tip: about 2% mutation.
Frozen: set mutation to 0% and run 30 generations. Does it ever finish?
Chaos: set mutation to 25% or more and run 30 generations without reaching 58 pixels.
What just happened?
- Each scribble is 64 on/off switches. Its score is how many pixels match the secret picture.
- Every generation the better scribbles are picked as parents, mixed together, and given a few random flips.
- With 0% mutation nobody can invent anything new, so the crowd gets stuck. With huge mutation the good bits get wrecked as fast as they are found.
- A little mutation (about 1 to 3%) and mixing parents is the sweet spot.
- Nobody told the crowd what a heart looks like. It only got a score.
How it works
- Start with a crowd of random answers.
- Score each one: how many pixels are right?
- Select parents. Better scores win more often (a small tournament of 3).
- Crossover: copy the first part from one parent and the rest from the other.
- Mutate: flip a few pixels at random. Keep the very best one unchanged.
- Repeat until the score stops improving.
For grown-ups: what's really going on
This is a genetic algorithm, a population-based search that needs only a fitness function (here: Hamming matches to a target), no gradients.
- Selection: size-3 tournament; elitism copies the best individual unchanged so the best score never drops.
- Crossover: single point. It lets two partial solutions combine (the building-block idea). Turn it off and progress slows because good bits can only spread by cloning.
- Mutation rate
μper bit. Withμ = 0diversity only shrinks (premature convergence). Withμ → 0.5each child is nearly random, so the search turns into random guessing. The balance is exploration vs exploitation; a common rule of thumb isμ ≈ 1/length. - Used for scheduling, design search, neuroevolution. It is good when the answer is hard to differentiate, but it can be slow and has no guarantee of finding the best answer.
Further reading: Mitchell, An Introduction to Genetic Algorithms (1996) · Eiben and Smith, Introduction to Evolutionary Computing.