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

#![warn(missing_docs)]
//! A small genetic algorithms library.
use rand::{seq::SliceRandom, Rng};
use rayon::prelude::*;

/// An interface for breeding, mutation, and fitness evaluation functionality.
///
/// The example code in this trait's method documentation is drawn from the
/// 'π approximator' example of this crate's repository (https://github.com/thfm/ecosystem/).
pub trait Organism {
    /// Evaluates the organism's fitness.
    ///
    /// # Examples
    ///
    /// ```rust
    /// impl Organism for PiApproximator {
    ///     fn fitness(&self) -> f64 {
    ///         let diff = (std::f64::consts::PI - self.value).abs();
    ///         1.0 / diff
    ///     }
    /// }
    /// ```
    fn fitness(&self) -> f64;

    /// Creates a new child by breeding the organism with another.
    ///
    /// # Examples
    ///
    /// ```rust
    /// impl Organism for PiApproximator {
    ///     fn breed(&self, other: &Self) -> Self {
    ///         Self {
    ///             value: (self.value + other.value) / 2.0,
    ///         }
    ///     }
    /// }
    /// ```
    fn breed(&self, other: &Self) -> Self;

    /// Modifies (or *mutates*) the organism, based on the given rate.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use rand::Rng;
    ///
    /// impl Organism for PiApproximator {
    ///     fn mutate(&mut self, rate: f64) {
    ///         let change = rand::thread_rng().gen_range(-rate, rate);
    ///         self.value += change;
    ///     }
    /// }
    /// ```
    fn mutate(&mut self, rate: f64);
}

/// A collection of organisms.
pub struct Ecosystem<O: Organism> {
    /// A vector containing the organisms.
    pub organisms: Vec<O>,
    /// The current generation number.
    pub generation: u32,
}

impl<O: Organism + std::marker::Send + std::marker::Sync> Ecosystem<O> {
    /// Creates a new ecosystem with the given organisms.
    pub fn new(organisms: Vec<O>) -> Self {
        Self {
            organisms,
            generation: 0,
        }
    }

    /// Returns the organism in the ecosystem with the highest fitness.
    pub fn fittest(&self) -> &O {
        self.organisms
            .iter()
            .fold(&self.organisms[0], |fittest, organism| {
                if organism.fitness() > fittest.fitness() {
                    organism
                } else {
                    fittest
                }
            })
    }

    /// Creates the next generation of organisms through the breeding
    /// of suitable organisms.
    pub fn breed_next_generation(&mut self, mutation_rate: f64) {
        let next_generation: Vec<_> = (0..self.organisms.len())
            .into_par_iter()
            .map(|_| {
                let mother = self.select_suitable_organism();
                let father = self.select_suitable_organism();

                let mut child = mother.breed(father);
                child.mutate(mutation_rate);
                child
            })
            .collect();

        self.organisms = next_generation;
        self.generation += 1;
    }

    /// Selects an organism in the ecosystem that is suitable for breeding,
    /// based on fitness values.
    ///
    /// # Panics
    ///
    /// This method panics if the ecosystem contains no organisms.
    fn select_suitable_organism(&self) -> &O {
        let mut rng = rand::thread_rng();
        loop {
            let organism = self
                .organisms
                .choose(&mut rng)
                .unwrap_or_else(|| panic!("there are no organisms in the ecosystem"));
            if organism.fitness() > rng.gen_range(0.0, self.fittest().fitness()) {
                break &organism;
            }
        }
    }
}