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.



15
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
 
# File 'lib/mhl/genetic_algorithm_solver.rb', line 15

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

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

    begin
      @mutation_probability = opts[:mutation_probability].to_f
      @mutation_rv = \
        ERV::RandomVariable.new(:distribution           => :geometric,
                                :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,
                                :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, :max_value => 1.0)
    @mutation_rv      = ERV::RandomVariable.new(:distribution => :uniform, :max_value => 1.0)

  else
    raise ArgumentError, 'Only integer and bitstring genotype representations are supported!'
  end

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

  @controller = opts[:controller]

  @pool = Concurrent::FixedThreadPool.new(Concurrent::processor_count * 4)

  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 Logger::WARN)
  end
end

Instance Attribute Details

#mutation_probability ⇒ Object

mutation_probability is the parameter that controls the intensity of mutation



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

def mutation_probability
  @mutation_probability
end

Instance Method Details

#solve(func) ⇒ 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)



92
93
94
95
96
97
98
99
100
101
102
103
104
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
 
# File 'lib/mhl/genetic_algorithm_solver.rb', line 92

def solve(func)
  # 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

    # create latch to control program termination
    latch = Concurrent::CountDownLatch.new(@population_size)

    # assess fitness for every member of the population
    population.each do |s|
      @pool.post do
        # do we need to syncronize this call through population_mutex?
        # probably not.
        ret = func.call(s[:genotype])

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

        # update latch
        latch.count_down
      end
    end

    # wait for all the threads to terminate
    latch.wait

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

    # print results
    puts "> 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