Crate genetic_algorithm

source ·
Expand description

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

Quick Usage

use genetic_algorithm::strategy::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_target_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::new(true)) // crossover all individual genes between 2 chromosomes for offspring
    .with_mutate(MutateOnce::new(0.2))    // mutate a single gene with a 20% probability per chromosome
    .with_compete(CompeteElite::new())    // sort the chromosomes by fitness to determine crossover order
    .with_extension(ExtensionNoop::new()) // extension step, disabled
    .call(&mut rng)
    .unwrap();

println!("{}", evolve);

Examples

Modules

  • chromosome
    The chromosome is a container for the genes and caches a fitness score
  • compete
    The competition phase, where chromosomes are lined up for pairing in the crossover phase. Excess chromosomes, beyond the target_population_size, are dropped.
  • crossover
    The crossover phase where every two parent chromosomes create two children chromosomes. The competition phase determines the order of the parent pairing (overall with fitter first). If you choose to keep the parents, the parents will compete with their own children and the population is temporarily overbooked and half of it will be discarded in the competition phase.
  • extension
    When approacking a (local) optimum in the fitness score, the variation in the population goes down dramatically. This reduces the efficiency, but also has the risk of local optimum lock-in. To increase the variation in the population, an extension mechanisms can optionally be used
  • fitness
    The search goal to optimize towards (maximize or minimize).
  • genotype
    The search space for the algorithm.
  • meta
    One cool thing to do with genotypes is to make a meta-genotype of all the Crossover/Mutate/Compete strategies and other Evolve parameters. This could be used to optimize the parameters of some other genetic algorithm. Yes, a simple nested for loop would also work, but where is the fun in that? But I wasn’t able to find an elegant approach to creating such a heterogene setup. It was tried with Trait objects, Any and Enums, but all didn’t work well:
  • mutate
    The mutation strategy, very important for avoiding local optimum lock-in. But don’t overdo it, as it degenerates the population too much if overused. Use a mutation probability generally between 5% and 20%.
  • population
    The population is a container for Chromosomes
  • strategy
    solution strategies for finding the best chromosomes.