My First Attempt at a Genetic Algorithm

by Jason Swett,

What Led Up to This

I’ve been vaguely interested in AI for a long time but I’ve never really done anything with it. I remember in 2008 or so a co-worker mentioned something to me called “genetic algorithms”. That sounded interesting to me.

As someone who’s also interested in biology and paleontology I’m intrigued by the idea of creating little virtual organisms that somehow reproduce and evolve on their own, creating new lifeforms that the programmer could not have anticipated.

I realize that the image conjured up by my mind is not exactly a typical application of genetic programming. But that’s the image that makes the idea appealing to me.

My Program

Well, finally, about ten years later, I’ve decided to finally mess around with genetic algorithms. I somehow stumbled upon a great tutorial called Genetic Algorithms in Plain English which I’ve decided to use as the basis for my work.

I’ll let you read the tutorial if you want the full background but I’ll also provide a little bit of background here. And before I proceed, I should let you know that I have absolutely no idea what I’m doing. So don’t take anything I say here as fact.

I decided to program my genetic algorithm in Ruby. I didn’t want to have to learn genetic algorithms and some new programming language on top of each other, so I decided to use a language I was already quite comfortable with.

The idea with this program is that it will generate an expression and the goal is for the expression to add up to the number 15.

The expression my program generates could be something valid like 3 + 2 or 8 * 3, or it could be something invalid like / + 9 or even * /. If the expression is valid, it gets evaluated and the result is checked to see if it’s 15. If the expression is not valid, it gets skipped.

Here’s the content of my program.

Here’s the tail of a few sample outputs.

Is it Really a Genetic Algorithm?

This is an amusing program but I’m not really sure it’s a genetic algorithm. What would the “genetic” part be? Seems like there should be some swapping of chromosomes happening at some point. These numbers should be banging the hell out of each other. Unfortunately, my program seems pretty G-rated.

My next step will be to examine the genetic algorithm tutorial a little more closely to see how I might be able to make this genetic algorithm a little more legit.

Next Steps

After this I got a real genetic algorithm working.


One thought on “My First Attempt at a Genetic Algorithm

  1. Stephen Jones

    You’re right. This is less like a genetic algorithm and more like a “Thousands monkeys writing Shakespeare” simulation. Every once in a while the target answer will appear but it doesn’t become more likely.

    To make this truly genetic, you need selection, breeding and mutation. Specifically:

    1. A gene pool. You need to maintain an array of best attempts and every generation throw out the worst, breed the best and mutate some others.
    2. A non-binary evaluation function. Without this, your true/false evaluation function will find solutions but much slower because good or even near-perfect solutions will never be rewarded. Of course, you need to reward the most points to equations evaluating to the target but also some points for ones that are close to the target and even some for equations that are well-formed (i.e. correct equations).
    3. Breeding. Every generation, pick a few winners and splice them together (Ex: First six bits of A plus last six bits of B or odd bits of A plus even bits of B, etc)
    4. Selection: Every generation, throw out N strings that evaluate the worst.
    5. Mutation. Although Random_binary_string is a kind of all-or-nothing mutation, you also need partial mutations: Replace genes culled from the pool (previous step) with either newly bred genes or genes with some or all of their bits mutated.

    Using the above, your program will start spitting out better and better answers until it plateaus at some point. Armed with a better algorithm you might want to apply it to more interesting targets like equations that evaluate to prime numbers or points along a line, etc. By just changing the evaluation function, the same program can solve a variety of tough problems


Leave a Reply

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