pub struct Evolve<G: Genotype, M: Mutate, F: Fitness<Genotype = G>, S: Crossover, C: Compete> {
pub current_iteration: usize,
pub current_generation: usize,
pub degenerate: bool,
pub best_generation: usize,
/* private fields */
}Expand description
The Evolve strategy initializes with a random population of chromosomes (unless the genotype seeds specific genes to start with). Then the Evolve strategy runs through generations of chromosomes in a loop:
- crossover to produce new offspring with a mix of parents chromosome genes
- mutate a subset of chromosomes to add some additional diversity
- calculate fitness for all chromosomes
- compete to pair up chromosomes for crossover in next generation and drop excess chromosomes
- store best chromosome
- 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
Optionally a degeneration_range can be set. When approacking a (local) optimum in the fitness score, the variation in the population goes down dramatically. This reduces the efficiency, but also has the risk of local optimum lock-in. Set this parameter to simulate a cambrian explosion, where there is only mutation until the population diversity is large enough again. The controlling metric is fitness score standard deviation in the population. The degeneration has a hysteresis switch, where the degeneration is activated at the start bound of the range, and deactivated at the end bound of the range. The lower bound should be around zero or slightly above (meaning no variation left in population). The higher bound is more difficult to configure, as it depends on the fitness function behaviour (expected spread per mutation). So the higher bound is a case by case analysis.
Can call_repeatedly from the EvolveBuilder, when solution has tendency to get stuck in local optimum
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
.build()
.unwrap();
// the search strategy
let mut rng = rand::thread_rng(); // a randomness provider implementing Trait rand::Rng
let evolve = Evolve::builder()
.with_genotype(genotype)
.with_population_size(100) // evolve with 100 chromosomes
.with_target_fitness_score(0) // goal is 0 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_degeneration_range(0.005..0.995) // simulate cambrian explosion when reaching a local optimum
.with_fitness(CountTrue) // count the number of true values in the chromosomes
.with_fitness_ordering(FitnessOrdering::Minimize) // aim for the least true values
.with_multithreading(true) // use all cores for calculating the fitness of the population
.with_crossover(CrossoverUniform(true)) // crossover all individual genes between 2 chromosomes for offspring
.with_mutate(MutateOnce(0.2)) // mutate a single gene with a 20% probability per chromosome
.with_compete(CompeteElite) // sort the chromosomes by fitness to determine crossover order
.call(&mut rng)
.unwrap();
// it's all about the best chromosome after all
let best_chromosome = evolve.best_chromosome().unwrap();
assert_eq!(best_chromosome.genes, vec![false; 100])Fields
current_iteration: usizecurrent_generation: usizedegenerate: boolbest_generation: usize