Genetic algorithms and Island Model for rUBY


Introduction

Genetic algorithms are loved for their flexibility and easiness of understanding. The island model is initially a way to distribute genetic algorithm, but also can provide better results than genetic algorithm even if distribution of computations is not considered

Gimuby is providing genetic algorithms and island model as a Ruby library. Few technical choice are imposed to the end user and most execution parameters can be easily controlled like mutation strategy, selection strategy, scaling, sharing, reproduction strategy.

Gimuby doesn't use multiprocessing of any kind, thus its island models are not distributed in any sense.

Why using Gimuby

Easy problems

Most problems studied at school are of a special kind that make them computationnaly easy to solve optimally. You find the right formula for your model and then you compute what input optimizes your system.

Hard problems

(Un)fortunately some problem are harder, and in thus, for some weirdos, more interesting. One of the most known examples is the Traveling Salesman Problem (TSP). A salesman needs to go in twenty different cities, what order will lead to the shortest path? To date, no quick way is known about how to find the best order without testing every possibilities (about a billion billions).

Heuristics

Usually systems can work with with not the best but some acceptable solution, because in the end, salesmen are outside, working. Approximative and empirical method called heuristics are used to pragmatically tackle those problems.

Metaheuristics

Genetic algorithms and the island model belong to a kind of heuristic called metaheuristics. They are providing a generic tool to solve hard problems.

Is your problem hard?

The first thing you must know is the nature of your problem. If you don't know what you are doing and have a doubt about your problem, there's a 50% probability that you may are using Gimuby to solve a problem that doesn't need metaheuristics.

The risk is to spend development time and computational time to find a half good solution, when your problem could be solved optimally with less resources. Talk with operational research experts if this point seems critical to your business.

Use Gimuby

If you understand all the above, you may want to use Ruby to solve your problem. So far Gimuby seems to provide the most advanced genetic algorithms implementation available on the language for the following reasons:

  • Support of the island model.
  • Highly customisable.
  • Optimized genetic algorithm available (around the settings of default parameters).

Installation

Gimuby is available for Ruby 1.8.7 and above..

gem install gimuby

Basic usage

Gimuby will always try to minimize the fitness returned of its individuals. If you want to maximize a function, you will have to learn the subtle usage of the "-" symbol.

The simplest usage of Gimuby that can be be made is the optimization of mathematical function with only one property: the input variables are float that belong to the same interval.

In that case you just need to implement your function, wrap it inside a Solution class and run an algorithm with Gimuby.

require 'gimuby'
require 'gimuby/genetic/solution/function_based_solution'

class SampleProblemSolution < FunctionBasedSolution

  def evaluate
    product = 1.0
    @x_values.each do |x_value|
      product *= x_value
    end
    product
  end

  protected

  def get_x_value_min
    -3.0
  end

  def get_x_value_max
    3.0
  end

  def get_dimension_number
    3
  end
end

factory = Gimuby.get_factory
factory.optimal_population = TRUE
optimizer = factory.get_population {next SampleProblemSolution.new}

100.times do
  optimizer.generation_step
end

puts '[' + optimizer.get_best_solution.get_solution_representation.join(',') + ']'
puts optimizer.get_best_fitness
                        

The example above looks dense, but is available with detailed comments inside the source.

Advanced usage

The basic usage hides complexity because it is using an edge case where solutions mutation, check and reproduction strategies can be easily inferred.

Most of those strategies can be reused depending on the problem you are trying to tackle.

require 'gimuby'
require 'gimuby/genetic/solution/solution'
require 'gimuby/genetic/solution/mutation_strategy/mutation_strategy'
require 'gimuby/genetic/solution/check_strategy/check_strategy'

class ArraySplitProblem

  def initialize
    @values = [-12,32,42,0,0,-1,4,27,30,22,76,12,11,27]
  end

  def evaluate(list_of_indexes)
    if (list_of_indexes.length.to_f - @values.length.to_f / 2.0).abs >= 1
      raise Exception.new('Unexpected list_of_indexes, invalid solution')
    end

    sum_1 = 0
    sum_2 = 0
    (0..@values.length - 1).each do |index|
      if list_of_indexes.include? index
        sum_1 += @values[index]
      else
        sum_2 += @values[index]
      end
    end
    (sum_1 - sum_2).abs
  end

  def get_values_number
    @values.length
  end

end

$array_split_problem = ArraySplitProblem.new

class RemoveOneMutationStrategy < MutationStrategy

  # @param solution Solution
  def perform_mutation(solution)
    representation = solution.get_solution_representation
    representation.delete representation.choice
    solution.set_solution_representation representation
    solution.send(:check)
  end
end

class LimitedArraySampleCheckStrategy < CheckStrategy

  def initialize(reference_array, sample_size)
    @reference_array = reference_array
    @sample_size = sample_size
  end

  attr_accessor :reference_array
  attr_accessor :sample_size

  def check(representation)
    representation = representation.clone
    representation.uniq!
    while representation.length < @sample_size
      try_with = @reference_array.choice
      unless representation.include? try_with
        representation.push try_with
      end
    end
    representation
  end

end

class ArraySplitSolution < Solution

  def initialize(picked_indexes = nil)
    potential_indexes = get_potential_indexes
    sample_size = potential_indexes.length / 2
    @check_strategy = LimitedArraySampleCheckStrategy.new(potential_indexes,
                                                          sample_size)
    @new_generation_strategy = CrossOverNewGenerationStrategy.new()
    @mutation_strategy = RemoveOneMutationStrategy.new
    super(picked_indexes)
    check
  end

  def evaluate
    $array_split_problem.evaluate(@picked_indexes)
  end

  def get_solution_representation
    @picked_indexes.clone
  end

  def set_solution_representation(representation)
    @picked_indexes = representation.clone
  end

  protected

  def init_representation
    @picked_indexes = []
    check
  end

  def get_potential_indexes
    values_number = $array_split_problem.get_values_number
    potential_indexes = *(0..values_number - 1)
    potential_indexes
  end

end

factory = Gimuby.get_factory
factory.optimal_population = TRUE

optimizer = factory.get_population {next ArraySplitSolution.new}

100.times do
  optimizer.generation_step
end

puts '[' + optimizer.get_best_solution.get_solution_representation.join(',') + ']'
puts optimizer.get_best_fitness

                        

This example is available with its comments.

Philosophy

Gimuby has been designed to enable highly customisable behaviors.

Many elements can be modified by setting what are called strategies. A strategy specify how a given behavior is run. The following strategies are available:

  • ConnectStrategy (island model related): connects the population of the island model (also called archipelago).
  • PickStrategy (genetic algorithms related): select individuals (also called solution) for reproduction
  • ReplaceStrategy (genetic algorithms related): replace individuals to make the new generation of a population
  • CheckStrategy (solution related): checks that an individual is correct.
  • MutationStrategy (solution related): mutates an individual
  • NewGenerationStrategy (solution related): produces new individuals from two parents

Those strategies are here to make code factorisation possible among problems. There are a few problems that are implemented inside Gimuby that uses those factorisation.

Finer customisation can be achieved by overriding Population and Archipelago classes but this would cancel the usage of the factory.

An example performs a manual instantiation of the optimizers. It's the best place to start if you want to customize these aspects.

Similar libraries

Similar Ruby libraries sorted according how interesting I think they are: AI4R, gga4r and darwinning.

License

Copyright 2014 Fräntz Miccoli released under the MIT License.

Fork me on GitHub