easy_ga/
genetic_algorithm.rs

1//! This module contains the definition and implementation of the GeneticAlgorithm class
2//! wich is the handler for our `Gene` to do the logic.
3
4use core::fmt;
5use rand::Rng;
6use std::error::Error;
7
8use crate::logger;
9use crate::selection::*;
10use crate::Gene;
11
12/// Default value for our population size.
13const POPULATION_SIZE_DEFAULT: usize = 100;
14/// Default value for our max generations aka iterations.
15const MAX_ITERATIONS_DEFAULT: u32 = 1000;
16/// Default value for mutation probability to perform mutation on the genes.
17const MUTATION_RATE_DEFAULT: f32 = 0.05;
18/// Default value percentage of individuals to survive to the next generation.
19const SELECTION_RATE_DEFAULT: f32 = 0.90;
20
21/// Reasons to stop the algorithm.
22#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
23pub enum StopCriteria {
24    MaxIterations,
25    FitnessAchieved,
26    Unknown,
27}
28
29/// Struct for our genetic algorithm handler.
30pub struct GeneticAlgorithm<T: Gene + Copy> {
31    /// Size of the population, wich means the amount of `Gene`'s our generation can handle.
32    population_size: usize,
33    /// Num of the max iterations our algorithm will perform.
34    iterations: u32,
35    /// The current iteration the algorithm is.
36    current_iteration: u32,
37    /// The current generation.
38    generation: Vec<T>,
39    /// Historic with all our past generations.
40    generation_historic: Vec<Vec<T>>,
41    /// The mutation percentage.
42    mutation_rate: f32,
43    /// The percentage of individuals to survive to the next generation.
44    ///
45    /// # Example
46    /// If we have a `population_size` of 100 genes and a `selection_rate` of 0.9. Then, 90 genes will advance to the new generation and 10 will be generated via crossover.
47    selection_rate: f32,
48    /// The selection algorithm to perform the Selection::select.
49    selection_algorithm: Box<dyn Selection>,
50    /// The fitness value to reach to end the algorithm.
51    fitness_goal: f64,
52    /// If the algorithm is running or not
53    running: bool,
54    /// The best gene overall.
55    best_gene: T,
56    /// The stop reason if the algorithm has stopped.
57    stop_criteria: StopCriteria,
58}
59
60impl<T: Gene + Copy> GeneticAlgorithm<T> {
61    /// Creates a new `GeneticAlgorithm` with default values.
62    /// * `population_size` = 100
63    /// * `iterations` = 1000
64    /// * `mutation_rate` = 0.05
65    /// * `selection_rate` = 0.90
66    /// * `selection_algorithm` = SelectionAlgorithms::Tournament(2)
67    /// * `fitness_goal` = f64::MAX
68    pub fn new() -> Self {
69        let generation = (0..POPULATION_SIZE_DEFAULT).map(|_| T::init()).collect();
70        let generation_historic = vec![Vec::clone(&generation)];
71        let return_value = GeneticAlgorithm {
72            population_size: POPULATION_SIZE_DEFAULT,
73            iterations: MAX_ITERATIONS_DEFAULT,
74            current_iteration: 0,
75            generation,
76            generation_historic,
77            mutation_rate: MUTATION_RATE_DEFAULT,
78            selection_rate: SELECTION_RATE_DEFAULT,
79            selection_algorithm: Box::new(SelectionAlgorithms::Tournament(2)),
80            fitness_goal: f64::MAX,
81            running: false,
82            best_gene: T::init(),
83            stop_criteria: StopCriteria::Unknown,
84        };
85
86        logger::LOG(
87            logger::VerbosityLevel::LOW,
88            format!(
89                "GeneticAlgorithm created with default values:\n{}",
90                return_value
91            )
92            .as_str(),
93        );
94
95        return_value
96    }
97
98    /// Creates a new `GeneticAlgorithm` with specific values.
99    ///
100    /// # Arguments
101    ///
102    /// * `population_size` - The population of the generation.
103    /// * `iterations` - The number of max iterations.
104    /// * `mutation_rate` - The mutation probability for a gene.
105    /// * `selection_rate` - The percentage of individuals to survive to the next generation.
106    /// * `selection_algorithm` - Box object with a Selection trait to perform the selection algorithm.
107    /// * `fitness_goal` - The fitness value target.
108    pub fn new_with_values(
109        population_size: usize,
110        iterations: u32,
111        mutation_rate: f32,
112        selection_rate: f32,
113        selection_algorithm: Box<dyn Selection>,
114        fitness_goal: f64,
115    ) -> Self {
116        if mutation_rate > 1.0 || mutation_rate < 0.0 {
117            panic!("Mutation rate not in rage between 0.0 and 1.0");
118        }
119
120        if selection_rate > 1.0 || selection_rate < 0.0 {
121            panic!("Selection rate not in rage between 0.0 and 1.0");
122        }
123
124        let generation = (0..population_size).map(|_| T::init()).collect();
125        let generation_historic = vec![vec![]];
126        let return_value = GeneticAlgorithm {
127            population_size,
128            iterations,
129            current_iteration: 0,
130            generation,
131            generation_historic,
132            mutation_rate,
133            selection_rate,
134            selection_algorithm,
135            fitness_goal,
136            running: false,
137            best_gene: T::init(),
138            stop_criteria: StopCriteria::Unknown,
139        };
140
141        logger::LOG(
142            logger::VerbosityLevel::LOW,
143            format!("GeneticAlgorithm created with values:\n{}", return_value).as_str(),
144        );
145
146        return_value
147    }
148
149    // TODO: Implement error handling when the algorithm will not be able to init.
150    /// Initiate the algorithm.    
151    pub fn init(mut self) -> Result<Self, Box<dyn Error>> {
152        self.running = true;
153        self.save_generation();
154        logger::LOG(
155            logger::VerbosityLevel::HIGH,
156            "Algorithm initiated properlly.",
157        );
158        Ok(self)
159    }
160
161    /// Runs the algorithm by itself without user control.
162    pub fn run(mut self) -> (T, StopCriteria) {
163        if !self.is_running() {
164            self = self.init().unwrap();
165        }
166
167        logger::LOG(logger::VerbosityLevel::HIGH, "Algorithm run started.");
168
169        while self.running {
170            self.next_iteration();
171        }
172
173        (self.best_gene, self.stop_criteria)
174    }
175
176    /// Goes iteration by iteration in case the user wants to have more control over the lifetime of the algorithm.
177    ///
178    /// # Returns
179    ///
180    /// `self.generation` - The new generation.
181    pub fn next_iteration(&mut self) -> &Vec<T> {
182        logger::LOG(
183            logger::VerbosityLevel::LOW,
184            format!(
185                ">>>>>>> Started iteration {} <<<<<<<",
186                self.current_iteration
187            )
188            .as_str(),
189        );
190
191        logger::LOG(
192            logger::VerbosityLevel::HIGH,
193            ">> Fitness calculation phase.",
194        );
195        // Calculate fitness.
196        for (i, gene) in self.generation.iter_mut().enumerate() {
197            gene.calculate_fitness();
198            logger::LOG(
199                logger::VerbosityLevel::MID,
200                format!("Gene {i} = {:?}", gene.get_fitness()).as_str(),
201            );
202        }
203
204        logger::LOG(logger::VerbosityLevel::HIGH, ">> Selection phase.");
205        // Selection.
206        let mut new_generation: Vec<T> = Vec::with_capacity(self.population_size);
207        let num_survivors: usize = (self.generation.len() as f32 * self.selection_rate) as usize;
208        let mut new_genes_num: usize = 0;
209
210        logger::LOG(
211            logger::VerbosityLevel::MID,
212            format!("Number of survivors = {:?}", num_survivors).as_str(),
213        );
214        while new_genes_num < num_survivors {
215            let gene_idx: usize = self.selection_algorithm.select(
216                &self
217                    .generation
218                    .iter()
219                    .map(|gene| gene.get_fitness())
220                    .collect(),
221            );
222            new_generation.push(self.generation[gene_idx]);
223            self.generation.remove(gene_idx);
224            new_genes_num += 1;
225        }
226
227        logger::LOG(logger::VerbosityLevel::HIGH, ">> Crossover phase.");
228        // Crossover
229        let mut rng = rand::thread_rng();
230        while new_genes_num < self.population_size {
231            let gen1_idx = rng.gen_range(0..new_generation.len());
232            let mut gen2_idx = gen1_idx;
233            while gen2_idx == gen1_idx {
234                gen2_idx = rng.gen_range(0..new_generation.len());
235            }
236            let gen1 = new_generation[gen1_idx];
237            let crossover_gen = gen1.crossover(&new_generation[gen2_idx]);
238            new_generation.push(crossover_gen);
239            new_genes_num += 1;
240            logger::LOG(
241                logger::VerbosityLevel::MID,
242                format!(
243                    "Crossover between gen1({:?}) and gen2({:?})",
244                    gen1.get_fitness(),
245                    new_generation[gen2_idx].get_fitness()
246                )
247                .as_str(),
248            );
249        }
250
251        logger::LOG(logger::VerbosityLevel::HIGH, ">> Mutation phase.");
252        // Mutation
253        let mut num_of_mutations = 0;
254        for gen in new_generation.iter_mut() {
255            if rng.gen_range(0.0..1.0) < self.mutation_rate {
256                gen.mutate();
257                num_of_mutations += 1;
258            }
259        }
260        logger::LOG(
261            logger::VerbosityLevel::MID,
262            format!("{} mutations performed.", num_of_mutations).as_str(),
263        );
264
265        // Save generation_historic & best_gene
266        self.generation = new_generation;
267        self.save_generation();
268
269        self.current_iteration += 1;
270
271        // Check stop criteria
272        self.check_stop_criteria();
273
274        &self.generation
275    }
276
277    /// Saves the generation just created and the best gene.
278    fn save_generation(&mut self) {
279        logger::LOG(logger::VerbosityLevel::HIGH, ">> Saving generation data.");
280        self.generation_historic.push(Vec::clone(&self.generation));
281
282        let mut best_fitness: f64 = self.best_gene.get_fitness();
283
284        for gene in self.generation.iter() {
285            if gene.get_fitness() > best_fitness {
286                self.best_gene = *gene;
287                best_fitness = gene.get_fitness();
288            }
289        }
290        logger::LOG(
291            logger::VerbosityLevel::LOW,
292            format!("Best gene with fitness = {:?}", best_fitness).as_str(),
293        );
294    }
295
296    /// Checks if the algorithm should stop or not.
297    fn check_stop_criteria(&mut self) {
298        if self.best_gene.get_fitness() >= self.fitness_goal {
299            self.running = false;
300            self.stop_criteria = StopCriteria::FitnessAchieved;
301            logger::LOG(
302                logger::VerbosityLevel::LOW,
303                format!("Algorithm must stop because of {:?}", self.stop_criteria).as_str(),
304            );
305        }
306
307        if self.current_iteration >= self.iterations {
308            self.running = false;
309            self.stop_criteria = StopCriteria::MaxIterations;
310            logger::LOG(
311                logger::VerbosityLevel::LOW,
312                format!("Algorithm must stop because of {:?}", self.stop_criteria).as_str(),
313            );
314        }
315    }
316
317    /// Sets the population size.
318    ///
319    /// # Notes
320    ///
321    /// If the population size is greather than the actual size, the generation ir resized filling the empty values with new genes of value `T`.
322    pub fn population_size(mut self, population_size: usize) -> Self {
323        if population_size >= self.population_size {
324            self.generation
325                .extend((0..population_size - self.generation.len()).map(|_| T::init()));
326        } else {
327            self.generation.resize(population_size, T::init());
328        }
329        self.population_size = population_size;
330        self
331    }
332
333    /// Sets the max number of iterations the algorithm will perform.
334    ///
335    /// # Notes
336    ///
337    /// If the max number passed is lower than the current generation, the algorithm will end.
338    pub fn iterations(mut self, iterations: u32) -> Self {
339        if iterations <= self.current_iteration {
340            panic!("Number of iterations is not greater  than the actual iteration.");
341        }
342
343        self.iterations = iterations;
344        self
345    }
346
347    /// Sets the mutation rate.
348    pub fn mutation_rate(mut self, mutation_rate: f32) -> Self {
349        if mutation_rate > 1.0 || mutation_rate < 0.0 {
350            panic!("Mutation rate not in rage between 0.0 and 1.0");
351        }
352
353        self.mutation_rate = mutation_rate;
354        self
355    }
356
357    /// Sets the selection rate.
358    pub fn selection_rate(mut self, selection_rate: f32) -> Self {
359        if selection_rate > 1.0 || selection_rate < 0.0 {
360            panic!("Selection rate not in rage between 0.0 and 1.0");
361        }
362
363        self.selection_rate = selection_rate;
364        self
365    }
366
367    /// Sets the selection algorithm.
368    pub fn selection_algorithm(mut self, selection_algorithm: Box<dyn Selection>) -> Self {
369        self.selection_algorithm = selection_algorithm;
370        self
371    }
372
373    /// Sets the fitness goal to reach and stop the algorithm.
374    pub fn fitness_goal(mut self, fitness_goal: f64) -> Self {
375        self.fitness_goal = fitness_goal;
376        self
377    }
378
379    /// Returns the population size.
380    pub fn get_population_size(&self) -> usize {
381        self.population_size
382    }
383
384    /// Returns the max iterations.
385    pub fn get_iterations(&self) -> u32 {
386        self.iterations
387    }
388
389    /// Returns the current iteration.
390    pub fn get_current_iteration(&self) -> u32 {
391        self.current_iteration
392    }
393
394    /// Returns the current generation.
395    pub fn get_generation(&self) -> Vec<T> {
396        self.generation.clone()
397    }
398
399    /// Returns all the generations the algorithm passed.
400    pub fn get_generation_historic(&self) -> Vec<Vec<T>> {
401        self.generation_historic.clone()
402    }
403
404    /// Returns the mutation rate.
405    pub fn get_mutation_rate(&self) -> f32 {
406        self.mutation_rate
407    }
408
409    /// Returns the selection rate.
410    pub fn get_selection_rate(&self) -> f32 {
411        self.selection_rate
412    }
413
414    pub fn get_fitness_goal(&self) -> f64 {
415        self.fitness_goal
416    }
417
418    /// Returns the best gene in all the generations.
419    pub fn get_best_gene(&self) -> T {
420        self.best_gene
421    }
422
423    /// Returns if the algorithm is currently running
424    pub fn is_running(&self) -> bool {
425        self.running
426    }
427
428    pub fn get_stop_criteria(&self) -> StopCriteria {
429        self.stop_criteria
430    }
431}
432
433/// Default trait implementation for GeneticAlgorithm.
434impl<T: Gene + Copy> Default for GeneticAlgorithm<T> {
435    fn default() -> Self {
436        Self::new()
437    }
438}
439
440/// Display trait implementation for GeneticAlgorithm.
441impl<T: Gene + Copy> fmt::Display for GeneticAlgorithm<T> {
442    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
443        write!(
444            f,
445             "{{\n\tpopulation_size: {},\n\titerations: {},\n\tcurrent_iteration: {},\n\tselection_rate: {},\n\tmutation_rate: {},\n\tfitness_goal: {:?},\n\tstop_criteria: {:?},\n\tbest_gene_fitness: {}\n}}",
446            self.population_size,
447            self.iterations,
448            self.current_iteration,
449            self.selection_rate,
450            self.mutation_rate,
451            self.fitness_goal,
452            self.stop_criteria,
453            self.best_gene.get_fitness()
454        )
455    }
456}
easy_ga/genetic_algorithm.rs

easy_ga/
genetic_algorithm.rs
