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 docs.rs

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 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(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 examples/evolve_nqueens
    • UniqueDiscreteGenotype<u8> with a 64x64 chess board setup
    • custom NQueensFitness fitness
• Knapsack problem: https://en.wikipedia.org/wiki/Knapsackproblem (10 items)
  • See examples/evolveknapsackdiscrete
    • DiscreteGenotype<(weight, value)> with a (0, 0) empty item to set on empty gene slots
    • custom KnapsackFitness(weight_limit) fitness, extra checking for duplicate items
  • See examples/evolveknapsackset
    • SetGenotype<(weight, value)> no need for empty items as the gene size is variable
    • custom KnapsackFitness(weight_limit) fitness
  • See examples/permutateknapsackset
    • SetGenotype<(weight, value)> permutable, because SetGenotype has only 1023 possible combinations, where DiscreteGenotype has 25937424601
    • custom KnapsackFitness(weight_limit) fitness
• Infinite Monkey theorem: https://en.wikipedia.org/wiki/Infinitemonkeytheorem
  • See examples/evolve_monkeys
    • DiscreteGenotype<u8> 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
  • See examples/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?
• Does Fitness need an associated trait for Genotype?, can this be made more light weight
• Use checked math or some big number type for chromosomepermutationssize as it overflows easily