gas/gas/
generation.rs

1use super::Gas;
2use crate::candidate::Candidate;
3
4#[mockall_double::double]
5use crate::rando::Rando;
6
7#[cfg(doc)]
8use crate::crossover::Crossover;
9#[cfg(doc)]
10use crate::fitness::FitnessConfig;
11#[cfg(doc)]
12use crate::mutation::Mutation;
13#[cfg(doc)]
14use crate::tournaments::Tournament;
15
16/// Given one generation of candidates, create the next generation.   The heart of the GA.
17///
18/// Each generation consists of the following steps:
19///
20/// 1. Run a [Tournament] to order the candidates.
21/// 2. Loop for each new child:
22/// a.  Select two parents.  Parent selection is biased by [Tournament] score and prefers selecting dissimilar parents.
23/// b.  Choose a [Crossover] algorithm to run on the two parents to create a child.
24/// c.  Choose a [Mutation] algorithm to run on the child
25///
26/// These arguments could be calculated inside this function rather than
27/// outside, but are taken as parameters so they don't have to be recalculated
28/// every generation:
29///
30/// * `rng`: pass [`Rando::new()`]
31/// * `score_weights`: pass [`FitnessConfig::weights()`] from [`Gas::fitness`]
32
33impl<const N: usize, const NSYMS: usize> Gas<N, NSYMS> {
34    pub fn generation(
35        &self,
36        population: &Vec<Candidate<N, NSYMS>>,
37        rng: &mut Rando,
38        score_weights: &Vec<f64>,
39    ) -> Vec<Candidate<N, NSYMS>> {
40        let mut nextgen = Vec::<Candidate<N, NSYMS>>::with_capacity(population.len());
41
42        // tournament phase
43        let (winner, weights) = self.cycle_tournament.run(&population, rng, score_weights);
44        nextgen.push(winner);
45        let mut popdist = rng.weighted_iter(&weights);
46
47        // crossover and mutation phase
48        let mut crossover_iter = self.crossovers.iter();
49        let mut mutation_iter = self.mutations.iter();
50
51        // 0 was winner of tournament, already pushed to nextgen
52        for _ in 1..population.len() {
53            let mut chromosone;
54            loop {
55                let left = &population[popdist.next().unwrap()];
56                let mut right;
57                let mut i = 0;
58                loop {
59                    right = &population[popdist.next().unwrap()];
60                    if left != right {
61                        if left.distance(&right) > self.taboo_distance {
62                            break;
63                        }
64                    }
65                    i += 1;
66                    if i > population.len() {
67                        eprintln!("TABOO!");
68                        break;
69                    }
70                }
71                let crossover = crossover_iter.next().unwrap();
72                let mutation = mutation_iter.next().unwrap();
73                chromosone = crossover.run(&left.chromosone, &right.chromosone, rng);
74                chromosone = mutation.run(&chromosone, rng);
75                if !nextgen.iter().any(|c| c.chromosone == chromosone) {
76                    break;
77                }
78            }
79            nextgen.push(Candidate::from_chromosone(&self, chromosone));
80        }
81
82        nextgen
83    }
84}
85
86#[cfg(test)]
87mod tests {
88    use super::*;
89
90    use mockall::predicate;
91
92    #[test]
93    fn test_generation() {
94        let gas = Gas::<5, 3>::dut();
95        let mut r = Rando::default();
96        r.expect_shuffle().times(1).return_const(()); // used by single_elimination_tournament
97        r.expect_weighted_iter() // used by generation to select parents
98            .times(1)
99            .return_const([0, 1].iter().cloned());
100        r.expect_gen_range() // used by mutate
101            .with(predicate::eq(0..5))
102            .times(1)
103            .return_const(1usize);
104        r.expect_gen_range() // used by mutate
105            .with(predicate::eq(0..3))
106            .times(1)
107            .return_const(1usize);
108
109        let pop = &mut vec![
110            Candidate::from_chromosone(&gas, [0, 0, 0, 0, 0]),
111            Candidate::from_chromosone(&gas, [1, 0, 1, 0, 1]),
112        ];
113        let nextgen = gas.generation(&pop, &mut r, &vec![1.0; 9]);
114        // second candidate has to win the tournament
115        Candidate::assert_eq(
116            &nextgen[0],
117            &Candidate::from_chromosone(&gas, [1, 0, 1, 0, 1]),
118        );
119    }
120}
gas/gas/generation.rs

gas/gas/
generation.rs
