This is the second part of a two-part article. Please read the first article if you haven’t already.
Reproduction
The chromosomes are reproduced with the weighted random (i.e. roulette machine) code that we just added to the Chromosome class. The idea is simple; take the existing chromosome pool, and replace it with a new pool of the same size, but, with only some of the old organisms being able to reproduce and keep their chromosomes going (we can think of the old organisms as dying).
[gist id=”3151534″]
Accordingly, the implementation is also very simple, just a loop and some fitness calculation tacked on (so that we don’t have to recalculate fitness manually). However, there is an important detail to notice. We are calling setRoulette outside the loop, since setRoulette is quite a heavy function, and we would otherwise be calling it unnecessarily multiple times.
A step back
You’re probably trying to absorb a whole stream of information being thrown at you all at once, and its important to understand the underlying idea rather than just how to “code it up”.
So far, we’ve implemented the ability to generate random bit strings of a specified length, which are called chromosomes. Then, we are able to calculate the “fitness” of these chromosomes from the function which we are trying to optimize. Finally, depending on these fitness levels, we are able to select which organisms/chromosomes will be able to reproduce.
The chromosomes that are unable to reproduce will die out, since they were not fit enough to survive.
Finding mates
As we’ll soon see, it is needed to match a chromosome with another one. This is usually done randomly, but, that takes a ton of resources, and, since the order is more or less random to begin with, we’re just going to be having the chromosomes mate up with the chromosome next to them in the array.
[gist id=”3151537″]
The method simply links two neighbours together, then, a hash is made of these to keep record of the relationships.
Crossing
Of course, we just kept reproducing the same chromosomes that we started out with, at the end, we would just have a pool of the fittest of the original chromosomes. But, this isn’t our goal; our goal is to look at the entire population of inputs.
So, we “cross” the chromosomes with others to get some randomness into the mix. Crossing is a very simple idea; if you have one chromosome of 1011 and another of 1100, crossing them two places from the left results in the first becoming 1000 and the second 1111. Basically, we swap the ends of the chromosomes.
The place where to swap them is called the crossover_site.
[gist id=”3151578″]
Again, the code is very straightforward. The “cross” method is an instance method, and it crosses a Chromosome object with another, and, doCrossings uses the getMates method in order to cross an entire list of chromosomes with their mates.
Out of the class!
Alright! We’re done with the class definition!
Now, we just have to put in a little bit of code that will make them methods in the class definition work together, and here it is, in all its glory:
[gist id=”3151608″]
We first generate random chromosomes, then, on each iteration, a new set is developed by reproducing from the old chromosomes (whose parent organisms presumably died). Then, we print out the Chromosome object, so we can see the fitness level and bit string. Finally, new mates are found and crossing is conducted.
Ready to rumble!
Running this code, you should see lot of output that doesn’t really matter much. What matters a lot is the last part of the output that prints out the chromosomes. Out of these, the one with the highest fitness level is said to be our predicted optimal organism.
So, give yourself a pat on the back, you just solved an optimization problem using evolutionary algorithms!
Turn up the volume
But, we’re still only dealing with 4 bits. That would have only taken 16 trials to do with brute force.
Genetic algorithms are much more powerful at higher scales, because they perform much better than brute force for some loss of accuracy in solution. But, to keep the code simple, optimizations haven’t really been put into place. For example, the roulette algorithm can be made much faster, but, that would require some deeper understanding and would really get in the way when trying to wrap your head around the concept of genetic algorithms.
Finishing it up
Genetic algorithms can be applied to a ton of places; searching and optimization problems are immediately evident, but, there also some other very interesting use cases. For example, GA’s are used all the time in cryptography to break codes since it can be brought down to optimizing a function in a certain direction.
Ruby is, in some respects, an excellent language to do GA’s in, because of how nimble and quick it is with strings. But, one must remember, Ruby will not be as fast as C or C++, and, not all applications can work with it. But, in my experience, Ruby has worked just fine for all except the most heavy duty of things.
Also, the Chromosome class that we developed during this post is completely reusable. Meaning that to solve different problems all you have to do is change the fitness function, and maybe tweak the way mating and cross overs are carried out, and, you’re set to go!
If you liked this article, please do Tweet it out using the Twitter button above, and, I’d love to hear your thoughts about it in the comments section below.
Of course, if you have any questions whatsoever, please don’t hesitate to drop a comment below, and I’ll help out as soon as I can.
Dhaivat PandyaI'm a developer, math enthusiast and student.
