Crate 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)

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

• 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 example/permutate_binary

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.

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.

evolve

A solution strategy for finding the best chromosomes.

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%.

permutate

A solution strategy for finding the best chromosomes in case of small problem spaces.

population

The population is a container for Chromosomes