genetic_algorithm.gemspec

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       = '[email protected]'
  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

genetic_algorithm.rb

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
      @[email protected]
      @first_run = false
    end

    def leaving_state?
      @[email protected]
    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

genetic_algorithm_spec.rb

require File.expand_path('genetic_algorithm.rb')

describe Programmer do
  # very lazy, did not add tests yet
end