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);
    }
}