oxigen/
selection.rs

1//! This module contains the Selection trait and the provided selection functions.
2
3use rand::distributions::{Standard, Uniform};
4use rand::prelude::*;
5use rayon::prelude::*;
6use std::ops::Range;
7use std::sync::mpsc::channel;
8use SelectionFunctions::*;
9
10/// This trait defines the select function used to select individuals for crossover.
11pub trait Selection: Send + Sync {
12    /// Returns a vector with the indices of the selected individuals according to
13    /// the fitness of the population and the selection rate.
14    fn select(&self, fitnesses: &[f64], selection_rate: usize) -> Vec<usize>;
15}
16
17/// Defines the number of tournaments parameter.
18pub struct NTournaments(pub usize);
19
20/// Provided selection functions
21pub enum SelectionFunctions {
22    /// Roulette function.
23    Roulette,
24    /// Tournaments function.
25    Tournaments(NTournaments),
26    /// Cup function, a cup tournament where the `selection_rate` first phases
27    /// of the tournament are selected (winner, final, semifinal, etc.).
28    Cup,
29}
30
31impl Selection for SelectionFunctions {
32    fn select(&self, fitnesses: &[f64], selection_rate: usize) -> Vec<usize> {
33        match self {
34            Roulette => {
35                let mut rgen = SmallRng::from_entropy();
36                let mut winners = Vec::with_capacity(selection_rate);
37                let mut probs = Vec::with_capacity(fitnesses.len());
38                let fitness_sum: f64 = fitnesses.iter().sum();
39                for fit in fitnesses {
40                    probs.push(fit / fitness_sum);
41                }
42                for _i in 0..selection_rate {
43                    let random: f64 = rgen.sample(Standard);
44                    let mut accum = 0_f64;
45                    for (ind, p) in probs.iter().enumerate() {
46                        if random <= accum + p {
47                            winners.push(ind);
48                            break;
49                        }
50                        accum += p;
51                    }
52                }
53
54                winners
55            }
56            Tournaments(n_tournaments) => {
57                let (sender, receiver) = channel();
58                let mut winners = Vec::with_capacity(n_tournaments.0);
59                Range {
60                    start: 0,
61                    end: n_tournaments.0,
62                }
63                .into_par_iter()
64                .for_each_with(sender, |s, _t| {
65                    let mut rgen = SmallRng::from_entropy();
66                    let mut fighters = Vec::with_capacity(selection_rate);
67                    for _f in 0..selection_rate {
68                        let sel = rgen.sample(Uniform::from(0..fitnesses.len()));
69                        fighters.push((sel, fitnesses[sel]));
70                    }
71                    s.send(
72                        fighters
73                            .par_iter()
74                            .max_by(|x, y| x.1.partial_cmp(&y.1).unwrap())
75                            .unwrap()
76                            .0,
77                    )
78                    .unwrap();
79                });
80
81                for win in receiver {
82                    winners.push(win);
83                }
84                winners
85            }
86            Cup => {
87                let mut rgen = SmallRng::from_entropy();
88                let mut winners = Vec::with_capacity(2_i32.pow(selection_rate as u32) as usize - 1);
89                let n_phases = (fitnesses.len() as f64).log2() as usize + 1;
90                let mut phases: Vec<Vec<(usize, f64)>> = Vec::with_capacity(n_phases);
91                // Initialize the phases members
92                for i in 0..n_phases {
93                    let size = 2_i32.pow(i as u32) as usize;
94                    phases.push(Vec::with_capacity(size));
95                    for _j in 0..size {
96                        phases[i].push((0, 0_f64));
97                    }
98                }
99                // Randomly initialize the last phase
100                let mut candidates = Vec::with_capacity(fitnesses.len());
101                for f in fitnesses {
102                    candidates.push(*f);
103                }
104                {
105                    let last_phase = &mut phases[n_phases - 1];
106                    let mut i = 0;
107                    while i < last_phase.len() {
108                        let sel = rgen.sample(Uniform::from(0..candidates.len()));
109                        last_phase[i] = (sel, candidates[sel]);
110                        candidates.remove(sel);
111                        i += 1;
112                    }
113                }
114
115                // Do the fights
116                Self::cup_phase_fight(&mut phases, n_phases - 1);
117
118                // Push winners
119                for phase in phases
120                    .iter()
121                    .enumerate()
122                    .filter(|(i, _p)| *i < selection_rate as usize)
123                    .map(|(_i, p)| p)
124                {
125                    for winner in phase.iter() {
126                        if winners.is_empty() {
127                            winners.push(winner.0);
128                        } else {
129                            let index = rgen.sample(Uniform::from(0..winners.len()));
130                            winners.insert(index, winner.0);
131                        }
132                    }
133                }
134
135                winners
136            }
137        }
138    }
139}
140
141impl SelectionFunctions {
142    fn cup_phase_fight(phases: &mut Vec<Vec<(usize, f64)>>, phase: usize) {
143        let (sender, receiver) = channel();
144
145        Range {
146            start: 0,
147            end: phases[phase].len() / 2,
148        }
149        .into_par_iter()
150        .for_each_with(sender, |s, i| {
151            let ind1 = i * 2;
152            let ind2 = ind1 + 1;
153
154            if phases[phase][ind1].1 >= phases[phase][ind2].1 {
155                s.send((i, phases[phase][ind1])).unwrap();
156            } else {
157                s.send((i, phases[phase][ind2])).unwrap();
158            }
159        });
160        for (i, child) in receiver {
161            phases[phase - 1][i] = child;
162        }
163        if phase > 1 {
164            Self::cup_phase_fight(phases, phase - 1);
165        }
166    }
167}
oxigen/selection.rs

oxigen/
selection.rs
