lgp/core/
instructions.rs

1use crate::utils::random::generator;
2use itertools::Itertools;
3use rand::Rng;
4
5use super::{
6    engines::breed_engine::{Breed, BreedEngine},
7    instruction::Instruction,
8};
9
10impl Breed<Instructions> for BreedEngine {
11    fn two_point_crossover(
12        mate_1: &Instructions,
13        mate_2: &Instructions,
14    ) -> (Instructions, Instructions) {
15        let mut instructions_a = mate_1.clone();
16        let mut instructions_b = mate_2.clone();
17
18        debug_assert!(!instructions_a.is_empty());
19        debug_assert!(!instructions_b.is_empty());
20
21        let a_start = generator().gen_range(0..instructions_a.len());
22        let b_start = generator().gen_range(0..instructions_b.len());
23
24        let a_end = if a_start == instructions_a.len() - 1 {
25            None
26        } else {
27            debug_assert!(instructions_a.len() > a_start);
28            Some(generator().gen_range(a_start + 1..instructions_a.len()))
29        };
30
31        let b_end = if b_start == instructions_b.len() - 1 {
32            None
33        } else {
34            debug_assert!(instructions_b.len() > b_start);
35            Some(generator().gen_range(b_start + 1..instructions_b.len()))
36        };
37
38        let a_chunk = match a_end {
39            None => &instructions_a[a_start..],
40            Some(a_end_idx) => &instructions_a[a_start..a_end_idx],
41        }
42        .iter()
43        .cloned()
44        .collect_vec();
45
46        let b_chunk = match b_end {
47            None => &instructions_b[b_start..],
48            Some(b_end_idx) => &instructions_b[b_start..b_end_idx],
49        }
50        .iter()
51        .cloned()
52        .collect_vec();
53
54        if let Some(a_end_idx) = a_end {
55            instructions_a.splice(a_start..a_end_idx, b_chunk)
56        } else {
57            instructions_a.splice(a_start.., b_chunk)
58        }
59        .collect_vec();
60
61        if let Some(b_end_idx) = b_end {
62            instructions_b.splice(b_start..b_end_idx, a_chunk)
63        } else {
64            instructions_b.splice(b_start.., a_chunk)
65        }
66        .collect_vec();
67
68        debug_assert!(!instructions_a.is_empty(), "instructions A after crossover");
69        debug_assert!(!instructions_b.is_empty(), "instructions B after crossover");
70
71        (instructions_a, instructions_b)
72    }
73}
74
75pub type Instructions = Vec<Instruction>;
76
77#[cfg(test)]
78mod tests {
79
80    use crate::core::{
81        engines::{
82            breed_engine::{Breed, BreedEngine},
83            generate_engine::{Generate, GenerateEngine},
84        },
85        instruction::InstructionGeneratorParameters,
86        program::ProgramGeneratorParameters,
87    };
88
89    #[test]
90    fn given_two_programs_when_two_point_crossover_multiple_times_then_instruction_set_never_grows()
91    {
92        let max_instructions = 100;
93        let parameters = ProgramGeneratorParameters {
94            max_instructions,
95            instruction_generator_parameters: InstructionGeneratorParameters {
96                n_extras: 1,
97                external_factor: 10.,
98                n_inputs: 4,
99                n_actions: 2,
100            },
101        };
102
103        let mut program_a = GenerateEngine::generate(parameters);
104        let mut program_b = GenerateEngine::generate(parameters);
105
106        for _ in 0..100 {
107            let parent_a_instruction_len = program_a.instructions.len();
108            let parent_b_instruction_len = program_b.instructions.len();
109
110            let (new_parent_a, new_parent_b) =
111                BreedEngine::two_point_crossover(&program_a, &program_b);
112
113            debug_assert!(!new_parent_a.instructions.is_empty());
114            debug_assert!(!new_parent_b.instructions.is_empty());
115
116            debug_assert!(
117                new_parent_a.instructions.len()
118                    <= parent_a_instruction_len + parent_b_instruction_len
119            );
120            debug_assert!(
121                new_parent_b.instructions.len()
122                    <= parent_a_instruction_len + parent_b_instruction_len
123            );
124
125            program_a = new_parent_a;
126            program_b = new_parent_b;
127        }
128    }
129}
lgp/core/instructions.rs

lgp/core/
instructions.rs
