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.