ge 0.2.0

Genetic algorithm traits and algorithm
Documentation 
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

//! Genetic algorithm tools

extern crate rand;
use rand::Rng;

mod genome;
pub use self::genome::Genome;

/// Genetic algorithm
///
/// # Arguments
/// * `pop_size`: number of individuals in the population
/// * `n_iter`: number of iterations to run algorithm
/// * `replace_rate`: rate at which individuals will be repleaced with results
///     of crossover
/// * `mut_rate`: rate of mutation in individuals
/// * `rng`: Random number generator that will be used to get randomness
///
/// # Return
/// The final generation of `n_iter` iterations, zipped with its fitness, sorted
/// by fitness
pub fn genetic_algorithm<G, R, O>(
    pop_size:     usize,
    n_iter:       usize,
    replace_rate: f32,
    mutate_rate:  f32,
    mut rng:      R
    ) -> Vec<(G, O)>
where G: Genome + Clone,
      R: Rng,
      O: Ord,
{
    // initial population, zipped with fitness and sorted
    let mut pop = init_generation(pop_size, &mut rng);

    // run survival of the fittest simulation
    for _ in 0..n_iter {
        pop = next_generation(pop, replace_rate, mutate_rate, &mut rng);
    }

    pop
}

/// Create an initial generation of specified size
///
/// # Arguments
/// * `size`: size of population
/// * `rng`: Random number generator to pull randomness from
///
/// # Return
/// An entirely random generation, sorted by fitness
fn init_generation<G, R, O>(size: usize, rng: &mut R) -> Vec<(G, O)>
where G: Genome,
      R: Rng,
      O: Ord
{
    let mut gen: Vec<(G, O)> = Vec::with_capacity(size);
    for _ in 0..size {
        let indv = G::genesis(rng);
        let fitness = indv.fitness();
        gen.push((indv, fitness));
    }

    gen.sort_by(|a, b| a.1.cmp(&b.1));
    gen
}

/// Create the next generation
///
/// # Arguments
/// * `gen`: base generation
/// * `replace_rate`: fraction of population that will be replaced by the
///     results of cross-over
/// * `mutate_rate`: Rate of mutation in individuals
/// * `rng`: Random number generator to pull randomness from
///
/// # Return
/// Successor generation to `gen, zipped with, and sorted by fitness
fn next_generation<G, R, O>(
    gen:          Vec<(G, O)>,
    replace_rate: f32,
    mutate_rate:  f32,
    rng:          &mut R
    ) -> Vec<(G, O)>
where G: Genome + Clone,
      R: Rng,
      O: Ord,
{
    let mut new_gen: Vec<G> = Vec::with_capacity(gen.len());

    // Copy over the top performers
    let highest_idx = ((1f32 - replace_rate) * new_gen.len() as f32) as usize;
    for i in 0..highest_idx {
        new_gen[i] = gen[i].0.clone();
    }
    
    // create a mapping between candidates, this gaurentees no "self-love" will
    // occur
    let crosses = new_gen.len() - highest_idx;
    let mut mapping: Vec<usize> = (0..crosses).collect();
    rng.shuffle(&mut mapping);

    // cross over the top candidates with eachother
    for (i, j) in mapping.into_iter().enumerate() {
        // TODO: I would like this to not clone the two operands
        let (a, b) = (new_gen[i].clone(), new_gen[j].clone());
        new_gen.push(a.cross(&b, rng));
    }

    // Mutate step
    for e in new_gen.iter_mut() {
        *e = e.mutate(mutate_rate, rng);
    }

    let mut zipped_with_fit: Vec<(G, O)> = new_gen.into_iter()
        .map(|x| {
            let fitness = x.fitness();
            (x, fitness)
        }).collect();

    zipped_with_fit.sort_by(|a, b| a.1.cmp(&b.1));
    zipped_with_fit
}