After hearing a lot about genetic algorithms recently, I wanted to get stuck in myself and learn how it all works. Especially after reading Roger Alsing’s recent post on the Evolution of Mona Lisa (which is totally awesome).
The problem I wanted to solve was this:
Given a space with a number of non-overlapping circles, find the largest circle that can fit without overlapping any of the others
A genetic algorithm (GA) is a surprisingly simple idea at its core. In fact, of the few programs I’ve built so far, a lot of the code is exactly the same.
The algorithm I’ll discuss here works as follows:
Generate a random population of possible solutions
Assign a fitness score to each solution in the population
“Breed” a new generation of solutions by selecting random pairs (weighted by their fitness score) from the old population
Crossover each selected pair according to a crossover rate
Mutate each pair according to a mutation rate
Repeat steps 2 through 5
###Chromosomes and Genes
First up, we need a representation of our solution. We call this a chromosome.
Given that we want to find a circle, our solution needs to provide a position and a radius. We’ll encode these values in a binary string.
To store these values, we’ll divide our chromosome into three parts (or genes): center-x, center-y, and radius. If we use 10 bits for each gene, it looks like this:
To make reading out the encoded data a little easier, we’ll wrap this up in a class called LargestCircleChromosome. This class decodes the chromosome string as soon as it’s assigned, and stores the values in a Circle object.
Next, we need a way to measure the fitness score for a chromosome. This is the hardest part to get right, and how you implement it will vary depending on the problem you’re trying to solve.
The fitness score needs to be able to indicate how much better one chromosome is than another. The following method is effective enough for solving our problem:
A few things to note here:
If the circle goes out of bounds at all, give it a fitness score of 0 (effectively killing it off in this generation)
If the circle overlaps with any other circle, also kill it off with a fitness score of 0
The return value could simply be the radius, however using an exponent will cause the GA to favor slightly larger radii a lot better, and help us get an answer much faster
###Roulette Wheel Selection
Selecting random chromosomes according to their fitness score is also referred to as “roulette wheel selection”. You can imagine dividing up a circle into slices where the fitness score determines the size of each slice, then spinning it to choose our random chromosome.
Since we’re pulling out pairs, we can write this as a recursive method to pull out any number of chromosomes.
###Crossover and Mutation
The last building block we need is a way to crossover and mutate our chromosomes.
We start by defining a crossover rate and mutation rate. Playing with these values is very important to get a feel for how it affects the efficiency of the algorithm. The crossover rate can be quite high - we’ll use 0.7 - while the mutation rate should stay very low - we’ll use 0.01. I played with mutation rates ranging from 0.001 through to 0.1 which had varying effects on how the program performed.
Crossing over a pair of chromosomes is done by selecting a random point along both binary strings, and swapping the second section of each string:
Which, in code, looks like this:
You’ll notice the two calls to the mutateChromosomeString: method. As part of the crossover process, we apply our mutation function to each new chromosome.
Mutation is accomplished by looping through each bit in the chromosome binary string, and randomly toggling the value of each bit according to our mutation rate (defined above as 0.01).
#Putting It All Together
Now we can put all these parts together to perform the algorithm outlined at the beginning.
Dispatching this algorithm on a background thread lets us view the progress as it improves its best answer. We can use the progress() and completion() blocks to update our UI to reflect the current state of the system.
It’s quite fun to watch the circle grow and mutate itself, certainly feels like magic to me!
The complete source code for this project can be found here on Github.