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.
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.
(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).
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.
Genetic algorithms and the island model belong to a kind of heuristic called metaheuristics. They are providing a generic tool to solve hard problems.
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.
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:
Gimuby is available for Ruby 1.8.7 and above..
gem install gimuby
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.
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.
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:
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 Ruby libraries sorted according how interesting I think they are: AI4R, gga4r and darwinning.
Copyright 2014 Fräntz Miccoli released under the MIT License.