ga.rb

## Genetic Hello World in Ruby
# Based on https://github.com/jsvazic/GAHelloWorld

class Chromosome
  TARGET = "Hello World!"

  attr_reader :gene, :fitness

  def initialize(gene)
    @gene = gene
    @fitness = self.class.update_fitness(gene)
  end

  def [](*a)
    @gene[*a]
  end

  def self.update_fitness(gene)
    gene.each_byte.zip(TARGET.each_byte).inject(0) do |m, (a, b)|
      m + (a - b).abs
    end
  end

  def self.random
    gene = (0...TARGET.length).map do |x|
      (rand(91) + 32).chr
    end.join

    Chromosome.new(gene)
  end

  def mate(mate)
    pivot = rand(@gene.length)
    gene1 = @gene[0, pivot] +  mate[pivot..-1]
    gene2 =  mate[0, pivot] + @gene[pivot..-1]
    return Chromosome.new(gene1), Chromosome.new(gene2)
  end

  def mutate
    gene = @gene.dup
    delta = rand(91) + 32
    idx = rand(@gene.length)
    gene[idx] = ((gene[idx].ord + delta) % 122).chr
    
    Chromosome.new(gene)
  end
end

class Population
  TOURNAMENT = 3

  attr_reader :population

  def initialize(size = 1024, crossover = 0.8, elitism = 0.1, mutation = 0.03)
    @elitism = elitism
    @mutation = mutation
    @crossover = crossover
    @population = size.times.map { Chromosome.random }.sort_by { |x| x.fitness }
    @size = size
  end

  def selection
    best = @population[rand(@size)]
    TOURNAMENT.times do
      cont = @population[rand(@size)]
      if cont.fitness < best.fitness
        best = cont
      end
    end
    best
  end

  def select_parents
    return selection, selection
  end

  def evolve
    idx = (@size * @elitism).round
    buf = @population[0, idx]

    while idx < @size
      if rand <= @crossover
        p1, p2 = select_parents
        p1.mate(p2).each do |c|
          if rand <= @mutation
            buf << c.mutate
          else
            buf << c
          end
        end
        idx += 1
      else
        if rand <= @mutation
          buf << @population[idx].mutate
        else
          buf << @population[idx]
        end
      end
    end

    @population = buf.sort_by { |x| x.fitness }
  end
end

if $0 == __FILE__
  max = 16384
  pop = Population.new(2048, 0.8, 0.1, 0.3)

  max.times do |i|
    first = pop.population.first
    puts "Generation %d: %s" % [i, first.gene]
    if first.fitness.zero?
      break
    else
      pop.evolve
    end
  end
end