Contents
In searching for a way to draw transparent shapes in Pygame, I happened across a website describing how an approximation of the Mona Lisa had been evolved using overlapping transparent polygons. It sounded like a fun, and so once again, I started a new project. For simplicity and to speed up computation, I used circles, and for the most part, I used grey scale images.
Genetic algorithms
In order to use a genetic algorithm to solve a problem, you need a way to convert a string of numbers (or symbols) into possible solutions to the problem. This allows solutions to be mutated by changing symbols at random. Importantly, every possible string of symbols must generate a valid solution (even if the solution fails to solve the problem, it needs to not crash).
You also need a way of measuring the fitness of a solution - how close is it to completely solving the problem. This allows you to compare two potential solutions and select which is better.
A simple genetic algorithm works in the following way:
- Generate a random genome (the mother's genome)
- Measure the fitness of the solution encoded by the mother's genome (the mother's fitness)
- Randomly mutate the mother's genome to a daughter's genome
- Measure the fitness of the solution encoded by the daughter's genome (the daughter's fitness)
- If the daughter's fitness is greater than the mother's, then overwrite the mother's genome with the daughter's
- Go to step 3
As written here, the program will loop forever. You can stop it after it reaches an arbitrary number of loops (generations), after the fitness reaches an arbitrary level (though bear in mind that the program might get stuck in a dead-end and never reach this level), or until a genome is undefeated for an arbitrary number of generations.
The image genome
For each run of evolution, I fixed the number of circles. The reason being that the more circles an image has, the more able it will be to mimic the target image, so I figured that the number of circles would keep increasing. I might be interesting to allow the number of circles to change, but have a penalty for each circle, thus tending to select images made of the fewest circles.
Each circle has six parameters:
- an x-coordinate (0 to the image's width)
- a y-coordinate (0 to the image's height)
- a z-coordinate, which determines the order in which circles are drawn
- a diameter (from 0 to a third of the image’s height)
- a grey scale colour (0 to 255, corresponding to black to white)
- a transparency (0 to 255, corresponding to completely transparent to completely opaque)
The z-coordinate does not have a value as such, but is represented by the order of the circles in the genome. Circles are drawn in the order they appear in the genome onto a white background that has the same dimensions as the target image. Mutations in the z-coordinate therefore require the genome to be rearranged, allowing a circle from the back to be brought to the front. With 128 circles, a genome therefore consists of 6400 numbers.
The fitness measure
The fitness of the genome is measured by comparing each pixel of the generated image with the corresponding pixel in the target image. For grey scale images, each pixel has a value 0 corresponding to pure black and 255 corresponding to pure white. For each pixel I square the difference between the value from the target image and the generated image. I can therefore calculate the difference between two images by summing the squared difference of all the pixels. The lower this value is, the closer the two images are, and the ‘fitter’ the genome. In the subsequent updates I use this distance value (which I call d), though I've divided it by one million to make it more manageable. In general, a random genome have a d value around 200-300, and a highly evolved image have a d value around 8-12.