rusty_genes/operators/
selection.rs

1use super::*;
2use rand::distributions::Uniform;
3use rayon::prelude::*;
4
5/// Represents various selection strategies for selecting an individual from the population in
6/// an evolutionary algorithm.
7///
8/// # Note
9/// The selection strategy is an important aspect of an evolutionary algorithm. It determines how
10/// individuals are chosen from the population for reproduction and thereby, influences the diversity
11/// and convergence speed of the algorithm.
12///
13/// Each selection strategy has its own strengths and weaknesses, and the choice of strategy can
14/// significantly impact the performance of the evolutionary algorithm.
15#[derive(Debug, Clone, Copy, PartialEq)]
16pub enum SelectionStrategy {
17    /// The tournament selection strategy involves running a "tournament" among a few individuals
18    /// chosen at random from the population and selecting the winner (the one with the best fitness).
19    /// The size parameter represents the number of individuals to be selected for the tournament.
20    Tournament(usize /* size */),
21
22    /// The roulette wheel selection strategy involves choosing individuals based on their fitness
23    /// proportionate to the total fitness of the population, like spinning a roulette wheel.
24    RouletteWheel,
25
26    /// The Boltzmann selection strategy involves selecting individuals with a probability that is
27    /// a function of their fitness and a decreasing "temperature" parameter. The first parameter
28    /// represents the initial temperature, and the second one represents the cooling rate.
29    Boltzmann(f64 /* temperature */, f64 /* cooling rate */),
30
31    /// The rank selection strategy involves selecting individuals based on their rank in the population
32    /// when sorted by fitness, rather than their actual fitness values.
33    Rank,
34
35    /// The linear selection strategy involves selecting individuals with a probability that is a
36    /// linear function of their rank. The bias parameter determines the slope of the function.
37    Linear(f64 /* bias */),
38
39    /// The elitist selection strategy involves always selecting a certain ratio of the best individuals
40    /// in the population. The ratio parameter determines the proportion of individuals to be selected.
41    Elitist(f64 /* ratio */),
42}
43
44impl SelectionStrategy {
45    /// Creates the selector for the the selected selection strategy.
46    pub fn create_selector<I: Individual, R: Rng>(&self) -> Box<dyn SelectionMechanism<I, R>> {
47        match self {
48            SelectionStrategy::Tournament(size) => Box::new(TournamentSelection::new(*size)),
49            SelectionStrategy::RouletteWheel => Box::new(RouletteWheelSelection::new()),
50            SelectionStrategy::Rank => Box::new(RankSelection::new()),
51            SelectionStrategy::Linear(bias) => Box::new(LinearSelection::new(*bias)),
52            SelectionStrategy::Elitist(ratio) => Box::new(ElitistSelection::new(*ratio)),
53            SelectionStrategy::Boltzmann(temperature, cooling_rate) => {
54                Box::new(BoltzmannSelection::new(*temperature, *cooling_rate))
55            }
56        }
57    }
58}
59
60/// Defines the mechanism for selecting an individual from the population in an evolutionary
61/// algorithm.
62pub trait SelectionMechanism<I, R>: Sync
63where
64    I: Individual,
65    R: Rng,
66{
67    /// Prepares the mechanism for a new population.
68    ///
69    /// # Arguments
70    /// * `population` - A reference to the population from which an individual will be selected.
71    ///
72    /// # Note
73    /// This method is called once before selecting individuals from a new population. It
74    /// can be used to perform any necessary setup or pre-processing steps before selecting
75    /// individuals.
76    fn prepare(&mut self, population: &Population<I>);
77
78    /// Selects an individual from the population.
79    ///
80    /// # Arguments
81    /// * `population` - A reference to the population from which an individual will be
82    ///   selected.
83    /// * `rng` - A random number generator for stochastic selection strategies.
84    ///
85    /// # Note
86    /// The method should return a reference to the selected individual. The implementation
87    /// should take into account the fitness of the individuals in the population, as well as
88    /// any other selection criteria that are part of the selection strategy.
89    fn select<'a>(&self, population: &'a Population<I>, rng: &mut R) -> (usize, &'a I);
90
91    /// Selects an individual from the population, excluding a specific individual.
92    /// The selection attempt will be repeated for a specified number of tries (`max_tries`),
93    /// or until a different individual is found.
94    ///
95    /// # Arguments
96    /// * `population` - A reference to the population from which an individual will be selected.
97    /// * `rng` - A random number generator for stochastic selection strategies.
98    /// * `max_tries` - The maximum number of selection attempts before giving up.
99    ///   This parameter prevents potential infinite loops in cases where all individuals
100    ///   are the same.
101    /// * `excluded` - The individual to be excluded from selection.
102    ///
103    /// # Returns
104    /// Returns a tuple containing the index and a reference to the selected individual distinct
105    /// from the `excluded` one. If no different individual is found after `max_tries` attempts,
106    /// the method returns [`None`].
107    ///
108    /// # Note
109    /// This method is especially useful in genetic operations like crossover, where typically
110    /// two distinct individuals need to be selected from the population.
111    #[inline]
112    fn select_distinct<'a>(
113        &self,
114        population: &'a Population<I>,
115        rng: &mut R,
116        max_tries: usize,
117        excluded: &I,
118    ) -> Option<(usize, &'a I)>
119    where
120        I: Individual,
121        R: Rng,
122    {
123        for _ in 0..max_tries {
124            let (index, candidate) = self.select(population, rng);
125            if candidate != excluded {
126                return Some((index, candidate));
127            }
128        }
129        None
130    }
131}
132
133/// Represents the tournament selection algorithm.
134///
135/// # Note
136/// The tournament selection method involves selecting a fixed number of random
137/// candidates from the population (determined by tournament's size) and choosing
138/// the candidate with the highest fitness.
139#[derive(Clone, Copy, PartialEq, Eq)]
140pub struct TournamentSelection {
141    size: usize,
142}
143
144impl TournamentSelection {
145    /// Creates a new instance.
146    ///
147    /// # Panics
148    /// The method will panic if `size` is zero.
149    pub fn new(size: usize) -> Self {
150        assert!(size != 0);
151        Self { size }
152    }
153
154    /// Gets the tournament size.
155    pub fn size(&self) -> usize {
156        self.size
157    }
158
159    /// Sets the tournament size.
160    ///
161    /// # Panics
162    /// The method will panic if `size` is zero.
163    pub fn set_size(&mut self, size: usize) {
164        assert!(size != 0);
165        self.size = size
166    }
167}
168
169impl<I, R> SelectionMechanism<I, R> for TournamentSelection
170where
171    I: Individual,
172    R: Rng,
173{
174    #[inline]
175    fn prepare(&mut self, _population: &Population<I>) {}
176
177    #[inline]
178    fn select<'a>(&self, population: &'a Population<I>, rng: &mut R) -> (usize, &'a I) {
179        rng.sample_iter(Uniform::new(0, population.len()))
180            .take(self.size)
181            .max() // The population is already sorted by the fitness of individuals
182            .map(|i| (i, &population[i]))
183            .unwrap()
184    }
185}
186
187/// Represents the roulette-wheel selection algorithm used in genetic algorithms.
188///
189/// # Note
190/// The roulette wheel selection method calculates the total fitness of the
191/// population and chooses a random target value. It iterates over the population,
192/// summing up the fitness values, and selects the first individual whose cumulative
193/// fitness is greater than or equal to the target value.
194#[derive(Default, Clone, Copy, PartialEq)]
195pub struct RouletteWheelSelection {
196    total_fitness: f64,
197}
198
199impl RouletteWheelSelection {
200    /// Creates a new instance.
201    pub fn new() -> Self {
202        Self { total_fitness: 0.0 }
203    }
204}
205
206impl<I, R> SelectionMechanism<I, R> for RouletteWheelSelection
207where
208    I: Individual,
209    R: Rng,
210{
211    #[inline]
212    fn prepare(&mut self, population: &Population<I>) {
213        self.total_fitness = population.par_iter().map(|i| i.fitness()).sum();
214    }
215
216    #[inline]
217    fn select<'a>(&self, population: &'a Population<I>, rng: &mut R) -> (usize, &'a I) {
218        let target_fitness = rng.gen::<f64>() * self.total_fitness;
219        let mut cumulative_fitness = 0.0;
220        for (index, individual) in population.iter().enumerate() {
221            cumulative_fitness += individual.fitness();
222            if cumulative_fitness >= target_fitness {
223                return (index, individual);
224            }
225        }
226        (population.len() - 1, population.last().unwrap())
227    }
228}
229
230/// Represents the Boltzmann selection algorithm used in genetic algorithms.
231///
232/// # Note
233/// In Boltzmann selection, the selection probability of an individual is determined by
234/// its fitness relative to other individuals in the population and the algorithm's
235/// temperature parameter. The Boltzmann distribution from statistical mechanics is used
236/// to create a probability distribution for selection.
237///
238/// This strategy encourages exploration in the early stages and exploitation in the
239/// later stages of the algorithm by adjusting the temperature and cooling rate.
240#[derive(Clone, Copy, PartialEq)]
241pub struct BoltzmannSelection {
242    temperature: f64,
243    cooling_rate: f64,
244    total_scaled_fitness: f64,
245}
246
247impl BoltzmannSelection {
248    /// Creates a new instance.
249    ///
250    /// # Panic
251    /// The method will panic if `cooling_rate` is zero.
252    pub fn new(temperature: f64, cooling_rate: f64) -> Self {
253        assert!(cooling_rate != 0.0);
254        Self {
255            temperature,
256            cooling_rate,
257            total_scaled_fitness: 0.0,
258        }
259    }
260
261    /// Gets the current temperature.
262    pub fn temperature(&self) -> f64 {
263        self.temperature
264    }
265
266    /// Sets the current temperature.
267    pub fn set_temperature(&mut self, temperature: f64) {
268        self.temperature = temperature
269    }
270
271    /// Gets the cooling rate.
272    pub fn cooling_rate(&self) -> f64 {
273        self.cooling_rate
274    }
275
276    /// Sets the cooling rate.
277    ///
278    /// # Panic
279    /// The method will panic if `cooling_rate` is zero.
280    pub fn set_cooling_rate(&mut self, cooling_rate: f64) {
281        assert!(cooling_rate != 0.0);
282        self.cooling_rate = cooling_rate
283    }
284
285    /// Calculates the Boltzmann scaled fitness of an individual.
286    #[inline]
287    fn scaled_fitness<I: Individual>(&self, individual: &I) -> f64 {
288        (individual.fitness() / self.temperature).exp()
289    }
290}
291
292impl<I, R> SelectionMechanism<I, R> for BoltzmannSelection
293where
294    I: Individual,
295    R: Rng,
296{
297    #[inline]
298    fn prepare(&mut self, population: &Population<I>) {
299        self.temperature *= self.cooling_rate;
300        self.total_scaled_fitness = population
301            .par_iter()
302            .map(|i| self.scaled_fitness(i))
303            .sum();
304    }
305
306    #[inline]
307    fn select<'a>(&self, population: &'a Population<I>, rng: &mut R) -> (usize, &'a I) {
308        let target_fitness = rng.gen::<f64>() * self.total_scaled_fitness;
309        let mut cumulative_fitness = 0.0;
310        for (index, individual) in population.iter().enumerate() {
311            cumulative_fitness += self.scaled_fitness(individual);
312            if cumulative_fitness >= target_fitness {
313                return (index, individual);
314            }
315        }
316        (population.len() - 1, population.last().unwrap())
317    }
318}
319
320/// Represents the rank selection algorithm used in genetic algorithms.
321///
322/// # Note
323/// In rank selection, the population is first sorted by fitness. A random target rank is
324/// chosen, based on the total ranks of the population. The algorithm iterates over the
325/// sorted population, summing up the ranks, and returns the first individual whose
326/// cumulative rank is greater than or equal to the target rank.
327#[derive(Default, Clone, Copy, PartialEq, Eq)]
328pub struct RankSelection {}
329
330impl RankSelection {
331    /// Creates a new instance.
332    pub fn new() -> Self {
333        Self {}
334    }
335}
336
337impl<I, R> SelectionMechanism<I, R> for RankSelection
338where
339    I: Individual,
340    R: Rng,
341{
342    #[inline]
343    fn prepare(&mut self, _population: &Population<I>) {
344        // The population is already sorted by the fitness of individuals
345    }
346
347    #[inline]
348    fn select<'a>(&self, population: &'a Population<I>, rng: &mut R) -> (usize, &'a I) {
349        let n = population.len();
350        let total_ranks = n * (n + 1) / 2;
351        let target_rank = rng.gen_range(1..=total_ranks);
352
353        let mut cumulative_rank = 0;
354        for (index, individual) in population.iter().enumerate() {
355            cumulative_rank += index + 1;
356            if cumulative_rank >= target_rank {
357                return (index, individual);
358            }
359        }
360        (0, population.first().unwrap())
361    }
362}
363
364/// Represents the elitist selection algorithm used in genetic algorithms.
365///
366/// # Note
367/// Elitist selection directly favors the best-performing individuals in a population,
368/// ensuring that top performers have a chance to pass their genetic information to the
369/// next generation. This promotes convergence to an optimal solution.
370///
371/// The algorithm works by selecting a fixed percentage of the best individuals based
372/// on their fitness values. This typically involves sorting the population by fitness
373/// and selecting the top-ranked individuals.
374///
375/// Note that using a high selection ratio in elitist selection may lead to premature
376/// convergence and a loss of population diversity.
377pub struct ElitistSelection {
378    ratio: f64,
379}
380
381impl ElitistSelection {
382    /// Creates a new instance.
383    ///
384    /// # Panics
385    /// The method will panic if `ratio` is not between 0.0 (inclusive)
386    /// and 1.0 (exclusive).
387    pub fn new(ratio: f64) -> Self {
388        assert!((0.0..1.0).contains(&ratio));
389        Self { ratio }
390    }
391
392    /// Gets the selection ratio.
393    pub fn ratio(&self) -> f64 {
394        self.ratio
395    }
396
397    /// Sets the selection ratio.
398    ///
399    /// # Panics
400    /// The method will panic if `ratio` is not between 0.0 (inclusive)
401    /// and 1.0 (exclusive).
402    pub fn set_ratio(&mut self, ratio: f64) {
403        assert!((0.0..1.0).contains(&ratio));
404        self.ratio = ratio
405    }
406}
407
408impl<I, R> SelectionMechanism<I, R> for ElitistSelection
409where
410    I: Individual,
411    R: Rng,
412{
413    #[inline]
414    fn prepare(&mut self, _population: &Population<I>) {
415        // The population is already sorted by the fitness of individuals
416    }
417
418    #[inline]
419    fn select<'a>(&self, population: &'a Population<I>, rng: &mut R) -> (usize, &'a I) {
420        let selection_bound = (population.len() as f64 * self.ratio).floor() as usize;
421        let index = rng.gen_range(selection_bound..population.len());
422        (index, &population[index])
423    }
424}
425
426/// Represents the linear selection algorithm used in genetic algorithms.
427///
428/// # Note
429/// Linear selection is a variant of rank-based selection that introduces a bias factor
430/// to adjust the selection pressure. Higher bias values result in stronger selection
431/// pressure, which means individuals with higher fitness values have a higher chance
432/// of being selected.
433#[derive(Clone, Copy, PartialEq)]
434pub struct LinearSelection {
435    bias: f64,
436}
437
438impl LinearSelection {
439    /// Creates a new instance.
440    pub fn new(bias: f64) -> Self {
441        Self { bias }
442    }
443
444    /// Gets the bias factor.
445    pub fn bias(&self) -> f64 {
446        self.bias
447    }
448
449    /// Sets the bias factor.
450    pub fn set_bias(&mut self, bias: f64) {
451        self.bias = bias
452    }
453}
454
455impl<I, R> SelectionMechanism<I, R> for LinearSelection
456where
457    I: Individual,
458    R: Rng,
459{
460    #[inline]
461    fn prepare(&mut self, _population: &Population<I>) {
462        // The population is already sorted by the fitness of individuals
463    }
464
465    #[inline]
466    fn select<'a>(&self, population: &'a Population<I>, rng: &mut R) -> (usize, &'a I) {
467        let index = population.len()
468            - ((population.len() as f64)
469                * (self.bias
470                    - ((self.bias * self.bias - 4.0 * (self.bias - 1.0) * rng.gen::<f64>())
471                        .sqrt()))
472                / 2.0
473                / (self.bias - 1.0)) as usize
474            - 1;
475        (index, &population[index])
476    }
477}
478
479#[cfg(test)]
480mod tests {
481    use super::*;
482
483    #[derive(Debug, Clone, Copy, PartialEq)]
484    struct MockIndividual {
485        fitness: f64,
486    }
487
488    impl Individual for MockIndividual {
489        fn fitness(&self) -> f64 {
490            self.fitness
491        }
492    }
493
494    const POPULATION_SIZE: usize = 10;
495    const ITERATIONS: usize = 100000;
496    const CONFIDENCE: f64 = 0.01;
497
498    fn create_test_population() -> Population<MockIndividual> {
499        (0..POPULATION_SIZE)
500            .map(|i| MockIndividual {
501                fitness: i as f64 / POPULATION_SIZE as f64,
502            })
503            .collect::<Vec<_>>()
504            .try_into()
505            .unwrap()
506    }
507
508    fn collect_samples<S>(strategy: &mut S) -> (Vec<MockIndividual>, Vec<u32>)
509    where
510        S: SelectionMechanism<MockIndividual, SmallRng>,
511    {
512        let mut rng = SmallRng::seed_from_u64(0);
513        let population = create_test_population();
514        let mut counts = vec![0; POPULATION_SIZE];
515
516        strategy.prepare(&population);
517        for _ in 0..ITERATIONS {
518            let (index, _) = strategy.select(&population, &mut rng);
519            counts[index] += 1;
520        }
521        (population.into(), counts)
522    }
523
524    #[test]
525    fn test_tournament_selection_probabilities() {
526        let mut tournament = TournamentSelection::new(2);
527        let (population, observed_counts) = collect_samples(&mut tournament);
528
529        for (index, count) in observed_counts.into_iter().enumerate() {
530            let observed_probability = count as f64 / ITERATIONS as f64;
531            let expected_probability = (1.0
532                - (index as f64 / population.len() as f64).powi(tournament.size as i32))
533                - (1.0
534                    - ((index as f64 + 1.0) / population.len() as f64)
535                        .powi(tournament.size as i32));
536
537            assert!((observed_probability - expected_probability).abs() < CONFIDENCE);
538        }
539    }
540
541    #[test]
542    fn test_roulette_wheel_selection_probabilities() {
543        let mut roulette_wheel = RouletteWheelSelection::new();
544        let (population, observed_counts) = collect_samples(&mut roulette_wheel);
545
546        let total_fitness = population.iter().map(|i| i.fitness).sum::<f64>();
547        for (index, count) in observed_counts.into_iter().enumerate() {
548            let observed_probability = count as f64 / ITERATIONS as f64;
549            let expected_probability = population[index].fitness / total_fitness;
550
551            assert!((observed_probability - expected_probability).abs() < CONFIDENCE);
552        }
553    }
554
555    #[test]
556    fn test_rank_selection_probabilities() {
557        let mut rank = RankSelection::new();
558        let (population, observed_counts) = collect_samples(&mut rank);
559
560        let total_ranks = population.len() * (population.len() + 1) / 2;
561        for (index, count) in observed_counts.into_iter().enumerate() {
562            let observed_probability = count as f64 / ITERATIONS as f64;
563            let expected_probability = (index + 1) as f64 / total_ranks as f64;
564
565            assert!((observed_probability - expected_probability).abs() < CONFIDENCE);
566        }
567    }
568
569    #[test]
570    fn test_elitist_selection_probabilities() {
571        let mut elitist = ElitistSelection::new(0.7);
572        let (population, observed_counts) = collect_samples(&mut elitist);
573
574        let selection_bound = (population.len() as f64 * elitist.ratio).floor() as usize;
575        for (index, count) in observed_counts.into_iter().enumerate() {
576            let observed_probability = count as f64 / ITERATIONS as f64;
577            let expected_probability = if index >= selection_bound {
578                1.0 / (population.len() - selection_bound) as f64
579            } else {
580                0.0
581            };
582
583            assert!((observed_probability - expected_probability).abs() < CONFIDENCE);
584        }
585    }
586
587    #[test]
588    fn test_boltzmann_selection_probabilities() {
589        // We keep the temperature constant for this test (cooling_rate = 1.0)
590        let mut boltzmann = BoltzmannSelection::new(5.0, 1.0);
591        let (population, observed_counts) = collect_samples(&mut boltzmann);
592
593        let total_scaled_fitness = population
594            .iter()
595            .map(|i| (i.fitness / boltzmann.temperature).exp())
596            .sum::<f64>();
597        for (index, count) in observed_counts.into_iter().enumerate() {
598            let observed_probability = count as f64 / ITERATIONS as f64;
599            let expected_probability =
600                (population[index].fitness / boltzmann.temperature).exp() / total_scaled_fitness;
601
602            assert!((observed_probability - expected_probability).abs() < CONFIDENCE);
603        }
604    }
605
606    #[test]
607    fn test_linear_selection_probabilities() {
608        let mut linear = LinearSelection::new(1.25);
609        let (_, observed_counts) = collect_samples(&mut linear);
610
611        let mut last_observed_probability: Option<f64> = None;
612        for count in observed_counts {
613            let observed_probability = count as f64 / ITERATIONS as f64;
614            if let Some(previous_observed_probability) = last_observed_probability {
615                assert!(observed_probability + CONFIDENCE > previous_observed_probability);
616            }
617            last_observed_probability = Some(observed_probability);
618        }
619    }
620}
rusty_genes/operators/selection.rs

rusty_genes/operators/
selection.rs
