#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
Refactorings
No refactoring yet !
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.