Genetic algorithm

genetic.rb

# Genetic algorithm
# Guesses a sequence of numbers. Average distance from the target set is the fitness function.

require 'pp'

LENGTH = 100
MIN_VAL = 0
MAX_VAL = 100
PERFECT_SET = 0.upto(LENGTH-1).to_a


class Chromosome
  attr_reader :genes
  def initialize
    @genes = []
  end
  
  def <<(x)
    @genes << x.to_i
  end
  
  def add_random(ct)
    ct.times { @genes << rand(MAX_VAL) }
  end
  
  def ==(chromosome)
    self.genetic_code == chromosome.genetic_code
  end
  
  def [](x)
    @genes[x]
  end
  
  def randomize!
    @genes = []
    add_random(LENGTH)
  end
  
  def mutate(severity = 50)
    severity.times do |x|
      random_index = @genes.length - 1
      @genes[random_index] += rand(3) - 1
    end
  end
  
  def breed(chromosome)
    # Choose half the genes of self and half the genes of other
    child = Chromosome.new
    1.upto(@genes.length) do |oct|
      idx = oct - 1
      child << (rand(2).zero? ? @genes[idx] : chromosome.genes[idx])
    end
    child.mutate
    child
  end
  
  def genetic_code
    @genes.map {|x| x.to_s.rjust(2,?0)}.join ?-
  end
  def to_s
    "<C<#{genetic_code}>>"
  end

  class << self
    def random
      c = self.new
      c.randomize!
      c
    end
    
    def load(array)
      Chromosome.new.tap {|c| array.map {|x| c << x}}
    end
  end
end

class Environment
  attr_reader :generation, :results, :pool
  def initialize
    @generation = 0
  end
  
  def maximum_distance
    MAX_VAL - MIN_VAL
  end
  
  def maximum_total_distance
    maximum_distance * LENGTH
  end
    
  
  def fitness(chromosome)
    results = { chromosome: chromosome, distance: 0, annealed_distance: [] }
    chromosome.genes.each_index do |idx|
      distance = (PERFECT_SET[idx] - chromosome[idx]).abs
      results[:annealed_distance] << self.maximum_distance - distance
      results[:distance] += distance
    end
    results[:fitness] =  1.0 - (results[:distance] / self.maximum_total_distance.to_f)
    results
  end
  
  def pool=(chromosomes)
    @pool = chromosomes
  end
  
  def run_generation
    @generation += 1
    @results = @pool.map {|c| fitness(c)}.sort {|x,y| y[:fitness] <=> x[:fitness]}
  end
  
  def average_fitness
    @results.inject(0) {|s,i| s += i[:fitness]} / @results.length
  end
  
  def annealed_eugenics(r1, r2)
    child = Chromosome.new
    0.upto(LENGTH - 1) do |idx|
      r1ad = r1[:annealed_distance][idx]
      r2ad = r2[:annealed_distance][idx]
      ch1 = r1[:chromosome]
      ch2 = r2[:chromosome]
      if r1ad > r2ad
        child << ch1[idx]
      else
        child << ch2[idx]
      end
    end
    child.mutate
    child
  end
end

if __FILE__ == $0
  annealed = Environment.new
  genetic = Environment.new
  base_pool = 1000.times.map { Chromosome.random }
  perfect = Chromosome.load(PERFECT_SET)
  puts "Ideal chromosome: #{perfect}\n\n"
  
  
  
  annealed.pool = base_pool
  genetic.pool = base_pool

  50.times do
    genetic.run_generation
    annealed.run_generation
    
    puts ?= * 20
    puts "Annealed: Generation #{annealed.generation}. Pool Size #{annealed.pool.length}."
    puts "  Best fitness: #{annealed.results.first[:fitness]}"
    puts "  Average fitness: #{annealed.average_fitness}"
    puts "  Winner: #{annealed.results.first[:chromosome]}"
    puts $/
    
    annealed_pool = []
    idx = 1
    until annealed_pool.length >= 1000
      0.upto(idx-1) do |i|
        annealed_pool << annealed.annealed_eugenics( annealed.results[i], annealed.results[idx] )
      end
      idx += 1
    end
    annealed.pool = annealed_pool
    
    puts "Genetic: Generation #{genetic.generation}. Pool Size #{genetic.pool.length}."
    puts "  Best fitness: #{genetic.results.first[:fitness]}"
    puts "  Average fitness: #{genetic.average_fitness}"
    puts "  Winner: #{genetic.results.first[:chromosome]}"
    puts $/

    genetic_pool = []
    idx = 1
    until genetic_pool.length >= 1000
      0.upto(idx-1) do |i|
        4.times do
          genetic_pool << genetic.results[idx][:chromosome].breed( genetic.results[i][:chromosome] )
        end
        idx += 1
      end
    end
    genetic.pool = genetic_pool
  end
end