gistfile1.rb

# Genetic algorithm playaround
# chendo 2009
require 'rubygems'
require 'levenshtein'

class GA
  
  def initialize
    @pop = Array.new(100).map { random_string }
  end
  
  def fitness(string)
    goal = "The quick brown fox jumped over the lazy dog"
    Levenshtein.distance(string, goal)
  end

  def random_string
    r = Array.new(44).map { randchr }.join 
  end

  def randchr
    (rand(27) + ?A).chr.send(rand(2) == 0 ? :upcase : :downcase).gsub('[', ' ')
  end

  def trim_bad
    @pop = @pop[0, 20]
  end
  
  def breed(a, b)
    combine_point = rand(44)
    ret = a[0, combine_point]
    ret += b[combine_point, 44]
    ret
  end
  
  def mutate(a)
    a[rand(44)] = randchr
    a
  end
  
  def evolve
    trim_bad
    puts @pop.first
    while @pop.size < 100
      a = rand(20)
      b = rand(20)
      @pop << mutate(breed(@pop[a], @pop[b]))
      @pop.uniq!
    end
    @pop.sort! do |a, b|
      fitness(a) <=> fitness(b)
    end
  end
  
  def pop
    @pop
  end
end

a = GA.new
1000.times {a.evolve}

# a.pop[0, 10].each do |s|
#   p s, a.fitness(s)
# end