darwin_rs/simulation.rs
1//! This module defines structures and methods for an EA simulation.
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 std::time::Instant;
17
18use jobsteal::make_pool;
19
20use individual::{Individual, IndividualWrapper};
21use population::Population;
22
23/// The `SimulationType` type. Speficies the criteria on how a simulation should stop.
24#[derive(Debug,Clone)]
25pub enum SimulationType {
26 /// Finish the simulation when a number of iteration has been reached.
27 EndIteration(u32),
28 /// Finish the simulation when a specific fitness is rached.
29 /// That means if at least one of the individuals has this fitness.
30 /// The fitness is calculated using the implemented `calculate_fitness` functions
31 /// of the `Individual` trait.
32 EndFitness(f64),
33 /// Finish the simulation when a specific improvement factor is reached.
34 /// That means the relation between the very first fitness and the current fitness of the
35 /// fittest individual.
36 EndFactor(f64),
37}
38
39/// The `Simulation` type. Contains all the information / configuration for the simulation to run.
40/// Use the `SimulationBuilder` in order to create a simulation.
41pub struct Simulation<T: Individual + Send + Sync> {
42 /// How should the simulation stop ?
43 pub type_of_simulation: SimulationType,
44 /// The number of threads to use to speed up calculation.
45 pub num_of_threads: usize,
46 /// All the populations for the simulation. Contains all individuals for the simulation.
47 pub habitat: Vec<Population<T>>,
48 /// The total run time for the simulation. This will be calculated once the stimulation has
49 /// finished.
50 pub total_time_in_ms: f64,
51 /// The result of the simulation: `improvement_factor`, `original_fitness` and a vector of
52 /// fittest individuals.
53 pub simulation_result: SimulationResult<T>,
54 /// If this feature is enabled, then the most fittest individual of all populations is
55 /// shared between all the populations.
56 pub share_fittest: bool,
57 /// The total number of global fittest individual to keep, default: 10
58 /// After each interation the most fittest individual of all populations is determinded.
59 /// And this individual is copied into a global "high score list" of the whole simulation,
60 /// if it is better then the highest entry.
61 /// This number specifies how many of these global individuals should be kept.
62 /// (i.e. the size of the "high score list")
63 pub num_of_global_fittest: usize,
64 /// Do not output every time a new fittest individual is found, only every nth times.
65 /// n == output_every
66 pub output_every: u32,
67 /// Counter that will be incremented every iteration. If output_every_counter > output_every then
68 /// the new fittest individual will be written to the log.
69 pub output_every_counter: u32,
70 /// Only share the most fittest individual between the populations if the counter reaches
71 /// this value: share_counter >= share_every.
72 pub share_every: u32,
73 /// Counter that will be incremented every iteration. If share_counter >= share_every then the
74 /// most fittest individual is shared between all the populations.
75 pub share_counter: u32
76}
77
78/// The `SimulationResult` Type. Holds the simulation results:
79/// All the fittest individuals, the `improvement_factor`, the `iteration_counter` and the
80/// `original_fitness`.
81#[derive(Clone)]
82pub struct SimulationResult<T: Individual + Send + Sync> {
83 /// The current improvement factor, that means the ration between the very first and the
84 /// current fitness.
85 pub improvement_factor: f64,
86 /// The very first calculated fitness, when the simulation just started.
87 pub original_fitness: f64,
88 /// Vector of fittest individuals. This will change during the simulation as soon as a new
89 /// more fittest individual is found and pushed into the first position (index 0).
90 pub fittest: Vec<IndividualWrapper<T>>,
91 /// How many iteration did the simulation run.
92 pub iteration_counter: u32
93}
94
95/// This implements the the functions `run`, `print_fitness` and `update_results` (private)
96/// for the struct `Simulation`.
97impl<T: Individual + Send + Sync + Clone> Simulation<T> {
98 /// This actually runs the simulation.
99 /// Depending on the type of simulation (`EndIteration`, `EndFactor` or `EndFitness`)
100 /// the iteration loop will check for the stop condition accordingly.
101 pub fn run(&mut self) {
102 // Initialize timer
103 let start_time = Instant::now();
104
105 // Calculate the fitness for all individuals in all populations at the beginning.
106 for population in &mut self.habitat {
107 population.calculate_fitness();
108 }
109
110 let mut iteration_counter = 0;
111 let mut pool = make_pool(self.num_of_threads).unwrap();
112
113 // Initialize:
114 // - The fittest individual.
115 // - The fitness at the beginning of the simulation. This is uesed to calculate the
116 // overall improvement later on.
117 self.simulation_result = SimulationResult {
118 improvement_factor: 0.0,
119 original_fitness: self.habitat[0].population[0].fitness,
120 fittest: vec![self.habitat[0].population[0].clone()],
121 iteration_counter: 0
122 };
123
124 info!("original_fitness: {}", self.simulation_result.original_fitness);
125
126 // Check which type of simulation to run.
127 match self.type_of_simulation {
128 SimulationType::EndIteration(end_iteration) => {
129 for _ in 0..end_iteration {
130 pool.scope(|scope|
131 for population in &mut self.habitat {
132 scope.submit(move || { population.run_body() });
133 });
134
135 self.update_results();
136 };
137 self.simulation_result.iteration_counter = end_iteration;
138 }
139
140 SimulationType::EndFactor(end_factor) => {
141 loop {
142 iteration_counter += 1;
143 pool.scope(|scope|
144 for population in &mut self.habitat {
145 scope.submit(move || { population.run_body() });
146 });
147
148 self.update_results();
149
150 if self.simulation_result.improvement_factor <= end_factor {
151 break;
152 }
153 };
154 self.simulation_result.iteration_counter = iteration_counter;
155 }
156
157 SimulationType::EndFitness(end_fitness) => {
158 loop {
159 iteration_counter += 1;
160 pool.scope(|scope|
161 for population in &mut self.habitat {
162 scope.submit(move || { population.run_body() });
163 });
164
165 self.update_results();
166
167 if self.simulation_result.fittest[0].fitness <= end_fitness {
168 break;
169 }
170 };
171 self.simulation_result.iteration_counter = iteration_counter;
172 }
173 } // End of match
174
175 let elapsed = start_time.elapsed();
176
177 self.total_time_in_ms = elapsed.as_secs() as f64 * 1000.0 + elapsed.subsec_nanos() as f64 / 1000_000.0;
178 }
179
180 /// This is a helper function that the user can call after the simulation stops in order to
181 /// see all the fitness values for all the individuals that participated to the overall
182 /// improvement.
183 pub fn print_fitness(&self) {
184 for wrapper in &self.simulation_result.fittest {
185 info!("fitness: {}, num_of_mutations: {}, population: {}",
186 wrapper.fitness, wrapper.num_of_mutations, wrapper.id);
187 }
188 }
189
190 /// Update the internal state of the simulation: Has a new fittest individual been found ?
191 /// Do we want to share it across all the other populations ?
192 /// Also calculates the improvement factor.
193 fn update_results(&mut self) {
194 // Determine the fittest individual of all populations.
195 let mut new_fittest_found = false;
196
197 // Increment the output counter
198 // Only write an output if the max value output_every is reached
199 self.output_every_counter += 1;
200
201 for population in &mut self.habitat {
202 if population.population[0].fitness < self.simulation_result.fittest[0].fitness {
203 new_fittest_found = true;
204 self.simulation_result.fittest.insert(0, population.population[0].clone());
205 // See https://github.com/willi-kappler/darwin-rs/issues/12
206 self.simulation_result.fittest.truncate(self.num_of_global_fittest);
207 population.fitness_counter += 1;
208 if self.output_every_counter >= self.output_every {
209 info!("new fittest: fitness: {}, population id: {}, counter: {}", population.population[0].fitness,population.id,
210 population.fitness_counter);
211 self.output_every_counter = 0
212 }
213 // Call methond `new_fittest_found` of the newly found fittest individual.
214 // The default implementation for this method does nothing.
215 population.population[0].individual.new_fittest_found();
216 }
217 }
218
219 // Now copy the most fittest individual back to each population
220 // if the user has specified it and the share_every count is reached
221 self.share_counter += 1;
222 if self.share_fittest && new_fittest_found && (self.share_counter >= self.share_every) {
223 for population in &mut self.habitat {
224 population.population[0] = self.simulation_result.fittest[0].clone();
225 }
226 self.share_counter = 0;
227 }
228
229 self.simulation_result.improvement_factor =
230 self.simulation_result.fittest[0].fitness /
231 self.simulation_result.original_fitness;
232
233 }
234}