1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

//! A genetic algorithm implementation for Rust.
//! Inspired by the book [Genetic Algorithms in Elixir](https://pragprog.com/titles/smgaelixir/genetic-algorithms-in-elixir/)
//!
//! There are three main elements to this approach:
//! * The [Genotype](crate::genotype) (the search space)
//! * The [Fitness](crate::fitness) function (the search goal)
//! * The [Strategy](crate::strategy::Strategy) (the search strategy)
//!     * [Evolve](crate::strategy::evolve::Evolve) (evolution strategy)
//!     * [Permutate](crate::strategy::permutate::Permutate) (for small search spaces, with a 100% guarantee)
//!     * [HillClimb](crate::strategy::hill_climb::HillClimb) (when search space is convex with little local optima or when crossover is impossible/inefficient)
//!
//! Terminology:
//! * [Population](crate::population): a population has `population_size` number of individuals (called chromosomes).
//! * [Chromosome](crate::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](crate::genotype): holds the `genes_size` and alleles and knows how to generate and mutate chromosomes efficiently
//! * [Fitness](crate::fitness): knows how to determine the fitness of a chromosome
//!
//! ## Quick Usage
//!
//! ```rust
//! 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_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
//!
//! * N-Queens puzzle <https://en.wikipedia.org/wiki/Eight_queens_puzzle>
//!     * See [examples/evolve_nqueens](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/evolve_nqueens.rs)
//!     * See [examples/hill_climb_nqueens](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/hill_climb_nqueens.rs)
//!     * `UniqueGenotype<u8>` with a 64x64 chess board setup
//!     * custom `NQueensFitness` fitness
//! * Knapsack problem: <https://en.wikipedia.org/wiki/Knapsack_problem>
//!     * See [examples/evolve_knapsack](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/evolve_knapsack.rs)
//!     * See [examples/permutate_knapsack](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/permutate_knapsack.rs)
//!     * `BinaryGenotype<(weight, value)>` each gene encodes presence in the knapsack
//!     * custom `KnapsackFitness(&items, weight_limit)` fitness
//! * Infinite Monkey theorem: <https://en.wikipedia.org/wiki/Infinite_monkey_theorem>
//!     * See [examples/evolve_monkeys](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/evolve_monkeys.rs)
//!     * `DiscreteGenotype<char>` 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](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/evolve_binary_lru_cache_fitness.rs)
//!     * _Note: doesn't help performance much in this case..._
//! * Permutation strategy instead of Evolve strategy for small search spaces, with a 100% guarantee
//!     * See [examples/permutate_knapsack](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/permutate_knapsack.rs)
//! * HillClimb strategy instead of Evolve strategy, when crossover is impossible or inefficient
//!     * See [examples/hill_climb_nqueens](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/hill_climb_nqueens.rs)
//!     * See [examples/hill_climb_table_seating](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/hill_climb_table_seating.rs)
//!

pub mod chromosome;
pub mod compete;
pub mod crossover;
pub mod fitness;
pub mod genotype;
pub mod meta;
pub mod mutate;
pub mod population;
pub mod strategy;