Genetic algorithms and Island Model for rUBY

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:

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

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:

- 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 Ruby libraries sorted according how interesting I think they are: AI4R, gga4r and darwinning.

Copyright 2014 FrĂ¤ntz Miccoli released under the MIT License.