evolutionary/crossover/permuted/
ordered_crossover.rs

1use std::collections::{HashSet, VecDeque};
2
3use rand::{thread_rng, Rng};
4use rayon::{prelude::ParallelIterator, slice::ParallelSliceMut};
5
6use crate::{population::IntPerm, Individual};
7
8use super::Crossover;
9
10/// # Ordered Crossover (OX)
11///
12/// The ordered crossover operator (OX) is a crossover operator for permutation-based chromosomes.
13/// It maintains the relative order of the elements in the parent chromosomes. With the `crossover_rate`
14/// probability it chooses two points in the parents, maintain the elements between the points and
15/// fill the remaining positions with the elements of the other parent in the order they appear.
16#[derive(Clone)]
17pub struct OrderedCrossover {
18    pub crossover_rate: f64,
19}
20
21impl Default for OrderedCrossover {
22    fn default() -> Self {
23        OrderedCrossover {
24            crossover_rate: 0.8,
25        }
26    }
27}
28
29impl OrderedCrossover {
30    pub fn apply_ox(parent1: &mut Vec<i64>, parent2: &mut Vec<i64>, start: usize, end: usize) {
31        let len = parent1.len();
32
33        let mut missing1 = HashSet::new();
34        let mut missing2 = HashSet::new();
35
36        let mut queue1 = VecDeque::new();
37        let mut queue2 = VecDeque::new();
38
39        for i in 0..start {
40            missing1.insert(parent1[i]);
41            missing2.insert(parent2[i]);
42        }
43        for i in end + 1..len {
44            missing1.insert(parent1[i]);
45            missing2.insert(parent2[i]);
46        }
47
48        for i in 0..len {
49            if missing1.contains(&parent2[i]) {
50                queue1.push_back(parent2[i]);
51            }
52            if missing2.contains(&parent1[i]) {
53                queue2.push_back(parent1[i]);
54            }
55        }
56
57        for i in 0..start {
58            parent1[i] = queue1.pop_front().unwrap();
59            parent2[i] = queue2.pop_front().unwrap();
60        }
61        for i in end + 1..len {
62            parent1[i] = queue1.pop_front().unwrap();
63            parent2[i] = queue2.pop_front().unwrap();
64        }
65    }
66}
67
68impl Crossover<IntPerm> for OrderedCrossover {
69    fn crossover(&self, population: &mut Vec<IntPerm>) {
70        population.par_chunks_mut(2).for_each_init(
71            || thread_rng(),
72            |rng, chunk| {
73                if rng.gen_bool(self.crossover_rate) {
74                    let mut parent1 = chunk[0].clone();
75                    let mut parent2 = chunk[1].clone();
76
77                    let len = parent1.get_chromosome().len();
78
79                    let start = rng.gen_range(0..len);
80                    let end = rng.gen_range(start..len);
81
82                    OrderedCrossover::apply_ox(
83                        &mut parent1.chromosome,
84                        &mut parent2.chromosome,
85                        start,
86                        end,
87                    );
88
89                    chunk[0] = parent1;
90                    chunk[1] = parent2;
91                }
92            },
93        );
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    use crate::crossover::OrderedCrossover;
100
101    #[test]
102    fn ox_crossover() {
103        //                                     |        |
104        let mut parent1 = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
105        let mut parent2 = vec![5, 7, 4, 9, 1, 3, 6, 2, 8];
106
107        OrderedCrossover::apply_ox(&mut parent1, &mut parent2, 2, 5);
108
109        assert_eq!(parent1, vec![7, 9, 3, 4, 5, 6, 1, 2, 8]);
110        assert_eq!(parent2, vec![2, 5, 4, 9, 1, 3, 6, 7, 8]);
111    }
112}
evolutionary/crossover/permuted/ordered_crossover.rs

evolutionary/crossover/permuted/
ordered_crossover.rs
