ecrs 0.1.0-beta.4

Evolutionary computation tools & algorithms
Documentation 
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

//! 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::pheromone::Pheromone;
use crate::aco::FMatrix;

/// # Ants Behaviour
///
/// Trait contains common actions of ants simulation.
pub trait AntsBehaviour<A: Ant, G: Goodness<P>, P: Pheromone> {
    /// 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 P, 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<FMatrix>> AntsBehaviour<A, G, FMatrix> 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<FMatrix>, L: LocalUpdate> AntsBehaviour<A, G, FMatrix> 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 }
    }
}