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, 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_extension(ExtensionMassExtinction::new(10, 0.1)) // (E) optional builder step, simulate cambrian explosion by mass extinction, when fitness score cardinality drops to 10, trim to 10% of population
44//! .with_select(SelectElite::new(0.9)) // (E) sort the chromosomes by fitness to determine crossover order and select 90% of the population for crossover (drop 10% of population)
45//! .with_crossover(CrossoverUniform::new()) // (E) crossover all individual genes between 2 chromosomes for offspring (and restore back to 100% of target population size by keeping the best parents alive)
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_chromosome_age(10) // (E) kill chromosomes after 10 generations
56//! .with_reporter(StrategyReporterSimple::new(usize::MAX)) // (E,H,P) optional builder step, report on new best chromsomes only
57//! .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
58//! .with_rng_seed_from_u64(0); // (E,H) for testing with deterministic results
59//!
60//! // the search strategy (specified)
61//! let (strategy, _) = builder
62//! .with_variant(StrategyVariant::Permutate(PermutateVariant::Standard))
63//! // .with_variant(StrategyVariant::Evolve(EvolveVariant::Standard))build str
64//! // .with_variant(StrategyVariant::HillClimb(HillClimbVariant::Stochastic))
65//! // .with_variant(StrategyVariant::HillClimb(HillClimbVariant::SteepAscent))
66//! .call_speciated(3)
67//! .unwrap();
68//!
69//! // it's all about the best genes after all
70//! let (best_genes, best_fitness_score) = strategy.best_genes_and_fitness_score().unwrap();
71//! assert_eq!(best_genes, vec![false; 10]);
72//! assert_eq!(best_fitness_score, 0);
73//! ````
74pub mod builder;
75pub mod evolve;
76pub mod hill_climb;
77pub mod permutate;
78pub mod prelude;
79pub mod reporter;
80
81use self::evolve::EvolveVariant;
82use self::hill_climb::HillClimbVariant;
83use self::permutate::PermutateVariant;
84use crate::chromosome::Chromosome;
85use crate::extension::ExtensionEvent;
86use crate::fitness::{FitnessCache, FitnessOrdering, FitnessValue};
87use crate::genotype::Genotype;
88use crate::mutate::MutateEvent;
89use crate::population::Population;
90use std::collections::HashMap;
91use std::fmt::Display;
92use std::time::Duration;
93
94pub use self::builder::{
95 Builder as StrategyBuilder, TryFromBuilderError as TryFromStrategyBuilderError,
96};
97
98pub use self::reporter::Duration as StrategyReporterDuration;
99pub use self::reporter::Noop as StrategyReporterNoop;
100pub use self::reporter::Simple as StrategyReporterSimple;
101
102#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)]
103pub enum StrategyAction {
104 SetupAndCleanup,
105 Extension,
106 Select,
107 Crossover,
108 Mutate,
109 Fitness,
110 UpdateBestChromosome,
111 Other,
112}
113pub const STRATEGY_ACTIONS: [StrategyAction; 8] = [
114 StrategyAction::SetupAndCleanup,
115 StrategyAction::Extension,
116 StrategyAction::Select,
117 StrategyAction::Crossover,
118 StrategyAction::Mutate,
119 StrategyAction::Fitness,
120 StrategyAction::UpdateBestChromosome,
121 StrategyAction::Other,
122];
123
124#[derive(Copy, Clone, Debug)]
125pub enum StrategyVariant {
126 Evolve(EvolveVariant),
127 HillClimb(HillClimbVariant),
128 Permutate(PermutateVariant),
129}
130impl Display for StrategyVariant {
131 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
132 match self {
133 StrategyVariant::Evolve(EvolveVariant::Standard) => write!(f, "evolve"),
134 StrategyVariant::HillClimb(HillClimbVariant::Stochastic) => {
135 write!(f, "hill_climb/stochastic")
136 }
137 StrategyVariant::HillClimb(HillClimbVariant::SteepestAscent) => {
138 write!(f, "hill_climb/steepest_ascent")
139 }
140 StrategyVariant::Permutate(PermutateVariant::Standard) => write!(f, "permutate"),
141 }
142 }
143}
144
145pub trait Strategy<G: Genotype> {
146 fn call(&mut self);
147 fn best_generation(&self) -> usize;
148 fn best_fitness_score(&self) -> Option<FitnessValue>;
149 fn best_genes(&self) -> Option<G::Genes>;
150 fn best_genes_and_fitness_score(&self) -> Option<(G::Genes, FitnessValue)> {
151 if let Some(fitness_value) = self.best_fitness_score() {
152 self.best_genes().map(|genes| (genes, fitness_value))
153 } else {
154 None
155 }
156 }
157 /// strategy can be boxed, need a way to get to the reporter
158 fn flush_reporter(&mut self, _output: &mut Vec<u8>);
159}
160
161pub trait StrategyConfig: Display {
162 fn variant(&self) -> StrategyVariant;
163 fn fitness_ordering(&self) -> FitnessOrdering;
164 // stored on config instead of state as it is a cache external to the strategy
165 fn fitness_cache(&self) -> Option<&FitnessCache> {
166 None
167 }
168 fn par_fitness(&self) -> bool;
169 fn replace_on_equal_fitness(&self) -> bool;
170}
171
172/// Stores the state of the strategy.
173/// The expected general fields are:
174/// * current_iteration: `usize`
175/// * current_generation: `usize`
176/// * best_generation: `usize`
177/// * best_chromosome: `G::Chromosome`
178/// * chromosome: `G::Chromosome`
179/// * populatoin: `Population<G::Chromosome>` // may be empty
180pub trait StrategyState<G: Genotype>: Display {
181 fn chromosome_as_ref(&self) -> &Option<G::Chromosome>;
182 fn chromosome_as_mut(&mut self) -> &mut Option<G::Chromosome>;
183 fn population_as_ref(&self) -> &Population<G::Chromosome>;
184 fn population_as_mut(&mut self) -> &mut Population<G::Chromosome>;
185 fn best_fitness_score(&self) -> Option<FitnessValue>;
186 fn best_generation(&self) -> usize;
187 fn current_generation(&self) -> usize;
188 fn current_iteration(&self) -> usize;
189 fn stale_generations(&self) -> usize;
190 fn current_scale_index(&self) -> Option<usize>;
191 fn population_cardinality(&self) -> Option<usize>;
192 fn durations(&self) -> &HashMap<StrategyAction, Duration>;
193 fn add_duration(&mut self, action: StrategyAction, duration: Duration);
194 fn total_duration(&self) -> Duration;
195 fn close_duration(&mut self, total_duration: Duration) {
196 if let Some(other_duration) = total_duration.checked_sub(self.total_duration()) {
197 self.add_duration(StrategyAction::Other, other_duration);
198 }
199 }
200 fn fitness_duration_rate(&self) -> f32 {
201 let fitness_duration = self
202 .durations()
203 .get(&StrategyAction::Fitness)
204 .copied()
205 .unwrap_or_else(Duration::default);
206 fitness_duration.as_secs_f32() / self.total_duration().as_secs_f32()
207 }
208
209 fn increment_stale_generations(&mut self);
210 fn reset_stale_generations(&mut self);
211 // return tuple (new_best_chomesome, improved_fitness). This way a sideways move in
212 // best_chromosome (with equal fitness, which doesn't update the best_generation) can be
213 // distinguished for reporting purposes
214 // TODO: because the StrategyReporter trait is not used, all StrategyState are implementing a
215 // specialized version of this function for additional reporting
216 fn is_better_chromosome(
217 &self,
218 contending_chromosome: &G::Chromosome,
219 fitness_ordering: &FitnessOrdering,
220 replace_on_equal_fitness: bool,
221 ) -> (bool, bool) {
222 match (
223 self.best_fitness_score(),
224 contending_chromosome.fitness_score(),
225 ) {
226 (None, None) => (false, false),
227 (Some(_), None) => (false, false),
228 (None, Some(_)) => (true, true),
229 (Some(current_fitness_score), Some(contending_fitness_score)) => match fitness_ordering
230 {
231 FitnessOrdering::Maximize => {
232 if contending_fitness_score > current_fitness_score {
233 (true, true)
234 } else if replace_on_equal_fitness
235 && contending_fitness_score == current_fitness_score
236 {
237 (true, false)
238 } else {
239 (false, false)
240 }
241 }
242 FitnessOrdering::Minimize => {
243 if contending_fitness_score < current_fitness_score {
244 (true, true)
245 } else if replace_on_equal_fitness
246 && contending_fitness_score == current_fitness_score
247 {
248 (true, false)
249 } else {
250 (false, false)
251 }
252 }
253 },
254 }
255 }
256}
257
258/// Reporter with event hooks for all Strategies.
259/// You are encouraged to roll your own implementation, depending on your needs.
260///
261/// Event hooks in lifecycle:
262/// * `on_enter` (before setup)
263/// * `on_start` (of run loop)
264/// * *in run loop:*
265/// * `on_new_generation`
266/// * `on_new_best_chromosome`
267/// * `on_new_best_chromosome_equal_fitness`
268/// * `on_extension_event`
269/// * `on_mutate_event`
270/// * `on_finish` (of run loop)
271/// * `on_exit` (after cleanup)
272///
273/// It has an associated type Genotype, just like Fitness, so you can implement reporting with
274/// access to your domain's specific Genotype and Chromosome etc..
275///
276/// For reference, take a look at the provided strategy independent
277/// [StrategyReporterSimple](self::reporter::Simple) implementation, or strategy specific
278/// [EvolveReporterSimple](self::evolve::EvolveReporterSimple),
279/// [HillClimbReporterSimple](self::hill_climb::HillClimbReporterSimple) and
280/// [PermutateReporterSimple](self::permutate::PermutateReporterSimple) implementations.
281///
282/// # Example:
283/// ```rust
284/// use genetic_algorithm::strategy::evolve::prelude::*;
285///
286/// #[derive(Clone)]
287/// pub struct CustomReporter { pub period: usize }
288/// impl StrategyReporter for CustomReporter {
289/// type Genotype = BinaryGenotype;
290///
291/// fn on_new_generation<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
292/// &mut self,
293/// _genotype: &Self::Genotype,
294/// state: &S,
295/// _config: &C,
296/// ) {
297/// if state.current_generation() % self.period == 0 {
298/// println!(
299/// "periodic - current_generation: {}, stale_generations: {}, best_generation: {}, scale_index: {:?}",
300/// state.current_generation(),
301/// state.stale_generations(),
302/// state.best_generation(),
303/// state.current_scale_index(),
304/// );
305/// }
306/// }
307///
308/// fn on_new_best_chromosome<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
309/// &mut self,
310/// _genotype: &Self::Genotype,
311/// state: &S,
312/// _config: &C,
313/// ) {
314/// println!(
315/// "new best - generation: {}, fitness_score: {:?}, scale_index: {:?}",
316/// state.current_generation(),
317/// state.best_fitness_score(),
318/// state.current_scale_index(),
319/// );
320/// }
321///
322/// fn on_exit<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
323/// &mut self,
324/// _genotype: &Self::Genotype,
325/// state: &S,
326/// _config: &C,
327/// ) {
328/// println!("exit - iteration: {}", state.current_iteration());
329/// STRATEGY_ACTIONS.iter().for_each(|action| {
330/// if let Some(duration) = state.durations().get(action) {
331/// println!(" {:?}: {:.3?}", action, duration);
332/// }
333/// });
334/// println!(
335/// " Total: {:.3?} ({:.0}% fitness)",
336/// &state.total_duration(),
337/// state.fitness_duration_rate() * 100.0
338/// );
339/// }
340/// }
341/// ```
342pub trait StrategyReporter: Clone + Send + Sync {
343 type Genotype: Genotype;
344
345 fn flush(&mut self, _output: &mut Vec<u8>) {}
346 fn on_enter<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
347 &mut self,
348 _genotype: &Self::Genotype,
349 _state: &S,
350 _config: &C,
351 ) {
352 }
353 fn on_exit<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
354 &mut self,
355 _genotype: &Self::Genotype,
356 _state: &S,
357 _config: &C,
358 ) {
359 }
360 fn on_start<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
361 &mut self,
362 _genotype: &Self::Genotype,
363 _state: &S,
364 _config: &C,
365 ) {
366 }
367 fn on_finish<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
368 &mut self,
369 _genotype: &Self::Genotype,
370 _state: &S,
371 _config: &C,
372 ) {
373 }
374 fn on_new_generation<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
375 &mut self,
376 _genotype: &Self::Genotype,
377 _state: &S,
378 _config: &C,
379 ) {
380 }
381 fn on_new_best_chromosome<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
382 &mut self,
383 _genotype: &Self::Genotype,
384 _state: &S,
385 _config: &C,
386 ) {
387 }
388 fn on_new_best_chromosome_equal_fitness<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
389 &mut self,
390 _genotype: &Self::Genotype,
391 _state: &S,
392 _config: &C,
393 ) {
394 }
395 fn on_extension_event<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
396 &mut self,
397 _event: ExtensionEvent,
398 _genotype: &Self::Genotype,
399 _state: &S,
400 _config: &C,
401 ) {
402 }
403 fn on_mutate_event<S: StrategyState<Self::Genotype>, C: StrategyConfig>(
404 &mut self,
405 _event: MutateEvent,
406 _genotype: &Self::Genotype,
407 _state: &S,
408 _config: &C,
409 ) {
410 }
411}