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

```rust use genetic_algorithm::strategy::evolve::prelude::*;

// the search space let genotype = BinaryGenotype::builder() // boolean alleles .withgenessize(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 calculateforchromosome(&mut self, chromosome: &Chromosome) -> Option { Some(chromosome.genes.iter().filter(|&value| *value).count() as FitnessValue) } }

// the search strategy let mut rng = rand::threadrng(); // a randomness provider implementing Trait rand::Rng let evolve = Evolve::builder() .withgenotype(genotype) .withpopulationsize(100) // evolve with 100 chromosomes .withtargetfitnessscore(100) // goal is 100 times true in the best chromosome .withfitness(CountTrue) // count the number of true values in the chromosomes .withcrossover(CrossoverUniform(true)) // crossover all individual genes between 2 chromosomes for offspring .withmutate(MutateOnce(0.2)) // mutate a single gene with a 20% probability per chromosome .with_compete(CompeteElite) // sort the chromosomes by fitness to determine crossover order .call(&mut rng); .unwrap()

println!("{}", evolve); ```

Examples

Run with cargo run --example [EXAMPLE_BASENAME] --release

• N-Queens puzzle https://en.wikipedia.org/wiki/Eightqueenspuzzle.
  • See examples/evolve_nqueens
  • See examples/hillclimbnqueens
  • UniqueGenotype<u8> with a 64x64 chess board setup
  • custom NQueensFitness fitness
• Knapsack problem: https://en.wikipedia.org/wiki/Knapsackproblem
  • See examples/evolveknapsack
  • 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/Infinitemonkeytheorem
  • 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/evolvebinarylrucachefitness
  • Note: doesn't help performance much in this case...
• Permutation strategy instead of Evolve strategy for small search spaces, with a 100% guarantee
  • See examples/permutate_knapsack
• HillClimb strategy instead of Evolve strategy, when crossover is impossible or inefficient
  • See examples/hillclimbnqueens
  • See examples/hillclimbtable_seating

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

• Maybe seed best_chromosome back into population after degenerate?
• 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
• Redo degenerationrange, as it is tricky to configure. Depends on how fitness behaves (expected spread per mutation). Maybe redo as degenerationduration in term of generations to hold on to it, triggered by standard trigger when no variation in fitness score is left.

MAYBE

• Store age on chromosome?
• Add Tournament competition with duplicates (needs cloning)
• Add Roulette competition with and without duplicates (with fitness ordering)
• Add OrderOne crossover for UniqueGenotype?
• Add WholeArithmetic crossover for ContinuousGenotype?
• Rename Continuous to Real?