Diversion: Genetic Algorithms

In what will hopefully be an ongoing feature, I am posting a small exploration into an area of computer science. I’ve been interested in genetic algorithms for a while, and decided to try my hand at one.  Read on to see what I learned.

Starting with the tutorial at AI Junkie, I began working on a simple genetic algorithm.  I used the proposed exercise, to find an equation that results in a given number.  I cleaned up the example spec a bit, and added support for a unary minus to allow negative numbers.

More importantly, I learned a few interesting things.  For one, we’re really talking about a large population for this example, I ended up using 20,000 population members over 100,000 generations.  Even so, because of the nature of this problem, there are large gaps in the solution space, so most solutions, if they are found, are discovered in less than 500 generations.  I also found it better, when doing chromosome crossovers, to break on the edge of operators, rather than at any random point, and I also discovered that for this problem, a good mutation rate helps, but if it’s too high, solutions with a high fitness score may mutate into uselessness.  Perhaps the digital equivalent of my population living near Chernobyl or Fukushima…  I guess that rules out any chance of X-Men for now.

I think that the most important things to take away from this exercise are that in order to use a genetic algorithm, you need a deep understanding of the problem, and what constitutes a good solution.  It would also help to have a better formula for determining fitness, in this case.  For this problem, the weight of individual genes is not equal, and not even position dependent.  This is due to the nature of arithmetic.  Multiplication and division will have a larger impact on the result of an equation than addition or subtraction, given the same operands.  Therefore a chromosome could be nearly a solution, but with a mutation in the wrong place, it becomes totally unfit, where a similar mutation in a different position would have made it a perfect match.

Following is the code: