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
/// randomly reduced regardless of fitness using the survival_rate (fraction of population). The
/// elitism_rate ensures the passing of the best chromosomes before random reduction starts
/// (doesn't care about best chromosome uniqueness).
///
/// Population will recover in the following generations
#[derive(Debug, Clone)]
pub struct MassExtinction<G: EvolveGenotype> {
    _phantom: PhantomData<G>,
    pub cardinality_threshold: usize,
    pub survival_rate: f32,
    pub elitism_rate: f32,
}

impl<G: EvolveGenotype> Extension for MassExtinction<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("MassExtinction".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();

                    let remaining_size: usize = ((population_size as f32 * self.survival_rate)
                        .ceil() as usize)
                        .min(population_size)
                        .max(2);

                    let remaining_size = remaining_size.saturating_sub(elitism_size);

                    state.population.shuffle(rng);
                    state.population.truncate(remaining_size);

                    state.population.chromosomes.append(&mut elite_chromosomes);
                    let population_size = state.population.size();
                    // 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> MassExtinction<G> {
    /// Create a new MassExtinction extension. Triggers when population diversity drops below threshold.
    /// * `cardinality_threshold` - trigger when unique chromosomes drop below this count
    /// * `survival_rate` - fraction of population that survives the extinction event
    /// * `elitism_rate` - fraction of elite chromosomes preserved during extinction
    pub fn new(cardinality_threshold: usize, survival_rate: f32, elitism_rate: f32) -> Self {
        Self {
            _phantom: PhantomData,
            cardinality_threshold,
            survival_rate,
            elitism_rate,
        }
    }
}