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

//! Genetic algorithm tools

extern crate rand;
use rand::Rng;

extern crate num;
use num::traits::Float;

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
/// TODO
pub fn genetic_algorithm<G, R, O, F>(
    pop_size:     usize,
    n_iter:       usize,
    replace_rate: F,
    mutate_rate:  F,
    mut rng:      R
    ) -> Vec<(G, O)>
where G: Genome + Clone, // TODO, see if `Clone` this is really necessary
      R: Rng,
      O: Ord,
      F: Float
{
    // 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
/// TODO
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`: TODO
/// * `replace_rate`: TODO
/// * `mutate_rate`: TODO
/// * `rng`: TODO
///
/// # Return
/// TODO
fn next_generation<G, R, O, F>(
    gen:          Vec<(G, O)>,
    replace_rate: F,
    mutate_rate:  F,
    rng:          R
    ) -> Vec<(G, O)>
where G: Genome + Clone,
      R: Rng,
      O: Ord,
      F: Float
{
    let mut new_gen: Vec<G> = Vec::with_capacity(gen.len());

    // let highest_idx = ((1. - replace_rate) * new_gen.len()) as usize;
    // for i in 0..highest_idx {
    //     new_gen[i] = gen[i].0.clone();
    // }
    
    // TODO: crossover

    // TODO: mutation

    new_gen.into_iter()
        .map(|x| {
            let fitness = x.fitness();
            (x, fitness)
        }).collect()
}