genetic_algorithm 0.27.2

//! A solution strategy for finding the best chromosome using evolution
mod builder;
pub mod prelude;
mod reporter;

pub use self::builder::{
    Builder as EvolveBuilder, TryFromBuilderError as TryFromEvolveBuilderError,
};

use super::{
    Strategy, StrategyAction, StrategyConfig, StrategyReporter, StrategyReporterNoop,
    StrategyState, StrategyVariant,
};
use crate::chromosome::{Chromosome, Genes};
use crate::crossover::Crossover;
use crate::extension::{Extension, ExtensionNoop};
use crate::fitness::{Fitness, FitnessCache, FitnessOrdering, FitnessValue};
use crate::genotype::EvolveGenotype;
use crate::mutate::Mutate;
use crate::population::Population;
use crate::select::Select;
use rand::rngs::SmallRng;
use std::cell::RefCell;
use std::collections::HashMap;
use std::fmt;
use std::sync::atomic::{AtomicBool, Ordering};
use std::sync::Arc;
use std::time::{Duration, Instant};
use thread_local::ThreadLocal;

pub use self::reporter::Simple as EvolveReporterSimple;
pub use crate::strategy::reporter::Duration as EvolveReporterDuration;
pub use crate::strategy::reporter::Noop as EvolveReporterNoop;

#[derive(Copy, Clone, Debug, Default)]
pub enum EvolveVariant {
    #[default]
    Standard,
}

/// The Evolve strategy initializes with a random population of chromosomes (unless the genotype
/// seeds specific genes to sample from), calculates [fitness](crate::fitness) for all chromosomes
/// and sets a first best chromosome (if any).
///
/// Then the Evolve strategy runs through generations of chromosomes in a loop:
/// * [select](crate::select) and pair up chromosomes for crossover
/// * [crossover](crate::crossover) to produce new offspring with a mix of parents chromosome
/// * [mutate](crate::mutate) the offspring chromosomes to add some additional diversity
/// * calculate [fitness](crate::fitness) for all chromosomes
/// * store best chromosome and check ending conditions
///
/// The ending conditions are one or more of the following:
/// * target_fitness_score: when the ultimate goal in terms of fitness score is known and reached
/// * max_stale_generations: when the ultimate goal in terms of fitness score is unknown and one depends on some convergion
///   threshold, or one wants a duration limitation next to the target_fitness_score
/// * max_generations: when the ultimate goal in terms of fitness score is unknown and there is a effort constraint
/// * With a scaled [crate::genotype::MutationType] (e.g. RangeScaled, StepScaled):
///   * When max_generations or max_stale_generations is reached, the current scale ends.
///     If more scales remain, advance to the next scale and reset scale_generation and
///     stale_generations to zero, then continue. If already at the smallest scale, the
///     ending condition terminates the run.
///   * Without scaled mutation types, ending conditions simply terminate the run.
///
/// General Hyper-parameters:
/// * `replacement_rate` (selection): the target fraction of the population which exists of
///   children. Generational Replacement and Steady-State Replacement can both be
///   modelled with this parameter by setting it respectively to 1.0 and 0.2-0.8.
///   High values converge faster, but risk losing good solutions. Low values
///   convergence slower. If there is a shortage of population after the ideal
///   fraction, firstly remaining non-selected children and secondly remaining
///   non-selected parents will be used to fill the shortage to avoid population
///   collapse.
/// * `elitism_rate` (selection): a non-generational elite gate, which ensures passing of the
///   best chromosomes before selection and replacement takes place. Value should
///   typically be very low, between 0.01 and 0.05. Relevant for
///   `SelectTournament` where the best chromosome is not guaranteed to be
///   selected for a tournament if the `population_size` is larger than the
///   `target_population_size`
/// * `selection_rate` (crossover): the fraction of parents which are selected for
///   reproduction. This selection adds offspring to the population, the other
///   parents do not. The population now grows by the added offspring, as the
///   parents are not replaced yet. Value should typically be between 0.4 and
///   0.8. High values risk of premature convergence. Low values reduce diversity
///   if overused.
/// * `crossover_rate (or recombination-rate)` (crossover): the fraction of selected parents
///   to crossover, the remaining parents just clone as offspring. Value should
///   typically be between 0.5 and 0.8. High values converge faster, but risk
///   losing good solutions. Low values have poor exploration and risk of
///   premature convergence
/// * `mutation_probability` (mutation): the fraction of offspring which gets mutated.
///   Typically low, between 0.01 and 0.10. High values reduces convergence
///   ability. Low have a risk of stagnation.
///
///
/// There are optional mutation distance limitations for
/// [RangeGenotype](crate::genotype::RangeGenotype) and
/// [MultiRangeGenotype](crate::genotype::MultiRangeGenotype) chromosomes, see [crate::genotype::MutationType].
///
/// There are reporting hooks in the loop receiving the [EvolveState], which can by handled by an
/// [StrategyReporter] (e.g. [EvolveReporterDuration], [EvolveReporterSimple]). But you are encouraged to
/// roll your own, see [StrategyReporter].
///
/// For [Evolve] the reporting has an additional `on_selection_complete` hook, because that is a
/// more interesting point in the loop, as the population and cardinality are refreshed after
/// selection. As the `on_generation_complete` contains all the new mutations, most of which will
/// be immediately selected out. This gives the false impression of good cardinality while there is
/// actually little.
///
/// Below is the exact order of actions and hooks
/// * [reporter](crate::strategy::reporter) on_enter hook
/// * setup
/// * [reporter](crate::strategy::reporter) on_start hook
/// * loop while not finished
///   * increment generation
///   * [select](crate::select)
///     * before hook: filter by age
///     * call implementation
///     * after hook: update population cardinality (enabled)
///   * [reporter](crate::strategy::reporter) on_selection_complete hook
///   * [extension](crate::extension) after_selection_complete hook
///   * [crossover](crate::crossover)
///     * before hook: no-op
///     * call implementation (includes age increment internally)
///     * after hook: update population cardinality (disabled)
///   * [reporter](crate::strategy::reporter) on_crossover_complete hook
///   * [extension](crate::extension) after_crossover_complete hook
///   * [mutate](crate::mutate)
///     * before hook: no-op
///     * call implementation (only on offspring internally)
///     * after hook: update population cardinality (disabled)
///   * [reporter](crate::strategy::reporter) on_mutation_complete hook
///   * [extension](crate::extension) after_mutation_complete hook
///   * [fitness](crate::fitness) calculation
///   * update best chromosome
///   * [reporter](crate::strategy::reporter) on_generation_complete hook
///   * [extension](crate::extension) after_generation_complete hook
///   * scale and reset ending conditions for new scale
///   * check ending conditions
/// * [reporter](crate::strategy::reporter) on_finish hook
/// * cleanup
/// * [reporter](crate::strategy::reporter) on_exit hook
///
/// From the [EvolveBuilder] level, there are several calling mechanisms:
/// * [call](EvolveBuilder::call): this runs a single evolve strategy
/// * [call_repeatedly](EvolveBuilder::call_repeatedly): this runs multiple independent evolve
///   strategies and returns the best one (or short circuits when the target_fitness_score is
///   reached)
/// * [call_par_repeatedly](EvolveBuilder::call_par_repeatedly): this runs multiple independent
///   evolve strategies in parallel and returns the best one (or short circuits when the
///   target_fitness_score is reached). This is separate and independent from the
///   `with_par_fitness()` flag on the builder, which determines multithreading of the fitness
///   calculation inside the evolve strategy. Both can be combined.
/// * [call_speciated](EvolveBuilder::call_speciated): this runs multiple independent
///   evolve strategies and then selects their best results against each other in one final evolve
///   strategy (or short circuits when the target_fitness_score is reached)
/// * [call_par_speciated](EvolveBuilder::call_par_speciated): this runs multiple independent
///   evolve strategies in parallel and then selects their best results against each other in one
///   final evolve strategy (or short circuits when the target_fitness_score is reached). This is
///   separate and independent from the `with_par_fitness()` flag on the builder, which determines
///   multithreading of the fitness calculation inside the evolve strategy. Both can be combined.
///
/// All multithreading mechanisms are implemented using [rayon::iter] and [std::sync::mpsc].
///
/// See [EvolveBuilder] for initialization options.
///
/// Example:
/// ```
/// use genetic_algorithm::strategy::evolve::prelude::*;
/// use genetic_algorithm::fitness::placeholders::CountTrue;
///
/// // the search space
/// let genotype = BinaryGenotype::builder() // boolean alleles
///     .with_genes_size(100)                // 100 genes per chromosome
///     .with_genes_hashing(true)            // store genes_hash on chromosome (required for fitness_cache and deduplication extension, optional for better population cardinality estimation)
///     .with_chromosome_recycling(true)     // recycle genes memory allocations
///     .build()
///     .unwrap();
///
/// // 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_extension(ExtensionMassExtinction::new(10, 0.1, 0.02)) // optional builder step, simulate cambrian explosion by mass extinction, when population cardinality drops to 10 after the selection, trim to 10% of population
///     .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::Minimize)       // aim for the least true values
///     .with_fitness_cache(1000)                               // enable caching of fitness values (LRU size 1000), only works when genes_hash is stored in chromosome. Only useful for long stale runs, but better to increase population diversity
///     .with_par_fitness(true)                                 // optional, defaults to false, use parallel fitness calculation
///     .with_target_population_size(100)                       // evolve with 100 chromosomes
///     .with_target_fitness_score(0)                           // ending condition if 0 times true in the best chromosome
///     .with_valid_fitness_score(10)                           // block ending conditions until at most a 10 times true in the best chromosome
///     .with_max_stale_generations(1000)                       // stop searching if there is no improvement in fitness score for 1000 generations (per scaled_range)
///     .with_max_generations(1_000_000)                        // optional, stop searching after 1M generations
///     .with_max_chromosome_age(10)                            // kill chromosomes after 10 generations
///     .with_reporter(EvolveReporterSimple::new(100))          // optional builder step, report every 100 generations
///     .with_replace_on_equal_fitness(true)                    // optional, defaults to true
///     .with_rng_seed_from_u64(0)                              // for testing with deterministic results
///     .call()
///     .unwrap();
///
/// // 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![false; 100]);
/// assert_eq!(best_fitness_score, 0);
/// ```
pub struct Evolve<
    G: EvolveGenotype,
    M: Mutate<Genotype = G>,
    F: Fitness<Genotype = G>,
    S: Crossover<Genotype = G>,
    C: Select<Genotype = G>,
    E: Extension<Genotype = G>,
    SR: StrategyReporter<Genotype = G>,
> {
    pub genotype: G,
    pub fitness: F,
    pub plugins: EvolvePlugins<M, S, C, E>,
    pub config: EvolveConfig,
    pub state: EvolveState<G>,
    pub reporter: SR,
    pub rng: SmallRng,
}

pub struct EvolvePlugins<M: Mutate, S: Crossover, C: Select, E: Extension> {
    pub mutate: M,
    pub crossover: S,
    pub select: C,
    pub extension: E,
}

pub struct EvolveConfig {
    pub variant: EvolveVariant,
    pub fitness_ordering: FitnessOrdering,
    pub par_fitness: bool,
    pub replace_on_equal_fitness: bool,

    pub target_fitness_score: Option<FitnessValue>,
    pub max_stale_generations: Option<usize>,
    pub max_generations: Option<usize>,
    pub valid_fitness_score: Option<FitnessValue>,
    pub fitness_cache: Option<FitnessCache>,

    pub target_population_size: usize,
    pub max_chromosome_age: Option<usize>,
    // cooperative abort signal, checked once per generation. When set the run stops early,
    // returning the best chromosome found so far. Independent of the other ending conditions and
    // not blocked by valid_fitness_score.
    pub abort_flag: Option<Arc<AtomicBool>>,
}

/// Stores the state of the Evolve strategy.
#[derive(Clone)]
pub struct EvolveState<G: EvolveGenotype> {
    pub current_iteration: usize,
    // generation counters are usize, not a bigint: they count generations actually evaluated, which
    // is bounded by wall-clock time and stays well within usize (overflowing u64 needs ~1.8e19
    // evaluations — centuries even at 1e9/s), so a terminating run never overflows them.
    pub current_generation: usize,
    pub stale_generations: usize,
    pub scale_generation: usize,
    pub best_generation: usize,
    pub best_fitness_score: Option<FitnessValue>,
    pub best_chromosome: Option<Chromosome<G::Allele>>,
    pub chromosome: Option<Chromosome<G::Allele>>,
    pub population: Population<G::Allele>,
    pub durations: HashMap<StrategyAction, Duration>,
    pub population_cardinality: Option<usize>,
}

impl<
        G: EvolveGenotype,
        M: Mutate<Genotype = G>,
        F: Fitness<Genotype = G>,
        S: Crossover<Genotype = G>,
        C: Select<Genotype = G>,
        E: Extension<Genotype = G>,
        SR: StrategyReporter<Genotype = G>,
    > Strategy<G> for Evolve<G, M, F, S, C, E, SR>
{
    fn call(&mut self) {
        let now = Instant::now();
        self.reporter
            .on_enter(&self.genotype, &self.state, &self.config);
        let mut fitness_thread_local: Option<ThreadLocal<RefCell<F>>> = None;
        if self.config.par_fitness {
            fitness_thread_local = Some(ThreadLocal::new());
        }
        self.setup(fitness_thread_local.as_ref());

        self.reporter
            .on_start(&self.genotype, &self.state, &self.config);
        while !self.is_finished() {
            self.state.increment_generation();

            // select
            self.plugins
                .select
                .before(&self.genotype, &mut self.state, &self.config);
            self.plugins.select.call(
                &self.genotype,
                &mut self.state,
                &self.config,
                &mut self.reporter,
                &mut self.rng,
            );
            self.plugins
                .select
                .after(&self.genotype, &mut self.state, &self.config);
            self.reporter
                .on_selection_complete(&self.genotype, &self.state, &self.config);
            self.plugins.extension.after_selection_complete(
                &mut self.genotype,
                &mut self.state,
                &self.config,
                &mut self.reporter,
                &mut self.rng,
            );

            // crossover
            self.state.population.increment_age();
            self.plugins
                .crossover
                .before(&self.genotype, &mut self.state, &self.config);
            self.plugins.crossover.call(
                &self.genotype,
                &mut self.state,
                &self.config,
                &mut self.reporter,
                &mut self.rng,
            );
            self.plugins
                .crossover
                .after(&self.genotype, &mut self.state, &self.config);
            self.reporter
                .on_crossover_complete(&self.genotype, &self.state, &self.config);
            self.plugins.extension.after_crossover_complete(
                &mut self.genotype,
                &mut self.state,
                &self.config,
                &mut self.reporter,
                &mut self.rng,
            );

            // mutate
            self.plugins
                .mutate
                .before(&self.genotype, &mut self.state, &self.config);
            self.plugins.mutate.call(
                &self.genotype,
                &mut self.state,
                &self.config,
                &mut self.reporter,
                &mut self.rng,
            );
            self.plugins
                .mutate
                .after(&self.genotype, &mut self.state, &self.config);
            self.reporter
                .on_mutation_complete(&self.genotype, &self.state, &self.config);
            self.plugins.extension.after_mutation_complete(
                &mut self.genotype,
                &mut self.state,
                &self.config,
                &mut self.reporter,
                &mut self.rng,
            );

            // fitness
            self.fitness.call_for_state_population(
                &self.genotype,
                &mut self.state,
                &self.config,
                fitness_thread_local.as_ref(),
            );
            self.state.update_best_chromosome_and_report(
                &self.genotype,
                &self.config,
                &mut self.reporter,
            );

            // end of generation
            self.reporter
                .on_generation_complete(&self.genotype, &self.state, &self.config);
            self.plugins.extension.after_generation_complete(
                &mut self.genotype,
                &mut self.state,
                &self.config,
                &mut self.reporter,
                &mut self.rng,
            );
            self.state.scale(&mut self.genotype, &self.config);
        }
        self.reporter
            .on_finish(&self.genotype, &self.state, &self.config);
        self.cleanup(fitness_thread_local.as_mut());
        self.state.close_duration(now.elapsed());
        self.reporter
            .on_exit(&self.genotype, &self.state, &self.config);
    }
    fn best_generation(&self) -> usize {
        self.state.best_generation
    }
    fn best_fitness_score(&self) -> Option<FitnessValue> {
        self.state.best_fitness_score()
    }
    fn best_genes(&self) -> Option<Genes<G::Allele>> {
        self.state
            .best_chromosome
            .as_ref()
            .map(|c| c.genes().clone())
    }
    fn flush_reporter(&mut self, output: &mut Vec<u8>) {
        self.reporter.flush(output);
    }
}
impl<
        G: EvolveGenotype,
        M: Mutate<Genotype = G>,
        F: Fitness<Genotype = G>,
        S: Crossover<Genotype = G>,
        C: Select<Genotype = G>,
        E: Extension<Genotype = G>,
        SR: StrategyReporter<Genotype = G>,
    > Evolve<G, M, F, S, C, E, SR>
{
    pub fn best_chromosome(&self) -> Option<Chromosome<G::Allele>> {
        if let Some(best_genes) = self.best_genes() {
            let mut chromosome = Chromosome::new(best_genes);
            chromosome.set_fitness_score(self.best_fitness_score());
            Some(chromosome)
        } else {
            None
        }
    }
}

impl<
        G: EvolveGenotype,
        M: Mutate<Genotype = G>,
        F: Fitness<Genotype = G>,
        S: Crossover<Genotype = G>,
        C: Select<Genotype = G>,
    > Evolve<G, M, F, S, C, ExtensionNoop<G>, StrategyReporterNoop<G>>
{
    pub fn builder() -> EvolveBuilder<G, M, F, S, C, ExtensionNoop<G>, StrategyReporterNoop<G>> {
        EvolveBuilder::new()
    }
}

impl<
        G: EvolveGenotype,
        M: Mutate<Genotype = G>,
        F: Fitness<Genotype = G>,
        S: Crossover<Genotype = G>,
        C: Select<Genotype = G>,
        E: Extension<Genotype = G>,
        SR: StrategyReporter<Genotype = G>,
    > Evolve<G, M, F, S, C, E, SR>
{
    pub fn setup(&mut self, fitness_thread_local: Option<&ThreadLocal<RefCell<F>>>) {
        let now = Instant::now();
        self.state.population = self
            .genotype
            .population_constructor(self.config.target_population_size, &mut self.rng);
        self.state
            .add_duration(StrategyAction::SetupAndCleanup, now.elapsed());

        self.fitness.call_for_state_population(
            &self.genotype,
            &mut self.state,
            &self.config,
            fitness_thread_local,
        );
        self.state.update_best_chromosome_and_report(
            &self.genotype,
            &self.config,
            &mut self.reporter,
        );

        if self.state.best_fitness_score().is_none() {
            let chromosome = &self.state.population.chromosomes[0];
            self.state.best_generation = self.state.current_generation;
            self.state.best_chromosome = Some(chromosome.clone());
            self.reporter
                .on_new_best_chromosome(&self.genotype, &self.state, &self.config);
            self.state.reset_stale_generations();
        }
    }

    pub fn cleanup(&mut self, fitness_thread_local: Option<&mut ThreadLocal<RefCell<F>>>) {
        let now = Instant::now();
        self.state.chromosome.take();
        self.state.population.chromosomes.clear();
        if let Some(thread_local) = fitness_thread_local {
            thread_local.clear();
        }
        self.state
            .add_duration(StrategyAction::SetupAndCleanup, now.elapsed());
    }

    fn is_finished(&self) -> bool {
        self.is_conclusive() || self.is_exhausted()
    }
    // conclusive end of the run: the target fitness score was reached, or the run was aborted.
    // The repeat/speciated builders short-circuit on this per run (no point launching more once a
    // run is conclusive), as opposed to is_finished which also ends on the give-up conditions.
    fn is_conclusive(&self) -> bool {
        // cooperative abort
        if self
            .config
            .abort_flag
            .as_ref()
            .is_some_and(|flag| flag.load(Ordering::Relaxed))
        {
            return true;
        }
        // target_fitness_score
        if let Some(target_fitness_score) = self.config.target_fitness_score {
            if let Some(fitness_score) = self.best_fitness_score() {
                return match self.config.fitness_ordering {
                    FitnessOrdering::Maximize => fitness_score >= target_fitness_score,
                    FitnessOrdering::Minimize => fitness_score <= target_fitness_score,
                };
            }
        }
        false
    }
    // exhausted end of the run: a give-up condition (max_stale_generations / max_generations) has
    // triggered. These are blocked by valid_fitness_score until the best chromosome is at least
    // valid, so the run does not give up on an unacceptable solution.
    fn is_exhausted(&self) -> bool {
        if let Some(valid_fitness_score) = self.config.valid_fitness_score {
            if let Some(fitness_score) = self.best_fitness_score() {
                let valid = match self.config.fitness_ordering {
                    FitnessOrdering::Maximize => fitness_score >= valid_fitness_score,
                    FitnessOrdering::Minimize => fitness_score <= valid_fitness_score,
                };
                if !valid {
                    return false;
                }
            }
        }
        if let Some(max_stale_generations) = self.config.max_stale_generations {
            if self.state.stale_generations >= max_stale_generations {
                return true;
            }
        }
        if let Some(max_generations) = self.config.max_generations {
            if self.state.scale_generation >= max_generations {
                return true;
            }
        }
        false
    }
}

impl StrategyConfig for EvolveConfig {
    fn fitness_ordering(&self) -> FitnessOrdering {
        self.fitness_ordering
    }
    fn fitness_cache(&self) -> Option<&FitnessCache> {
        self.fitness_cache.as_ref()
    }
    fn par_fitness(&self) -> bool {
        self.par_fitness
    }
    fn replace_on_equal_fitness(&self) -> bool {
        self.replace_on_equal_fitness
    }
    fn variant(&self) -> StrategyVariant {
        StrategyVariant::Evolve(self.variant)
    }
}

impl<G: EvolveGenotype> StrategyState<G> for EvolveState<G> {
    fn chromosome_as_ref(&self) -> &Option<Chromosome<G::Allele>> {
        &self.chromosome
    }
    fn population_as_ref(&self) -> &Population<G::Allele> {
        &self.population
    }
    fn chromosome_as_mut(&mut self) -> &mut Option<Chromosome<G::Allele>> {
        &mut self.chromosome
    }
    fn population_as_mut(&mut self) -> &mut Population<G::Allele> {
        &mut self.population
    }
    fn best_generation(&self) -> usize {
        self.best_generation
    }
    fn best_fitness_score(&self) -> Option<FitnessValue> {
        self.best_fitness_score
    }
    fn current_generation(&self) -> usize {
        self.current_generation
    }
    fn current_iteration(&self) -> usize {
        self.current_iteration
    }
    fn increment_generation(&mut self) {
        self.current_generation += 1;
        self.scale_generation += 1;
    }
    fn stale_generations(&self) -> usize {
        self.stale_generations
    }
    fn increment_stale_generations(&mut self) {
        self.stale_generations += 1;
    }
    fn reset_stale_generations(&mut self) {
        self.stale_generations = 0;
    }
    fn scale_generation(&self) -> usize {
        self.scale_generation
    }
    fn reset_scale_generation(&mut self) {
        self.scale_generation = 0;
    }
    fn population_cardinality(&self) -> Option<usize> {
        self.population_cardinality
    }
    fn durations(&self) -> &HashMap<StrategyAction, Duration> {
        &self.durations
    }
    fn add_duration(&mut self, action: StrategyAction, duration: Duration) {
        *self.durations.entry(action).or_default() += duration;
    }
    fn total_duration(&self) -> Duration {
        self.durations.values().sum()
    }
    fn best_genes(&self) -> Option<Genes<G::Allele>> {
        self.best_chromosome.as_ref().map(|c| c.genes().clone())
    }
}

impl<G: EvolveGenotype> EvolveState<G> {
    fn update_best_chromosome_and_report<SR: StrategyReporter<Genotype = G>>(
        &mut self,
        genotype: &G,
        config: &EvolveConfig,
        reporter: &mut SR,
    ) {
        let now = Instant::now();
        if let Some(contending_chromosome) =
            self.population.best_chromosome(config.fitness_ordering)
        {
            match self.is_better_chromosome(
                contending_chromosome,
                &config.fitness_ordering,
                config.replace_on_equal_fitness,
            ) {
                (true, true) => {
                    self.best_generation = self.current_generation;
                    self.best_fitness_score = contending_chromosome.fitness_score();
                    self.best_chromosome = Some(contending_chromosome.clone());
                    reporter.on_new_best_chromosome(genotype, self, config);
                    self.reset_stale_generations();
                }
                (true, false) => {
                    self.best_chromosome = Some(contending_chromosome.clone());
                    reporter.on_new_best_chromosome_equal_fitness(genotype, self, config);
                    self.increment_stale_generations();
                }
                _ => self.increment_stale_generations(),
            }
        } else {
            self.increment_stale_generations();
        }
        self.add_duration(StrategyAction::UpdateBestChromosome, now.elapsed());
    }
    fn scale(&mut self, genotype: &mut G, config: &EvolveConfig) {
        if let Some(max_generations) = config.max_generations {
            if self.scale_generation >= max_generations && genotype.increment_scale_index() {
                self.reset_scale_generation();
                self.reset_stale_generations();
            }
        }
        if let Some(max_stale_generations) = config.max_stale_generations {
            if self.stale_generations >= max_stale_generations && genotype.increment_scale_index() {
                self.reset_scale_generation();
                self.reset_stale_generations();
            }
        }
    }
    pub fn update_population_cardinality(&mut self, genotype: &G, _config: &EvolveConfig) {
        self.population_cardinality = if genotype.genes_hashing() {
            self.population.genes_cardinality()
        } else {
            self.population.fitness_score_cardinality()
        }
    }
}

impl<
        G: EvolveGenotype,
        M: Mutate<Genotype = G>,
        F: Fitness<Genotype = G>,
        S: Crossover<Genotype = G>,
        C: Select<Genotype = G>,
        E: Extension<Genotype = G>,
        SR: StrategyReporter<Genotype = G>,
    > TryFrom<EvolveBuilder<G, M, F, S, C, E, SR>> for Evolve<G, M, F, S, C, E, SR>
{
    type Error = TryFromEvolveBuilderError;

    fn try_from(builder: EvolveBuilder<G, M, F, S, C, E, SR>) -> Result<Self, Self::Error> {
        if builder.genotype.is_none() {
            Err(TryFromEvolveBuilderError(
                "Evolve requires a EvolveGenotype",
            ))
        } else if builder.fitness.is_none() {
            Err(TryFromEvolveBuilderError("Evolve requires a Fitness"))
        } else if builder.mutate.is_none() {
            Err(TryFromEvolveBuilderError(
                "Evolve requires a Mutate strategy",
            ))
        } else if builder.crossover.is_none() {
            Err(TryFromEvolveBuilderError(
                "Evolve requires a Crossover strategy",
            ))
        } else if builder.select.is_none() {
            Err(TryFromEvolveBuilderError(
                "Evolve requires a Select strategy",
            ))
        } else if builder.max_stale_generations.is_none()
            && builder.max_generations.is_none()
            && builder.target_fitness_score.is_none()
        {
            Err(TryFromEvolveBuilderError(
                "Evolve requires at least a max_stale_generations, max_generations or target_fitness_score ending condition",
            ))
        } else {
            let rng = builder.rng();
            let genotype = builder.genotype.unwrap();
            let state = EvolveState::new(&genotype);
            let target_population_size = builder.target_population_size;

            Ok(Self {
                genotype,
                fitness: builder.fitness.unwrap(),
                plugins: EvolvePlugins {
                    mutate: builder.mutate.unwrap(),
                    crossover: builder.crossover.unwrap(),
                    select: builder.select.unwrap(),
                    extension: builder.extension,
                },
                config: EvolveConfig {
                    target_population_size,
                    max_stale_generations: builder.max_stale_generations,
                    max_generations: builder.max_generations,
                    max_chromosome_age: builder.max_chromosome_age,
                    target_fitness_score: builder.target_fitness_score,
                    valid_fitness_score: builder.valid_fitness_score,
                    fitness_ordering: builder.fitness_ordering,
                    fitness_cache: builder.fitness_cache,
                    par_fitness: builder.par_fitness,
                    replace_on_equal_fitness: builder.replace_on_equal_fitness,
                    abort_flag: builder.abort_flag,
                    ..Default::default()
                },
                state,
                reporter: builder.reporter,
                rng,
            })
        }
    }
}

impl Default for EvolveConfig {
    fn default() -> Self {
        Self {
            variant: Default::default(),
            target_population_size: 100,
            max_stale_generations: None,
            max_generations: None,
            max_chromosome_age: None,
            target_fitness_score: None,
            valid_fitness_score: None,
            fitness_ordering: FitnessOrdering::Maximize,
            fitness_cache: None,
            par_fitness: false,
            replace_on_equal_fitness: true,
            abort_flag: None,
        }
    }
}
impl EvolveConfig {
    pub fn new() -> Self {
        Self::default()
    }
}
impl<G: EvolveGenotype> EvolveState<G> {
    pub fn new(genotype: &G) -> Self {
        Self {
            current_iteration: 0,
            current_generation: 0,
            stale_generations: 0,
            scale_generation: 0,
            best_generation: 0,
            best_fitness_score: None,
            best_chromosome: None,
            chromosome: None,
            population: Population::new_empty(genotype.chromosome_recycling()),
            population_cardinality: None,
            durations: HashMap::new(),
        }
    }
}

impl<
        G: EvolveGenotype,
        M: Mutate<Genotype = G>,
        F: Fitness<Genotype = G>,
        S: Crossover<Genotype = G>,
        C: Select<Genotype = G>,
        E: Extension<Genotype = G>,
        SR: StrategyReporter<Genotype = G>,
    > fmt::Display for Evolve<G, M, F, S, C, E, SR>
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        writeln!(f, "evolve:")?;
        writeln!(f, "  fitness: {:?}", self.fitness)?;
        writeln!(f)?;

        writeln!(f, "{}", self.plugins)?;
        writeln!(f, "{}", self.config)?;
        writeln!(f, "{}", self.state)?;
        writeln!(f, "{}", self.genotype)
    }
}

impl<M: Mutate, S: Crossover, C: Select, E: Extension> fmt::Display for EvolvePlugins<M, S, C, E> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        writeln!(f, "evolve_plugins:")?;
        writeln!(f, "  mutate: {:?}", self.mutate)?;
        writeln!(f, "  crossover: {:?}", self.crossover)?;
        writeln!(f, "  select: {:?}", self.select)?;
        writeln!(f, "  extension: {:?}", self.extension)
    }
}

impl fmt::Display for EvolveConfig {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        writeln!(f, "evolve_config:")?;
        writeln!(
            f,
            "  target_population_size: {}",
            self.target_population_size
        )?;
        writeln!(
            f,
            "  max_stale_generations: {:?}",
            self.max_stale_generations
        )?;
        writeln!(f, "  max_generations: {:?}", self.max_generations)?;
        writeln!(f, "  max_chromosome_age: {:?}", self.max_chromosome_age)?;
        writeln!(f, "  valid_fitness_score: {:?}", self.valid_fitness_score)?;
        writeln!(f, "  target_fitness_score: {:?}", self.target_fitness_score)?;
        writeln!(f, "  fitness_ordering: {:?}", self.fitness_ordering)?;
        writeln!(f, "  par_fitness: {:?}", self.par_fitness)
    }
}

impl<G: EvolveGenotype> fmt::Display for EvolveState<G> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        writeln!(f, "evolve_state:")?;
        writeln!(f, "  current iteration: {:?}", self.current_iteration)?;
        writeln!(f, "  current generation: {:?}", self.current_generation)?;
        writeln!(f, "  stale generations: {:?}", self.stale_generations)?;
        writeln!(
            f,
            "  population cardinality: {:?}",
            self.population_cardinality
        )?;
        writeln!(f, "  best fitness score: {:?}", self.best_fitness_score())
    }
}