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 Evolve strategy (the search strategy)

Documentation

See crate.io

Quick Usage

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

// the search space let genotype = BinaryGenotype::builder() // boolean genes .withgenesize(100) // 100 of them .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 callforchromosome(&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(CrossoverAll(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 .build() .unwrap() .call(&mut rng);

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

Examples

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

• N-Queens puzzle https://en.wikipedia.org/wiki/Eightqueenspuzzle.
  • See example/evolve_nqueens
  • UniqueDiscreteGenotype<u8> with a 64x64 chess board setup and custom NQueensFitness fitness
• Knapsack problem: https://en.wikipedia.org/wiki/Knapsackproblem
  • See example/evolveknapsack
  • DiscreteGenotype<(weight, value)> with a custom KnapsackFitness(weight_limit) fitness
• Infinite Monkey theorem: https://en.wikipedia.org/wiki/Infinitemonkeytheorem
  • See example/evolve_monkeys
  • DiscreteGenotype<u8> 100 monkeys randomly typing characters in a loop
• Custom Fitness function with LRU cache
  • See example/evolvebinarylrucachefitness
  • Note: doesn't help performance much in this case...
• Permutation strategy instead of Evolve strategy for small search spaces
  • See example/permutate_binary

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
• Support genotypes with variable length (for knapsack problem). A Bag / Set type?
• Add a chromosome stream for Permutate, instead of initializing the full population