wafrift_evolution/evolution/crossover/
strategies.rs

1use crate::evolution::Chromosome;
2use rand::Rng;
3
4/// Crossover strategy for breeding chromosomes.
5#[derive(Debug, Clone, Copy, PartialEq, Eq)]
6pub enum CrossoverStrategy {
7    Uniform,
8    SinglePoint,
9    MultiPoint(usize),
10    OrderBased,
11}
12
13fn canonical_gene_names(parent_a: &Chromosome, parent_b: &Chromosome) -> Vec<String> {
14    let mut names = Vec::new();
15    for (name, _) in &parent_a.genes {
16        if !names.contains(name) {
17            names.push(name.clone());
18        }
19    }
20    for (name, _) in &parent_b.genes {
21        if !names.contains(name) {
22            names.push(name.clone());
23        }
24    }
25    names
26}
27
28fn gene_value_for(parent: &Chromosome, name: &str) -> Option<String> {
29    parent
30        .genes
31        .iter()
32        .find(|(gene_name, _)| gene_name == name)
33        .map(|(_, value)| value.clone())
34}
35
36fn value_from_parent(primary: &Chromosome, secondary: &Chromosome, name: &str) -> String {
37    gene_value_for(primary, name)
38        .or_else(|| gene_value_for(secondary, name))
39        .unwrap_or_else(|| String::from("None"))
40}
41
42fn build_child<F>(parent_a: &Chromosome, parent_b: &Chromosome, mut choose_a: F) -> Chromosome
43where
44    F: FnMut(usize, &str) -> bool,
45{
46    let child_genes = canonical_gene_names(parent_a, parent_b)
47        .into_iter()
48        .enumerate()
49        .map(|(index, name)| {
50            let value = if choose_a(index, &name) {
51                value_from_parent(parent_a, parent_b, &name)
52            } else {
53                value_from_parent(parent_b, parent_a, &name)
54            };
55            (name, value)
56        })
57        .collect();
58    Chromosome::new(child_genes)
59}
60
61/// Uniform crossover: each gene independently from either parent.
62#[must_use]
63pub fn uniform_crossover(
64    parent_a: &Chromosome,
65    parent_b: &Chromosome,
66    rng: &mut impl Rng,
67) -> Chromosome {
68    build_child(parent_a, parent_b, |_, _| rng.gen_bool(0.5))
69}
70
71/// Single-point crossover: split genes at one point and swap tails.
72#[must_use]
73pub fn single_point_crossover(
74    parent_a: &Chromosome,
75    parent_b: &Chromosome,
76    rng: &mut impl Rng,
77) -> Chromosome {
78    let gene_names = canonical_gene_names(parent_a, parent_b);
79    let max_len = gene_names.len();
80    if max_len == 0 {
81        return Chromosome::new(Vec::new());
82    }
83    let point = rng.gen_range(1..=max_len);
84    build_child(parent_a, parent_b, |index, _| index < point)
85}
86
87/// Multi-point crossover: split at multiple points.
88#[must_use]
89pub fn multi_point_crossover(
90    parent_a: &Chromosome,
91    parent_b: &Chromosome,
92    num_points: usize,
93    rng: &mut impl Rng,
94) -> Chromosome {
95    let gene_names = canonical_gene_names(parent_a, parent_b);
96    let max_len = gene_names.len();
97    if max_len == 0 {
98        return Chromosome::new(Vec::new());
99    }
100    let mut points: Vec<usize> = (0..num_points.min(max_len))
101        .map(|_| rng.gen_range(1..max_len))
102        .collect();
103    points.sort_unstable();
104    points.dedup();
105    build_child(parent_a, parent_b, |index, _| {
106        points.iter().filter(|point| index >= **point).count() % 2 == 0
107    })
108}
109
110/// Order-based crossover: preserves relative ordering of genes.
111#[must_use]
112pub fn order_based_crossover(
113    parent_a: &Chromosome,
114    parent_b: &Chromosome,
115    rng: &mut impl Rng,
116) -> Chromosome {
117    build_child(parent_a, parent_b, |_, name| {
118        let prefer_a = parent_a
119            .genes
120            .iter()
121            .position(|(gene_name, _)| gene_name == name)
122            .unwrap_or(usize::MAX);
123        let prefer_b = parent_b
124            .genes
125            .iter()
126            .position(|(gene_name, _)| gene_name == name)
127            .unwrap_or(usize::MAX);
128        if prefer_a == prefer_b {
129            rng.gen_bool(0.5)
130        } else {
131            prefer_a < prefer_b
132        }
133    })
134}
135
136/// Perform crossover using a specified strategy.
137#[must_use]
138pub fn crossover_with_strategy(
139    parent_a: &Chromosome,
140    parent_b: &Chromosome,
141    strategy: CrossoverStrategy,
142    rng: &mut impl Rng,
143) -> Chromosome {
144    match strategy {
145        CrossoverStrategy::Uniform => uniform_crossover(parent_a, parent_b, rng),
146        CrossoverStrategy::SinglePoint => single_point_crossover(parent_a, parent_b, rng),
147        CrossoverStrategy::MultiPoint(points) => {
148            multi_point_crossover(parent_a, parent_b, points, rng)
149        }
150        CrossoverStrategy::OrderBased => order_based_crossover(parent_a, parent_b, rng),
151    }
152}
wafrift_evolution/evolution/crossover/strategies.rs

wafrift_evolution/evolution/crossover/
strategies.rs
