darwin_rs/
individual.rs

1//! This module defines the trait and the data structure needed for specifying each individual in a population.
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
16// external modules
17use std::cmp::Ordering;
18
19/// A wrapper helper struct for the individuals.
20/// It does the book keeping of the fitness and the number of mutations this individual
21/// has to run in one iteration.
22#[derive(Debug,Clone)]
23pub struct IndividualWrapper<T: Individual> {
24    /// The actual individual, user defined struct.
25    pub individual: T,
26    /// The current calculated fitness for this individual.
27    pub fitness: f64,
28    /// The number of mutation this individual is doing in one iteration.
29    pub num_of_mutations: u32,
30    /// The id of the population that this individual belongs to. Just for statistics.
31    pub id: u32,
32}
33
34/// Implement this for sorting
35impl<T: Individual> PartialEq for IndividualWrapper<T> {
36    fn eq(&self, other: &IndividualWrapper<T>) -> bool {
37        self.fitness == other.fitness
38    }
39}
40
41/// Implement this for sorting
42impl<T: Individual> Eq for IndividualWrapper<T> {}
43
44/// Implement this for sorting
45impl<T: Individual> Ord for IndividualWrapper<T> {
46    fn cmp(&self, other: &IndividualWrapper<T>) -> Ordering {
47        self.partial_cmp(other).expect("Fitness of Individual is NaN")
48    }
49}
50
51/// Implement this for sorting
52impl<T: Individual> PartialOrd for IndividualWrapper<T> {
53    fn partial_cmp(&self, other: &IndividualWrapper<T>) -> Option<Ordering> {
54        self.fitness.partial_cmp(&other.fitness)
55    }
56}
57
58/// This trait has to be implemented for the user defined struct.
59/// In order to share common data between all individuals use Arc. See TSP and OCR exmaples.
60///
61/// TODO: add serialization, see https://github.com/willi-kappler/darwin-rs/issues/11
62pub trait Individual {
63    /// This method mutates the individual. Usually this is a cheap and easy to implement
64    /// function. In order to improve the simulation, the user can make this function a bit
65    /// "smarter". This is nicely shown in the tsp and tsp2 example. The tsp2 example contains
66    /// two types of mutation, tsp just one:
67    ///
68    /// examples/tsp: 1. swap position
69    ///
70    /// examples/tsp2: 1. swap position, 2. rotate (shift) positions
71    ///
72    /// By just adding this one additional mutation type the simulation converges much faster
73    /// to the optimum. Of course rotation can be "simulated" by a number of swaps, but re-doing
74    /// all these steps takes time and the chances that these steps are taken in the correct
75    /// order by just randomly swaping positions are very slim. So just start with one simple
76    /// mutation function (one operation) and add more and more "smarter" mutation types to the
77    /// mutate function.
78    fn mutate(&mut self);
79    /// This method calculates the fitness for the individual. Usually this is an expensive
80    /// operation and a bit more difficult to implement, compared to the mutation method above.
81    /// The lower the fitness value, the better (healthier) the individual is and the closer
82    /// the individual is to the perfect solution. This can also correspont to the number of
83    /// errors like for example in the sudoku or queens problem case.
84    fn calculate_fitness(&mut self) -> f64;
85    /// This method resets each individual to an initial state.
86    /// For example in the "queens" case it would reset the queens position randomly
87    /// (or all in the first row).
88    fn reset(&mut self);
89    /// This method is called whenever a new fittest individual is found. It is usefull when you
90    /// want to provide some additional information or do some statistics.
91    /// It is optional and the default implementation does nothing.
92    fn new_fittest_found(&mut self) {
93
94    }
95}
96
97#[cfg(test)]
98mod test {
99    use super::{IndividualWrapper, Individual};
100
101    struct IndividualTest1;
102
103    impl Individual for IndividualTest1 {
104        fn mutate(&mut self) {
105        }
106
107        fn calculate_fitness(&mut self) -> f64 {
108            0.0
109        }
110
111        fn reset(&mut self) {
112
113        }
114    }
115
116    #[test]
117    fn compare1() {
118        let individual1 = IndividualWrapper{individual: IndividualTest1, fitness: 1.2, num_of_mutations: 21, id: 1};
119        let individual2 = IndividualWrapper{individual: IndividualTest1, fitness: 5.93, num_of_mutations: 7, id: 1};
120
121        assert!(individual2 > individual1);
122    }
123
124    #[test]
125    fn compare2() {
126        let individual1 = IndividualWrapper{individual: IndividualTest1, fitness: 3.78, num_of_mutations: 21, id: 1};
127        let individual2 = IndividualWrapper{individual: IndividualTest1, fitness: 7.12, num_of_mutations: 7, id: 1};
128
129        assert!(individual1 < individual2);
130    }
131
132    #[test]
133    fn compare3() {
134        let individual1 = IndividualWrapper{individual: IndividualTest1, fitness: 21.996, num_of_mutations: 11, id: 1};
135        let individual2 = IndividualWrapper{individual: IndividualTest1, fitness: 21.996, num_of_mutations: 34, id: 1};
136
137        assert!(individual1 == individual2);
138    }
139}
darwin_rs/individual.rs

darwin_rs/
individual.rs
