Struct Evolve

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

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, optional for better population cardinality estimation)
    .build()
    .unwrap();

// the search strategy
let evolve = Evolve::builder()
    .with_genotype(genotype)
    .with_select(SelectElite::new(0.9))                    // sort the chromosomes by fitness to determine crossover order and select 90% of the population for crossover (drop 10% of population)
    .with_extension(ExtensionMassExtinction::new(10, 0.1)) // optional builder step, simulate cambrian explosion by mass extinction, when fitness score cardinality drops to 10 after the selection, trim to 10% of population
    .with_crossover(CrossoverUniform::new())               // crossover all individual genes between 2 chromosomes for offspring (and restore back to 100% of target population size by keeping the best parents alive)
    .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
    .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, F: Fitness<Genotype = G>, S: Crossover, C: Select, E: Extension, SR: StrategyReporter<Genotype = G>> Evolve<G, M, F, S, C, E, SR>

where G::Chromosome: GenesOwner<Genes = G::Genes>,

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

impl<G: EvolveGenotype, M: Mutate, F: Fitness<Genotype = G>, S: Crossover, 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, F: Fitness<Genotype = G>, S: Crossover, 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, F: Fitness<Genotype = G>, S: Crossover, 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, F: Fitness<Genotype = G>, S: Crossover, 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<G::Genes>

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<(G::Genes, FitnessValue)>

impl<G: EvolveGenotype, M: Mutate, F: Fitness<Genotype = G>, S: Crossover, 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.