Source code for the Breeding Strings article.

breeding-strings.rb

#!/usr/bin/env ruby
# encoding: utf-8

=begin
* Name: string-breeder.rb
*   This script will breed the string value: "Hello World" (sans quotes) 
*   or whatever was passed as the argument.
*   No warranties implied, but feel free to copy, modify, and share.
* Author: Juris Galang
* Date: February 2009
* License:
=end

REFERENCE  = ARGV.first || "Hello World"
MINLEN     = 2
MAXLEN     = 80
MAXSIZE    = 1000
ELITE_SIZE = 15
MAXCODE    = 256
MUTATION   = 0.25

class String
  def fitness		
    other  = REFERENCE
    length = other.size < self.size ? self.size : other.size
    result = 0
    length.times do |i|
      m = (i < self.size) ? self[i].ord : 0
      n = (i < other.size) ? other[i].ord : 0
      result += (m - n).abs
    end
    result
  end

  def *(other)
    m      = rand(self.size - 2) + 1
    tail   = self[m .. -1]
    head   = (m >= other.size) ? other : other[0 .. m-1]
    result = head + tail
    result.mutate! if rand < MUTATION
    result
  end

  def mutate!
    index = rand(self.size + 1)
    gene  = rand(MAXCODE).chr
    (index == self.size) ? self << gene : self[index] = gene
    self
  end
end

def seed
  @population = []
  while @population.size < MAXSIZE
    maxlen   = rand(MAXLEN) + MINLEN
    organism = ''
    while organism.size < maxlen
      gene      = rand(MAXCODE).chr
	    organism << gene
    end
    @population << organism
  end
end

def evaluate
  @population.sort{ |a, b| a.fitness <=> b.fitness }.shift(ELITE_SIZE)
end

def breed(elite)
  @population = []
  while @population.size < MAXSIZE do
    a = elite[rand(elite.size)]
    b = elite[rand(elite.size)] 
    next if a.equal? b
    @population << a * b
  end
end

def best
  @population.first
end

seed
generation = 0
while true 
  puts "#{best} (#{generation})"
  break if best == REFERENCE
  elite = evaluate
  breed(elite)
  generation += 1
end