genetic_algorithm_traits/
population.rs

1use crate::individual::Individual;
2use crate::utils::argsort;
3
4/// The container for your individuals in a genetic algorithm.
5pub trait Population<'a> {
6    /// The Type of individuals your population should consist of.
7    type Individual: Individual<'a> + 'a;
8    /// The iteratore type if you iterate over your individuals. It depends on the data container you use
9    /// to store individuals in your implementation of `Population`.
10    type IndividualCollection: Iterator<Item = &'a <Self as Population<'a>>::Individual>;
11    /// Given the pool of current individuals, compute the fitness of your individuals to solve the
12    /// problem at hand.
13    ///
14    /// # Arguments
15    ///
16    /// * `cost_data` - The data neccessary to assess the fitness of an individual.
17    ///
18    fn fitnesses(
19        &'a self,
20        cost_data: &'a <<Self as Population<'a>>::Individual as Individual<'a>>::IndividualCost,
21    ) -> Vec<(f64, &Self::Individual)> {
22        self.iter()
23            .map(|solution| (solution.fitness(cost_data), solution))
24            .collect()
25    }
26    /// Get the n fittest individuals in your population.
27    ///
28    /// # Arguments
29    ///
30    /// * `n` - The number of individuals you would like to get
31    /// * `cost_data` - The cost data structure your individuals need to compute
32    /// their fitness.
33    ///
34    fn get_n_fittest(
35        &'a self,
36        n: usize,
37        cost_data: &'a <<Self as Population<'a>>::Individual as Individual<'a>>::IndividualCost,
38    ) -> Vec<Self::Individual> {
39        let individuals_by_fitness = self.fitnesses(cost_data);
40        argsort(
41            &individuals_by_fitness
42                .iter()
43                .map(|(fitness, _)| *fitness)
44                .collect::<Vec<f64>>(),
45        )
46        .iter()
47        .take(n)
48        .map(|idx| individuals_by_fitness[*idx].1.clone())
49        .collect()
50    }
51    /// Get the n fittest individuals in your population as population routes object. This is typically used
52    /// to select the top n inidividuals, before continuing to evolve the routes further.
53    ///
54    /// # Arguments
55    ///
56    /// * `n` - The number of individuals you would like to have.
57    /// * `cost_data` - The cost data structure your indivudals need to compute their fitness.
58    ///
59    fn get_fittest_population(
60        &'a self,
61        n: usize,
62        cost_data: &'a <<Self as Population<'a>>::Individual as Individual<'a>>::IndividualCost,
63    ) -> Self;
64    /// Evolve your population.
65    ///
66    /// The evolution consists of the following stages:
67    /// 1) `crossover` between all 1,...,n indivials. Each individual will not be `crossover`ed
68    /// with itself, but as the crossover is not neccessarily symmetric `indivdual_a.crossover(indivual_b)` as well
69    /// as `individual_b.crossover(individual_a)` will be computed.
70    /// 2) `mutate` is applied to all individuals.
71    ///
72    /// The difference to the `evolve_individuals` function is that this needs to be implemented in the struct
73    /// that implements this trait because how the population is constructed depends on the representation you
74    /// choose to use. Please use the `evolve_individuals`-function to get the updated inviduals. You could use an
75    /// iterator or implement the `From<Vec<Individuals>>`-trait.
76    ///
77    /// # Arguments
78    ///
79    /// * `mutate_prob` - The probabilty of an inviduals beeing mutated. Is applied via `individuals.mutate`.
80    fn evolve(&self, mutate_prob: f32) -> Self;
81    /// Evolve your population.
82    ///
83    /// The evolution consists of the following stages:
84    /// 1) `crossover` between all 1,...,n indivials. Each individual will not be `crossover`ed
85    /// with itself, but as the crossover is not neccessarily symmetric `indivdual_a.crossover(indivual_b)` as well
86    /// as `individual_b.crossover(individual_a)` will be computed.
87    /// 2) `mutate` is applied to all individuals.
88    ///
89    /// # Arguments
90    ///
91    /// * `mutate_prob` - The probabilty of an inviduals beeing mutated. Is applied via `individuals.mutate`.
92    // TODO: I only use `Vec` here because the type of the iterator is too complicated.
93    // this creates overhead and should be optimized
94    fn evolve_individuals(&'a self, mutate_prob: f32) -> Vec<Self::Individual> {
95        self
96            // for all individuals 1 .. n crossover with all other individuals excluding the same individual.
97            .iter()
98            .enumerate()
99            .map(|(idx, main_individual)| {
100                self.iter()
101                    // Skip the individual itself, e.g. don't crossover the individual with itself.
102                    .enumerate()
103                    .filter(move |&(individual_index, _)| individual_index != idx)
104                    .map(|(_, individual)| {
105                        main_individual.crossover(individual).mutate(mutate_prob)
106                    })
107            })
108            .flatten()
109            .chain(self.iter().cloned())
110            .collect()
111    }
112    /// Iterate over the individuals in your population.
113    fn iter(&'a self) -> Self::IndividualCollection;
114}
genetic_algorithm_traits/population.rs

genetic_algorithm_traits/
population.rs
