3 Vertices
Polyvolve is a genetic algorithm that attempts to create a target image out of transparent polygons. The original idea came from a blog post from Rojer Johansson, although my implementation is quite a bit different. All of the code can be found on my GitHub.
The algorithm starts by creating a bunch of randomized individual candidates to represent the target image. A string of DNA represents each individual. This DNA is translated from values between 0 and 1 to coordinates of polygon vertices and RGBA color values. Each individual’s generated image is compared against the target image to evaluate their “fitness.” The highest scoring individuals then become parents and create a new generation by combining their DNA. These children have a chance to mutate and generate completely different genomes as well. This process is repeated generation after generation, and the overall population fitness gets higher and higher. Eventually leading to some cool-looking pictures!
3 Vertices
3 Vertices
Changing amount of vertices for different effects.
For image comparison, the logical thing to do would be to use the mean squared error between the RGB values of the target and individual images. However, for some reason, I could not get that to work. The pictures would never come close to the target image. Instead, I used was the Structural Similarity Index which produced much better results.
The breeding functions I implemented were a two-point crossover and a random inheritance. Both seemed to work equally well.
I implemented a few different mutation functions. The first gave each DNA piece of every child an equal chance of mutating to a random value. The second first gave every child a chance to become a mutant. If they did, then each DNA piece for that child only had a separate chance to mutant to a random value. I then implemented both of these methods, but instead of each mutated gene taking on a random value, they were incremented a random percentage away from their original position. This ended up working much better, as the polygons are more prone to do smaller shifts.
I wanted to get a shout-out to Chris Cummins for his awesome javascript implementation that I stumbled across.