After being inspired by this link, I planned to implement a similar Genetic Algorithm. The algorithm uses a sequence of mutating polygons to recreate an image. Since I was taking a Coursera refresher in R, I decided to give it a shot in that language.

Although, this has been described as a Genetic Algorithm or Genetic Programming, I thought the description was kind of stretched. A more accurate description is a Hill Climbing Algorithm:

1. Initialize: Start with a random polygon
2. Incremental change: Add, mutate, or remove polygons
3. Comparison: Use a fitness function to compare the change with original – the “winner” goes through to the next round
4. Repeat steps 2 & 3

The mutations were done using some fixed parameters I picked arbitrarily while coding, but I haven’t had a chance to fiddle with them yet:

1. Mutation probability – 25% chance of each polygon to mutate slightly
2. Color mutation – 15% range for each RGB color value to change in polygon
3. Height/Width mutation – 5% range for each point of the polygon to change
4. Add polygon – 25% chance of a random new polygon to be added in a generation
5. Remove polygon – 25% chance of a random polygon in current sequence to be removed in a generation
6. Polygon vertices – 3, 4, or 5 points per polygon, chosen randomly
7. Polygon transparency – 0.5 alpha in RGBA color space

The fitness function is a mean square error in color space.

There were a few issues I ran into using R for this, which I didn’t anticipate. R has a graphics device but I couldn’t figure out how to run my fitness function (a pixel by pixel comparison in color space) on it. Instead, I had to read & write images to disk, which was a big hurdle in computation. The alternative would be to do the comparison while the images are stored as matrices. However, I couldn’t figure out the conversion from multiple stacked RGBA polygons (polygons with transparency) to an RGB color.

I also coded the polygon vertices to be within the image dimensions, unless they mutate out. This boundary has a tendency to create a white space around the image. Maybe in the future I will fix that.

Regardless, I let it run a few times with different images. During the inauguration, I ran it with the US flag. Earlier, I did a test run with the Mona Lisa. I was impatient and used small images to speed up the results. I also ended the trials after the incremental mutations became too infrequent. As you can see below, the general shape is achievable, but getting the details would take a lot more iterations.

Results

US flag video of evolution through all successful iterations:

[youtube http://www.youtube.com/watch?v=4Sfl7GN5NMU&rel=0&h=126&w=224;]

Mona Lisa select images of evolution:

In 18 samples…