src/libgenetics.rb

   1 # == Synopsis
   2 #
   3 # Library to support genetic algorithms
   4 #
   5 # == Author
   6 # Neil Smith
   7 #
   8 # == Change history
   9 # Version 1.1::  23 April 2008
  10
  11 # A single genome in a population
  12 class Genome
  13
  14   attr_accessor :genome
  15
  16   # Create a random genome of the given length
  17   def initialize(bitstring_or_length)
  18     if bitstring_or_length.class == Fixnum
  19       @genome = []
  20       (1..bitstring_or_length).each do |i|
  21         @genome << rand(2)
  22       end
  23     else
  24       @genome = bitstring_or_length
  25     end
  26   end
  27
  28   # Mutate a genome with the given rate per bit
  29   def mutate(mutation_probability = 0.05)
  30     new_genome = Genome.new(@genome.length)
  31     (0...@genome.length).each do |i|
  32       if rand < mutation_probability
  33         if @genome[i] == 0
  34           new_genome.genome[i] = 1
  35         else
  36           new_genome.genome[i] = 0
  37         end
  38       else
  39         new_genome.genome[i] = @genome[i]
  40       end
  41     end
  42     new_genome
  43   end
  44
  45   # Mutate a genome in-place with the given rate per bit
  46   def mutate!(mutation_probability = 0.05)
  47     (0...@genome.length).each do |i|
  48       if rand < mutation_probability
  49         if @genome[i] == 0
  50           @genome[i] = 1
  51         else
  52           @genome[i] = 0
  53         end
  54       end
  55     end
  56     @genome
  57   end
  58
  59   # Crossover two genomes at the given point
  60   def crossover(other_genome, crossover_point)
  61     raise ArgumentError, "Different size genomes" if @genome.length != other_genome.genome.length
  62     raise ArgumentError, "Our of bounds crossover point" if crossover_point < 0 or crossover_point > @genome.length
  63     child1 = Genome.new(0)
  64     child2 = Genome.new(0)
  65     child1.genome = @genome[0, crossover_point] + other_genome.genome[crossover_point, @genome.length]
  66     child2.genome = other_genome.genome[0, crossover_point] + @genome[crossover_point, @genome.length]
  67     [child1, child2]
  68   end
  69
  70 end
  71
  72
  73 class Array
  74   def to_decimal
  75     val = 0
  76     bits = self.dup
  77     while not bits.empty?
  78       val = val * 2 + bits[0]
  79       bits = bits[1..bits.length]
  80     end
  81     val
  82   end
  83
  84   def gray_encode
  85     gray = self[0..0]
  86     (1...self.length).each do |i|
  87       if (self[i - 1] == 1) ^ (self[i] == 1)
  88         gray << 1
  89       else
  90         gray << 0
  91       end
  92     end
  93     gray
  94   end
  95
  96   def gray_decode
  97     binary = self[0..0]
  98     (1...self.length).each do |i|
  99       if (binary[i - 1] == 1) ^ (self[i] == 1)
 100         binary << 1
 101       else
 102         binary << 0
 103       end
 104     end
 105     binary
 106   end
 107
 108 end
 109
 110 class Fixnum
 111   def to_bitstring(min_length = 0)
 112     bits = []
 113     k = self
 114     while k > 0 do
 115       if k % 2 == 1
 116         bits << 1
 117       else
 118         bits << 0
 119       end
 120       k = k >> 1
 121     end
 122     while bits.length < min_length do
 123       bits << 0
 124     end
 125     bits.reverse
 126   end
 127 end
 128
 129
 130 # A population of genomes
 131 class Population
 132   attr_accessor :individuals
 133
 134   # Create a population of a given size
 135   def initialize(population_size, genome_length = 0)
 136     @individuals = []
 137     1.upto(population_size) { @individuals << Genome.new(genome_length) }
 138   end
 139
 140   # Perform the crossover step in a population, giving a new population
 141   def crossover(crossover_rate)
 142     parents = @individuals.dup # genomes that haven't been parents yet
 143     next_population = Population.new(0)
 144     while parents.length > 1
 145       parent1 = parents.delete_at(rand(parents.length)).dup
 146       parent2 = parents.delete_at(rand(parents.length)).dup
 147       if rand < crossover_rate
 148         child1, child2 = parent1.crossover parent2, rand(parent1.genome.length)
 149         next_population.individuals << child1 << child2
 150       else
 151         next_population.individuals << parent1 << parent2
 152       end
 153     end
 154     next_population.individuals.concat parents # pick up any parents that didn't get a chance to mate
 155     next_population
 156   end
 157
 158   # Perform the mutation step in a population, giving a new population
 159   def mutation(mutation_rate)
 160     parents = @individuals.dup # genomes that haven't been parents yet
 161     next_population = Population.new(0)
 162     while parents.length > 0
 163       parent = parents.pop.dup
 164       child = parent.mutate mutation_rate
 165       next_population.individuals << child
 166     end
 167     next_population
 168   end
 169
 170   def make_next_generation(tournament_winner_success_rate = 0.8, game_length = 1000, crossover_rate = 0.7, mutation_rate = 0.05)
 171     @individuals = tournament_select_population(tournament_winner_success_rate, game_length, false)
 172     @individuals = crossover(crossover_rate)
 173     @individuals = mutation(mutation_rate)
 174   end
 175
 176 end