13 unstable releases (6 breaking)
new 0.7.0 | May 25, 2023 |
---|---|
0.6.0 | Oct 14, 2022 |
0.5.4 | Oct 14, 2022 |
0.5.0 | Jul 7, 2022 |
#202 in Algorithms
33 downloads per month
225KB
4.5K
SLoC
genetic-algorithm
A genetic algorithm implementation for Rust. Inspired by the book Genetic Algorithms in Elixir
There are three main elements to this approach:
- The Genotype (the search space)
- The Fitness function (the search goal)
- The strategy (the search strategy)
- Evolve (evolution strategy)
- Permutate (for small search spaces, with a 100% guarantee)
- HillClimb (when search space is convex with little local optima or when crossover is impossible/inefficient)
Terminology:
- Population: a population has
population_size
number of individuals (called chromosomes). - Chromosome: a chromosome has
genes_size
number of genes - Gene: a gene is a combination of position in the chromosome and value of the gene (allele)
- Allele: alleles are the possible values of the genes
- Genotype: holds the
genes_size
and alleles and knows how to generate and mutate chromosomes efficiently - Fitness: knows how to determine the fitness of a chromosome
Documentation
See docs.rs
Quick Usage
use genetic_algorithm::strategy::evolve::prelude::*;
// the search space
let genotype = BinaryGenotype::builder() // boolean alleles
.with_genes_size(100) // 100 genes per chromosome
.build()
.unwrap();
println!("{}", genotype);
// the search goal to optimize towards (maximize or minimize)
#[derive(Clone, Debug)]
pub struct CountTrue;
impl Fitness for CountTrue {
type Genotype = BinaryGenotype;
fn calculate_for_chromosome(&mut self, chromosome: &Chromosome<Self::Genotype>) -> Option<FitnessValue> {
Some(chromosome.genes.iter().filter(|&value| *value).count() as FitnessValue)
}
}
// the search strategy
let mut rng = rand::thread_rng(); // a randomness provider implementing Trait rand::Rng
let evolve = Evolve::builder()
.with_genotype(genotype)
.with_population_size(100) // evolve with 100 chromosomes
.with_target_fitness_score(100) // goal is 100 times true in the best chromosome
.with_fitness(CountTrue) // count the number of true values in the chromosomes
.with_crossover(CrossoverUniform::new(true)) // crossover all individual genes between 2 chromosomes for offspring
.with_mutate(MutateOnce::new(0.2)) // mutate a single gene with a 20% probability per chromosome
.with_compete(CompeteElite::new()) // sort the chromosomes by fitness to determine crossover order
.with_extension(ExtensionNoop::new()) // extension step, disabled
.call(&mut rng);
.unwrap()
println!("{}", evolve);
Examples
Run with cargo run --example [EXAMPLE_BASENAME] --release
- N-Queens puzzle https://en.wikipedia.org/wiki/Eight_queens_puzzle.
- See examples/evolve_nqueens
- See examples/hill_climb_nqueens
UniqueGenotype<u8>
with a 64x64 chess board setup- custom
NQueensFitness
fitness
- Knapsack problem: https://en.wikipedia.org/wiki/Knapsack_problem
- See examples/evolve_knapsack
- See examples/permutate_knapsack
BinaryGenotype<(weight, value)>
each gene encodes presence in the knapsack- custom
KnapsackFitness(&items, weight_limit)
fitness
- Infinite Monkey theorem: https://en.wikipedia.org/wiki/Infinite_monkey_theorem
- See examples/evolve_monkeys
DiscreteGenotype<char>
100 monkeys randomly typing characters in a loop- custom fitness using hamming distance
- Custom Fitness function with LRU cache
- See examples/evolve_binary_lru_cache_fitness
- Note: doesn't help performance much in this case...
- Permutation strategy instead of Evolve strategy for small search spaces, with a 100% guarantee
- HillClimb strategy instead of Evolve strategy, when crossover is impossible or inefficient
Tests
Run tests with cargo test
Benchmarks
Implemented using criterion. Run benchmarks with cargo bench
Profiling
Implemented using criterion and pprof.
Find the flamegraph in: ./target/criterion/profile_evolve_binary/profile/flamegraph.svg
Run with cargo run --example profile_evolve_binary --release -- --bench --profile-time 5
TODO
- Make duration stats return Duration, so we can choose sec/milli/micro afterwards.
- Make fitness/simple_sum generic
- Does Fitness need an associated trait for Genotype? Can this be made more lightweight?
- Add simulated annealing strategy
MAYBE
- Add Roulette competition with and without duplicates (with fitness ordering)
- Add OrderOne crossover for UniqueGenotype?
- Add WholeArithmetic crossover for ContinuousGenotype?
- Rename Continuous to Real?
ISSUES
- MutateDynamicOnce and MutateDynamicRounds are mutable, but the MutateDispatch reinitializes each round. Fix in feature/enum_plugins branch
Dependencies
~4.5MB
~95K SLoC