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
//! This module defines the trait and the data structure needed for specifying each individual in a population. //! //! 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 //! //! // external modules use std::cmp::Ordering; /// A wrapper helper struct for the individuals. /// It does the book keeping of the fitness and the number of mutations this individual /// has to run in one iteration. #[derive(Debug,Clone)] pub struct IndividualWrapper<T: Individual> { /// The actual individual, user defined struct. pub individual: T, /// The current calculated fitness for this individual. pub fitness: f64, /// The number of mutation this individual is doing in one iteration. pub num_of_mutations: u32, /// The id of the population that this individual belongs to. Just for statistics. pub id: u32, } /// Implement this for sorting impl<T: Individual> PartialEq for IndividualWrapper<T> { fn eq(&self, other: &IndividualWrapper<T>) -> bool { self.fitness == other.fitness } } /// Implement this for sorting impl<T: Individual> Eq for IndividualWrapper<T> {} /// Implement this for sorting impl<T: Individual> Ord for IndividualWrapper<T> { fn cmp(&self, other: &IndividualWrapper<T>) -> Ordering { self.partial_cmp(other).expect("Fitness of Individual is NaN") } } /// Implement this for sorting impl<T: Individual> PartialOrd for IndividualWrapper<T> { fn partial_cmp(&self, other: &IndividualWrapper<T>) -> Option<Ordering> { self.fitness.partial_cmp(&other.fitness) } } /// This trait has to be implemented for the user defined struct. /// In order to share common data between all individuals use Arc. See TSP and OCR exmaples. /// /// TODO: add serialization, see https://github.com/willi-kappler/darwin-rs/issues/11 pub trait Individual { /// This method mutates the individual. Usually this is a cheap and easy to implement /// function. In order to improve the simulation, the user can make this function a bit /// "smarter". This is nicely shown in the tsp and tsp2 example. The tsp2 example contains /// two types of mutation, tsp just one: /// /// examples/tsp: 1. swap position /// /// examples/tsp2: 1. swap position, 2. rotate (shift) positions /// /// By just adding this one additional mutation type the simulation converges much faster /// to the optimum. Of course rotation can be "simulated" by a number of swaps, but re-doing /// all these steps takes time and the chances that these steps are taken in the correct /// order by just randomly swaping positions are very slim. So just start with one simple /// mutation function (one operation) and add more and more "smarter" mutation types to the /// mutate function. fn mutate(&mut self); /// This method calculates the fitness for the individual. Usually this is an expensive /// operation and a bit more difficult to implement, compared to the mutation method above. /// The lower the fitness value, the better (healthier) the individual is and the closer /// the individual is to the perfect solution. This can also correspont to the number of /// errors like for example in the sudoku or queens problem case. fn calculate_fitness(&mut self) -> f64; /// This method resets each individual to an initial state. /// For example in the "queens" case it would reset the queens position randomly /// (or all in the first row). fn reset(&mut self); /// This method is called whenever a new fittest individual is found. It is usefull when you /// want to provide some additional information or do some statistics. /// It is optional and the default implementation does nothing. fn new_fittest_found(&mut self) { } } #[cfg(test)] mod test { use super::{IndividualWrapper, Individual}; struct IndividualTest1; impl Individual for IndividualTest1 { fn mutate(&mut self) { } fn calculate_fitness(&mut self) -> f64 { 0.0 } fn reset(&mut self) { } } #[test] fn compare1() { let individual1 = IndividualWrapper{individual: IndividualTest1, fitness: 1.2, num_of_mutations: 21, id: 1}; let individual2 = IndividualWrapper{individual: IndividualTest1, fitness: 5.93, num_of_mutations: 7, id: 1}; assert!(individual2 > individual1); } #[test] fn compare2() { let individual1 = IndividualWrapper{individual: IndividualTest1, fitness: 3.78, num_of_mutations: 21, id: 1}; let individual2 = IndividualWrapper{individual: IndividualTest1, fitness: 7.12, num_of_mutations: 7, id: 1}; assert!(individual1 < individual2); } #[test] fn compare3() { let individual1 = IndividualWrapper{individual: IndividualTest1, fitness: 21.996, num_of_mutations: 11, id: 1}; let individual2 = IndividualWrapper{individual: IndividualTest1, fitness: 21.996, num_of_mutations: 34, id: 1}; assert!(individual1 == individual2); } }