My Second Attempt at a Genetic Algorithm

by Jason Swett,

In my previous post I tried to create a genetic algorithm (GA). The idea was that the GA would slap together some numbers and symbols to try to hit a target number. For example, some conceivable expressions would be 5 + 9, 5 * 2 or even something halfway nonsensical like - - 3.

I was able to write a program that would generate these random expressions and see if their results hit my target number. For example, if my target number was 15, an expression of 3 * 5 would be recognized as a success and my program would stop executing. This was mildly amusing but it was not yet a genetic algorithm. I hadn’t yet fully understood what my GA was supposed to be.

The crucial thing my GA was missing was some form of evolution via sexual reproduction and/or mutation. What I needed was a program that would create a generation of chromosomes, then let that generation create a new generation of fitter offspring, then let that new generation create yet another generation of even fitter offspring, and so on. In this particular case, fitness would be determined by how close each chromosome got to the target number.

After some fiddling I arrived at the following bit of code.

Here’s the first generation of chromosomes my program created.

The columns are 1) the chromosome encoding, 2) the expression, 3) the expression’s result, and 4) the chromosome’s fitness score. The fitness score is determined by how close the result is to the target number. Since my target number in this case is 100 and the top chromosome spit out 68, the score in this case is 1 / ((100 – 68) + 1) = 0.0303. (You can see that a result of 100 would be 1 / ((100 – 100) + 1) = 1)

The way the next generation is created is to take the fittest chromosome (8 / 1 * 8 + 4) and let it bang all the other chromosomes to produce offspring. Here’s the result from that:

As you can see, the average fitness has gone up. The fittest member of this generation is also fitter than the fittest member of the previous generation. Let’s run it again.

This time the fittest member is no fitter than the fittest member of the previous generation but the average fitness has gone up. If we run the code again, all the chromosomes end up with equal fitness.

At this point no more evolution is possible without mutation, and since my program doesn’t involve mutation, no more evolution is possible with my program. So 73 is as close to 100 as we’re going to get on this try.

What Next?

I originally embarked upon this exercise because I had been vaguely curious for years about how GAs work. This exercise has given me enough understanding to satisfy that curiosity.

I can imagine some interesting places to go next. First, it seems like a flaw that there’s a less-than-100% chance of my program generating a 100%-fit chromosome for this relatively simple case. Maxing out at 73 seems like a pretty weak result.

Second, it would be interesting to apply a GA to something more entertaining than finding a number close to 100. It would be cool to hook a GA up to some sort of physics engine and create organisms that walk or slither or swim.


Leave a Reply

Your email address will not be published. Required fields are marked *