use rand::{thread_rng, Rng}; use crate::Gene; #[derive(Clone, PartialEq, Debug)] pub struct Chromosome { pub genes: Vec, pub fitness: f64, } impl Chromosome { // map: Container for all genes; genes[i] is the index inside map pub fn new(genes: Vec, map: &Vec) -> Chromosome { let mut ret = Chromosome { genes, fitness: 0.0, }; ret.evaluate_fitness(map); ret } pub fn evaluate_fitness(&mut self, map: &Vec) { self.fitness = 0.0; for i in 0..self.genes.len() - 1 { self.fitness += map[self.genes[i]].dist(&map[self.genes[i+1]]); } } const MUTATION_PROBABILITY: f64 = 0.01; pub fn mutate(&mut self, map: &Vec) { let mut rng = thread_rng(); if ! rng.gen_bool(Self::MUTATION_PROBABILITY) { return; } let (i, j) = (rng.gen_range(0..self.genes.len()), rng.gen_range(0..self.genes.len())); self.genes.swap(i, j); self.evaluate_fitness(map); } // self & other - parents // Single-point crossover pub fn crossover_with(&self, other: &Self, map: &Vec) -> Vec { assert!(!other.genes.is_empty(), "Crossing over with chromosome without genes!"); let i = if other.genes.len() == 1 { 1 } else { thread_rng().gen_range(1..other.genes.len()) }; self.crossover_with_point(other, map, i) } fn crossover_with_point(&self, other: &Self, map: &Vec, i: usize) -> Vec { let mut child1 = self.genes[..i].to_vec(); for elem in &other.genes { if child1.len() == other.genes.len() { break; } if ! child1.contains(&elem) { child1.push(*elem); } } let mut child2 = other.genes[..i].to_vec(); for elem in &self.genes { if child2.len() == self.genes.len() { break; } if ! child2.contains(&elem) { child2.push(*elem); } } vec![ Chromosome::new(child1, map), Chromosome::new(child2, map), ] } } #[test] fn test_evaluate_fitness() { let map = vec![ Gene { x: 4.0, y: 1.0, name: "".to_string() }, Gene { x: 3.0, y: 0.0, name: "".to_string() }, Gene { x: 2.0, y: 5.0, name: "".to_string() }, ]; let g = Chromosome::new(vec![0, 1, 2], &map); assert_eq!(format!("{:.3}", g.fitness), "6.513", "Bad evaluate_fitness, incorrect calculation!"); } #[test] fn test_mutate() { let map = vec![ Gene { x: 4.0, y: 1.0, name: "".to_string() }, Gene { x: 3.0, y: 0.0, name: "".to_string() }, Gene { x: 2.0, y: 5.0, name: "".to_string() }, ]; let mut g = Chromosome::new(vec![0, 1, 2], &map); 'test: { for _ in 0..10000 { g.mutate(&map); if format!("{:.3}", g.fitness) != "6.513" { break 'test; } } assert!(false, "Bad mutate, never swapped genes"); } } #[test] fn test_single_point_crossover() { let map = vec![ Gene { x: 4.0, y: 1.0, name: "".to_string() }, Gene { x: 3.0, y: 0.0, name: "".to_string() }, Gene { x: 2.0, y: 5.0, name: "".to_string() }, ]; let g1 = Chromosome::new(vec![0, 1], &map); let g2 = Chromosome::new(vec![2, 1], &map); let crossed = g1.crossover_with(&g2, &map); let g1s = Chromosome::new(vec![0, 2], &map); let g2s = Chromosome::new(vec![2, 0], &map); assert_eq!(crossed[0], g1s, "Bad crossover (2 genes)!"); assert_eq!(crossed[1], g2s, "Bad crossover (2 genes)!"); let map = vec![ Gene { x: 4.0, y: 1.0, name: "".to_string() }, Gene { x: 3.0, y: 0.0, name: "".to_string() }, Gene { x: 2.0, y: 5.0, name: "".to_string() }, Gene { x: 8.0, y: 4.0, name: "".to_string() }, Gene { x: 7.0, y: 1.0, name: "".to_string() }, ]; let g1 = Chromosome::new(vec![0, 1, 2, 3, 4], &map); let g2 = Chromosome::new(vec![4, 3, 2, 1, 0], &map); let crossed = g1.crossover_with_point(&g2, &map, 3); let g1s = Chromosome::new(vec![0, 1, 2, 4, 3], &map); let g2s = Chromosome::new(vec![4, 3, 2, 0, 1], &map); assert_eq!(crossed[0], g1s, "Bad crossover (5 genes)!"); assert_eq!(crossed[1], g2s, "Bad crossover (5 genes)!"); }