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

use genetic_algorithm::evolve::prelude::*;

// the search space
let genotype = BinaryGenotype::builder() // boolean genes
    .with_gene_size(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 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(CrossoverAll(true)) // crossover all individual genes between 2 chromosomes for offspring
    .with_mutate(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/Eight_queens_puzzle.
  • See examples/evolve_nqueens
    • UniqueDiscreteGenotype<u8> with a 64x64 chess board setup
    • custom NQueensFitness fitness
• Knapsack problem: https://en.wikipedia.org/wiki/Knapsack_problem (10 items)
  • See examples/evolve_knapsack_discrete
    • 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/evolve_knapsack_set
    • SetGenotype<(weight, value)> no need for empty items as the gene size is variable
    • custom KnapsackFitness(weight_limit) fitness
  • See examples/permutate_knapsack_set
    • SetGenotype<(weight, value)> permutable, because SetGenotype has only 1023 possible combinations, where DiscreteGenotype has 25_937_424_601
    • custom KnapsackFitness(weight_limit) fitness
• Infinite Monkey theorem: https://en.wikipedia.org/wiki/Infinite_monkey_theorem
  • 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/evolve_binary_lru_cache_fitness
  • 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 chromosome_permutations_size as it overflows easily