Module strategy

Expand description

solution strategies for finding the best chromosomes.

There are 4 strategies:

See strategies for details. Normally, you build a specific strategy and call directly from the specific builder. But there is an option for building the superset StrategyBuilder and calling from there. You call from the builder, as repeatedly options clone the builder first. The execution is switched based on the provided with_variant(). The call options are:

call() simply run once
call_repeatedly(usize), call repeatedly and take the best (or short-circuit on target fitness score)
- fallback to call() once for Permutate
call_par_repeatedly(usize), as above, but high level parallel execution
- fallback to call() once for Permutate, but force with_par_fitness(true)
call_speciated(usize), call repeatedly and then run one final round with the best chromosomes from the previous rounds as seeds
- fallback to call() once for Permutate
- fallback to call_repeatedly(usize) for HillClimb
call_par_speciated(usize), as above, but high level parallel execution
- fallback to call() once for Permutate, but force with_par_fitness(true)
- fallback to call_par_repeatedly(usize) for HillClimb

Note: Only Genotypes which implement all strategies are eligable for the superset builder. RangeGenotype and other floating point range based genotypes currently do not support Permutation unless scaled

Example:

use genetic_algorithm::strategy::prelude::*;
use genetic_algorithm::fitness::placeholders::CountTrue;

// the search space
let genotype = BinaryGenotype::builder()
    .with_genes_size(10)
    .with_genes_hashing(true) // store genes_hash on chromosome (required for fitness_cache and deduplication extension, optional for better population cardinality estimation)
    .build()
    .unwrap();

// the search strategy (superset), steps marked (E)volve, (H)illClimb and (P)ermutate
let builder = StrategyBuilder::new()
    .with_genotype(genotype)                                // (E,H,P) the genotype
    .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
    .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
    .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)
    .with_mutate(MutateSingleGene::new(0.2))                // (E) mutate offspring for a single gene with a 20% probability per chromosome
    .with_fitness(CountTrue)                                // (E,H,P) count the number of true values in the chromosomes
    .with_fitness_ordering(FitnessOrdering::Minimize)       // (E,H,P) aim for the least true values
    .with_fitness_cache(1000)                               // (E) enable caching of fitness values, only works when genes_hash is stored in chromosome.
    .with_par_fitness(true)                                 // (E,H,P) optional, defaults to false, use parallel fitness calculation
    .with_target_population_size(100)                       // (E) evolve with 100 chromosomes
    .with_target_fitness_score(0)                           // (E,H) ending condition if 0 times true in the best chromosome
    .with_valid_fitness_score(1)                            // (E,H) block ending conditions until at most a 1 times true in the best chromosome
    .with_max_stale_generations(100)                        // (E,H) stop searching if there is no improvement in fitness score for 100 generations
    .with_max_generations(1_000_000)                        // (E,H) optional, stop searching after 1M generations
    .with_max_chromosome_age(10)                            // (E) kill chromosomes after 10 generations
    .with_reporter(StrategyReporterSimple::new(usize::MAX)) // (E,H,P) optional builder step, report on new best chromosomes only
    .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
    .with_rng_seed_from_u64(0);                             // (E,H) for testing with deterministic results

// the search strategy (specified)
let (strategy, _) = builder
    .with_variant(StrategyVariant::Permutate(PermutateVariant::Standard))
    // .with_variant(StrategyVariant::Evolve(EvolveVariant::Standard))build str
    // .with_variant(StrategyVariant::HillClimb(HillClimbVariant::Stochastic))
    // .with_variant(StrategyVariant::HillClimb(HillClimbVariant::SteepAscent))
    .call_speciated(3)
    .unwrap();

// it's all about the best genes after all
let (best_genes, best_fitness_score) = strategy.best_genes_and_fitness_score().unwrap();
assert_eq!(best_genes, vec![false; 10]);
assert_eq!(best_fitness_score, 0);

Re-exports§

pub use self::builder::Builder as StrategyBuilder;
pub use self::builder::TryFromBuilderError as TryFromStrategyBuilderError;
pub use self::reporter::Duration as StrategyReporterDuration;
pub use self::reporter::Noop as StrategyReporterNoop;
pub use self::reporter::Simple as StrategyReporterSimple;

Modules§

builder
evolve: A solution strategy for finding the best chromosome using evolution
hill_climb: A solution strategy for finding the best chromosome, when search space is convex with little local optima or crossover is impossible or inefficient
permutate: A solution strategy for finding the best chromosome in case of small problem spaces (with a 100% guarantee)
prelude
reporter: Generic strategy reporters:

Enums§

StrategyAction
StrategyVariant

Constants§

STRATEGY_ACTIONS

Traits§