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
106
107
108
109

//! Ants simulation strategies
//!
//! Contains strategies on how should an ant behave, and when to update edge [crate::aco::goodness].
use crate::aco::ant::Ant;
use crate::aco::goodness::Goodness;
use crate::aco::local_update::LocalUpdate;
use crate::aco::FMatrix;

/// # Ants Behaviour
///
/// Trait contains common actions of ants simulation.
pub trait AntsBehaviour<A: Ant, G: Goodness> {
  /// Simulates ant by deciding on order of operations.
  ///
  /// ## Arguments
  /// * `pheromone` - Pheromone after global pheromone update rule was applied.
  /// * `ants` - ants to be simulated
  /// * `goodness_op` - Implementation of [Goodness].
  fn simulate_ants(
    &mut self,
    ants: &mut [A],
    pheromone: &mut FMatrix,
    goodness_op: &mut G,
  ) -> Vec<Vec<usize>>;
}
/// # Ant System ants behaviour
///
/// Implements [AntsBehaviour]. Ants are simulated as described in Ant System algorithm with the
/// exception of goodness calculation. By providing [crate::aco::goodness::CanonicalGoodness] simulations
/// will be fully equivalent to Ant System.
pub struct AntSystemAB;

impl<A: Ant, G: Goodness> AntsBehaviour<A, G> for AntSystemAB {
  fn simulate_ants(
    &mut self,
    ants: &mut [A],
    pheromone: &mut FMatrix,
    goodness_op: &mut G,
  ) -> Vec<Vec<usize>> {
    let goodness = goodness_op.apply(pheromone);
    let solution_size = pheromone.nrows();

    let mut paths: Vec<Vec<usize>> = Vec::with_capacity(ants.len());
    for ant in ants.iter_mut() {
      ant.clear();
      ant.chose_staring_place();
      for _ in 1..solution_size {
        ant.go_to_next_place(&goodness);
      }

      if ant.is_stuck() {
        break;
      }
      let path = ant.path();
      paths.push(path.to_vec())
    }

    paths
  }
}

/// # Ant Colony System ants behaviour
///
/// Implements [AntsBehaviour]. Ants are simulated as described in Ant Colony System algorithm with the
/// exception of goodness calculation.
pub struct AntColonySystemAB<L: LocalUpdate> {
  local_update: L,
}

impl<A: Ant, G: Goodness, L: LocalUpdate> AntsBehaviour<A, G> for AntColonySystemAB<L> {
  fn simulate_ants(
    &mut self,
    ants: &mut [A],
    pheromone: &mut FMatrix,
    goodness_op: &mut G,
  ) -> Vec<Vec<usize>> {
    let solution_size = pheromone.nrows();

    ants.iter_mut().for_each(|a| {
      a.clear();
      a.chose_staring_place()
    });

    let mut paths: Vec<Vec<usize>> = Vec::with_capacity(ants.len());

    for _ in 1..solution_size {
      let goodness = goodness_op.apply(pheromone);
      paths.clear();
      for ant in ants.iter_mut() {
        if ant.is_stuck() {
          continue;
        }
        ant.go_to_next_place(&goodness);

        let path = ant.path();
        paths.push(path.to_vec())
      }
      self.local_update.apply(pheromone, &paths)
    }
    paths
  }
}

impl<L: LocalUpdate> AntColonySystemAB<L> {
  /// Creates a new [AntColonySystemAB] instance with specified update rule
  pub fn with_rule(rule: L) -> Self {
    Self { local_update: rule }
  }
}