Class: GeneticOptimizer

Inherits:
Optimizer show all
Includes:
LoggedClass
Defined in:
lib/genetic_optimizer.rb

Overview

This class can be used to construct Optimizers based on the genetic algorithm. There are a few “variables” for controlling the behavior of this class.

(TODO This could be refactored to make this more flexible)

The following aspects can be specified by the user:

  1. The population size.

  2. The selection algorithm can be defined by a Proc reciving the following

parameters: the results array and a random object.

  1. The number of genotypes to be constructed by the crossover operation.

  2. The probability for the crossover operation to “switch sides”, for more on

this, see the crossover description in the folloing paragraphs.

  1. The number of genotypes to be constructed by the mutation operation.

  2. The probability for the mutation operation to change a flag.

The algorithm works as follows: The population gets randomly generated in the beginning. Then the select-repopulate-loop starts. The population gets new members with the crossover and mutation opertion.

The crossover algorithm takes “genes” from one genotype and adds it to the result and continues to do so until it randomly switches sides and from then on takes from the other side again. The mutation algorithm goes over all “genes” and according to some probability chooses to change some to a random value.

After that the user provided selection function reduces the population to a reasonable number.

Constant Summary

Constants included from LoggedClass

LoggedClass::LoggedClasses

Instance Attribute Summary

Attributes inherited from Optimizer

#results

Instance Method Summary collapse

Methods included from LoggedClass

#debug, #error, #fatal, generate_outputter_config, included, #info, #warn

Methods inherited from Optimizer

#run

Constructor Details

#initialize(name, seed, evaluator, population_size, select, crossovers, crossover_probability, mutations, mutation_probability, termination_criterion, flag_set, load_state_filename = nil) ⇒ GeneticOptimizer

Returns a new generation based Optimizer.

Parameters:

  • name (String)

    Name of the Algorithm.

  • seed (Fixnum)

    The seed for the random generator.

  • evaluator (Evaluator)

    The Evaluator to use.

  • select (Proc)

    The selection function.

  • crossovers (Fixnum)

    The number of genotypes to be generated by the crossover operation.

  • crossover_probability (Float)

    The probability for the crossover operation to “switch sides”. See the class documentation for more on this.

  • mutations (Fixnum)

    The number of genotypes to be generated by the mutation operation.

  • mutation_probability (Float)

    The probability for the mutation operation to change an element of a candidate.

  • termination_criterion (Proc)

    The termination criterion.

  • flag_set (FlagSet)

    The flag set to use.

  • load_state_filename (String) (defaults to: nil)

    The name of a file to load the state from.


42
43
44
45
46
47
48
49
50
51
52
53
# File 'lib/genetic_optimizer.rb', line 42

def initialize(name, seed, evaluator, population_size, select,
               crossovers, crossover_probability,
               mutations, mutation_probability,
               termination_criterion, flag_set, load_state_filename = nil)
  super name, seed, evaluator, load_state_filename
  @population_size, @flag_set = population_size, flag_set
  @select, @termination_criterion = select, termination_criterion
  @crossovers, @mutations = crossovers, mutations
  @crossover_probability = crossover_probability
  @mutation_probability = mutation_probability
  @genotypes = []
end

Instance Method Details

#crossover(geno1, geno2, prob) ⇒ Object


108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
# File 'lib/genetic_optimizer.rb', line 108

def crossover(geno1, geno2, prob)
  # iterate over all components
  geno_new = geno1.dup
  select_first = false

  geno2.each_with_index do |flag, idx|
    if @random.rand <= prob then
      select_first = !select_first
    end
    geno_new[idx] = flag[:value] unless select_first
  end

  debug "Genetic: crossover 1 #{geno1.show_binstring}\n" +
    "Genetic: crossover 2 #{geno2.show_binstring}\n" +
    "Genetic: crossover = #{geno_new.show_binstring}"
  geno_new
end

#load_state(filename) ⇒ Object


149
150
151
152
153
# File 'lib/genetic_optimizer.rb', line 149

def load_state(filename)
  File.open(filename, "r") do |file|
    _, @steps, @results, @genotypes, @random = Marshal.restore @file.read
  end
end

#mutate(geno, prob) ⇒ Object


127
128
129
130
131
132
133
134
135
136
137
138
# File 'lib/genetic_optimizer.rb', line 127

def mutate(geno, prob)
  geno = geno.dup

  geno.each_with_index do |flag, idx|
    if @random.rand <= prob then
      debug "Genetic: Mutating #{flag}"
      geno[idx] = flag[:flag].pick(@random)
    end
  end

  geno
end

#repopulate(genotypes) ⇒ Object


82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# File 'lib/genetic_optimizer.rb', line 82

def repopulate(genotypes)
  previous_genotypes = genotypes.dup
  crossover_genotypes = []

  @crossovers.times do
    # select random pairs and crossover them
    candidate = crossover(*(previous_genotypes.
                            shuffle(random: @random)[0..1]),
                            @crossover_probability)
    while crossover_genotypes.include? candidate do
      candidate = crossover(*(previous_genotypes.
                              shuffle(random: @random)[0..1]),
                              @crossover_probability)
    end
    crossover_genotypes << candidate
  end

  mutation_genotypes = previous_genotypes[0...@mutations].map do |genotype|
    mutate genotype, @mutation_probability
  end

  crossover_genotypes + mutation_genotypes + previous_genotypes
end

#save_state(filename) ⇒ Object


141
142
143
144
145
146
# File 'lib/genetic_optimizer.rb', line 141

def save_state(filename)
  File.open(filename, "w") do |file|
    file.write (Marshal.dump [:genetic, @steps, @results,
                              @genotypes, @random])
  end
end

#stepObject


56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
# File 'lib/genetic_optimizer.rb', line 56

def step()
  if @steps.zero? then
    @genotypes, = (OptimizerUtils.get_init OptimizerUtils.get_init_mutate,
                                           @population_size,
                                           @flag_set)[@genotypes,
                                                      @results,
                                                      @random, nil]
  end

  @genotypes = repopulate @genotypes

  # evaluate genotypes
  @results << (@evaluator[@genotypes].zip (@genotypes.map do |genotype|
    genotype.dup
  end))

  # increment step-counter
  @steps += 1
  @evaluator.step

  @genotypes = @select[@results, @random]

  raise OptimizerCompleteSignal if @termination_criterion[@steps, @results]
end