Saturday, April 11, 2009

Simple Genetic Algorithm

Edit: Hopefully fixed now.

Edit: Looks like the coloring is whacked out below, but I'm too lazy to clean it up right now. Sorry for the inconvenience.

Sorry for not posting for a bit. I've got a rather large post coming up, but in the meantime, here's a quick one on genetic algorithms (OK, a bit grandiose for what it really is). A couple of weeks ago, I was in Palm Springs with time to kill in the evenings and ran across this post on converting a string using simple mutation and random selection. It took only a short period of time to get the initial version going, and then a few refactorings later, I ended up with this. Getting this ready to publish, I found a few other things that would be nice to put in and better ways to do things, but let's just put it out and you can fix it up (or not) if you like. One thing to warn though there is no error checking on the inputs.

Ok, here's the main program. It reads in the command line arguments and starts everything going.


#!ruby
# == Synopsis
# Runs the weasle program
#
# == Usage
# ruby Weasel.rb [-g generations] [-o number of offspring] [-d desired string]
#
# == Author
# Scott LaBounty
#
# == Copyright
# Copyright(c) 2009 Scott LaBounty
#
#

require 'getoptlong'
require 'rdoc/usage'
require 'population'
require 'organism'

# Set up the command line options
opts = GetoptLong.new(
["--max_generations", "-g", GetoptLong::REQUIRED_ARGUMENT],
["--number_offspring", "-o", GetoptLong::REQUIRED_ARGUMENT],
["--desired_string", "-d", GetoptLong::REQUIRED_ARGUMENT],
["--help", "-h", GetoptLong::NO_ARGUMENT]
)

# Set the default values for the options
max_generations = 5000
number_offspring = 100
desired_string = "methinks it is like a weasel"

# Parse the command line options. If we find one we don't recognize
# an exception will be thrown and we'll rescue with a RDoc::usage
begin
opts.each do | opt, arg|
case opt
when "--max_generations"
max_generations = arg.to_i
when "--number_offspring"
number_offspring = arg.to_i
when "--desired_string"
desired_string = arg
when "--verbose"
RDoc::usage
end
end
rescue
RDoc::usage
end

puts "max_generations = #{max_generations} number_offspring = #{number_offspring} desired_string = #{desired_string}"

# Create the desired organism witht the desired string.
desired_organism = Organism.new(desired_string)

# Create a population with the desired organism, the maximum number of generations, and the number of offspring.
population = Population.new(desired_organism, max_generations, number_offspring)

# Evolve the population
population.evolve



Next up is the population.rb file. It contains the code for evolving the organism and selecting the next generation. It also does the printing out of the current values.

require 'organism'

#
# Population class.
#
class Population

# Initialize with a desired_organism, the maximum number of generations to
# go, and the number of offspring in each generation.
def initialize(desired_organism, max_generations, number_offspring)
@desired_organism = desired_organism
@max_generations = max_generations
@number_offspring = number_offspring
end

# Evolve the population using the desired_organism as a pattern to generate
# the current_organism. Loop generating the number of offspring in each pass
# and pick the best one as the new current_organism. Don't go for more than the
# maximum number of generations.
def evolve
num_generations = 0
current_organism = Organism.new(@desired_organism)
current_organism.randomize
while (current_organism != @desired_organism) && ((num_generations += 1) < @max_generations)

# Create the offspring array and generate the number of offspring
# from the current_organism.
offspring = []
1.upto @number_offspring do
o = Organism.new(current_organism)
o.mutate
offspring << o
end

# Find the best offspring from the ones we
# created above and make it the current offspring.
best_offspring = offspring[0]
best_count = 0
count = 0
offspring.each do | o |
count = o.compare(@desired_organism)
if count >= best_count
best_offspring = o
best_count = count
end
end

# Set the new current_organism to the best_offspring.
current_organism = best_offspring

# Print out the best/current offspring and the matching count to
# see how we're doing.
puts "generation = #{num_generations}: best_offspring = #{best_offspring}: count = #{count}"
end

# Print out the final tally.
puts "Number of generations to result = #{num_generations}"
end
end



Finally, there's the organism itself. We derive from the String class so we can take advantage of the methods already in String.


#
# Organism class that is derived from String. For the alphabet, we use lower case
# letters, and the space only.
class Organism < String

@@alphabet = ["a", "b", "c", "d", "e",
"f", "g", "h", "i", "j",
"k", "l", "m", "n", "o",
"p", "q", "r", "s", "t",
"u", "v", "w", "x", "y","z", " "]

# Completely randomize the string.
def randomize
0.upto length-1 do |i|
self[i] = @@alphabet[rand(27)]
end
end

# Replace a single character in the string with
# a new one from the alphabet. We could turn this into a one-liner,
# but the multiple lines help with readability.
def mutate
replace_position = rand(self.length)
replace_value = @@alphabet[rand(27)]
self[replace_position] = replace_value
end

# Compart the two strings and return the
# number of positions that match.
def compare(d)
count = 0
0.upto d.length-1 do | i |
if d[i] == self[i] then
count = count + 1
end
end
return count
end
end


So there you go. Probably the simplest genetic program you could possibly write. As noted above, there's no error checking so be careful with the input strings. The easiest thing here would be to convert the string to lower case and remove everything else but spaces. The other big problem is that the code is more Java/C++ like than it is Ruby like. Mostly this is a reflection of my background and I'd be very interested in ways you have to make it more Ruby like.

Leave any questions or notes in the comments as usual.

1 comment:

  1. you have a nice site. thanks for sharing this site. you can download lots of ebooks from here

    http://feboook.blogspot.com

    ReplyDelete