Project: Genetic Algorithm 1: Image Evolution

Image Evolution

This was a fun project I did to get further practice with Python and do something vaguely related to AI with it.

A genetic algorithm is a technique to find a problem in a space where there are too many possible solutions to exhaust in a brute force manner. It mimics the process of natural selection to evolve an approximately optimum solution over time.

Imagine a blank 128x128 canvas, onto which 50 circles are painted. The circles vary randomly in their position, size and colour:

Let's call this a 'painting', although really it is not a static image; it is sequence of circle-drawing instructions to be carried out in order.

Now imagine we have a target image:

We can compare the generated painting with the target image using a mean squared error (MSE) calculation to get a measure of how close it is. As you can imagine, the MSE is very high in this case because there's no resemblance.

For the genetic algorithm, we create a 'population' of 1000 such random paintings. This is Generation 0. None of them are going to look anything like the Mona Lisa.

Using the MSE measure, we can calculate a 'fitness score' for each painting in the population. Now we're ready for some evolutionary magic.

What we want to do is create a new population of paintings - Generation 1 - drawing from the best of the previous generation. Specifically, we:

1. Select two 'parent' paintings from the previous generation with higher than average fitness scores.
2. Combine those two.
3. Have a chance of a random mutation on the resulting 'child' painting.
4. Keep doing this until we have a new population the same size as the old one.
   

Then we evaluate the fitness of all the paintings in the new generation, and repeat the entire process.

Over 2000 generations, the paintings evolve into an approximation of the target image:

Obviously you can't paint the Mona Lisa with just 50 circles, but it does a pretty good job of attempting it. Refresh the page to restart these animations.

Here are a few more:

Variables

There are a lot of variables to experiment with in a system like this:

• The number of circles
• The maximum circle size
• The population size
• How much of the population can become parents of the next generation
  
• The chance of a mutation
• Which attribute of the circle mutates
  
• How many generations
  

There are also key functions that can be implemented in many different ways:

• How parents are selected from one generation to contribute to the next.
• How parents are combined to form a 'child' painting.
• How mutation happens during this process.
  

I experimented with different versions of all of the above to find an approximate optimum. Mutation in particular has many options because the x position, y position, circle radius and each element of the colour (red, green, blue and alpha) can be mutated separately.

Initially I made it choose randomly which of those attributes of a circle is mutated each time. But since some are bound to be more effective than others, I started tracking each attribute's effectiveness over time. It turns out that mutating the colour is generally more effective than changing the x or y position of a circle. To benefit from this feedback, my code now mutates the most effective attribute more often than the others, leading to faster improvements.

Computing Cost

Compared with other problem spaces, using a genetic algorithm for image evolution is very computationally expensive. Each time I ran the program to do the 2000 generations took about 30 minutes. I could have let it go on for a greater number of generations, obviously, but with diminishing returns.

With unlimited computing power you could have many thousands of circles and a larger population, and leave it going for many more generations. But in the real world the computing cost would rapidly become unmanageable. For this project, these numbers were sufficient to demonstrate the concept.

Conclusion

Generic algorithms are interesting but not much used in the real world. They involve a lot of randomness, and so are inherently inefficient. Real world biological evolution took billions of years to arrive at anything interesting. In most problem spaces we have information we can inject to arrive at a solution much more efficiently and quickly. So for the most part, genetic algorithm systems like this one are interesting really just for novelty value.

Having said that, the internet assures me that they are used across a range of real world applications, including robotics, logistics, economics, telecommunications, marketing and engineering design.