u_schedule/ga/
operators.rs

1//! Configurable genetic operators for scheduling.
2//!
3//! Provides runtime-selectable crossover and mutation strategies
4//! via [`GeneticOperators`].
5//!
6//! # Usage
7//!
8//! ```
9//! use u_schedule::ga::operators::{GeneticOperators, CrossoverType, MutationType};
10//!
11//! let ops = GeneticOperators::default();
12//! assert_eq!(ops.crossover_type, CrossoverType::POX);
13//! assert_eq!(ops.mutation_type, MutationType::Swap);
14//! ```
15
16use rand::Rng;
17
18use super::chromosome::{
19    insert_mutation, invert_mutation, jox_crossover, lox_crossover, mav_mutation, pox_crossover,
20    swap_mutation, ScheduleChromosome,
21};
22use super::problem::ActivityInfo;
23
24/// Crossover strategy for scheduling chromosomes.
25#[derive(Debug, Clone, Copy, PartialEq, Eq)]
26pub enum CrossoverType {
27    /// Precedence Operation Crossover (Bierwirth et al., 1996).
28    POX,
29    /// Linear Order Crossover (Falkenauer & Bouffouix, 1991).
30    LOX,
31    /// Job-based Order Crossover (Yamada & Nakano, 1997).
32    JOX,
33}
34
35/// Mutation strategy for scheduling chromosomes.
36#[derive(Debug, Clone, Copy, PartialEq, Eq)]
37pub enum MutationType {
38    /// Swap two random positions in the OSV.
39    Swap,
40    /// Remove and reinsert at a random position.
41    Insert,
42    /// Reverse a random segment of the OSV.
43    Invert,
44}
45
46/// Runtime-selectable genetic operators for scheduling GA.
47///
48/// Wraps crossover and mutation strategy selection so that
49/// u-aps can switch operators via configuration without
50/// changing the GA problem definition.
51///
52/// # Example
53///
54/// ```
55/// use u_schedule::ga::operators::{GeneticOperators, CrossoverType, MutationType};
56///
57/// let ops = GeneticOperators {
58///     crossover_type: CrossoverType::LOX,
59///     mutation_type: MutationType::Invert,
60/// };
61/// ```
62#[derive(Debug, Clone)]
63pub struct GeneticOperators {
64    /// Crossover strategy.
65    pub crossover_type: CrossoverType,
66    /// OSV mutation strategy.
67    pub mutation_type: MutationType,
68}
69
70impl Default for GeneticOperators {
71    fn default() -> Self {
72        Self {
73            crossover_type: CrossoverType::POX,
74            mutation_type: MutationType::Swap,
75        }
76    }
77}
78
79impl GeneticOperators {
80    /// Performs crossover using the configured strategy.
81    pub fn crossover<R: Rng>(
82        &self,
83        p1: &ScheduleChromosome,
84        p2: &ScheduleChromosome,
85        activities: &[ActivityInfo],
86        rng: &mut R,
87    ) -> (ScheduleChromosome, ScheduleChromosome) {
88        match self.crossover_type {
89            CrossoverType::POX => pox_crossover(p1, p2, activities, rng),
90            CrossoverType::LOX => lox_crossover(p1, p2, activities, rng),
91            CrossoverType::JOX => jox_crossover(p1, p2, activities, rng),
92        }
93    }
94
95    /// Performs mutation using the configured strategy.
96    ///
97    /// Always also applies MAV mutation to diversify resource assignments.
98    pub fn mutate<R: Rng>(
99        &self,
100        chromosome: &mut ScheduleChromosome,
101        activities: &[ActivityInfo],
102        rng: &mut R,
103    ) {
104        match self.mutation_type {
105            MutationType::Swap => swap_mutation(chromosome, rng),
106            MutationType::Insert => insert_mutation(chromosome, rng),
107            MutationType::Invert => invert_mutation(chromosome, rng),
108        }
109        mav_mutation(chromosome, activities, rng);
110    }
111}
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116    use rand::rngs::SmallRng;
117    use rand::SeedableRng;
118
119    fn sample_activities() -> Vec<ActivityInfo> {
120        vec![
121            ActivityInfo {
122                task_id: "T1".into(),
123                sequence: 1,
124                process_ms: 1000,
125                candidates: vec!["M1".into(), "M2".into()],
126            },
127            ActivityInfo {
128                task_id: "T1".into(),
129                sequence: 2,
130                process_ms: 2000,
131                candidates: vec!["M2".into()],
132            },
133            ActivityInfo {
134                task_id: "T2".into(),
135                sequence: 1,
136                process_ms: 1500,
137                candidates: vec!["M1".into(), "M3".into()],
138            },
139        ]
140    }
141
142    #[test]
143    fn test_default_operators() {
144        let ops = GeneticOperators::default();
145        assert_eq!(ops.crossover_type, CrossoverType::POX);
146        assert_eq!(ops.mutation_type, MutationType::Swap);
147    }
148
149    #[test]
150    fn test_crossover_pox() {
151        let acts = sample_activities();
152        let ops = GeneticOperators::default();
153        let mut rng = SmallRng::seed_from_u64(42);
154        let p1 = ScheduleChromosome::random(&acts, &mut rng);
155        let p2 = ScheduleChromosome::random(&acts, &mut rng);
156
157        let (c1, c2) = ops.crossover(&p1, &p2, &acts, &mut rng);
158        assert_eq!(c1.osv.len(), 3);
159        assert_eq!(c2.osv.len(), 3);
160    }
161
162    #[test]
163    fn test_crossover_lox() {
164        let acts = sample_activities();
165        let ops = GeneticOperators {
166            crossover_type: CrossoverType::LOX,
167            mutation_type: MutationType::Swap,
168        };
169        let mut rng = SmallRng::seed_from_u64(42);
170        let p1 = ScheduleChromosome::random(&acts, &mut rng);
171        let p2 = ScheduleChromosome::random(&acts, &mut rng);
172
173        let (c1, c2) = ops.crossover(&p1, &p2, &acts, &mut rng);
174        assert_eq!(c1.osv.len(), 3);
175        assert_eq!(c2.osv.len(), 3);
176    }
177
178    #[test]
179    fn test_crossover_jox() {
180        let acts = sample_activities();
181        let ops = GeneticOperators {
182            crossover_type: CrossoverType::JOX,
183            mutation_type: MutationType::Swap,
184        };
185        let mut rng = SmallRng::seed_from_u64(42);
186        let p1 = ScheduleChromosome::random(&acts, &mut rng);
187        let p2 = ScheduleChromosome::random(&acts, &mut rng);
188
189        let (c1, c2) = ops.crossover(&p1, &p2, &acts, &mut rng);
190        assert_eq!(c1.osv.len(), 3);
191        assert_eq!(c2.osv.len(), 3);
192    }
193
194    #[test]
195    fn test_mutation_swap() {
196        let acts = sample_activities();
197        let ops = GeneticOperators::default();
198        let mut rng = SmallRng::seed_from_u64(42);
199        let mut ch = ScheduleChromosome::random(&acts, &mut rng);
200
201        ops.mutate(&mut ch, &acts, &mut rng);
202        assert_eq!(ch.osv.len(), 3);
203    }
204
205    #[test]
206    fn test_mutation_insert() {
207        let acts = sample_activities();
208        let ops = GeneticOperators {
209            crossover_type: CrossoverType::POX,
210            mutation_type: MutationType::Insert,
211        };
212        let mut rng = SmallRng::seed_from_u64(42);
213        let mut ch = ScheduleChromosome::random(&acts, &mut rng);
214
215        ops.mutate(&mut ch, &acts, &mut rng);
216        assert_eq!(ch.osv.len(), 3);
217    }
218
219    #[test]
220    fn test_mutation_invert() {
221        let acts = sample_activities();
222        let ops = GeneticOperators {
223            crossover_type: CrossoverType::POX,
224            mutation_type: MutationType::Invert,
225        };
226        let mut rng = SmallRng::seed_from_u64(42);
227        let mut ch = ScheduleChromosome::random(&acts, &mut rng);
228
229        ops.mutate(&mut ch, &acts, &mut rng);
230        assert_eq!(ch.osv.len(), 3);
231    }
232
233    #[test]
234    fn test_mutate_always_applies_mav() {
235        let acts = sample_activities();
236        let ops = GeneticOperators::default();
237        let mut rng = SmallRng::seed_from_u64(42);
238        let ch = ScheduleChromosome::random(&acts, &mut rng);
239        let original_mav = ch.mav.clone();
240
241        // Run enough mutations that MAV changes at least once
242        let mut mav_changed = false;
243        for _ in 0..50 {
244            let mut ch2 = ch.clone();
245            ops.mutate(&mut ch2, &acts, &mut rng);
246            if ch2.mav != original_mav {
247                mav_changed = true;
248                break;
249            }
250        }
251        assert!(
252            mav_changed,
253            "MAV mutation should occur alongside OSV mutation"
254        );
255    }
256}
u_schedule/ga/operators.rs

u_schedule/ga/
operators.rs
