#genetic #ga

genetic_algorithm

A genetic algorithm implementation

4 releases (2 breaking)

Uses new Rust 2021

new 0.3.1 May 16, 2022
0.2.0 May 13, 2022
0.1.1 May 11, 2022
0.1.0 May 10, 2022

#184 in Algorithms

Download history 53/week @ 2022-05-09

53 downloads per month

Custom license

120KB
2.5K SLoC

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)

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

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

// the search space
let genotype = BinaryGenotype::builder() // boolean alleles
    .with_genes_size(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 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(CrossoverUniform(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
    .call(&mut rng);
    .unwrap()

println!("{}", evolve);

Examples

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

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?

MAYBE

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

Dependencies

~1MB
~22K SLoC