competitive/heuristic/
simurated_annealing.rs

1use super::Xorshift;
2
3#[derive(Debug)]
4pub struct SimuratedAnnealing {
5    pub iter_count: usize,
6    pub now: std::time::Instant,
7    pub time: f64,
8    pub temperture: f64,
9    pub log_table: Vec<f64>,
10    pub rand: Xorshift,
11
12    pub is_maximize: bool,
13    pub start_temp: f64,
14    pub end_temp: f64,
15    pub time_limit: f64,
16    pub update_interval: usize,
17}
18impl Default for SimuratedAnnealing {
19    fn default() -> Self {
20        let now = std::time::Instant::now();
21        let log_table = (0..Self::LOG_TABLE_SIZE)
22            .map(|i| ((i * 2 + 1) as f64 / (Self::LOG_TABLE_SIZE * 2) as f64).ln())
23            .collect();
24        Self {
25            iter_count: 0,
26            now,
27            time: 0.,
28            temperture: 3e3,
29            log_table,
30            rand: Xorshift::new_with_seed(Self::SEED),
31            is_maximize: true,
32            start_temp: 3e3,
33            end_temp: 1e-8,
34            time_limit: 1.99,
35            update_interval: 0xff,
36        }
37    }
38}
39impl SimuratedAnnealing {
40    pub const LOG_TABLE_SIZE: usize = 0x10000;
41    pub const SEED: u64 = 0xbeef_cafe;
42
43    pub fn new() -> Self {
44        Default::default()
45    }
46    pub fn minimize(mut self) -> Self {
47        self.is_maximize = false;
48        self
49    }
50    pub fn set_start_temp(mut self, start_temp: f64) -> Self {
51        assert_eq!(self.iter_count, 0);
52        self.start_temp = start_temp;
53        self.temperture = start_temp;
54        self
55    }
56    pub fn set_end_temp(mut self, end_temp: f64) -> Self {
57        self.end_temp = end_temp;
58        self
59    }
60    pub fn set_time_limit(mut self, time_limit: f64) -> Self {
61        self.time_limit = time_limit;
62        self
63    }
64    pub fn set_update_interval(mut self, update_interval: usize) -> Self {
65        assert!(update_interval > 0);
66        self.update_interval = update_interval;
67        self
68    }
69    pub fn is_accepted(&mut self, current_score: f64, next_score: f64) -> bool {
70        let diff = if self.is_maximize {
71            next_score - current_score
72        } else {
73            current_score - next_score
74        };
75        diff >= 0.
76            || diff
77                > self.log_table[self.rand.rand(Self::LOG_TABLE_SIZE as u64) as usize]
78                    * self.temperture
79    }
80    pub fn is_end(&mut self) -> bool {
81        self.iter_count += 1;
82        if self.iter_count % self.update_interval == 0 {
83            self.time = self.now.elapsed().as_secs_f64();
84            let temp_ratio = (self.end_temp - self.start_temp) / self.time_limit;
85            self.temperture = self.start_temp + temp_ratio * self.time;
86            self.time >= self.time_limit
87        } else {
88            false
89        }
90    }
91}
competitive/heuristic/simurated_annealing.rs

competitive/heuristic/
simurated_annealing.rs
