# GimubyGenetic 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.

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.

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. 