ge/
lib.rs

1//! Genetic algorithm tools
2
3extern crate rand;
4use rand::Rng;
5
6mod genome;
7pub use self::genome::Genome;
8
9/// Genetic algorithm
10///
11/// # Arguments
12/// * `pop_size`: number of individuals in the population
13/// * `n_iter`: number of iterations to run algorithm
14/// * `replace_rate`: rate at which individuals will be repleaced with results
15///     of crossover
16/// * `mut_rate`: rate of mutation in individuals
17/// * `rng`: Random number generator that will be used to get randomness
18///
19/// # Return
20/// The final generation of `n_iter` iterations, zipped with its fitness, sorted
21/// by fitness
22pub fn genetic_algorithm<G, R, O>(
23    pop_size:     usize,
24    n_iter:       usize,
25    replace_rate: f32,
26    mutate_rate:  f32,
27    mut rng:      R
28    ) -> Vec<(G, O)>
29where G: Genome + Clone,
30      R: Rng,
31      O: Ord,
32{
33    // initial population, zipped with fitness and sorted
34    let mut pop = init_generation(pop_size, &mut rng);
35
36    // run survival of the fittest simulation
37    for _ in 0..n_iter {
38        pop = next_generation(pop, replace_rate, mutate_rate, &mut rng);
39    }
40
41    pop
42}
43
44/// Create an initial generation of specified size
45///
46/// # Arguments
47/// * `size`: size of population
48/// * `rng`: Random number generator to pull randomness from
49///
50/// # Return
51/// An entirely random generation, sorted by fitness
52fn init_generation<G, R, O>(size: usize, rng: &mut R) -> Vec<(G, O)>
53where G: Genome,
54      R: Rng,
55      O: Ord
56{
57    let mut gen: Vec<(G, O)> = Vec::with_capacity(size);
58    for _ in 0..size {
59        let indv = G::genesis(rng);
60        let fitness = indv.fitness();
61        gen.push((indv, fitness));
62    }
63
64    gen.sort_by(|a, b| a.1.cmp(&b.1));
65    gen
66}
67
68/// Create the next generation
69///
70/// # Arguments
71/// * `gen`: base generation
72/// * `replace_rate`: fraction of population that will be replaced by the
73///     results of cross-over
74/// * `mutate_rate`: Rate of mutation in individuals
75/// * `rng`: Random number generator to pull randomness from
76///
77/// # Return
78/// Successor generation to `gen, zipped with, and sorted by fitness
79fn next_generation<G, R, O>(
80    gen:          Vec<(G, O)>,
81    replace_rate: f32,
82    mutate_rate:  f32,
83    rng:          &mut R
84    ) -> Vec<(G, O)>
85where G: Genome + Clone,
86      R: Rng,
87      O: Ord,
88{
89    let mut new_gen: Vec<G> = Vec::with_capacity(gen.len());
90
91    // Copy over the top performers
92    let highest_idx = ((1f32 - replace_rate) * new_gen.len() as f32) as usize;
93    for i in 0..highest_idx {
94        new_gen[i] = gen[i].0.clone();
95    }
96    
97    // create a mapping between candidates, this gaurentees no "self-love" will
98    // occur
99    let crosses = new_gen.len() - highest_idx;
100    let mut mapping: Vec<usize> = (0..crosses).collect();
101    rng.shuffle(&mut mapping);
102
103    // cross over the top candidates with eachother
104    for (i, j) in mapping.into_iter().enumerate() {
105        // TODO: I would like this to not clone the two operands
106        let (a, b) = (new_gen[i].clone(), new_gen[j].clone());
107        new_gen.push(a.cross(&b, rng));
108    }
109
110    // Mutate step
111    for e in new_gen.iter_mut() {
112        *e = e.mutate(mutate_rate, rng);
113    }
114
115    let mut zipped_with_fit: Vec<(G, O)> = new_gen.into_iter()
116        .map(|x| {
117            let fitness = x.fitness();
118            (x, fitness)
119        }).collect();
120
121    zipped_with_fit.sort_by(|a, b| a.1.cmp(&b.1));
122    zipped_with_fit
123}
124
ge/lib.rs

ge/
lib.rs
