genetic_algorithm 0.27.1

A genetic algorithm implementation
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

use super::{Extension, ExtensionEvent};
use crate::genotype::EvolveGenotype;
use crate::strategy::evolve::{EvolveConfig, EvolveState};
use crate::strategy::{StrategyAction, StrategyReporter, StrategyState};
use rand::Rng;
use std::marker::PhantomData;
use std::time::Instant;

/// Simulates a cambrian explosion. The controlling metric is population cardinality in the
/// population after selection. When this cardinality drops to the threshold, the population is
/// mutated the provided number of times, where the [Genotype](crate::genotype::Genotype)
/// determines whether this is random, relative or scaled. The elitism_rate ensures the passing of
/// the best chromosomes before mutations are applied (doesn't care about best chromosome
/// uniqueness).
///
/// Duplicate mutations of the same gene are allowed. There is no change in population size.
#[derive(Debug, Clone)]
pub struct MassDegeneration<G: EvolveGenotype> {
    _phantom: PhantomData<G>,
    pub cardinality_threshold: usize,
    pub number_of_mutations: usize,
    pub elitism_rate: f32,
}

impl<G: EvolveGenotype> Extension for MassDegeneration<G> {
    type Genotype = G;

    fn after_selection_complete<R: Rng, SR: StrategyReporter<Genotype = G>>(
        &mut self,
        genotype: &mut G,
        state: &mut EvolveState<G>,
        config: &EvolveConfig,
        reporter: &mut SR,
        rng: &mut R,
    ) {
        if state.population.size() >= config.target_population_size {
            let now = Instant::now();
            if let Some(cardinality) = state.population_cardinality() {
                if cardinality <= self.cardinality_threshold {
                    reporter.on_extension_event(
                        ExtensionEvent("MassDegeneration".to_string()),
                        genotype,
                        state,
                        config,
                    );
                    let population_size = state.population.size();

                    let elitism_size = ((population_size as f32 * self.elitism_rate).ceil()
                        as usize)
                        .min(population_size);
                    let mut elite_chromosomes =
                        self.extract_elite_chromosomes(genotype, state, config, elitism_size);
                    let elitism_size = elite_chromosomes.len();

                    for chromosome in state.population.chromosomes.iter_mut() {
                        genotype.mutate_chromosome_genes(
                            self.number_of_mutations,
                            true,
                            chromosome,
                            rng,
                        );
                    }

                    state.population.chromosomes.append(&mut elite_chromosomes);
                    // move back to front, elite_chromosomes internally unordered
                    for i in 0..elitism_size {
                        state
                            .population
                            .chromosomes
                            .swap(i, population_size - 1 - i);
                    }
                }
            }
            state.add_duration(StrategyAction::Extension, now.elapsed());
        }
    }
}

impl<G: EvolveGenotype> MassDegeneration<G> {
    /// Create a new MassDegeneration extension. Triggers when population diversity drops below threshold.
    /// Applies rounds of random mutation to non-elite chromosomes.
    /// * `cardinality_threshold` - trigger when unique chromosomes drop below this count
    /// * `number_of_rounds` - number of rounds of random mutation applied
    /// * `elitism_rate` - fraction of elite chromosomes preserved during degeneration
    pub fn new(cardinality_threshold: usize, number_of_rounds: usize, elitism_rate: f32) -> Self {
        Self {
            _phantom: PhantomData,
            cardinality_threshold,
            number_of_mutations: number_of_rounds,
            elitism_rate,
        }
    }
}