Evolutionary algorithm example in Ruby

#!/usr/bin/ruby -w

# This program is based on this evolutionar computation introduction:
# http://blog.uncommons.org/2009/01/20/practical-evolutionary-computation-an-introduction/
#
# usage: ruby evolution.rb [generations] [goal]
# example: ruby evolution.rb
#          ruby evolution.rb 100
#          ruby evolution.rb 100 "I make the universe"

# We can set a goal(string) for evolution, and the Evolution object
# will evolute towards the goal you set.
class Evolution
  attr_accessor :set

  # The goal(string) can contain only upcase characters and space
  # CHARSET in fact is gene pool
  CHARSET = ('A'..'Z').to_a + [' ']
  CHARSET_LENGTH = CHARSET.length

  # goal: evolution goal is a string, like 'hello world'
  # population: the population of the society. default to 100, means
  #             there're 100 parents in the initial environment. And
  #             the environment can only support 100 livings.
  # mutation_rate: the possibility of gene mutation. default to 0.01,
  #                means a gene 'A' in one generation has 1/100 possibility
  #                to mutate to random gene in CHARSET
  def initialize(goal,population=100,mutation_rate=0.01)
    @goal = goal
    @population = population
    @mutation_rate = mutation_rate

    # @set is the environment all livings live in
    @set = []
    @strlen = goal.length

    # fill the environment with livings
    population.times {|i|
      str = ""
      @strlen.times {|j| str << CHARSET[rand(CHARSET_LENGTH)] }
      @set << str
    }
  end

  # evolution function
  # reproduce: how many generations should the evolution have
  def run(reproduce=1000)
    reproduce.times {|i| generation }
    sort_and_cut(@set).each {|s| puts "#{s} : #{score s}" }
  end

  private

  # one generation
  def generation
    score_set
    pick
    crossover
    mutation
  end

  # give mutation chance to every living in our environment
  def mutation
    k = 1/@mutation_rate
    for str in @set
      str.length.times {|i|
        str[i] = CHARSET[rand(CHARSET_LENGTH)] if rand(k) == 0
      }
    end
  end

  # choose two parent
  # produce offspring
  def crossover
    set = @set.uniq

    offsprings = []
    if set.length == 1
      offsprings = @set
    else
      (set.length-1).times {|i|
        (i+1).upto(set.length-1) {|j|
          pivot = rand(@strlen) + 1
          par1_a, par1_b = set[i][0,pivot], set[i][pivot,@strlen]
          par2_a, par2_b = set[j][0,pivot], set[j][pivot,@strlen]
          offsprings << "#{par1_a}#{par2_b}"
          offsprings << "#{par2_a}#{par1_b}"
        }
      }
    end

    @set = sort_and_cut(offsprings)
  end

  # pick the good candicates (high score)
  # score 2 candicate will have high possiblity to be choosen than score
  # 1 candicate
  def pick
    pool = []
    @score_map.each {|str,score|
      score.times {|i|
        pool << str
      }
    }
    pool.sort! {|a,b| rand(3) - 1} # shuffle
    pool_len = pool.length
    
    @set = []
    @population.times {|i|
      @set << pool[rand(pool_len)]
    }
  end

  # compute score for every candicates
  def score_set
    @score_map = {}
    for str in @set
      @score_map[str] = score(str)
    end
    @score_map
  end

  # score will tell us the simliarity between the str and goal
  # score = the same character on the correct position with goal
  def score(str)
    score = 0
    @strlen.times {|i|
      score += 1 if str[i] == @goal[i]
    }
    score
  end

  # sort livings by score and only the livings with highest score
  # will left. They're the selection of nature.
  def sort_and_cut(set)
    set.sort_by {|s| -(score s)}[0,@population]
  end

end

if __FILE__ == $0
  times = ARGV[0] ? ARGV[0].to_i : 20
  goal = ARGV[1] ? ARGV[1].upcase : 'HELLO WORLD'
  e = Evolution.new(goal)
  e.run times
end