1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

use super::*;
use gen_iter::GenIter;

impl<T> TspSolver<T>
where
    T: TspDistance,
{
    pub fn ant_colony_optimization(&mut self, ants: usize) -> impl Iterator<Item = TspRecord> + '_
    where
        T: Serialize,
    {
        let mut path = (0..self.objects.len()).collect::<Vec<usize>>();
        path.shuffle(&mut self.rng);
        GenIter(move || {
            yield self.get_record();
            loop {
                let mut ant_paths = Array2::zeros((ants, path.len()));
                for i in 0..ants {
                    for (j, value) in self.build_path(&path).iter().enumerate() {
                        ant_paths[[i, j]] = *value;
                    }
                }
                let (new_path, new_distance) = self.collect_best_path(ant_paths);
                if new_distance < self.best_distance {
                    self.best_path = new_path;
                    self.best_distance = new_distance;
                    self.improves += 1;
                    self.save_best();
                    yield self.get_record()
                }
                self.steps += 1;
            }
        })
    }
    fn save_best(&self)
    where
        T: Serialize,
    {
        match self.save(&self.check_points) {
            Ok(_) => {}
            Err(e) => {
                println!("{e:?} {}", self.check_points.display());
                tracing::error!("{}", e)
            }
        }
    }

    fn build_path(&mut self, path: &[usize]) -> Array1<usize> {
        let mut visited = vec![false; self.objects.len()];
        let mut ant_path = Array1::zeros((path.len(),));
        ant_path[0] = path[0];
        visited[path[0]] = true;
        for i in 1..path.len() {
            let next = self.select_next(ant_path[i - 1], &visited);
            ant_path[i] = next;
            visited[next] = true;
        }
        ant_path
    }

    fn select_next(&mut self, current: usize, visited: &[bool]) -> usize {
        let pheromones = self.compute_pheromones(current, visited);
        let total_pheromones = pheromones.iter().sum::<f64>();
        let probabilities = pheromones.iter().map(|&p| p / total_pheromones).collect::<Vec<_>>();
        let mut cum_prob = 0.0;
        let random_value = self.rng.gen::<f64>();
        for (i, &prob) in probabilities.iter().enumerate() {
            cum_prob += prob;
            if random_value <= cum_prob {
                return i;
            }
        }
        probabilities.iter().enumerate().max_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap()).unwrap().0
    }

    fn compute_pheromones(&self, current: usize, visited: &[bool]) -> Vec<f64> {
        let mut pheromones = vec![0.0; self.objects.len()];
        for (i, obj) in self.objects.iter().enumerate() {
            if visited[i] {
                continue;
            }
            let distance = T::distance(obj, &self.objects[current]);
            pheromones[i] = self.compute_pheromone(distance);
        }
        pheromones
    }

    fn compute_pheromone(&self, distance: f64) -> f64 {
        1.0 / distance
    }

    fn collect_best_path(&self, ant_paths: Array2<usize>) -> (Array1<usize>, f64) {
        let mut best_path = Array1::zeros((ant_paths.shape()[1],));
        let mut best_distance = f64::max_value();
        for i in 0..ant_paths.shape()[0] {
            let path = ant_paths.row(i);
            let distance = T::total(self.objects.view(), path);
            if distance < best_distance {
                best_path = path.to_owned();
                best_distance = distance;
            }
        }
        (best_path, best_distance)
    }
}