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