solverforge_solver/phase/localsearch/acceptor/
value_tabu.rs

1// Value tabu acceptor.
2
3use std::fmt::Debug;
4
5use solverforge_core::domain::PlanningSolution;
6
7use super::Acceptor;
8
9/// Value tabu acceptor - maintains a tabu list based on assigned values.
10///
11/// Unlike entity tabu which forbids recently moved entities, value tabu
12/// forbids recently used values. This is useful when the problem has
13/// expensive values that shouldn't be over-utilized.
14///
15/// # Example
16///
17/// ```
18/// use solverforge_solver::phase::localsearch::ValueTabuAcceptor;
19///
20/// let acceptor = ValueTabuAcceptor::new(7);
21/// assert!(!acceptor.is_value_tabu(42));
22/// ```
23pub struct ValueTabuAcceptor {
24    // Maximum number of values to remember.
25    value_tabu_size: usize,
26    // List of tabu value hashes.
27    value_tabu_list: Vec<u64>,
28    // Current step's assigned values.
29    current_step_values: Vec<u64>,
30}
31
32impl Debug for ValueTabuAcceptor {
33    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
34        f.debug_struct("ValueTabuAcceptor")
35            .field("value_tabu_size", &self.value_tabu_size)
36            .field("tabu_list_len", &self.value_tabu_list.len())
37            .finish()
38    }
39}
40
41impl Clone for ValueTabuAcceptor {
42    fn clone(&self) -> Self {
43        Self {
44            value_tabu_size: self.value_tabu_size,
45            value_tabu_list: self.value_tabu_list.clone(),
46            current_step_values: self.current_step_values.clone(),
47        }
48    }
49}
50
51impl ValueTabuAcceptor {
52    /// Creates a new value tabu acceptor.
53    ///
54    /// # Arguments
55    /// * `value_tabu_size` - Maximum number of values to remember as tabu. Must be > 0.
56    ///
57    /// # Panics
58    ///
59    /// Panics if `value_tabu_size` is 0.
60    pub fn new(value_tabu_size: usize) -> Self {
61        assert!(value_tabu_size > 0, "value_tabu_size must be > 0, got 0");
62        Self {
63            value_tabu_size,
64            value_tabu_list: Vec::with_capacity(value_tabu_size),
65            current_step_values: Vec::new(),
66        }
67    }
68
69    /// Records that a value was assigned in the current step.
70    ///
71    /// Call this with the hash of the assigned value before accepting the move.
72    pub fn record_value_assignment(&mut self, value_hash: u64) {
73        self.current_step_values.push(value_hash);
74    }
75
76    pub fn is_value_tabu(&self, value_hash: u64) -> bool {
77        self.value_tabu_list.contains(&value_hash)
78    }
79}
80
81impl Default for ValueTabuAcceptor {
82    fn default() -> Self {
83        Self::new(7)
84    }
85}
86
87impl<S: PlanningSolution> Acceptor<S> for ValueTabuAcceptor {
88    fn is_accepted(&mut self, last_step_score: &S::Score, move_score: &S::Score) -> bool {
89        // Accept improving moves
90        if move_score > last_step_score {
91            return true;
92        }
93
94        // Accept equal moves for plateau exploration
95        if move_score >= last_step_score {
96            return true;
97        }
98
99        false
100    }
101
102    fn phase_started(&mut self, _initial_score: &S::Score) {
103        self.value_tabu_list.clear();
104        self.current_step_values.clear();
105    }
106
107    fn phase_ended(&mut self) {
108        self.value_tabu_list.clear();
109    }
110
111    fn step_started(&mut self) {
112        self.current_step_values.clear();
113    }
114
115    fn step_ended(&mut self, _step_score: &S::Score) {
116        // Add current step's values to tabu list
117        for value_hash in &self.current_step_values {
118            if self.value_tabu_list.len() >= self.value_tabu_size {
119                self.value_tabu_list.remove(0);
120            }
121            self.value_tabu_list.push(*value_hash);
122        }
123        self.current_step_values.clear();
124    }
125}
126
127#[cfg(test)]
128#[path = "value_tabu_tests.rs"]
129mod tests;
solverforge_solver/phase/localsearch/acceptor/value_tabu.rs

solverforge_solver/phase/localsearch/acceptor/
value_tabu.rs
