genetic_algorithm/strategy.rs
1//! solution strategies for finding the best chromosomes.
2//!
3//! There are 4 strategies:
4//! * [Evolve, Standard](self::evolve::Evolve)
5//! * [Permutate, Standard](self::permutate::Permutate)
6//! * [HillClimb, Stochastic](self::hill_climb::HillClimb)
7//! * [HillClimb, SteepestAscent](self::hill_climb::HillClimb)
8//!
9//! See strategies for details. Normally, you build a specific strategy and call directly from the
10//! specific builder. But there is an option for building the superset [StrategyBuilder] and calling
11//! from there. You call from the builder, as repeatedly options clone the builder first. The
12//! execution is switched based on the provided `with_variant()`. The call options are:
13//! * `call()` simply run once
14//! * `call_repeatedly(usize)`, call repeatedly and take the best (or short-circuit on target fitness score)
15//! * fallback to `call()` once for Permutate
16//! * `call_par_repeatedly(usize)`, as above, but high level parallel execution
17//! * fallback to `call()` once for Permutate, but force `with_par_fitness(true)`
18//! * `call_speciated(usize)`, call repeatedly and then run one final round with the best chromosomes from the previous rounds as seeds
19//! * fallback to `call()` once for Permutate
20//! * fallback to `call_repeatedly(usize)` for HillClimb
21//! * `call_par_speciated(usize)`, as above, but high level parallel execution
22//! * fallback to `call()` once for Permutate, but force `with_par_fitness(true)`
23//! * fallback to `call_par_repeatedly(usize)` for HillClimb
24//!
25//! *Note: Only Genotypes which implement all strategies are eligable for the superset builder.*
26//! *RangeGenotype and other floating point range based genotypes currently do not support Permutation*
27//!
28//! Example:
29//! ```
30//! use genetic_algorithm::strategy::prelude::*;
31//! use genetic_algorithm::fitness::placeholders::CountTrue;
32//!
33//! // the search space
34//! let genotype = BinaryGenotype::builder()
35//! .with_genes_size(10)
36//! .with_genes_hashing(true) // store genes_hash on chromosome (required for fitness_cache and deduplication extension, optional for better population cardinality estimation)
37//! .build()
38//! .unwrap();
39//!
40//! // the search strategy (superset), steps marked (E)volve, (H)illClimb and (P)ermutate
41//! let builder = StrategyBuilder::new()
42//! .with_genotype(genotype) // (E,H,P) the genotype
43//! .with_select(SelectElite::new(0.5, 0.02)) // (E) 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
44//! .with_extension(ExtensionMassExtinction::new(10, 0.1, 0.02)) // (E) optional builder step, simulate cambrian explosion by mass extinction, when population cardinality drops to 10 after the selection, trim to 10% of population
45//! .with_crossover(CrossoverUniform::new(0.7, 0.8)) // (E) 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)
46//! .with_mutate(MutateSingleGene::new(0.2)) // (E) mutate offspring for a single gene with a 20% probability per chromosome
47//! .with_fitness(CountTrue) // (E,H,P) count the number of true values in the chromosomes
48//! .with_fitness_ordering(FitnessOrdering::Minimize) // (E,H,P) aim for the least true values
49//! .with_fitness_cache(1000) // (E) enable caching of fitness values, only works when genes_hash is stored in chromosome.
50//! .with_par_fitness(true) // (E,H,P) optional, defaults to false, use parallel fitness calculation
51//! .with_target_population_size(100) // (E) evolve with 100 chromosomes
52//! .with_target_fitness_score(0) // (E,H) ending condition if 0 times true in the best chromosome
53//! .with_valid_fitness_score(1) // (E,H) block ending conditions until at most a 1 times true in the best chromosome
54//! .with_max_stale_generations(100) // (E,H) stop searching if there is no improvement in fitness score for 100 generations
55//! .with_max_generations(1_000_000) // (E,H) optional, stop searching after 1M generations
56//! .with_max_chromosome_age(10) // (E) kill chromosomes after 10 generations
57//! .with_reporter(StrategyReporterSimple::new(usize::MAX)) // (E,H,P) optional builder step, report on new best chromosomes only
58//! .with_replace_on_equal_fitness(true) // (E,H,P) optional, defaults to false, maybe useful to avoid repeatedly seeding with the same best chromosomes after mass extinction events
59//! .with_rng_seed_from_u64(0); // (E,H) for testing with deterministic results
60//!
61//! // the search strategy (specified)
62//! let (strategy, _) = builder
63//! .with_variant(StrategyVariant::Permutate(PermutateVariant::Standard))
64//! // .with_variant(StrategyVariant::Evolve(EvolveVariant::Standard))build str
65//! // .with_variant(StrategyVariant::HillClimb(HillClimbVariant::Stochastic))
66//! // .with_variant(StrategyVariant::HillClimb(HillClimbVariant::SteepAscent))
67//! .call_speciated(3)
68//! .unwrap();
69//!
70//! // it's all about the best genes after all
71//! let (best_genes, best_fitness_score) = strategy.best_genes_and_fitness_score().unwrap();
72//! assert_eq!(best_genes, vec![false; 10]);
73//! assert_eq!(best_fitness_score, 0);
74//! ````
75pub mod builder;
76pub mod evolve;
77pub mod hill_climb;
78pub mod permutate;
79pub mod prelude;
80pub mod reporter;
81
82use self::evolve::EvolveVariant;
83use self::hill_climb::HillClimbVariant;
84use self::permutate::PermutateVariant;
85use crate::chromosome::Chromosome;
86use crate::extension::ExtensionEvent;
87use crate::fitness::{FitnessCache, FitnessOrdering, FitnessValue};
88use crate::genotype::Genotype;
89use crate::mutate::MutateEvent;
90use crate::population::Population;
91use std::collections::HashMap;
92use std::fmt::Display;
93use std::time::Duration;
94
95pub use self::builder::{
96 Builder as StrategyBuilder, TryFromBuilderError as TryFromStrategyBuilderError,
97};
98
99pub use self::reporter::Duration as StrategyReporterDuration;
100pub use self::reporter::Noop as StrategyReporterNoop;
101pub use self::reporter::Simple as StrategyReporterSimple;
102
103#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)]
104pub enum StrategyAction {
105 SetupAndCleanup,
106 Extension,
107 Select,
108 Crossover,
109 Mutate,
110 Fitness,
111 UpdateBestChromosome,
112 Other,
113}
114pub const STRATEGY_ACTIONS: [StrategyAction; 8] = [
115 StrategyAction::SetupAndCleanup,
116 StrategyAction::Extension,
117 StrategyAction::Select,
118 StrategyAction::Crossover,
119 StrategyAction::Mutate,
120 StrategyAction::Fitness,
121 StrategyAction::UpdateBestChromosome,
122 StrategyAction::Other,
123];
124
125#[derive(Copy, Clone, Debug)]
126pub enum StrategyVariant {
127 Evolve(EvolveVariant),
128 HillClimb(HillClimbVariant),
129 Permutate(PermutateVariant),
130}
131impl Display for StrategyVariant {
132 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
133 match self {
134 StrategyVariant::Evolve(EvolveVariant::Standard) => write!(f, "evolve"),
135 StrategyVariant::HillClimb(HillClimbVariant::Stochastic) => {
136 write!(f, "hill_climb/stochastic")
137 }
138 StrategyVariant::HillClimb(HillClimbVariant::SteepestAscent) => {
139 write!(f, "hill_climb/steepest_ascent")
140 }
141 StrategyVariant::Permutate(PermutateVariant::Standard) => write!(f, "permutate"),
142 }
143 }
144}
145
146pub trait Strategy<G: Genotype> {
147 fn call(&mut self);
148 fn best_generation(&self) -> usize;
149 fn best_fitness_score(&self) -> Option<FitnessValue>;
150 fn best_genes(&self) -> Option<G::Genes>;
151 fn best_genes_and_fitness_score(&self) -> Option<(G::Genes, FitnessValue)> {
152 if let Some(fitness_value) = self.best_fitness_score() {
153 self.best_genes().map(|genes| (genes, fitness_value))
154 } else {
155 None
156 }
157 }
158 /// strategy can be boxed, need a way to get to the reporter
159 fn flush_reporter(&mut self, _output: &mut Vec<u8>);
160}
161
162pub trait StrategyConfig: Display {
163 fn variant(&self) -> StrategyVariant;
164 fn fitness_ordering(&self) -> FitnessOrdering;
165 // stored on config instead of state as it is a cache external to the strategy
166 fn fitness_cache(&self) -> Option<&FitnessCache> {
167 None
168 }
169 fn par_fitness(&self) -> bool;
170 fn replace_on_equal_fitness(&self) -> bool;
171}
172
173/// Stores the state of the strategy.
174/// The expected general fields are:
175/// * current_iteration: `usize`
176/// * current_generation: `usize`
177/// * best_generation: `usize`
178/// * best_chromosome: `G::Chromosome`
179/// * chromosome: `G::Chromosome`
180/// * populatoin: `Population<G::Chromosome>` // may be empty
181pub trait StrategyState<G: Genotype>: Display {
182 fn chromosome_as_ref(&self) -> &Option<G::Chromosome>;
183 fn chromosome_as_mut(&mut self) -> &mut Option<G::Chromosome>;
184 fn population_as_ref(&self) -> &Population<G::Chromosome>;
185 fn population_as_mut(&mut self) -> &mut Population<G::Chromosome>;
186 fn best_fitness_score(&self) -> Option<FitnessValue>;
187 fn best_generation(&self) -> usize;
188 fn current_generation(&self) -> usize;
189 fn current_iteration(&self) -> usize;
190 fn stale_generations(&self) -> usize;
191 fn current_scale_index(&self) -> Option<usize>;
192 fn population_cardinality(&self) -> Option<usize>;
193 fn durations(&self) -> &HashMap<StrategyAction, Duration>;
194 fn add_duration(&mut self, action: StrategyAction, duration: Duration);
195 fn total_duration(&self) -> Duration;
196 fn close_duration(&mut self, total_duration: Duration) {
197 if let Some(other_duration) = total_duration.checked_sub(self.total_duration()) {
198 self.add_duration(StrategyAction::Other, other_duration);
199 }
200 }
201 fn fitness_duration_rate(&self) -> f32 {
202 let fitness_duration = self
203 .durations()
204 .get(&StrategyAction::Fitness)
205 .copied()
206 .unwrap_or_else(Duration::default);
207 fitness_duration.as_secs_f32() / self.total_duration().as_secs_f32()
208 }
209
210 fn increment_stale_generations(&mut self);
211 fn reset_stale_generations(&mut self);
212 // return tuple (new_best_chomesome, improved_fitness). This way a sideways move in
213 // best_chromosome (with equal fitness, which doesn't update the best_generation) can be
214 // distinguished for reporting purposes
215 // TODO: because the StrategyReporter trait is not used, all StrategyState are implementing a
216 // specialized version of this function for additional reporting
217 fn is_better_chromosome(
218 &self,
219 contending_chromosome: &G::Chromosome,
220 fitness_ordering: &FitnessOrdering,
221 replace_on_equal_fitness: bool,
222 ) -> (bool, bool) {
223 match (
224 self.best_fitness_score(),
225 contending_chromosome.fitness_score(),
226 ) {
227 (None, None) => (false, false),
228 (Some(_), None) => (false, false),
229 (None, Some(_)) => (true, true),
230 (Some(current_fitness_score), Some(contending_fitness_score)) => match fitness_ordering
231 {
232 FitnessOrdering::Maximize => {
233 if contending_fitness_score > current_fitness_score {
234 (true, true)
235 } else if replace_on_equal_fitness
236 && contending_fitness_score == current_fitness_score
237 {
238 (true, false)
239 } else {
240 (false, false)
241 }
242 }
243 FitnessOrdering::Minimize => {
244 if contending_fitness_score < current_fitness_score {
245 (true, true)
246 } else if replace_on_equal_fitness
247 && contending_fitness_score == current_fitness_score
248 {
249 (true, false)
250 } else {
251 (false, false)
252 }
253 }
254 },
255 }
256 }
257}
258
259/// Reporter with event hooks for all Strategies.
260/// You are encouraged to roll your own implementation, depending on your needs.
261///
262/// Event hooks in lifecycle:
263/// * `on_enter` (before setup)
264/// * `on_start` (of run loop)
265/// * *in run loop:*
266/// * `on_new_generation`
267/// * `on_new_best_chromosome`
268/// * `on_new_best_chromosome_equal_fitness`
269/// * `on_extension_event`
270/// * `on_mutate_event`
271/// * `on_finish` (of run loop)
272/// * `on_exit` (after cleanup)
273///
274/// It has an associated type Genotype, just like Fitness, so you can implement reporting with
275/// access to your domain's specific Genotype and Chromosome etc..
276///
277/// For reference, take a look at the provided strategy independent
278/// [StrategyReporterSimple](self::reporter::Simple) implementation, or strategy specific
279/// [EvolveReporterSimple](self::evolve::EvolveReporterSimple),
280/// [HillClimbReporterSimple](self::hill_climb::HillClimbReporterSimple) and
281/// [PermutateReporterSimple](self::permutate::PermutateReporterSimple) implementations.
282///
283/// # Example:
284/// ```rust
285/// use genetic_algorithm::strategy::evolve::prelude::*;
286///
287/// #[derive(Clone)]
288/// pub struct CustomReporter { pub period: usize }
289/// impl StrategyReporter for CustomReporter {
290/// type Genotype = BinaryGenotype;
291///
292/// fn on_new_generation<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
293/// &mut self,
294/// _genotype: &Self::Genotype,
295/// state: &S,
296/// _config: &C,
297/// ) {
298/// if state.current_generation() % self.period == 0 {
299/// println!(
300/// "periodic - current_generation: {}, stale_generations: {}, best_generation: {}, scale_index: {:?}",
301/// state.current_generation(),
302/// state.stale_generations(),
303/// state.best_generation(),
304/// state.current_scale_index(),
305/// );
306/// }
307/// }
308///
309/// fn on_new_best_chromosome<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
310/// &mut self,
311/// _genotype: &Self::Genotype,
312/// state: &S,
313/// _config: &C,
314/// ) {
315/// println!(
316/// "new best - generation: {}, fitness_score: {:?}, scale_index: {:?}",
317/// state.current_generation(),
318/// state.best_fitness_score(),
319/// state.current_scale_index(),
320/// );
321/// }
322///
323/// fn on_exit<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
324/// &mut self,
325/// _genotype: &Self::Genotype,
326/// state: &S,
327/// _config: &C,
328/// ) {
329/// println!("exit - iteration: {}", state.current_iteration());
330/// STRATEGY_ACTIONS.iter().for_each(|action| {
331/// if let Some(duration) = state.durations().get(action) {
332/// println!(" {:?}: {:.3?}", action, duration);
333/// }
334/// });
335/// println!(
336/// " Total: {:.3?} ({:.0}% fitness)",
337/// &state.total_duration(),
338/// state.fitness_duration_rate() * 100.0
339/// );
340/// }
341/// }
342/// ```
343pub trait StrategyReporter: Clone + Send + Sync {
344 type Genotype: Genotype;
345
346 fn flush(&mut self, _output: &mut Vec<u8>) {}
347 fn on_enter<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
348 &mut self,
349 _genotype: &Self::Genotype,
350 _state: &S,
351 _config: &C,
352 ) {
353 }
354 fn on_exit<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
355 &mut self,
356 _genotype: &Self::Genotype,
357 _state: &S,
358 _config: &C,
359 ) {
360 }
361 fn on_start<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
362 &mut self,
363 _genotype: &Self::Genotype,
364 _state: &S,
365 _config: &C,
366 ) {
367 }
368 fn on_finish<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
369 &mut self,
370 _genotype: &Self::Genotype,
371 _state: &S,
372 _config: &C,
373 ) {
374 }
375 fn on_new_generation<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
376 &mut self,
377 _genotype: &Self::Genotype,
378 _state: &S,
379 _config: &C,
380 ) {
381 }
382 fn on_new_best_chromosome<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
383 &mut self,
384 _genotype: &Self::Genotype,
385 _state: &S,
386 _config: &C,
387 ) {
388 }
389 fn on_new_best_chromosome_equal_fitness<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
390 &mut self,
391 _genotype: &Self::Genotype,
392 _state: &S,
393 _config: &C,
394 ) {
395 }
396 fn on_extension_event<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
397 &mut self,
398 _event: ExtensionEvent,
399 _genotype: &Self::Genotype,
400 _state: &S,
401 _config: &C,
402 ) {
403 }
404 fn on_mutate_event<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
405 &mut self,
406 _event: MutateEvent,
407 _genotype: &Self::Genotype,
408 _state: &S,
409 _config: &C,
410 ) {
411 }
412}