Struct genetic_algorithm::strategy::hill_climb::HillClimb

pub struct HillClimb<G: IncrementalGenotype, F: Fitness<Allele = G::Allele>, SR: HillClimbReporter<Allele = G::Allele>> {
    pub genotype: G,
    pub fitness: F,
    pub config: HillClimbConfig,
    pub state: HillClimbState<G::Allele>,
    pub reporter: SR,
    pub rng: SmallRng,
}

The HillClimb strategy is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an incremental change to the solution

There are 4 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.
• HillClimbVariant::StochasticSecondary: like Stochastic, but also randomly tries a random neighbour of the neighbour. Useful when a single mutation would generally not lead to improvement, because the problem space behaves more like a UniqueGenotype where genes must be swapped (but the UniqueGenotype doesn’t map to the problem space well)
• HillClimbVariant::SteepestAscentSecondary: like SteepestAscent, but also neighbours of neighbours are in scope. This is O(n^2) with regards to the SteepestAscent variant, so use with caution.

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 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
• 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
• With only allele_range(s) set on genotype:
  • Mutate uniformly over the complete allele range
    • Sample single random value for HillClimbVariant::Stochastic
    • Not valid for HillClimbVariant::SteepestAscent
  • Standard max_stale_generations ending condition

Using scaling for HillClimbVariant::StochasticSecondary and HillClimbVariant::SteepestAscentSecondary doesn’t make sense, though it will work.

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

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 and HillClimbVariant::StochasticSecondary 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(10)                    // ending condition if sum of genes is <= 0.00010 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 chromosome after all
let best_chromosome = hill_climb.best_chromosome().unwrap();
assert_eq!(best_chromosome.genes.into_iter().map(|v| v <= 1e-3).collect::<Vec<_>>(), vec![true; 16])

Fields

genotype: G

fitness: F

config: HillClimbConfig

state: HillClimbState<G::Allele>

reporter: SR

rng: SmallRng

Implementations

impl<G: IncrementalGenotype, F: Fitness<Allele = G::Allele>> HillClimb<G, F, HillClimbReporterNoop<G::Allele>>

pub fn builder() -> HillClimbBuilder<G, F, HillClimbReporterNoop<G::Allele>>

Trait Implementations

impl<G: IncrementalGenotype, F: Fitness<Allele = G::Allele>, SR: HillClimbReporter<Allele = G::Allele>> Display for HillClimb<G, F, SR>

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

Formats the value using the given formatter.

impl<G: IncrementalGenotype, F: Fitness<Allele = G::Allele>, SR: HillClimbReporter<Allele = G::Allele>> Strategy<G> for HillClimb<G, F, SR>

fn call(&mut self)

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

fn best_generation(&self) -> usize

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

impl<G: IncrementalGenotype, F: Fitness<Allele = G::Allele>, SR: HillClimbReporter<Allele = G::Allele>> TryFrom<Builder<G, F, SR>> for HillClimb<G, F, SR>

type Error = TryFromBuilderError

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.