chromosome/
selector.rs

1use alloc::vec::Vec;
2
3use crate::{cascade_sum::cascade_sum, chromosome::Chromosome};
4
5fn invert_normalize<T, I: Iterator<Item = T>>(values: I) -> impl Iterator<Item = f64>
6where
7    T: Into<f64> + Clone,
8    I: Clone,
9{
10    let coefficients = values.map(|v| -> f64 { 1_f64 / v.into() });
11    let sum: f64 = coefficients.clone().sum();
12    coefficients.map(move |v| v / sum)
13}
14
15#[cfg(test)]
16mod tests {
17    use alloc::vec::Vec;
18
19    #[test]
20    fn invert_normalize_test() {
21        use crate::selector::invert_normalize;
22        assert_eq!(
23            invert_normalize(vec![2, 4, 8, 8].into_iter()).collect::<Vec<_>>(),
24            vec![0.5, 0.25, 0.125, 0.125]
25        );
26    }
27}
28
29/// Genetic selector
30pub trait Selector<T> {
31    /// select_chromosome - selects not worst chromosomes with some random from vec
32    fn select_chromosome<R: rand::RngCore>(
33        &self,
34        chromosomes: &[Chromosome<T>],
35        rng: &mut R,
36    ) -> Vec<Chromosome<T>>;
37    /// return true if chromosome is ideal (solution of problem)
38    fn is_ideal_chromosome(&self, chromosome: &Chromosome<T>) -> bool;
39}
40
41/// Fitness trait provides interface for finging fitness value for chromosome
42///
43/// fitness value - the smaller it is, the closer the chromosome is to the ideal (more adapted). if 0 is an ideal chromosome (solution of the problem)
44///
45pub trait Fitness {
46    type Value;
47    fn fitness(&self, chromosome: &Chromosome<Self::Value>) -> Self::Value;
48    fn is_ideal_fitness(&self, fitness: Self::Value) -> bool;
49}
50
51/// FitnessSelector selects chromosomes by fitness values
52///
53/// Math:
54///
55/// S = 1 / f(c0) + 1 / f(c1) + ... + 1 / f(cn)
56/// chances = { 1 / f(c0) / S, 1 / f(c1) / S, ..., 1 / f(cn) / S }
57/// where f is fitness function
58///
59/// then selector random select N chromosomes with its select chance
60/// where N is len of input chromosomes vec
61///
62#[derive(Debug)]
63pub struct FitnessSelector<F> {
64    fitness: F,
65}
66
67impl<F: Fitness> From<F> for FitnessSelector<F> {
68    fn from(value: F) -> Self {
69        FitnessSelector { fitness: value }
70    }
71}
72
73fn abs64(v: f64) -> f64 {
74    #[cfg(feature = "std")]
75    {
76        v.abs()
77    }
78    #[cfg(not(feature = "std"))]
79    if v >= 0. {
80        v
81    } else {
82        -v
83    }
84}
85
86impl<T: Into<f64> + Clone, F: Fitness<Value = T>> Selector<T> for FitnessSelector<F> {
87    fn select_chromosome<R: rand::RngCore>(
88        &self,
89        chromosomes: &[Chromosome<T>],
90        rng: &mut R,
91    ) -> Vec<Chromosome<T>> {
92        let fitness = chromosomes.iter().map(|c| self.fitness.fitness(c));
93        let nfv = cascade_sum(invert_normalize(fitness).map(abs64).collect());
94
95        let mut result: Vec<Chromosome<T>> = Vec::with_capacity(chromosomes.len());
96        while result.len() < chromosomes.len() {
97            match nfv.random_index(rng) {
98                Some(i) => result.push(chromosomes[i].clone()),
99                _ => {}
100            };
101        }
102        result
103    }
104
105    fn is_ideal_chromosome(&self, chromosome: &Chromosome<T>) -> bool {
106        self.fitness
107            .is_ideal_fitness(self.fitness.fitness(chromosome))
108    }
109}
chromosome/selector.rs

chromosome/
selector.rs
