hw(3/AI): Tournament selection instead of roulette and proper output

1 files changed, 51 insertions, 22 deletions

diff --git a/Year 4/Artificial Intelligence/hw03/src/ex1.rs b/Year 4/Artificial Intelligence/hw03/src/ex1.rs
index 5da7c9b..9547e2b 100644
--- a/Year 4/Artificial Intelligence/hw03/src/ex1.rs
+++ b/Year 4/Artificial Intelligence/hw03/src/ex1.rs
@@ -1,5 +1,7 @@
+#![allow(non_snake_case)]
+use std::fmt;
 use text_io::{read};
-use rand::{Rng, thread_rng, seq::SliceRandom};
+use rand::{Rng, rngs::ThreadRng, thread_rng, seq::SliceRandom};
 
 #[derive(Debug)]
 struct Gene {
@@ -74,9 +76,7 @@ impl Chromosome {
         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()));
-        let temp = self.genes[i].clone();
-        self.genes[i] = self.genes[j];
-        self.genes[j] = temp;
+        self.genes.swap(i, j);
 
         self.evaluate_fitness(map);
     }
@@ -91,7 +91,7 @@ struct Generation {
 }
 
 impl Generation {
-    const POPULATION_SIZE: usize = 250;
+    const POPULATION_SIZE: usize = 700;
 
     fn new_population(map: &Vec<Gene>) -> Vec<Chromosome> {
         let mut rng = thread_rng();
@@ -122,25 +122,33 @@ impl Generation {
         }
     }
 
+    const TOURNAMENT_SIZE: usize = 5;
+
+    fn select(&self, rng: &mut ThreadRng) -> usize {
+        let mut tournament: Vec<usize> = Vec::new();
+        for _ in 0..Self::TOURNAMENT_SIZE {
+            tournament.push(rng.gen_range(0..self.population.len()));
+        }
+
+        tournament
+            .into_iter()
+            .min_by(|a, b| self.population[*a].fitness.partial_cmp(&self.population[*b].fitness).unwrap())
+            .unwrap()
+    }
+
     fn selection_crossover(&mut self) {
         let mut rng = thread_rng();
-        // Roulette selection
-        let sum_fitness: f64 = self.population.iter().map(|x| x.fitness).sum();
 
-        let mut prev_parent = usize::MAX;
-        for i in 0..self.population.len() {
-            if ! rng.gen_bool(self.population[i].fitness / sum_fitness) { continue; }
+        let mut new_generation: Vec<Chromosome> = Vec::new();
+        while new_generation.len() < self.population.len() {
+            let parent1 = self.select(&mut rng);
+            let parent2 = self.select(&mut rng);
+            if parent1 == parent2 { continue; }
 
-            if prev_parent != usize::MAX {
-                let children = self.population[prev_parent].crossover_with(&self.population[i], &self.map);
-                self.population[prev_parent] = children[0].clone();
-                self.population[i]           = children[1].clone();
-                prev_parent = usize::MAX;
-            }
-            else {
-                prev_parent = i;
-            }
+            let mut children = self.population[parent1].crossover_with(&self.population[parent2], &self.map);
+            new_generation.append(&mut children);
         }
+        self.population = new_generation;
     }
 
     fn mutate(&mut self) {
@@ -154,7 +162,7 @@ impl Generation {
         self
     }
 
-    const MAX_GENERATIONS: usize = 2000;
+    const MAX_GENERATIONS: usize = 250;
 
     fn terminated(&self) -> bool {
         self.t == Self::MAX_GENERATIONS || self.population[1..].iter().all(|x| *x == self.population[0])
@@ -169,6 +177,20 @@ impl Generation {
     }
 }
 
+impl fmt::Display for Generation {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        let best = self.population
+            .iter()
+            .min_by(|a, b| a.fitness.partial_cmp(&b.fitness).unwrap())
+            .unwrap();
+        for cityi in &best.genes[..best.genes.len()-1] {
+            write!(f, "{} -> ", self.map[*cityi].name)?;
+        }
+        writeln!(f, "{}", self.map[*best.genes.last().unwrap()].name)?;
+        writeln!(f, "{}", best.fitness)
+    }
+}
+
 pub fn main() {
     let mut G: Generation;
     let input: String = read!();
@@ -198,14 +220,21 @@ pub fn main() {
             })
             .collect();
         G = Generation::new_from_map(points);
-        println!("{:?}", G);
     }
 
     println!("{}", G.best_fitness());
+    let mut i = 0;
+
     while ! G.terminated() {
+        if i < 8 {
+            println!("{}", G.best_fitness());
+            i += 1;
+        }
         G.selection_crossover();
         G.mutate();
         G = G.next_generation();
     }
-    println!("{}", G.best_fitness());
+
+    println!("");
+    println!("{}", G);
 }