Genetic algorithm for making equations


  #formula_ga.rb

require 'equation'

class Population
  attr_accessor :equations, :match_found
  
  @match_found = false
  
  def initialize(size=50, target_number=0)
    @equations = []
    @size = size
    @target_number = target_number
    1.upto(@size) { @equations << Equation.new }
  end
   
  def evaluate_fitness(equation)
    deviation = @target_number - eval(equation.phenotype).to_f
    @match_found = true if deviation == 0 
    fitness = (1 / deviation).abs
    fitness = 0 if fitness.nan?
    return fitness
  end
  
  def reproduce
    reproduction_pool = []
    1.upto(@size / 2) { reproduction_pool << @equations.random }
    reproduction_pool = reproduction_pool.sort_by { |eq| evaluate_fitness(eq) }
    reproduction_pool.reverse!
    
    1.upto(reproduction_pool.size / 2) do |i|
      i = i - 1
      spawn = reproduction_pool[i].create_spawn
      evaluate_fitness(spawn)
      @equations << spawn
    end
  end
  
  def cull
    death_pool = []
    positions = Hash.new
    
    1.upto(@equations.size / 2) do
      equation = @equations.random
      death_pool << equation
      positions.store(equation, @equations.last_random_index)
    end
    
    death_pool = death_pool.sort_by { |eq| evaluate_fitness(eq) }
    
    1.upto(death_pool.size / 2) do |i|
      i = i - 1
      doomed_equation = death_pool[i]
      @equations.delete_at(positions[doomed_equation])      
    end
  end
  
  def display_all
    @equations.each do |eq|
      eq.display
      puts "Fitness: #{evaluate_fitness(eq)}"
    end
  end
  
  def next_generation
    reproduce
    cull unless @match_found
    display_all
  end
end

target_number = 67.2
pop = Population.new(50, target_number)
pop.display_all

until pop.match_found
  pop.next_generation
end

puts 'Match found!'
puts ''

sleep(1)
pop.equations = pop.equations.sort_by { |eq| pop.evaluate_fitness(eq) }
pop.display_all

#equation.rb

class Array
  attr_accessor :last_random_index
  
  def random
    @last_random_index = rand(self.length)
    self[@last_random_index]
  end
end

class Genome
  attr_accessor :code
  
  @@decode = {     '0000' => '0.0', '0001' => '1.0', '0010' => '2.0', '0011' => '3.0',
  '0100' => '4.0', '0101' => '5.0', '0110' => '6.0', '0111' => '7.0', '1000' => '8.0',
  '1001' => '9.0', '1010' => '+',   '1011' => '-',   '1100' => '*',   '1101' => '/' }
  @@operators = %w[+ - * /]
  @@numbers = %w[0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0]
  @@mutation_chance = 15 #One chance in this number of mutating.

  def initialize(min_length=4, max_length=32, copy_code='off')
    if copy_code == 'off'
      length = min_length + rand(1 + max_length - min_length)
      @code = generate_code(length)
    else
      @code = copy_code
    end
  end
  
  def generate_code(length)
    code = ''
    1.upto(length) do
      code += %w[0 1].random
    end
    code
  end
  
  def decode
    decoded = ''
    expected = :number
    
    1.upto(@code.length) do |i|
      if i % 4 == 0
        coded = @code.slice((i-4)..(i-1))
        symbol = @@decode[coded].to_s
        if expected == :number && @@numbers.include?(symbol)
          decoded += symbol
          expected = :operator
        elsif expected == :operator && @@operators.include?(symbol)
          decoded += symbol
          expected = :number        
        end
      end
    end
    
    if expected == :number
      decoded.chop!
    end
    
    return decoded
  end
  
  def mutate
    new_code = String.new(@code)
    
    i = 0
    new_code.each_byte do |bit|
      bit = bit.chr
      if rand(@@mutation_chance) == 0 
        if bit == '0'
          new_code[i] = '1'
        elsif bit == '1'
          new_code[i] = '0'
        end
      end      
      i += 1
    end
    
    if rand(@@mutation_chance) == 0
      action = [:add, :remove].random
      if action == :add
        new_code.insert(rand(new_code.length), %w[0 1].random) 
      elsif action == :remove
        new_code.slice!(rand(new_code.length))
      end
    end
    
    Genome.new(1, 1, new_code)
  end
end

class Equation
  attr_accessor :genome, :phenotype
  
  @@min_genome_size, @@max_genome_size = 64, 512
  
  def initialize(copy_genome='off')
    if copy_genome == 'off'
      @genome = Genome.new(@@min_genome_size, @@max_genome_size)
    else
      @genome = copy_genome.mutate
    end
    @phenotype = @genome.decode
  end
  
  def create_spawn
    spawn = Equation.new(self.genome)
  end
  
  def display
    puts @genome.code
    puts @phenotype
    puts eval(phenotype)
  end
end
  I'm working on a genetic algorithm that produces equations, using 0-9 and +-*/, that are equal to a target number. For example, if the target number is 13.5 it might find "9.0 + 4.0 + 1.0 / 2.0" or "5.0 * 2.0 * 2.0 / 2.0 + 7.0 / 2.0 + 0.0".

Right now it works, although it isn't very efficient. I still need to implement some form of recombination, for example. Before I do that I'd like to clean it up a bit though.

equation.rb and formula_ga.rb need to be in the same directory. You run formula_ga.rb.
  2008-06-09T01:55:12+00:00
  313
  Ruby
  genetic-algorithm-for-making-equations
  1
  Genetic algorithm for making equations
  
  2009-11-11T10:55:59+00:00
  632
  
    
      comment2 
      313
      comment2 
      2009-11-11T10:55:56+00:00
      359047
      Ruby
      0
      0
      On Genetic algorithm for making equations
      
      Eugzfmii
      link