Struct HillClimb

pub struct HillClimb<G: HillClimbGenotype, F: Fitness<Genotype = G>, SR: StrategyReporter<Genotype = G>> {
    pub genotype: G,
    pub fitness: F,
    pub config: HillClimbConfig,
    pub state: HillClimbState<G>,
    pub reporter: SR,
    pub rng: SmallRng,
}

The HillClimb strategy is an iterative algorithm that starts with a single arbitrary solution to a problem (unless the genotype seeds specific genes to sample a single starting point from), then attempts to find a better solution by making an incremental change to the solution

There are 2 variants:

• HillClimbVariant::Stochastic: does not examine all neighbors before deciding how to move. Rather, it selects a neighbor at random, and decides (based on the improvement in that neighbour) whether to move to that neighbor or to examine another
• HillClimbVariant::SteepestAscent: all neighbours are compared and the one with the best improvement is chosen.

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.
  • set to a high value for HillClimbVariant::Stochastic
  • set to a low value for HillClimbVariant::SteepestAscent, preferably even 1, unless there is a replace_on_equal_fitness consideration or some remaining randomness in the neighbouring population (see RangeGenotype below)

There are optional mutation distance limitations for RangeGenotype and MultiRangeGenotype neighbouring 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 for HillClimbVariant::Stochastic
    • Take both edges per gene for HillClimbVariant::SteepestAscent
  • 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
  • max_stale_generations could be set to 1, as there is no remaining randomness
• With allele_mutation_range(s) set on genotype:
  • Mutation distance taken uniformly from mutation range
    • Sample single random value for HillClimbVariant::Stochastic
    • Ensure to sample both a higer and lower value per gene for HillClimbVariant::SteepestAscent
  • Standard max_stale_generations ending condition
  • max_stale_generations should be set somewhat higher than 1 as there is some remaining randomness
• With only allele_range(s) set on genotype (not advised for hill climbing):
  • Mutate uniformly over the complete allele range
    • Sample single random value for HillClimbVariant::Stochastic
    • Ensure to sample both a higer and lower value per gene for HillClimbVariant::SteepestAscent
  • Standard max_stale_generations ending condition
  • max_stale_generations should be set substantially higher than 1 as there is a lot remaining randomness

There are reporting hooks in the loop receiving the HillClimbState, which can by handled by an StrategyReporter (e.g. HillClimbReporterDuration, HillClimbReporterSimple). But you are encouraged to roll your own, see StrategyReporter.

From the HillClimbBuilder level, there are several calling mechanisms:

• call: this runs a single HillClimb strategy
• call_repeatedly: this runs multiple independent HillClimb strategies and returns the best one (or short circuits when the target_fitness_score is reached)
• call_par_repeatedly: this runs multiple independent HillClimb 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 HillClimb strategy. Both can be combined.

Multithreading inside the HillClimbVariant::Stochastic using the with_par_fitness() builder step does nothing, due to the sequential nature of the search. But call_par_repeatedly still effectively multithreads for these variants as the sequential nature is only internal to the HillClimb strategy.

All multithreading mechanisms are implemented using rayon::iter and std::sync::mpsc.

See HillClimbBuilder for initialization options.

Example:

use genetic_algorithm::strategy::hill_climb::prelude::*;
use genetic_algorithm::fitness::placeholders::SumGenes;

// the search space
let genotype = RangeGenotype::builder()     // f32 alleles
    .with_genes_size(16)                    // 16 genes
    .with_allele_range(0.0..=1.0)           // allow gene values between 0.0 and 1.0
    .with_allele_mutation_range(-0.1..=0.1) // neighbouring step size randomly sampled from range
    .with_allele_mutation_scaled_range(vec![
      -0.1..=0.1,
      -0.01..=0.01,
      -0.001..=0.001
     ]) // neighbouring step size equal to start/end of each scaled range
    .build()
    .unwrap();

// the search strategy
let hill_climb = HillClimb::builder()
    .with_genotype(genotype)
    .with_variant(HillClimbVariant::SteepestAscent)   // check all neighbours for each round
    .with_fitness(SumGenes::new_with_precision(1e-5)) // sum the gene values of the chromosomes with precision 0.00001, which means multiply fitness score (isize) by 100_000
    .with_fitness_ordering(FitnessOrdering::Minimize) // aim for the lowest sum
    .with_par_fitness(true)                           // optional, defaults to false, use parallel fitness calculation
    .with_target_fitness_score(0)                     // ending condition if sum of genes is <= 0.00001 in the best chromosome
    .with_valid_fitness_score(100)                    // block ending conditions until at least the sum of genes <= 0.00100 is reached in the best chromosome
    .with_max_stale_generations(1000)                 // stop searching if there is no improvement in fitness score for 1000 generations
    .with_replace_on_equal_fitness(true)              // optional, defaults to true, crucial for some type of problems with discrete fitness steps like nqueens
    .with_reporter(HillClimbReporterSimple::new(100)) // optional, report every 100 generations
    .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) = hill_climb.best_genes_and_fitness_score().unwrap();
assert_eq!(best_genes.into_iter().map(|v| v <= 1e-3).collect::<Vec<_>>(), vec![true; 16]);
assert_eq!(best_fitness_score, 0);

Fields

genotype: G

fitness: F

config: HillClimbConfig

state: HillClimbState<G>

reporter: SR

rng: SmallRng

Implementations

impl<G: HillClimbGenotype, F: Fitness<Genotype = G>, SR: StrategyReporter<Genotype = G>> HillClimb<G, F, SR>

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

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

impl<G: HillClimbGenotype, F: Fitness<Genotype = G>> HillClimb<G, F, StrategyReporterNoop<G>>

pub fn builder() -> HillClimbBuilder<G, F, StrategyReporterNoop<G>>

impl<G: HillClimbGenotype, F: Fitness<Genotype = G>, SR: StrategyReporter<Genotype = G>> HillClimb<G, F, SR>

pub fn setup(&mut self)

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

Trait Implementations

impl<G: HillClimbGenotype, F: Fitness<Genotype = G>, SR: StrategyReporter<Genotype = G>> Display for HillClimb<G, F, SR>

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

Formats the value using the given formatter.

impl<G: HillClimbGenotype, F: Fitness<Genotype = G>, SR: StrategyReporter<Genotype = G>> Strategy<G> for HillClimb<G, F, 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: HillClimbGenotype, F: Fitness<Genotype = G>, SR: StrategyReporter<Genotype = G>> TryFrom<Builder<G, F, SR>> for HillClimb<G, F, SR>

type Error = TryFromStrategyBuilderError

The type returned in the event of a conversion error.

fn try_from(builder: HillClimbBuilder<G, F, SR>) -> Result<Self, Self::Error>

Performs the conversion.