~ruther/ctu-fee-eoa

ref: 0ef7b7f5f8bdcdf492b1fc419279e7a7ea3fe666 ctu-fee-eoa/codes/tsp_hw01/src/perturbations.rs -rw-r--r-- 3.2 KiB
0ef7b7f5 — Rutherther feat(tsp): add TSPInstance convertor to GenericGraph a month ago 
                                                                                
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
110
111
112
113
114
115
116
117
118
119
120
121
122

use std::marker::PhantomData;
use nalgebra::{allocator::Allocator, DefaultAllocator, Dim};
use rand::{Rng, RngCore};
use eoa_lib::perturbation::PerturbationOperator;
use crate::tsp::NodePermutation;

pub struct SwapPerturbation<D> {
    _phantom: PhantomData<D>
}

impl<D> SwapPerturbation<D> {
    pub fn new() -> Self {
        Self { _phantom: PhantomData }
    }
}

impl<D> PerturbationOperator for SwapPerturbation<D>
where
    D: Dim,
    DefaultAllocator: Allocator<D, D>,
    DefaultAllocator: Allocator<D>,
{
    type Chromosome = NodePermutation<D>;

    fn perturb(&self, chromosome: &mut Self::Chromosome, rng: &mut dyn RngCore) {
        let first = rng.random_range(0..chromosome.permutation.len());
        let second = rng.random_range(0..chromosome.permutation.len());
        chromosome.permutation.swap_rows(first, second);
    }
}

pub struct MovePerturbation<D> {
    _phantom: PhantomData<D>
}

impl<D> MovePerturbation<D> {
    pub fn new() -> Self {
        Self { _phantom: PhantomData }
    }
}

impl<D> PerturbationOperator for MovePerturbation<D>
where
    D: Dim,
    DefaultAllocator: Allocator<D, D>,
    DefaultAllocator: Allocator<D>,
{
    type Chromosome = NodePermutation<D>;

    fn perturb(&self, chromosome: &mut Self::Chromosome, rng: &mut dyn RngCore) {
        let from = rng.random_range(0..chromosome.permutation.len());
        let to = rng.random_range(0..chromosome.permutation.len());

        let element = chromosome.permutation[from];

        if from < to {
            for i in from..to {
                chromosome.permutation[i] = chromosome.permutation[i + 1];
            }
        } else {
            for i in (to+1..=from).rev() {
                chromosome.permutation[i] = chromosome.permutation[i - 1];
            }
        }

        chromosome.permutation[to] = element;
    }
}

pub struct ReverseSubsequencePerturbation<D> {
    _phantom: PhantomData<D>,
    min_subsequence_len: usize,
    max_subsequence_len: usize,
}

impl<D> ReverseSubsequencePerturbation<D> {
    pub fn new() -> Self {
        Self {
            _phantom: PhantomData,
            max_subsequence_len: usize::MAX,
            min_subsequence_len: 0,
        }
    }
}

impl<D> PerturbationOperator for ReverseSubsequencePerturbation<D>
where
    D: Dim,
    DefaultAllocator: Allocator<D, D>,
    DefaultAllocator: Allocator<D>,
{
    type Chromosome = NodePermutation<D>;

    fn perturb(&self, chromosome: &mut Self::Chromosome, rng: &mut dyn RngCore) {
        let len = chromosome.permutation.len();
        let index = rng.random_range(0..chromosome.permutation.len());
        let subsequence_len = rng.random_range(
            self.min_subsequence_len..(chromosome.permutation.len().min(self.max_subsequence_len))
        );

        // Reverse the subsequence between start and end (inclusive)
        let mut left = index;
        let mut right = (index + subsequence_len) % len;

        while left != right {
            chromosome.permutation.swap_rows(left, right);

            left += 1;
            left %= len;

            if left == right {
                break;
            }

            if right > 0 {
                right -= 1;
            } else {
                right = len - 1;
            }
        }
    }
}