Struct Evolve 

pub struct Evolve<G: EvolveGenotype, M: Mutate<Genotype = G>, F: Fitness<Genotype = G>, S: Crossover<Genotype = G>, C: Select, E: Extension, 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,
}

The Evolve strategy initializes with a random population of chromosomes (unless the genotype seeds specific genes to sample from), calculates 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 and pair up chromosomes for crossover
• extension an optional step triggering on population cardinality after selection (e.g. MassExtinction)
• crossover to produce new offspring with a mix of parents chromosome.
• mutate the offspring chromosomes to add some additional diversity
• calculate 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

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 and MultiRangeGenotype chromosomes. Listed in descending priority:

• With allele_mutation_scaled_range(s) set on genotype:
  • Mutation distance only on edges of current scale (e.g. -1 and +1 for -1..-1 scale), pick random edge
  • Scale down after max_stale_generations is reached and reset stale_generations to zero
  • Only trigger max_stale_generations ending condition when already reached the smallest scale
• With allele_mutation_range(s) set on genotype:
  • Mutation distance taken uniformly from mutation range
  • Standard max_stale_generations ending condition
• With only allele_range(s) set on genotype:
  • Mutate uniformly over the complete allele range
  • Standard max_stale_generations ending condition

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 on_new_generation hook is called just after selection, because that is a more interesting point in the loop.

From the EvolveBuilder level, there are several calling mechanisms:

• call: this runs a single evolve strategy
• 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: 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: 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: 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 false, maybe useful to avoid repeatedly seeding with the same best chromosomes after mass extinction events
    .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);

Fields

genotype: G

fitness: F

plugins: EvolvePlugins<M, S, C, E>

config: EvolveConfig

state: EvolveState<G>

reporter: SR

rng: SmallRng

Implementations

impl<G: EvolveGenotype, M: Mutate<Genotype = G>, F: Fitness<Genotype = G>, S: Crossover<Genotype = G>, C: Select, E: Extension, SR: StrategyReporter<Genotype = G>> Evolve<G, M, F, S, C, E, SR>

pub fn best_chromosome(&self) -> Option<Chromosome<G::Allele>>

impl<G: EvolveGenotype, M: Mutate<Genotype = G>, F: Fitness<Genotype = G>, S: Crossover<Genotype = G>, C: Select> Evolve<G, M, F, S, C, ExtensionNoop, StrategyReporterNoop<G>>

pub fn builder() -> EvolveBuilder<G, M, F, S, C, ExtensionNoop, StrategyReporterNoop<G>>

impl<G: EvolveGenotype, M: Mutate<Genotype = G>, F: Fitness<Genotype = G>, S: Crossover<Genotype = G>, C: Select, E: Extension, SR: StrategyReporter<Genotype = G>> Evolve<G, M, F, S, C, E, SR>

pub fn setup(&mut self, fitness_thread_local: Option<&ThreadLocal<RefCell<F>>>)

pub fn cleanup( &mut self, fitness_thread_local: Option<&mut ThreadLocal<RefCell<F>>>, )

Trait Implementations

impl<G: EvolveGenotype, M: Mutate<Genotype = G>, F: Fitness<Genotype = G>, S: Crossover<Genotype = G>, C: Select, E: Extension, SR: StrategyReporter<Genotype = G>> Display for Evolve<G, M, F, S, C, E, SR>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<G: EvolveGenotype, M: Mutate<Genotype = G>, F: Fitness<Genotype = G>, S: Crossover<Genotype = G>, C: Select, E: Extension, SR: StrategyReporter<Genotype = G>> Strategy<G> for Evolve<G, M, F, S, C, E, SR>

fn call(&mut self)

fn best_generation(&self) -> usize

fn best_fitness_score(&self) -> Option<FitnessValue>

fn best_genes(&self) -> Option<Genes<G::Allele>>

fn flush_reporter(&mut self, output: &mut Vec<u8>)

strategy can be boxed, need a way to get to the reporter

fn best_genes_and_fitness_score( &self, ) -> Option<(Genes<G::Allele>, FitnessValue)>

impl<G: EvolveGenotype, M: Mutate<Genotype = G>, F: Fitness<Genotype = G>, S: Crossover<Genotype = G>, C: Select, E: Extension, SR: StrategyReporter<Genotype = G>> TryFrom<Builder<G, M, F, S, C, E, SR>> for Evolve<G, M, F, S, C, E, SR>

type Error = TryFromStrategyBuilderError

The type returned in the event of a conversion error.

fn try_from( builder: EvolveBuilder<G, M, F, S, C, E, SR>, ) -> Result<Self, Self::Error>

Performs the conversion.