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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
//! 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) (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
//! * [Allele](crate::genotype::Allele): alleles are the possible values of the genes
//! * Gene: a gene is a combination of position in the chromosome and value of the gene (allele)
//! * [Genes](crate::chromosome::Genes): storage trait of the genes for a chromosome, always `Vec<Allele>`
//! * [Genotype](crate::genotype): Knows how to generate, mutate and crossover chromosomes efficiently
//! * [Fitness](crate::fitness): knows how to determine the fitness of a chromosome
//!
//! All multithreading mechanisms are implemented using [rayon::iter] and [std::sync::mpsc].
//!
//! ## 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; // Genes = Vec<bool>
//! fn calculate_for_chromosome(
//! &mut self,
//! chromosome: &FitnessChromosome<Self>,
//! _genotype: &FitnessGenotype<Self>
//! ) -> Option<FitnessValue> {
//! Some(chromosome.genes.iter().filter(|&value| *value).count() as FitnessValue)
//! }
//! }
//!
//! // the search strategy
//! let evolve = Evolve::builder()
//! .with_genotype(genotype)
//! .with_select(SelectElite::new(0.5, 0.02)) // sort the chromosomes by fitness to determine crossover order. Strive to replace 50% of the population with offspring. Allow 2% through the non-generational best chromosomes gate before selection and replacement
//! .with_crossover(CrossoverUniform::new(0.7, 0.8)) // crossover all individual genes between 2 chromosomes for offspring with 70% parent selection (30% do not produce offspring) and 80% chance of crossover (20% of parents just clone)
//! .with_mutate(MutateSingleGene::new(0.2)) // mutate offspring for a single gene with a 20% probability per chromosome
//! .with_fitness(CountTrue) // count the number of true values in the chromosomes
//! .with_fitness_ordering(FitnessOrdering::Maximize) // optional, default is Maximize, aim towards the most true values
//! .with_target_population_size(100) // evolve with 100 chromosomes
//! .with_target_fitness_score(100) // goal is 100 times true in the best chromosome
//! .with_reporter(EvolveReporterSimple::new(100)) // optional builder step, report every 100 generations
//! .call()
//! .unwrap();
//!
//! println!("{}", evolve);
//!
//! // it's all about the best genes after all
//! let (best_genes, best_fitness_score) = evolve.best_genes_and_fitness_score().unwrap();
//! assert_eq!(best_genes, vec![true; 100]);
//! assert_eq!(best_fitness_score, 100);
//! ```
//!
//! ## Tests
//!
//! Use `.with_rng_seed_from_u64(0)` builder step to create deterministic tests results.
//!
//! ## 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<Item(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)
//! * `ListGenotype<char>` 100 monkeys randomly typing characters in a loop
//! * custom fitness using hamming distance
//! * 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)
//! * See [examples/permutate_scrabble](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/permutate_scrabble.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)
//! * Explore internal and external multithreading options
//! * See [examples/explore_multithreading](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/explore_multithreading.rs)
//! * Use superset StrategyBuilder for easier switching in implementation
//! * See [examples/explore_strategies](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/explore_strategies.rs)
//! * Use fitness LRU cache
//! * See [examples/evolve_binary_cache_fitness](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/evolve_binary_cache_fitness.rs)
//! * _Note: doesn't help performance much in this case... or any case, better fix your population diversity_
//! * Custom Reporting implementation
//! * See [examples/permutate_scrabble](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/permutate_scrabble.rs)
//! * Custom Mutate implementation
//! * See [examples/evolve_milp_custom_mutate](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/evolve_milp_custom_mutate.rs)
//!
//! ## Heterogeneous Genotype Support
//!
//! [MultiRangeGenotype](crate::genotype::MultiRangeGenotype) supports heterogeneous chromosomes that mix
//! different gene semantics (continuous values, discrete choices, booleans) within a single
//! numeric type `T`.
//!
//! ## Performance considerations
//!
//! For the [Evolve](strategy::evolve::Evolve) strategy:
//!
//! * [Reporting](strategy::reporter): start with [EvolveReporterSimple](strategy::evolve::EvolveReporterSimple) for basic understanding of:
//! * fitness v. framework overhead
//! * staleness and population characteristics (cardinality etc.)
//! * [Select](select): no considerations. All selects are basically some form of in-place sorting
//! of some kind based on chromosome metadata. This is relatively fast compared to the rest of the
//! operations.
//! * [Crossover](crossover): the workhorse of internal parts. Crossover touches most genes each
//! generation, calculates genes hashes and clones up to the whole population to produce offspring
//! (depending on selection-rate).
//! * [Mutate](mutate): no considerations. It touches genes like crossover does, but should
//! be used sparingly anyway; with low gene counts (<10%) and low probability (5-20%)
//! * [Fitness](fitness): can be anything, but usually very dominant (>80% total time). This fully
//! depends on the user domain. Parallelize it using `with_par_fitness()` in the Builder. But
//! beware that parallelization has it's own overhead and is not always faster.
//!
//! So framework overhead is mostly Crossover. Practical overhead is mostly Fitness.
//!
//! Regarding the optionality of genes hashing and chromosomes recycling: For large
//! chromosomes, disabling chromosome recycling and enabling genes hashing leads to
//! a 3x factor in framework overhead. For small chromosomes, neither feature has
//! overhead effects. But do keep in mind that for large chromosomes the Fitness
//! calculation will be even more dominant with regards to the framework overhead
//! as it already is.
//! See [examples/evolve_large_genotype](https://github.com/basvanwesting/genetic-algorithm/blob/main/examples/evolve_large_genotype.rs)
//!
//! Default configuration for correctness AND performance
//! * .with_genes_hashing(true) // Required for proper GA dynamics
//! * .with_chromosome_recycling(true) // Still worth it for large chromosomes, maybe disable for easier custom implementations
//!