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.