Optimisation & Search

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

Best so far
Secret target

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?

How it works

  1. Start with a crowd of random answers.
  2. Score each one: how many pixels are right?
  3. Select parents. Better scores win more often (a small tournament of 3).
  4. Crossover: copy the first part from one parent and the rest from the other.
  5. Mutate: flip a few pixels at random. Keep the very best one unchanged.
  6. 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 μ = 0 diversity only shrinks (premature convergence). With μ → 0.5 each 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.