onemax/
onemax.rs

1// To execute this example run: cargo run --example onemax
2extern crate rsmath as r;
3extern crate rand;
4
5use rand::Rng;
6use r::algebra::matrix::*;
7use r::algebra::vector::*;
8
9/// Onemax is a basic problem of evolutionary algorithms. The aim of the problem is to find a individuals
10/// where its genes are all '1'. This is the first algorithm that I learned, when I was introduced to the
11/// world of the Genetics Algorithms.
12/// This algorithm is divided in different parts:
13/// * Initialization of variables: the needed variables and the initial population will be initializated.
14/// * Fitness calculation: the fitness will be calculated for the given problem (in this case the number of '1').
15/// * Tournament selection: a combination of individuals will "fight" each other. The ones with the best fitness
16///   will be selected for the next step. In total two arrays of winners will be generated
17/// * Crossover: using the winners (also called parents) the new population will be created. The individuals of the
18///   new population will be created as a product of the combination of the parents.
19/// * Mutation: if decided, a gene of the new population's individuals will be modified.
20/// * Elitism: to preserve that the best individual of the last population won't be deleted, will be saved on the
21///   new population.
22
23fn main() {
24    // initialization of variables
25    let pop_size: usize = 20;
26    let n_genes: usize = 10;
27    let max_gens: usize = 500;
28
29    let mut max_fitness_arr: Vec<u32> = Vec::new();
30    let mut median_fitness_arr: Vec<f64> = Vec::new();
31
32    let mut pop = Matrix::<u32>::random(pop_size, n_genes, &[0, 1]);
33
34    println!("initial population: \n{}", pop);
35
36    // iterate for the generations
37    for gen in 0..max_gens {
38
39        // get the fitness: number of '1'
40        let mut fitness = Vector::<u32>::new();
41        for gene in pop.row_iter() {
42            let sum = gene.iter().fold(0u32, |sum, &el| sum + el);
43            fitness.push(sum);
44        }
45
46        // get the best indiv and its fitness
47        let (max, idx_max) = fitness.max();
48        max_fitness_arr.push(max);
49
50        // save the best individual
51        let best_indiv = pop.row(idx_max).unwrap().clone();
52
53        // calculate the median fitness of the current generation
54        let median = fitness.median();
55        median_fitness_arr.push(median);
56
57        if (max as usize) == n_genes {
58            println!("value found in {} generations", gen);
59            println!("best fitness = {}", max);
60            println!("median fitness = {}", median);
61            println!("final pop:\n{}", pop);
62            break;
63        }
64
65        // Tournament selection
66        let matchup_a = Matrix::<u32>::random(pop_size, 2, &[0, (pop_size - 1) as u32]);
67        let matchup_b = Matrix::<u32>::random(pop_size, 2, &[0, (pop_size - 1) as u32]);
68
69        let parent_a = get_parent(&matchup_a, &fitness);
70        let parent_b = get_parent(&matchup_b, &fitness);
71
72        // Crossover
73        let mut new_pop = x_over(&pop, &parent_a, &parent_b);
74
75        // Mutation
76        mutation(&mut new_pop);
77
78        pop = new_pop.clone();
79
80        // Elitism
81        pop.set_row(0, &best_indiv);
82    }
83}
84
85fn get_parent(matchup: &Matrix<u32>, fitness: &Vector<u32>) -> Vector<u32> {
86    if matchup.ncols() != 2 {
87        panic!("number of rows of matchup must be 2");
88    }
89
90    let mut parent = Vector::<u32>::new();
91    for row in matchup.row_iter() {
92        let idx_first = row[0] as usize;
93        let idx_second = row[1] as usize;
94
95        if fitness.el(idx_first) >= fitness.el(idx_second) {
96            parent.push(row[0]);
97        } else {
98            parent.push(row[1]);
99        }
100    }
101    parent
102}
103
104fn x_over(pop: &Matrix<u32>, parent_a: &Vector<u32>, parent_b: &Vector<u32>) -> Matrix<u32> {
105    let mut new_pop = Matrix::<u32>::new();
106    let do_xover = Vector::<u32>::random(pop.nrows(), &[0, 1]);
107    for i in 0..pop.nrows() {
108        let mut new_indiv: Vec<u32> = Vec::new();
109        if do_xover.el(i) == 1 {
110            let crosspoint: usize = rand::thread_rng().gen_range(0, pop.ncols() + 1);
111            for j in 0..pop.ncols() {
112                if j <= crosspoint {
113                    let idx = parent_a.el(i) as usize;
114                    new_indiv.push(pop.get_element(idx, j));
115                } else {
116                    let idx = parent_b.el(i) as usize;
117                    new_indiv.push(pop.get_element(idx, j));
118                }
119            }
120        } else {
121            let idx = parent_a.el(i) as usize;
122            new_indiv = pop.row(idx).unwrap().clone();
123        }
124        new_pop.push_row(new_indiv);
125    }
126    new_pop
127}
128
129fn mutation(pop: &mut Matrix<u32>) {
130    let do_mutation = Matrix::<u32>::random(pop.nrows(), pop.ncols(), &[0, 1]);
131    for i in 0..pop.nrows() {
132        for j in 0..pop.ncols() {
133            if do_mutation.get_element(i, j) == 1 {
134                if pop.get_element(i, j) == 1 {
135                    pop.set_element(i, j, &0u32);
136                } else {
137                    pop.set_element(i, j, &1u32);
138                }
139            }
140        }
141    }
142}
onemax/onemax.rs

onemax/
onemax.rs
