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::new(true)) // crossover all individual genes between 2 chromosomes for offspring .withmutate(MutateOnce::new(0.2)) // mutate a single gene with a 20% probability per chromosome .withcompete(CompeteElite::new()) // sort the chromosomes by fitness to determine crossover order .withextension(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/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

• 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