class GeneticAlgorithm

Constants

VERSION

Public Class Methods

new(in_pop, prop = {}) click to toggle source

Must be initialized with a Array of chromosomes To be a chomosome the object must implement the next methods:

- fitness
- recombine
- mutate
- distance (only for multi-modal optimization)
Accepts the next properties:
 - max_population: maximum number of individuals that are allowed to form a generation.
 - logger: logger to write messages if given.
 - multi_recombination: set to true if the result of a chromosome's #recombination method
   returns an array. Default to false
 - multi_modal: set to true to use a multi-modal algorithm using deterministic crowding and a distance-derated fitness.
 - share_radius: in multi-modal optimization, determines the niche radius for derated fitness calculation.

# File lib/gga4r.rb, line 19
def initialize(in_pop, prop = {})
  @max_population =  prop[:max_population]
  @logger = prop[:logger] || Logger.new('/dev/null')
  @population = in_pop
  @multi_recombination = prop[:multi_recombination] || false
  @generations = []
  @multi_modal = prop[:multi_modal] || false
  @share_radius = prop[:share_radius] or 3
end

populate_from_file(filename, prop = {}) click to toggle source

Returns a GeneticAlgorithm object with the generations loaded from given files and with properties prop. Files must contain the chromosomes in YAML format.

# File lib/gga4r.rb, line 48
def self.populate_from_file(filename, prop = {})
  GeneticAlgorithm.new(YAML.load(File.open(filename, 'r')), prop)
end

Public Instance Methods

best_fit() click to toggle source

Returns an array with the best fitted individuals for last generation

# File lib/gga4r.rb, line 30
def best_fit
  @population.max_by(&:fitness)
end

best_fitted(n) click to toggle source

Returns an array with the best fitted n individuals from the population (might include local optima)

# File lib/gga4r.rb, line 35
def best_fitted(n)
  @population.uniq.sort_by{|c| -c.fitness}.first(n)
end

best_fitted_derated(n) click to toggle source

Returns an array with the best fitted n individuals from the population (might include local optima) Uses a distance-derated fitness metric

# File lib/gga4r.rb, line 41
def best_fitted_derated(n)
  @population.uniq.sort_by{|c| -(derated_fitness(c,@population))}.first(n)
end

evolve(num_steps = 1) click to toggle source

Evolves the actual generation num_steps steps (1 by default).

# File lib/gga4r.rb, line 63
def evolve(num_steps = 1)
  num_steps.times do |t|
    @population = selection(@population)
    new_gen = @population.map { |chromosome| chromosome.dup }
    if !@multi_modal
      @population += recombination(new_gen) + mutation(new_gen)
    else
      @population = deterministic_crowding(@population)
      @population = mutation(@population)
    end
  end
end

save_population(filename) click to toggle source

Saves into filename and in yaml format the generation that matchs with given generation number ( by default from last generation ).

# File lib/gga4r.rb, line 54
def save_population(filename)
  f = File.new(filename, "w")
  f.write(@population.to_yaml)
  f.close
end

Private Instance Methods

derated_fitness(c,g) click to toggle source

# File lib/gga4r.rb, line 126
def derated_fitness(c,g)
  share_count = g.map{|c2| [(1-c.distance(c2)/@share_radius),0].max }.sum
  share_count = Float::EPSILON if share_count==0
  c.fitness/share_count
end

deterministic_crowding(g) click to toggle source

# File lib/gga4r.rb, line 98
def deterministic_crowding(g)
  groups = g.shuffle
  group1 = groups.first(g.length/2)
  group2 = groups[g.length/2..-1]

  new_gen = []

  group1.each_with_index do |p1,i|
    p2 = group2[i]

    if p2

      c1, c2 = p1.recombine(p2)

      if p1.distance(c1) + p2.distance(c2) <= p1.distance(c2) + p2.distance(c1)
        new_gen << [p1,c1].max_by{|c| derated_fitness(c,g)}
        new_gen << [p2,c2].max_by{|c| derated_fitness(c,g)}
      else 
        new_gen << [p1,c2].max_by{|c| derated_fitness(c,g)}
        new_gen << [p2,c1].max_by{|c| derated_fitness(c,g)}
      end
    else
      new_gen << p1
    end
  end
  new_gen
end

mutation(g) click to toggle source

Mutates population

# File lib/gga4r.rb, line 133
def mutation(g)
  @logger.debug "Mutation " + g.size.to_s + " chromosomes." if @logger
  new_generation = g.dup
  new_generation.each do |chromosome|
    @logger.debug "Mutate" if @logger
    chromosome.mutate
  end
  new_generation
end

recombination(g) click to toggle source

Recombines population

# File lib/gga4r.rb, line 84
def recombination(g)
  @logger.debug "Recombination " + g.size.to_s + " chromosomes." if @logger
  new_generation = g.dup.shuffle!
  @logger.debug "Shuffled!" if @logger
  new_children = []
  new_generation.each_slice(2) do |chromosome1, chromosome2|
    next if chromosome2.nil?
    @logger.debug "Recombining" if @logger
    new_children << chromosome1.recombine(chromosome2)
  end
  new_children.flatten!(1) if @multi_recombination
  new_generation + new_children
end

selection(g) click to toggle source

Selects population to survive and recombine

# File lib/gga4r.rb, line 79
def selection(g)
    @max_population && g.length > @max_population ? g.sort_by{|c| -c.fitness}.first(@max_population) : g
end