Class: MHL::GeneticAlgorithmSolver

Inherits:
Object
  • Object
show all
Defined in:
lib/mhl/genetic_algorithm_solver.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(opts) ⇒ GeneticAlgorithmSolver

Returns a new instance of GeneticAlgorithmSolver.



16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/mhl/genetic_algorithm_solver.rb', line 16

def initialize(opts)
  @population_size = opts[:population_size].to_i
  unless @population_size and @population_size.even?
    raise ArgumentError, 'Even population size required!'
  end

  @exit_condition   = opts[:exit_condition]
  @start_population = opts[:genotype_space_conf][:start_population]

  @controller = opts[:controller]

  case opts[:logger]
  when :stdout
    @logger = Logger.new(STDOUT)
  when :stderr
    @logger = Logger.new(STDERR)
  else
    @logger = opts[:logger]
  end

  @quiet = opts[:quiet]

  if @logger
    @logger.level = (opts[:log_level] or :warn)
  end

  # perform genotype space-specific configuration
  case opts[:genotype_space_type]
  when :integer
    @genotype_space = IntegerVectorGenotypeSpace.new(opts[:genotype_space_conf], @logger)

    begin
      @mutation_probability = opts[:mutation_probability].to_f
      @mutation_rv = \
        ERV::RandomVariable.new(distribution: :geometric,
                                args: { probability_of_success: @mutation_probability })
    rescue
      raise ArgumentError, 'Mutation probability configuration is wrong.'
    end

    begin
      p_r = opts[:recombination_probability].to_f
      @recombination_rv = \
        ERV::RandomVariable.new(distribution: :uniform,
                                args: { min_value: -p_r, max_value: 1.0 + p_r })
    rescue
      raise ArgumentError, 'Recombination probability configuration is wrong.'
    end

  when :real
    @genotype_space = RealVectorGenotypeSpace.new(opts[:genotype_space_conf], @logger)

    # we have no mutation probability related parameters
    @mutation_rv = ERV::RandomVariable.new(distribution: :uniform, args: { max_value: 1.0 })

    begin
      p_r = opts[:recombination_probability].to_f
      @recombination_rv = \
        ERV::RandomVariable.new(distribution: :uniform,
                                args: { min_value: -p_r, max_value: 1.0 + p_r })
    rescue
      raise ArgumentError, 'Recombination probability configuration is wrong.'
    end

  when :bitstring
    @genotype_space   = BitstringGenotypeSpace.new(opts[:genotype_space_conf])
    @recombination_rv = ERV::RandomVariable.new(distribution: :uniform, args: { max_value: 1.0 })
    @mutation_rv      = ERV::RandomVariable.new(distribution: :uniform, args: { max_value: 1.0 })
  else
    raise ArgumentError, 'Only integer and bitstring genotype representations are supported!'
  end

end

Instance Attribute Details

#mutation_probability ⇒ Object

mutation_probability is the parameter that controls the intensity of mutation



14
15
16
 
# File 'lib/mhl/genetic_algorithm_solver.rb', line 14

def mutation_probability
  @mutation_probability
end

Instance Method Details

#solve(func, params = {}) ⇒ Object

This is the method that solves the optimization problem

Parameter func is supposed to be a method (or a Proc, a lambda, or any callable object) that accepts the genotype as argument (that is, the set of parameters) and returns the phenotype (that is, the function result)



105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
 
# File 'lib/mhl/genetic_algorithm_solver.rb', line 105

def solve(func, params={})
  # setup population
  if @start_population.nil?
    population = Array.new(@population_size) do
      # generate random genotype according to the chromosome type
      { genotype: @genotype_space.get_random }
    end
  else
    population = @start_population.map do |x|
      { genotype: x }
    end
  end

  # initialize variables
  gen = 0
  overall_best = nil

  population_mutex = Mutex.new

  # default behavior is to loop forever
  begin
    gen += 1
    @logger.info("GA - Starting generation #{gen}") if @logger

    # assess fitness for every member of the population
    if params[:concurrent]
      # the function to optimize is thread safe: call it multiple times in
      # a concurrent fashion
      # to this end, we use the high level promise-based construct
      # recommended by the authors of ruby's (fantastic) concurrent gem
      promises = population.map do |member|
        Concurrent::Promise.execute do
          # evaluate target function
          # do we need to syncronize this call through population_mutex?
          # probably not.
          ret = func.call(member[:genotype])

          # protect write access to population struct using mutex
          population_mutex.synchronize do
            # update fitness
            member[:fitness] = ret
          end
        end
      end

      # wait for all the spawned threads to finish
      promises.map(&:wait)
    else
      # the function to optimize is not thread safe: call it multiple times
      # in a sequential fashion
      population.each do |member|
        # evaluate target function
        ret = func.call(member[:genotype])
        # update fitness
        member[:fitness] = ret
      end
    end

    # find fittest member
    population_best = population.max_by {|x| x[:fitness] }

    # print results
    @logger.info "> gen #{gen}, best: #{population_best[:genotype]}, #{population_best[:fitness]}" unless @quiet

    # calculate overall best
    if overall_best.nil?
      overall_best = population_best
    else
      overall_best = [ overall_best, population_best ].max_by {|x| x[:fitness] }
    end

    # execute controller
    @controller.call(self, overall_best) if @controller

    # selection by binary tournament
    children = new_generation(population)

    # update population and generation number
    population = children
  end while @exit_condition.nil? or !@exit_condition.call(gen, overall_best)

  # return best sample
  overall_best
end