evolution_ternary/
selection.rs

1//! Selection methods: tournament, roulette wheel, rank-based.
2
3use crate::population::{TernaryAgent, TernaryPopulation, SimpleRng};
4
5/// Selection method to use.
6#[derive(Clone, Debug)]
7pub enum SelectionMethod {
8    /// Tournament selection with given tournament size.
9    Tournament { size: usize },
10    /// Roulette wheel (fitness-proportionate) selection.
11    RouletteWheel,
12    /// Rank-based selection: linear ranking with selective pressure.
13    RankBased { pressure: f64 },
14}
15
16impl SelectionMethod {
17    /// Default tournament selection (size 3).
18    pub fn tournament() -> Self {
19        SelectionMethod::Tournament { size: 3 }
20    }
21
22    /// Default rank-based (pressure 1.5).
23    pub fn rank_based() -> Self {
24        SelectionMethod::RankBased { pressure: 1.5 }
25    }
26}
27
28/// Selection trait — picks parents from a population.
29pub trait Selection {
30    /// Select `n` parents from the population.
31    fn select(&self, pop: &TernaryPopulation, n: usize, rng: &mut SimpleRng) -> Vec<TernaryAgent>;
32}
33
34impl Selection for SelectionMethod {
35    fn select(&self, pop: &TernaryPopulation, n: usize, rng: &mut SimpleRng) -> Vec<TernaryAgent> {
36        match self {
37            SelectionMethod::Tournament { size } => tournament_select(pop, n, *size, rng),
38            SelectionMethod::RouletteWheel => roulette_select(pop, n, rng),
39            SelectionMethod::RankBased { pressure } => rank_select(pop, n, *pressure, rng),
40        }
41    }
42}
43
44fn tournament_select(pop: &TernaryPopulation, n: usize, k: usize, rng: &mut SimpleRng) -> Vec<TernaryAgent> {
45    let pop_size = pop.size();
46    let k = k.max(1).min(pop_size);
47    (0..n)
48        .map(|_| {
49            let contenders: Vec<usize> = (0..k)
50                .map(|_| (rng.next_u64() as usize) % pop_size)
51                .collect();
52            let best_idx = *contenders.iter().max_by(|&&i, &&j| {
53                pop.agents[i].fitness.partial_cmp(&pop.agents[j].fitness).unwrap_or(std::cmp::Ordering::Equal)
54            }).unwrap();
55            pop.agents[best_idx].clone()
56        })
57        .collect()
58}
59
60fn roulette_select(pop: &TernaryPopulation, n: usize, rng: &mut SimpleRng) -> Vec<TernaryAgent> {
61    let min_fit = pop.agents.iter().map(|a| a.fitness).fold(f64::INFINITY, f64::min);
62    // Shift to make all fitnesses positive
63    let shift = if min_fit < 0.0 { -min_fit + 1.0 } else { 0.0 };
64    let shifted: Vec<f64> = pop.agents.iter().map(|a| a.fitness + shift).collect();
65    let total: f64 = shifted.iter().sum();
66    
67    if total == 0.0 {
68        // Uniform random if all fitness is zero
69        return (0..n)
70            .map(|_| pop.agents[(rng.next_u64() as usize) % pop.size()].clone())
71            .collect();
72    }
73
74    (0..n)
75        .map(|_| {
76            let mut r = rng.next_f64() * total;
77            for (i, &s) in shifted.iter().enumerate() {
78                r -= s;
79                if r <= 0.0 {
80                    return pop.agents[i].clone();
81                }
82            }
83            pop.agents.last().unwrap().clone()
84        })
85        .collect()
86}
87
88fn rank_select(pop: &TernaryPopulation, n: usize, pressure: f64, rng: &mut SimpleRng) -> Vec<TernaryAgent> {
89    // Sort by fitness descending, assign rank-based probabilities
90    let mut indexed: Vec<(usize, f64)> = pop.agents.iter().enumerate()
91        .map(|(i, a)| (i, a.fitness))
92        .collect();
93    indexed.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
94    
95    let pop_size = pop.size() as f64;
96    // Linear ranking: p_i = (2 - s + 2*(s-1)*(rank_i)/(N-1)) / N
97    let s = pressure.clamp(1.0, 2.0);
98    let probs: Vec<f64> = (0..indexed.len())
99        .map(|rank| {
100            let rank = rank as f64;
101            (2.0 - s + 2.0 * (s - 1.0) * (indexed.len() as f64 - 1.0 - rank) / (indexed.len() as f64 - 1.0).max(1.0)) / pop_size
102        })
103        .collect();
104    
105    let total: f64 = probs.iter().sum();
106    (0..n)
107        .map(|_| {
108            let mut r = rng.next_f64() * total;
109            for (i, &p) in probs.iter().enumerate() {
110                r -= p;
111                if r <= 0.0 {
112                    return pop.agents[indexed[i].0].clone();
113                }
114            }
115            pop.agents[indexed.last().unwrap().0].clone()
116        })
117        .collect()
118}
evolution_ternary/selection.rs

evolution_ternary/
selection.rs
