A genetic algorithm Crystal library that aims to be simple, but highly customizable.
-
Add the dependency to your
shard.yml
:dependencies: darwin: github: fgouvea/darwin.cr
-
Run
shards install
require "darwin"
# This will evaluate the fitness of each genome
class HelloWorldEvaluator < Darwin::Evaluator(Char)
def evaluate(genome : Array(Char)) : Float64
accuracy = 0.0
# Count how many characters in the genome match the string "hello world!"
(0...genome.size).each do |i|
accuracy += 1 if genome[i] == "hello world!".chars[i]
end
accuracy
end
end
config = Darwin::Config.new(
alphabet: Darwin::Alphabet::StringAlphabet.new("abcdefghijklmnopqrstuwvxyz?!,.; "),
genome_length: 12,
population_size: 50
)
engine = Darwin::Engine.new(
config: config,
evaluation: HelloWorldEvaluator.new)
engine.run(generations: 100)
engine.population[0].dna # => The fittest individual after running
To use darwin.cr
to execute the genetic algorithm (GA) you will have to:
- Code a class that extends
Darwin::Evaluator
and implementsevaluate(Array(T)) : Float64
to evaluate the fitness of a genome. - Crate a
Darwin::Config
object that defines: -
alphabet
- an instance ofDarwin::Alphabet::Alphabet(T)
. You can one of the alphabets provided in this liberary such asIntAlphabet
,ArrayAlphabet
orStringAlphabet
(see Alphabet section below) or implement your own.
-
genome_length
- how many genes are in each individual of the population.
-
population_size
- how many individuals are in the population in each generation.
- Crate a
Darwin::Engine
instance with the configuration and evaluator defined above
The engine
instance lets you run the GA. At the end of every generation the population will be sorted by fitness from highest to lowest, so the fittest individual can be accessed as engine.population[0]
.
You may have noticed that most of the classes included in this library have a generic type parameter T
. This refers to the type of a single gene in the algorithm. By making the classes generic for T
, Darwin can run for arrays of any type you want.
There are more options provided in the config
and engine
objects, as well as various implementations of the operators used in the GA (crossover, mutation, selection), all of which will be discussed in the sections below.
Additionally, you can declare a Darwin::PostProcessor
that will run after each generation to examine or print the results, such as:
class Printer < Darwin::PostProcessor(Char)
def process(engine : Darwin::Engine(Char))
puts "[#{engine.generation} #{engine.population[0].dna.join} (fitness = #{engine.population[0].fitness})]"
end
end
engine = Darwin::Engine.new(..., post: Printer.new)
The Darwin::Config
class has the following properties:
alphabet : Darwin::Alphabet::Alphabet(T)
- an instance ofDarwin::Alphabet::Alphabet(T)
. You can one of the alphabets provided in this liberary such asIntAlphabet
,ArrayAlphabet
orStringAlphabet
(see Alphabet section below) or implement your own.genome_length : Int32
- how many genes are in each individual of the population.population_size : Int32
- how many individuals are in the population in each generation.elitism : Int32
- number of the fittest individuals that will be carried over unchanged to the next population in every generation. This can sometimes help avoid regressions and speed up the algorithm. (Default = 0)
This properties can be assigned as named paremters in the constructor or changed with the setters (e.g. config.elitism = 2
) after the object has been initialized.
The Darwin::Engine
object is responsible for actually carrying out the GA and accepts the following parameters on initialization:
config : Config(T)
- the Darwin config object.evaluation : Evaluator(T)
- the evaluator object that will determine the fitness of an individual, which will in turn determine how likely it is to be selected for mating into the next generation. *crossover : CrossoverOperator(T)
- the crossover operator used to combine two individuals to generate another. By default this is an instance ofDarwin::Crossover::PointCrossover
. This class and its implementations are discussed in the Crossover section below.mutation : MutationOperator(T)
- the mutation operator used to randomly alter an individual to generate genetic diversity in the population. By default this is an instance ofDarwin::Mutation::SimpleMutator
. This class and its implementations are discussed in the Mutation section below.selection : SelectionOperator(T)
- the selection operator used to select two individuals for mating after their fitness has been determined. By default this is an instance ofDarwin::Selection::FitnessSelector
. his class and its implementations are discussed in the Selection section below.post : PostProcessor(T) | Nil
- a post processor that will be run after every generation.
The main method of the Engine
class is run(generations : Int32 = 1)
, which will run the operators of selection, crossover, mutation and evaluation, in this order, generating another generation. You can run 1 generation by simple calling engine.run
or run multiple generations as engine.run(10)
or engine.run(generations: 10)
, for example.
The fields that can be read from the engine
object are:
generation : Int32
- the generation number (starts at 1).population: Array(Genome(T))
- the population, sorted from highest fitness to lowest. TheGenome
object contains:-
dna : Array(T)
- the gene array that defines the individual.
-
fitness : Float64
- the fitness value calculated for the individual by theEvaluator
.
An alphabet is a collection of possible genes that can constitute the genomes in the GA.
It is important to note that the type of the genes is generic in the base Alphabet(T)
class, and the choice of type here will determine the type T
in all other generic classes of this library. For example, if you are working with an Alphabet(Int32)
, your crossover operators will be an implementation of Crossover(Int32)
.
The alphabets provided by this lib are:
Darwin::Alphabet::IntAlphabet
- an alphabet where anyInt32
can be a gene. Acceppts parametersmin
andmax
to control the range of integers allowed.Darwin::Alphabet::ArrayAlphabet(T)
- has an array of objects of typeT
that act as a gene in the genome.Darwin::Alphabet::StringAlphabet
- an easier way of making anArrayAlphabet(Char)
from a string. Initialized as `StringAlphabet.new(alphabet: "abcd...").
Examples:
i_alph = Darwin::Alphabet::IntAlphabet.new(min: 0, max: 9) # IntAlphabet < Alphabet(Int32)
a_alph = Darwin::Alphabet::ArrayAlphabet(String).new(genes: ["gene1", "gene2", "gene3"]) # ArrayAlphabet(String) < Alphabet(String)
s_alph = Darwin::Alphabet::StringAlphabet.new(alphabet: "qwerty") # StringAlphabet < ArrayAlphabet(Char) < Alphabet(Char)
i_alph.random_gene #=> ex: 5
a_alph.random_gene #=> ex: "gene3"
s_alph.random_gene #=> ex: 'w'
However, you may also implement your own Alphabet
and pass it when instantiating the config
file. You can do this by implementing:
abstract class Alphabet(T)
abstract def random_gene() : T
end
This random_gene()
method is used by the Engine
to instantiate the initial population, as well as by the mutator to alter genes in a genome.
The selection operator is responsible for - given a population of individual genomes - selecting two genomes to be combined to produce a new genome for the next population.
The implementation of the selection operator provided by this lib is the Darwin::Selection::FitnessSelector
class, which selects two individuals at random, weighted by the fitness of the individual in relation to the total fitness of the population. In this implementation an individual of fitness 2.0
will be twice as likely to be selected as an individual with a fitness of 1.0
.
However, you may also implement your own Selector
and pass it when instantiating the engine
.
A Selector
has to implement:
abstract class SelectionOperator(T)
abstract def select_mates(genomes : Array(Darwin::Genome(T))) : Tuple(Darwin::Genome(T), Darwin::Genome(T))
end
Please note that unlike the other operators, the selection operator receives the Darwin::Genome
object (described in the Engine section above), so that it can have access to the fitness of the individuals, which is important for this operation.
The crossover operator is responsible for combining two parent genomes to generate a new genome that will be carried over the next population.
The implementations provided out of the box by this library are:
Darwin::Crossover::PointCrossover
- selects a random point in the genome and copies everything before this point from one parent and everything after from the other (e.g. combiningAAAAA
andBBBBB
may result inAABBB
).Darwin::Crossover::UniformCrossover
- randomly selects each gene from either parent (e.g. combiningAAAAA
andBBBBB
may result inABAAB
).
If no crossover operator is passed to the engine
object, it will use PointCrossover
.
However, you may also implement your own Crossover
by implementing:
abstract class CrossoverOperator(T)
abstract def crossover(genome1 : Array(T), genome2 : Array(T)) : Array(T)
end
The mutation operator is responsible for randomly altering the genomes generated in the crossover step before adding them to the next generation. This is extremely important for the GA to add diversity to the population and making sure that it doesn't get stuck in a local maximum because a relevant gene doesn't exist in the population.
The implementation provided by this library is Darwin::Mutation::SimpleMutator
, which has a X% chance of mutating each gene for a random gene provided by the Alphabet
used.
The default mutator in the engine object is a SimpleMutator
with the alphabet provided in the Config
object and a mutatin rate of 0.1
(10%). If you wish to change the mutation rate, simply instantiate another SimpleMutator
when initializing the Engine
object, as in:
mutator = Darwin::Mutation::SimpleMutator(alphabet: config.alphabet, probability: your_probability_here)
engine = Darwin::Engine.new(..., mutation: mutator)
However, you may also implement your own Mutator
by implementing:
abstract class MutationOperator(T)
abstract def mutate(genome : Array(T)) : Array(T)
end
Different operator implementations should be added to their respective folders and namespaces. For example, a new Mutator
should go inside the src/darwin/mutation
folder and be declared inside the Darwin::Mutation
namespace.
As many things in the GA involve randomness, a mock of sorts of the Random
class is provided in spec/spec_helper.cr
, allowing us to define a sequence of results for the random methods:
rng = MockRandom(random_ints: [3, 2, 0])
rng.rand(0...10) #=> 3
rng.rand(0...10) #=> 2
rng.rand(0...10) #=> 0
rng.rand(0...10) #=> IndexError
Every class that has a random operation receives an optional rng
parameter on initialization, which we can use to pass the MockRandom
instance.
Also, every operator has a Stub
class that will return static results passed to it, as well as recording the parameters of the calls it received. Example:
m = Darwin::Mutation::StubMutator(mutation_results: [[0, 0 ,0], [1, 1, 1], [2, 2, 2]])
m.mutate([1, 2, 3]) #=> [0, 0, 0]
m.mutate([4, 5, 6]) #=> [1, 1, 1]
m.calls #=> [[1, 2, 3], [4, 5, 6]]
- Fork it (https://github.com/fgouvea/darwincr/fork)
- Create your feature branch (
git checkout -b my-new-feature
) - Commit your changes (
git commit -am 'Add some feature'
) - Push to the branch (
git push origin my-new-feature
) - Create a new Pull Request
- Fernando Gouvêa - creator and maintainer