darwin_rs/population.rs
1//! This module defines structure and methods for a population that is needed by a smulation.
2//!
3//! darwin-rs: evolutionary algorithms with Rust
4//!
5//! Written by Willi Kappler, Version 0.4 (2017.06.26)
6//!
7//! Repository: https://github.com/willi-kappler/darwin-rs
8//!
9//! License: MIT
10//!
11//! This library allows you to write evolutionary algorithms (EA) in Rust.
12//! Examples provided: TSP, Sudoku, Queens Problem, OCR
13//!
14//!
15
16use individual::{Individual, IndividualWrapper};
17
18/// The `Population` type. Contains the actual individuals (through a wrapper) and informations
19/// like the `reset_limit`. Use the `PopulationBuilder` in your main program to create populations.
20#[derive(Clone)]
21pub struct Population<T: Individual> {
22 /// The number of individuals for this population.
23 pub num_of_individuals: u32,
24 /// The actual population (vector of individuals).
25 pub population: Vec<IndividualWrapper<T>>,
26 /// The amount of iteration to wait until all individuals will be resetted.
27 /// This calls the `reset` method for each individual.
28 pub reset_limit: u32,
29 /// The start value of the reset limit.
30 pub reset_limit_start: u32,
31 /// The end value of the reset limit, if `reset_limit` >= `reset_limit_end`, then the `reset_limit`
32 /// will be resettet to the start value `reset_limit_start`.
33 /// If `reset_limit_end` == 0, this feature will be disabled.
34 pub reset_limit_end: u32,
35 /// The increment for the `reset_limit`. After the reset_limit value is reached, it will be
36 /// increased by the value of `reset_limit_increment`.
37 pub reset_limit_increment: u32,
38 /// The reset counter, if `reset_counter` >= `reset_limit`, all the individuals are discarded and
39 /// the simulation restarts anew with an increased `reset_limit`. This prevents local minima,
40 /// but also discards the current fittest individual.
41 pub reset_counter: u32,
42 /// The ID of the population, only used for statistics. For example: which population does
43 /// have the most fittest individuals ? This may help you to set the correct parameters for
44 /// your simulations.
45 pub id: u32,
46 /// Count how often this population has created (found) the fittest individual. This may help
47 /// you to fine tune the parameters for the population and the simulation in general.
48 pub fitness_counter: u64
49}
50
51impl<T: Individual + Send + Sync + Clone> Population<T> {
52 /// Just calculates the fitness for each individual.
53 /// Usually this is the most computational expensive operation, so optimize the
54 /// `calculate_fitness` method of your data structure ;-)
55 pub fn calculate_fitness(&mut self) {
56 for wrapper in &mut self.population {
57 wrapper.fitness = wrapper.individual.calculate_fitness();
58 }
59 }
60
61 /// This is the body that gets called for every iteration.
62 /// This function does the following:
63 ///
64 /// 1. Check if the reset limit is reached. If it is, this whole population is
65 /// discarded and re-initialized from the start. All the information about the
66 /// current fittest individual is lost. This is done to avoid local minima.
67 ///
68 /// 2. Clone the current population.
69 ///
70 /// 3. Mutate the current population using the `mutate_population` function.
71 ///
72 /// 4. Merge the newly mutated population and the original cloned population into one big
73 /// population twice the size.
74 ///
75 /// 5. Sort this new big population by fitness. So the fittest individual is at position 0.
76 ///
77 /// 6. Truncated the big population to its original size and thus gets rid of all the less fittest
78 /// individuals (they "die").
79 ///
80 /// 7. Check if the fittest individual (at index 0) in the current sorted population is better
81 /// (= fitter) than the global fittest individual of the whole simulation. If yes, the global
82 /// fittest individual is replaced.
83 ///
84 /// 8. Calculate the new improvement factor and prepare for the next iteration.
85 pub fn run_body(&mut self) {
86 // Is reset limit enabled ?
87 if self.reset_limit_end > 0 {
88 self.reset_counter += 1;
89
90 // Check if reset limit is reached
91 if self.reset_counter > self.reset_limit {
92 self.reset_limit += self.reset_limit_increment;
93 if self.reset_limit >= self.reset_limit_end {
94 self.reset_limit = self.reset_limit_start;
95 info!("reset_limit reset to reset_limit_start: {}, id: {}", self.reset_limit_start, self.id);
96 }
97 self.reset_counter = 0;
98 info!("new reset_limit: {}, id: {}, counter: {}", self.reset_limit, self.id, self.fitness_counter);
99
100 // Kill all individuals since we are most likely stuck in a local minimum.
101 // Why is it so ? Because the simulation is still running and the exit criteria
102 // hasn't been reached yet!
103 // Keep number of mutations.
104 for wrapper in &mut self.population {
105 wrapper.individual.reset();
106 wrapper.fitness = wrapper.individual.calculate_fitness();
107 }
108 }
109 }
110
111 // Keep original population.
112 let orig_population = self.population.clone();
113
114 // Mutate population
115 for wrapper in &mut self.population {
116 for _ in 0..wrapper.num_of_mutations {
117 // Maybe add super optimization ?
118 // See https://github.com/willi-kappler/darwin-rs/issues/10
119 wrapper.individual.mutate();
120 }
121 wrapper.fitness = wrapper.individual.calculate_fitness();
122 }
123
124 // Append original (unmutated) population to new (mutated) population.
125 self.population.extend(orig_population.iter().cloned());
126
127 // Sort by fitness
128 // Use random choice, see https://github.com/willi-kappler/darwin-rs/issues/7
129 self.population.sort();
130
131 // Reduce population to original length.
132 self.population.truncate(self.num_of_individuals as usize);
133
134 // Restore original number of mutation rate, since these will be lost because of sorting.
135 for (individual, orig_individual) in self.population
136 .iter_mut()
137 .zip(orig_population.iter()) {
138 individual.num_of_mutations = orig_individual.num_of_mutations;
139 }
140 }
141}