use crate::utils::fitness::Direction;
use serde::Serialize;
#[derive(Clone, Debug, PartialEq, Serialize)]
pub enum SelectionMethod {
Tournament { tournament_size: usize },
Roulette,
}
impl Default for SelectionMethod {
fn default() -> Self {
SelectionMethod::Tournament { tournament_size: 2 }
}
}
impl SelectionMethod {
pub fn apply(
&self,
scores: &[f32],
direction: Direction,
rng: &mut fastrand::Rng,
champion_count: usize,
) -> Vec<usize> {
match self {
Self::Tournament { tournament_size } => {
tournament_select(scores, direction, rng, *tournament_size, champion_count)
}
Self::Roulette => roulette_select(scores, direction, rng),
}
}
pub fn draw_one(
&self,
scores: &[f32],
direction: Direction,
rng: &mut fastrand::Rng,
) -> Option<usize> {
if scores.is_empty() {
return None;
}
match self {
Self::Roulette => roulette_select(scores, direction, rng).into_iter().next(),
Self::Tournament { tournament_size } => {
let k = (*tournament_size).max(1).min(scores.len());
let mut winner = rng.usize(0..scores.len());
for _ in 1..k {
let candidate = rng.usize(0..scores.len());
if direction.cmp(scores[candidate], scores[winner])
== std::cmp::Ordering::Greater
{
winner = candidate;
}
}
Some(winner)
}
}
}
pub fn label(&self) -> String {
match self {
Self::Tournament { tournament_size } => {
format!("tournament(k={})", tournament_size)
}
Self::Roulette => "roulette".to_string(),
}
}
}
fn roulette_select(scores: &[f32], direction: Direction, rng: &mut fastrand::Rng) -> Vec<usize> {
if scores.is_empty() {
return Vec::new();
}
let raw: Vec<f32> = match direction {
Direction::Maximize => scores.to_vec(),
Direction::Minimize => {
let max = scores.iter().cloned().fold(f32::NEG_INFINITY, f32::max);
scores.iter().map(|&s| max - s).collect()
}
};
let weights: Vec<f32> = raw.iter().map(|&w| w.max(0.0)).collect();
let total: f32 = weights.iter().sum();
if total <= 0.0 {
return vec![rng.usize(0..scores.len())];
}
let mut roll = rng.f32() * total;
for (i, &w) in weights.iter().enumerate() {
roll -= w;
if roll <= 0.0 {
return vec![i];
}
}
vec![weights.len() - 1]
}
fn tournament_select(
scores: &[f32],
direction: Direction,
rng: &mut fastrand::Rng,
tournament: usize,
champion_count: usize,
) -> Vec<usize> {
let n = scores.len();
if n == 0 {
return Vec::new();
}
let tournament = tournament.max(1);
let mut chosen = Vec::with_capacity(n);
let mut ranked: Vec<(usize, f32)> = scores.iter().enumerate().map(|(i, &s)| (i, s)).collect();
ranked.sort_by(|a, b| direction.cmp(a.1, b.1).reverse());
let elite_n = champion_count.min(n);
for &(idx, _) in ranked.iter().take(elite_n) {
chosen.push(idx);
}
while chosen.len() < n {
let mut winner = rng.usize(0..n);
for _ in 1..tournament {
let candidate = rng.usize(0..n);
if direction.cmp(scores[candidate], scores[winner]) == std::cmp::Ordering::Greater {
winner = candidate;
}
}
chosen.push(winner);
}
chosen
}
#[cfg(test)]
mod tests {
use super::*;
use proptest::prelude::*;
#[test]
fn test_tournament_labels_reflect_configured_size() {
let t = SelectionMethod::Tournament { tournament_size: 5 };
assert_eq!(t.label(), "tournament(k=5)");
assert_eq!(format!("{t}"), "tournament(size=5)");
let scores = vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0];
let mut rng = fastrand::Rng::with_seed(42);
let picked = t.apply(&scores, Direction::Maximize, &mut rng, 1);
assert_eq!(picked.len(), scores.len());
assert_eq!(SelectionMethod::default().label(), "tournament(k=2)");
}
#[test]
fn test_tournament_select_empty_and_single() {
let mut rng = fastrand::Rng::with_seed(1);
assert!(tournament_select(&[], Direction::Minimize, &mut rng, 3, 1).is_empty());
let one = tournament_select(&[2.5], Direction::Minimize, &mut rng, 3, 1);
assert_eq!(one, vec![0]);
}
#[test]
fn test_tournament_select_elitism_minimize() {
let scores = [3.0, 1.0, 4.0, 2.0];
let mut rng = fastrand::Rng::with_seed(7);
let chosen = tournament_select(&scores, Direction::Minimize, &mut rng, 2, 1);
assert_eq!(chosen.len(), scores.len());
assert!(chosen.contains(&1));
assert!(chosen.iter().all(|&i| i < scores.len()));
}
#[test]
fn test_tournament_select_elitism_maximize() {
let scores = [3.0, 1.0, 4.0, 2.0];
let mut rng = fastrand::Rng::with_seed(7);
let chosen = tournament_select(&scores, Direction::Maximize, &mut rng, 2, 1);
assert_eq!(chosen.len(), scores.len());
assert!(chosen.contains(&2));
}
#[test]
fn test_tournament_select_trends_toward_best() {
let scores: Vec<f32> = (0..8).map(|i| i as f32).collect();
let mut rng = fastrand::Rng::with_seed(3);
let chosen = tournament_select(&scores, Direction::Maximize, &mut rng, 8, 1);
assert!(chosen.contains(&7));
let best_count = chosen.iter().filter(|&&i| i == 7).count();
assert!(best_count >= chosen.len() / 2);
}
#[test]
fn test_tournament_select_multi_elite() {
let scores = [3.0, 1.0, 4.0, 2.0];
let mut rng = fastrand::Rng::with_seed(7);
let chosen = tournament_select(&scores, Direction::Maximize, &mut rng, 2, 2);
assert_eq!(chosen.len(), scores.len());
assert!(chosen[0] == 2 || chosen[1] == 2); assert!(chosen[0] == 0 || chosen[1] == 0); }
#[test]
fn test_apply_dispatches_tournament() {
let method = SelectionMethod::Tournament { tournament_size: 4 };
let scores = [5.0, 1.0, 3.0, 2.0];
let mut rng = fastrand::Rng::with_seed(9);
let chosen = method.apply(&scores, Direction::Minimize, &mut rng, 2);
assert_eq!(chosen.len(), 4);
assert!(chosen.contains(&1)); }
#[test]
fn test_label() {
let m = SelectionMethod::Tournament { tournament_size: 5 };
assert_eq!(m.label(), "tournament(k=5)");
} #[test]
fn test_roulette_biased_toward_higher_score() {
let scores = [3.0, 1.0];
let mut rng = fastrand::Rng::with_seed(99);
let n = 2_000;
let mut first = 0usize;
for _ in 0..n {
if SelectionMethod::Roulette
.apply(&scores, Direction::Maximize, &mut rng, 0)
.first()
== Some(&0)
{
first += 1;
}
}
let frac = first as f32 / n as f32;
assert!(
(0.65..0.85).contains(&frac),
"index 0 (weight 3) should win ~75% of draws, got {frac}"
);
}
#[test]
fn test_roulette_deterministic_and_minimize_inverts() {
let scores = [1.0, 9.0];
let mut rng = fastrand::Rng::with_seed(5);
let mut first = 0usize;
for _ in 0..500 {
if roulette_select(&scores, Direction::Minimize, &mut rng)[0] == 0 {
first += 1;
}
}
assert!(
first > 350,
"minimize should favor the smallest loss, got {first}/500"
);
let mut a = fastrand::Rng::with_seed(1234);
let mut b = fastrand::Rng::with_seed(1234);
for _ in 0..50 {
assert_eq!(
roulette_select(&scores, Direction::Maximize, &mut a),
roulette_select(&scores, Direction::Maximize, &mut b),
);
}
}
#[test]
fn draw_one_returns_none_only_for_an_empty_pool() {
let mut rng = fastrand::Rng::with_seed(1);
for method in [
SelectionMethod::Roulette,
SelectionMethod::Tournament { tournament_size: 3 },
] {
assert_eq!(method.draw_one(&[], Direction::Maximize, &mut rng), None);
let one = method.draw_one(&[7.0], Direction::Maximize, &mut rng);
assert_eq!(one, Some(0), "a one-net pool has one possible parent");
}
}
#[test]
fn tournament_draw_one_pressures_toward_the_best() {
let scores = [1.0, 5.0, 3.0, 9.0];
let method = SelectionMethod::Tournament { tournament_size: 4 };
let draws = 600;
let rate = |direction: Direction, seed: u64, winner: usize| {
let mut rng = fastrand::Rng::with_seed(seed);
let hits = (0..draws)
.filter(|_| method.draw_one(&scores, direction, &mut rng) == Some(winner))
.count();
hits as f32 / draws as f32
};
let best = rate(Direction::Maximize, 11, 3);
let worst = rate(Direction::Maximize, 12, 0);
assert!(
best > 0.55,
"the leader should win most tournaments, got {best}"
);
assert!(best > worst, "pressure toward the best: {best} vs {worst}");
let best_min = rate(Direction::Minimize, 13, 0);
assert!(
best_min > 0.55,
"Minimize must flip the favourite to the smallest score, got {best_min}"
);
}
#[test]
fn tournament_of_one_is_a_uniform_draw() {
let scores = [0.0, 0.0, 0.0, 0.0];
let method = SelectionMethod::Tournament { tournament_size: 1 };
let mut rng = fastrand::Rng::with_seed(7);
let mut seen = [false; 4];
for _ in 0..400 {
let i = method
.draw_one(&scores, Direction::Maximize, &mut rng)
.unwrap();
seen[i] = true;
}
assert!(seen.iter().all(|&s| s), "k=1 must reach every slot");
}
proptest! {
#[test]
fn prop_draw_one_stays_in_range_and_is_deterministic(
n in 1usize..20,
seed in 0u64..1_000_000u64,
maximize in proptest::bool::ANY,
tournament in 1usize..8,
) {
let scores: Vec<f32> = (0..n).map(|i| i as f32).collect();
let dir = if maximize { Direction::Maximize } else { Direction::Minimize };
let method = SelectionMethod::Tournament { tournament_size: tournament };
let mut a = fastrand::Rng::with_seed(seed);
let mut b = fastrand::Rng::with_seed(seed);
let first = method.draw_one(&scores, dir, &mut a);
prop_assert!(first.is_some());
prop_assert!(first.unwrap() < n);
prop_assert_eq!(first, method.draw_one(&scores, dir, &mut b));
}
}
proptest! {
#[test]
fn prop_select_preserves_size_and_elitism(
n in 1usize..12,
seed in 0u64..1_000_000u64,
maximize in proptest::bool::ANY,
tournament in 1usize..6,
) {
let mut rng = fastrand::Rng::with_seed(seed);
let scores: Vec<f32> = (0..n).map(|i| (i as f32) * 0.5 - 2.0).collect();
let dir = if maximize { Direction::Maximize } else { Direction::Minimize };
let method = SelectionMethod::Tournament { tournament_size: tournament };
let chosen = method.apply(&scores, dir, &mut rng, 1);
prop_assert_eq!(chosen.len(), n);
prop_assert!(chosen.iter().all(|&i| i < n));
let best = if maximize { n - 1 } else { 0 };
prop_assert!(chosen.contains(&best), "elitism keeps the best");
}
}
}