Struct genetic_algorithm::strategy::hill_climb::HillClimb

pub struct HillClimb<G: IncrementalGenotype, F: Fitness<Genotype = G>> {
    pub config: HillClimbConfig,
    pub state: HillClimbState<G>,
    /* private fields */
}

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 amount of improvement in that neighbor) whether to move to that neighbor or to examine another
• HillClimbVariant::SteepestAscent: all neighbours are compared and the closest to the solution 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
• min_scale: when the scaling drops below the precision and further refining is useless

The fitness is calculated each round:

• If the fitness is worse
  • the mutation is ignored and the next round is started based on the current best chromosome
  • if the scaling is set, the scale is reduced to zoom in on the local solution
  • the stale generation counter is incremented (functionally)
• If the fitness is equal
  • the mutated chromosome is taken for the next round.
  • if the scaling is set, the scale is reduced to zoom in on the local solution
  • the stale generation counter is incremented (functionally)
• If the fitness is better
  • the mutated chromosome is taken for the next round.
  • if the scaling is set, the scale is reset to its base scale
  • the stale generation counter is reset (functionally)

See HillClimbBuilder for initialization options.

Example:

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

// the search space
let genotype = ContinuousGenotype::builder() // f32 alleles
    .with_genes_size(16)                     // 16 genes
    .with_allele_range(0.0..1.0)             // values betwee 0.0 and 1.0
    .with_allele_neighbour_range(-0.1..0.1)  // neighbouring step size or 0.1 in both directions
    .build()
    .unwrap();

// the search strategy
let mut rng = rand::thread_rng(); // unused randomness provider implementing Trait rand::Rng
let hill_climb = HillClimb::builder()
    .with_genotype(genotype)
    .with_variant(HillClimbVariant::SteepestAscent) // check all neighbours for each round
    .with_fitness(SumContinuousGenotype(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_multithreading(true)                 // use all cores for calculating the fitness of the neighbouring_population (only used with HillClimbVariant::SteepestAscent)
    .with_scaling(Scaling::new(1.0, 0.8, 1e-5))  // start with neighbouring mutation scale 1.0 and multiply by 0.8 to zoom in on solution when stale, halt at 1e-5 scale
    .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
    .call(&mut rng)
    .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

config: HillClimbConfig

state: HillClimbState<G>

Implementations

impl<G: IncrementalGenotype, F: Fitness<Genotype = G>> HillClimb<G, F>

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

Trait Implementations

impl<G: IncrementalGenotype, F: Fitness<Genotype = G>> Display for HillClimb<G, F>

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

Formats the value using the given formatter.

impl<G: IncrementalGenotype, F: Fitness<Genotype = G>> Strategy<G> for HillClimb<G, F>

fn call<R: Rng>(&mut self, rng: &mut R)

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

fn best_generation(&self) -> usize

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

impl<G: IncrementalGenotype, F: Fitness<Genotype = G>> TryFrom<Builder<G, F>> for HillClimb<G, F>

type Error = TryFromBuilderError

The type returned in the event of a conversion error.

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

Performs the conversion.