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
//! This module defines structure and methods for a population that is needed by a smulation. //! //! 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 individual::{Individual, IndividualWrapper}; /// The `Population` type. Contains the actual individuals (through a wrapper) and informations /// like the `reset_limit`. Use the `PopulationBuilder` in your main program to create populations. #[derive(Clone)] pub struct Population<T: Individual> { /// The number of individuals for this population. pub num_of_individuals: u32, /// The actual population (vector of individuals). pub population: Vec<IndividualWrapper<T>>, /// The amount of iteration to wait until all individuals will be resetted. /// This calls the `reset` method for each individual. pub reset_limit: u32, /// The start value of the reset limit. pub reset_limit_start: u32, /// The end value of the reset limit, if `reset_limit` >= `reset_limit_end`, then the `reset_limit` /// will be resettet to the start value `reset_limit_start`. /// If `reset_limit_end` == 0, this feature will be disabled. pub reset_limit_end: u32, /// The increment for the `reset_limit`. After the reset_limit value is reached, it will be /// increased by the value of `reset_limit_increment`. pub reset_limit_increment: u32, /// The reset counter, if `reset_counter` >= `reset_limit`, all the individuals are discarded and /// the simulation restarts anew with an increased `reset_limit`. This prevents local minima, /// but also discards the current fittest individual. pub reset_counter: u32, /// The ID of the population, only used for statistics. For example: which population does /// have the most fittest individuals ? This may help you to set the correct parameters for /// your simulations. pub id: u32, /// Count how often this population has created (found) the fittest individual. This may help /// you to fine tune the parameters for the population and the simulation in general. pub fitness_counter: u64 } impl<T: Individual + Send + Sync + Clone> Population<T> { /// Just calculates the fitness for each individual. /// Usually this is the most computational expensive operation, so optimize the /// `calculate_fitness` method of your data structure ;-) pub fn calculate_fitness(&mut self) { for wrapper in &mut self.population { wrapper.fitness = wrapper.individual.calculate_fitness(); } } /// This is the body that gets called for every iteration. /// This function does the following: /// /// 1. Check if the reset limit is reached. If it is, this whole population is /// discarded and re-initialized from the start. All the information about the /// current fittest individual is lost. This is done to avoid local minima. /// /// 2. Clone the current population. /// /// 3. Mutate the current population using the `mutate_population` function. /// /// 4. Merge the newly mutated population and the original cloned population into one big /// population twice the size. /// /// 5. Sort this new big population by fitness. So the fittest individual is at position 0. /// /// 6. Truncated the big population to its original size and thus gets rid of all the less fittest /// individuals (they "die"). /// /// 7. Check if the fittest individual (at index 0) in the current sorted population is better /// (= fitter) than the global fittest individual of the whole simulation. If yes, the global /// fittest individual is replaced. /// /// 8. Calculate the new improvement factor and prepare for the next iteration. pub fn run_body(&mut self) { // Is reset limit enabled ? if self.reset_limit_end > 0 { self.reset_counter += 1; // Check if reset limit is reached if self.reset_counter > self.reset_limit { self.reset_limit += self.reset_limit_increment; if self.reset_limit >= self.reset_limit_end { self.reset_limit = self.reset_limit_start; info!("reset_limit reset to reset_limit_start: {}, id: {}", self.reset_limit_start, self.id); } self.reset_counter = 0; info!("new reset_limit: {}, id: {}, counter: {}", self.reset_limit, self.id, self.fitness_counter); // Kill all individuals since we are most likely stuck in a local minimum. // Why is it so ? Because the simulation is still running and the exit criteria // hasn't been reached yet! // Keep number of mutations. for wrapper in &mut self.population { wrapper.individual.reset(); wrapper.fitness = wrapper.individual.calculate_fitness(); } } } // Keep original population. let orig_population = self.population.clone(); // Mutate population for wrapper in &mut self.population { for _ in 0..wrapper.num_of_mutations { // Maybe add super optimization ? // See https://github.com/willi-kappler/darwin-rs/issues/10 wrapper.individual.mutate(); } wrapper.fitness = wrapper.individual.calculate_fitness(); } // Append original (unmutated) population to new (mutated) population. self.population.extend(orig_population.iter().cloned()); // Sort by fitness // Use random choice, see https://github.com/willi-kappler/darwin-rs/issues/7 self.population.sort(); // Reduce population to original length. self.population.truncate(self.num_of_individuals as usize); // Restore original number of mutation rate, since these will be lost because of sorting. for (individual, orig_individual) in self.population .iter_mut() .zip(orig_population.iter()) { individual.num_of_mutations = orig_individual.num_of_mutations; } } }