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.

CHARACTER_MAP = {
  '0000' => '0',
  '0001' => '1',
  '0010' => '2',
  '0011' => '3',
  '0100' => '4',
  '0101' => '5',
  '0110' => '6',
  '0111' => '7',
  '1000' => '8',
  '1001' => '9',
  '1010' => '+',
  '1011' => '-',
  '1100' => '*',
  '1101' => '/',
}

TARGET_NUMBER = 15

def random_binary_string
  12.times.collect { rand(2) }.join
end

def binary_string_into_expression(starting_string)
  starting_string.scan(/.{4}/).collect { |character_string|
    CHARACTER_MAP[character_string]
  }.join(' ')
end

def eval_expression(expression)
  begin
    eval(expression)
  rescue SyntaxError, NoMethodError, ZeroDivisionError
    nil
  end
end

def run
  result = nil
  number_of_attempts = 0

  while result != TARGET_NUMBER
    number_of_attempts += 1
    binary_string = random_binary_string
    expression = binary_string_into_expression(binary_string)
    result = eval_expression(expression)

    if result
      puts "#{binary_string} | #{expression.ljust(8, ' ')}| #{result}"
    end
  end

  puts "Got target number #{TARGET_NUMBER} in #{number_of_attempts} attempts"
end

Here’s the tail of a few sample outputs.

101110111000 | - - 8   | 8
011111001000 | 7 * 8   | 56
010010110111 | 4 - 7   | -3
000110111000 | 1 - 8   | -7
101110110110 | - - 6   | 6
011111010100 | 7 / 4   | 1
000011000101 | 0 * 5   | 0
011111001001 | 7 * 9   | 63
000011010001 | 0 / 1   | 0
101011100001 | +  1    | 1
001010110101 | 2 - 5   | -3
000111000001 | 1 * 1   | 1
011110101000 | 7 + 8   | 15
Got target number 15 in 936 attempts

000111001001 | 1 * 9   | 9
111011100010 |   2     | 2
011111010011 | 7 / 3   | 2
011011010011 | 6 / 3   | 2
010011000010 | 4 * 2   | 8
110111011111 | / /     | (?-mix: )
011110111001 | 7 - 9   | -2
011011000001 | 6 * 1   | 6
000010111001 | 0 - 9   | -9
011010110000 | 6 - 0   | 6
000010110000 | 0 - 0   | 0
010110100111 | 5 + 7   | 12
101011100110 | +  6    | 6
011010101001 | 6 + 9   | 15
Got target number 15 in 1736 attempts

011110110100 | 7 - 4   | 3
010011011001 | 4 / 9   | 0
101010100000 | + + 0   | 0
001011010100 | 2 / 4   | 0
101001001110 | + 4     | 4
000010110000 | 0 - 0   | 0
100011111110 | 8       | 8
100010110101 | 8 - 5   | 3
000011000000 | 0 * 0   | 0
100010101000 | 8 + 8   | 16
101001011110 | + 5     | 5
101110111000 | - - 8   | 8
010010101000 | 4 + 8   | 12
010011010001 | 4 / 1   | 4
001111000101 | 3 * 5   | 15
Got target number 15 in 167 attempts

111001111111 |  7      | 7
010110110011 | 5 - 3   | 2
011111001000 | 7 * 8   | 56
100111010110 | 9 / 6   | 1
010010110011 | 4 - 3   | 1
011011010010 | 6 / 2   | 3
101111110110 | -  6    | -6
011111000111 | 7 * 7   | 49
101101111111 | - 7     | -7
011111010100 | 7 / 4   | 1
011110100110 | 7 + 6   | 13
101010100110 | + + 6   | 6
111111110100 |   4     | 4
111010011111 |  9      | 9
011011101110 | 6       | 6
000010110101 | 0 - 5   | -5
011110110101 | 7 - 5   | 2
011110101000 | 7 + 8   | 15
Got target number 15 in 285 attempts

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.