Skip to content

Instantly share code, notes, and snippets.

@sebastiangeiger
Created January 18, 2012 17:08
Show Gist options
  • Save sebastiangeiger/1634106 to your computer and use it in GitHub Desktop.
Save sebastiangeiger/1634106 to your computer and use it in GitHub Desktop.
Gem::Specification.new do |s|
s.name = 'genetic_algorithm'
s.version = '0.0.1'
s.platform = Gem::Platform::RUBY
s.author = 'Sebastian Geiger'
s.email = 'sebastian.geiger@gmail.com'
s.summary = 'A primitive and unfinished genetic algorithm'
s.description = 'This algorithm will take a vector of a fixed length togther with a sum constraint and an executable. The executable must return the performance indicator, the vector should be consumed by the block in order to configure its operation. The performance measure is used to optimize the vector. This is work in progress!'
s.files = ['genetic_algorithm.rb']
s.test_file = 'genetic_algorithm_spec.rb'
s.require_path = '.'
s.add_development_dependency('rspec', ["~> 2.0"])
end
class GeneticAlgorithm
attr_reader :generations, :population_size, :state, :population
class Creature
attr_reader :genes,:fitness
attr_writer :sum_constraint, :genes
class << self
def create_first_generation(genes_length, sum_constraint)
creature = Creature.new
creature.initialize_with(genes_length,sum_constraint)
creature
end
def create_unique_individual(genes_length,constraint)
@@all_individuals_that_have_ever_lived ||= []
begin
individual = Creature::create_first_generation(genes_length,constraint)
end while seen_before?(individual)
@@all_individuals_that_have_ever_lived << individual.signature
individual
end
def seen_before?(individual)
@@all_individuals_that_have_ever_lived.include?(individual.signature)
end
end
def initialize_with(genes_length, sum_constraint)
@sum_constraint = sum_constraint
@genes = Array.new(genes_length,1)
throw "Allowed sum is too small for an array of length #{@genes.size}" if @genes.size>@sum_constraint
until constraints_fulfilled do
@genes.size.times do |i|
@genes[i] = rand(@sum_constraint-1)+1
end
end
@genes = @genes.shuffle
end
def constraints_fulfilled
@genes.inject(0){|sum,e| sum+=e} == @sum_constraint and @genes.min==1
end
def create_mutated_child
child = Creature.new
child.sum_constraint = @sum_constraint
child.genes = @genes
while Creature::seen_before?(child) or @genes.min < 1 do
child.genes = mutate(@genes)
end
@@all_individuals_that_have_ever_lived << child.signature
puts "Created child #{child} from #{self}"
child
end
def mutate(genes)
old_sum = genes.sum
decrementable_indices = []
genes.each_with_index do |gene, i|
decrementable_indices << i if gene > 1
end
genes[decrementable_indices.pick_random] -= 1
genes.pick_random += 1
throw "Magic duplication" unless genes.sum==old_sum
genes
end
def fitness=(fitness)
@fitness = Float(fitness)
end
def signature
return @genes.inspect
end
def to_s
"#{@fitness} | #{@genes.inspect}"
end
end
class UI
def initialize
$stdout.sync = true
@old_state = :not_running
@first_run = true
end
def register(model)
@model = model
end
def update
if leaving_state? and @old_state =~ :measuring_generation then
print " best fitness found: #{@model.previous_generation.collect{|i| i.fitness}.compact.min}"
end
print leaving_state? ? "\n":"\r" unless @first_run
if @model.state == :initializing_vectors then
print "Generating individual creatures: #{progress_bar(@model.latest_generation.size, @model.population_size)}"
end
if @model.state == :measuring_generation then
worked_elements = @model.latest_generation.select{|individual| individual.fitness}.size
print "Measuring generation #{@model.generation_number}: #{progress_bar(worked_elements, @model.population_size)}"
end
if @model.state == :creating_new_generation
print "Creating new generation"
end
if @model.state == :finished
print_generations
print_population
end
@old_state=@model.state
@first_run = false
end
def leaving_state?
@old_state!=@model.state
end
def progress_bar(progress, size)
result = "["
result += "#" * progress
result += "." * (size-progress)
result += "]"
end
def print_generations
# format="%#{@model.generations.collect{|g| g.collect{|i| i.fitness.to_s.size}.flatten.max}}s | %40s\n"
puts ""
puts "Summary:"
@model.generations.each_with_index do |generation,i|
puts "Generation #{i}"
# printf(format, "Fitness", "Genes")
generation.sort{|a,b| a.fitness <=> b.fitness}.each do |individual|
# printf(format, individual.fitness, individual.genes.inspect)
puts "#{individual.fitness} | #{individual.genes.inspect}"
end
end
end
def print_population
puts "Population"
puts @model.population.collect{|individual| "#{individual.fitness} | #{individual.genes.inspect}"}.join("\n")
end
end
class SilentUI
def register(model); end
def update; end
end
class << self
def run_optimization(genes_length,constraint, &block)
ui = UI.new
ga = GeneticAlgorithm.new(genes_length,constraint,:ui=>ui)
first_run = true
until ga.is_finished? do
ga.create_new_generation unless first_run
first_run = false
ga.measure_latest_generation(&block)
ga.choose_fittest_individuals
end
ga.change_state(:finished)
end
end
def initialize(genes_length,constraint,options = {})
@ui = options[:ui] || SilentUI.new
@ui.register(self)
@state = :initializing_vectors
initialize_vectors(genes_length,constraint)
end
def initialize_vectors(genes_length,constraint)
@generations = [[]]
@population = []
@population_size = 3
@iterations = 3
@population_size.times do |i|
individual = Creature::create_unique_individual(genes_length,constraint)
@generations.first << individual
@ui.update
end
end
def measure_latest_generation(&block)
change_state(:measuring_generation)
latest_generation.each do |individual|
individual.fitness = block.call(individual)
@ui.update
end
end
def latest_generation
@generations.last
end
def previous_generation
@generations[-2]
end
def generation_number
@generations.size-1
end
def is_finished?
generation_number == @iterations
end
def create_new_generation
change_state(:creating_new_generation)
new_generation = mutate(@population)
@generations << new_generation
end
def choose_fittest_individuals
@population = (@population+latest_generation).sort{|a,b| a.fitness <=> b.fitness}.take(@population_size)
end
def mutate(individuals)
result = []
individuals.size.times do
child = individuals.pick_random.create_mutated_child
result << child
end
result
end
def change_state(new_state)
# print "Changing from #{@state} to #{new_state}"
@state=new_state
@ui.update
end
end
#
# if __FILE__==$0 then
# GeneticAlgorithm.new([1,1,1,1,1,1,1].size,10)
# end
require File.expand_path('genetic_algorithm.rb')
describe Programmer do
# very lazy, did not add tests yet
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment