class MHL::GeneticAlgorithmSolver
Attributes
mutation_probability[R]
mutation_probability
is the parameter that controls the intensity of mutation
Public Class Methods
new(opts)
click to toggle source
# 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
Public Instance Methods
mutation_probability=(new_mp)
click to toggle source
# File lib/mhl/genetic_algorithm_solver.rb, line 90 def mutation_probability=(new_mp) unless new_mp > 0.0 and new_mp < 1.0 raise ArgumentError, 'Mutation probability needs to be > 0 and < 1' end @mutation_probability = new_mp @mutation_rv = \ ERV::RandomVariable.new(distribution: :geometric, args: { :probability_of_success => @mutation_probability }) end
solve(func, params={})
click to toggle source
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)
# 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
Private Instance Methods
binary_tournament(population)
click to toggle source
This method implements binary tournament selection, which is probably the most popular selection method for genetic algorithms
# File lib/mhl/genetic_algorithm_solver.rb, line 226 def binary_tournament(population) i = rand(population.size) j = rand(population.size - 1) j += 1 if j >= i select_fittest(population[i], population[j]) end
new_generation(population)
click to toggle source
reproduction with point mutation and one-point crossover
# File lib/mhl/genetic_algorithm_solver.rb, line 194 def new_generation(population) population_size = population.size # check correct population size # TODO: disable this check in non-debugging mode raise ArgumentError, 'Population size error!' if population_size != @population_size # prepare children children = [] # select members to reproduce through binary tournament selected = Array.new(@population_size) { |i| binary_tournament(population) } selected.shuffle! # reproduction selected.each_slice(2) do |p1, p2| # get two new samples... c1, c2 = @genotype_space.reproduce_from(p1, p2, @mutation_rv, @recombination_rv) # ...and add them to the children population children.push(c1, c2) # check correct population size # TODO: disable this check in non-debugging mode raise 'Children size error!' if children.size > population_size end return children end
select_fittest(*a)
click to toggle source
# File lib/mhl/genetic_algorithm_solver.rb, line 234 def select_fittest(*a) # TODO: disable this check in non-debugging mode raise 'Attempting to select the fittest sample of an empty population!' if a.empty? a.max_by {|x| x[:fitness] } end