talgene
Talgene
A simple programming abstraction layer over genetic algorithms implementations.
Installation
-
Add the dependency to your
shard.yml
:dependencies: talgene: github: nin93/talgene
-
Run
shards install
Usage
require "talgene"
Genome
Start by defining your genetic representation for your model. In the following example we implement a solution for the knapsack problem.
An abstract class Talgene::Genome
is provided for this purpose, requiring you to implement all the methods needed. Within each model a fitness
function is expected to be defined to evaluate the solution domain:
record Item, value : Float64, weight : Float64 do
property? inside : Bool = false
end
class Knapsack < Talgene::Genome(Item)
def initialize(@genes : Array(Item), @max_weight : Float64)
end
def fitness
weight = 0.0
reduce 0.0 do |fitness, item|
unless item.inside?
fitness
else
if (weight += item.weight) > @max_weight
break 0.0
else
fitness + item.value
end
end
end
end
end
One could implement custom, yet classic, rules for genetic recombination such as crossover and mutation functions. For example, using our Knapsack
model from above:
class Knapsack < Talgene::Genome(Item)
# Storing a mutation rate as well
def initialize(@genes : Array(Item), @max_weight : Float64, @mutation_rate : Float64)
end
def cross(other : Knapsack) : Knapsack
new_genes = Talgene::Crossable.single_point_cross(@genes, other.genes).sample
Knapsack.new new_genes, @max_weight, @mutation_rate
end
def mutate : Knapsack
new_genes = map do |item|
new_item = item.dup
if @mutation_rate > rand
new_item.inside = !new_item.inside?
end
new_item
end
Knapsack.new new_genes, @max_weight, @mutation_rate
end
end
Generation
We now need to define the rules to perform a selection among competing individuals within a population and start a new generation. This is done by inheriting from the Talgene::Generation
abstract class and by implementing an advance
method:
class Generation < Talgene::Generation(Knapsack)
def advance : Generation
# Avoid recombination with self
other_bucket = population.reject do |knapsack|
knapsack.same? fittest
end
new_population = Array.new population.size do
fittest.cross(other_bucket.sample).mutate
end
Generation.new new_population
end
end
System
Talgene::System
takes care to iterate through generations. We load the generation zero:
# Initialize your generation zero
population_zero = [...] of Knapsack
generation_zero = Generation.new population_zero
sys = Talgene::System.new generation_zero, max_advances: 100
# Use `include_first: true` to include the generation zero
sys = Talgene::System.new generation_zero, max_advances: 100, include_first: true
Since Talgene::System
includes the Iterator
module, a set of convenient methods are provided such as max_by
, skip_while
, select
, each_cons
.
# The fittest among all generations is easy to find with `max_of`.
fittest_ever = sys.max_of &.fittest
fittest_ever.fitness # => 26.5
Optionally, a Talgene::System
can be initialized with a rule declaring when an evolution process should be ended in advance, useful in those cases in which we would expect a good enough individual beforehand.
For instance:
sys = Talgene::System.new generation_zero, max_advances: 100 do
stop_on do |current|
current.best_fitness > 26
end
end
# Consume the iterator
sys.size # => 4
sys.next # => Iterator::Stop::INSTANCE
A full example can be found in the examples folder.
Contributing
- Fork it (https://github.com/nin93/talgene/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
Contributors
- Elia Franzella - creator and maintainer
talgene
- 1
- 0
- 0
- 0
- 0
- almost 2 years ago
- January 23, 2023
MIT License
Fri, 22 Nov 2024 19:45:05 GMT