solverforge_solver/phase/localsearch/acceptor/
tabu_search.rs

1//! Tabu search acceptor.
2
3use std::fmt::Debug;
4
5use solverforge_core::domain::PlanningSolution;
6
7use super::Acceptor;
8
9/// Tabu search acceptor - maintains a tabu list of recently visited solutions.
10///
11/// Tabu search prevents revisiting recently explored solutions by maintaining
12/// a tabu list. This helps escape local optima and prevents cycling.
13///
14/// This implementation tracks recent scores to identify solutions that should
15/// be forbidden (tabu). A more sophisticated implementation would track the
16/// actual moves or entity changes.
17///
18/// # Example
19///
20/// ```
21/// use solverforge_solver::phase::localsearch::TabuSearchAcceptor;
22/// use solverforge_core::score::SimpleScore;
23/// use solverforge_core::domain::PlanningSolution;
24///
25/// #[derive(Clone)]
26/// struct MySolution;
27/// impl PlanningSolution for MySolution {
28///     type Score = SimpleScore;
29///     fn score(&self) -> Option<Self::Score> { None }
30///     fn set_score(&mut self, _: Option<Self::Score>) {}
31/// }
32///
33/// let acceptor = TabuSearchAcceptor::<MySolution>::new(7);
34/// ```
35pub struct TabuSearchAcceptor<S: PlanningSolution> {
36    /// Maximum size of the tabu list.
37    tabu_size: usize,
38    /// List of tabu (forbidden) scores.
39    tabu_list: Vec<S::Score>,
40    /// Whether to accept improving moves even if tabu.
41    aspiration_enabled: bool,
42    /// Best score seen so far (for aspiration criterion).
43    best_score: Option<S::Score>,
44}
45
46impl<S: PlanningSolution> Debug for TabuSearchAcceptor<S> {
47    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
48        f.debug_struct("TabuSearchAcceptor")
49            .field("tabu_size", &self.tabu_size)
50            .field("tabu_list_len", &self.tabu_list.len())
51            .field("aspiration_enabled", &self.aspiration_enabled)
52            .finish()
53    }
54}
55
56impl<S: PlanningSolution> Clone for TabuSearchAcceptor<S> {
57    fn clone(&self) -> Self {
58        Self {
59            tabu_size: self.tabu_size,
60            tabu_list: self.tabu_list.clone(),
61            aspiration_enabled: self.aspiration_enabled,
62            best_score: self.best_score,
63        }
64    }
65}
66
67impl<S: PlanningSolution> TabuSearchAcceptor<S> {
68    /// Creates a new tabu search acceptor.
69    ///
70    /// # Arguments
71    /// * `tabu_size` - Maximum number of solutions to remember as tabu
72    pub fn new(tabu_size: usize) -> Self {
73        Self {
74            tabu_size,
75            tabu_list: Vec::with_capacity(tabu_size),
76            aspiration_enabled: true,
77            best_score: None,
78        }
79    }
80
81    /// Creates a tabu search acceptor without aspiration.
82    ///
83    /// Without aspiration, tabu moves are never accepted, even if they
84    /// would lead to a new best solution.
85    pub fn without_aspiration(tabu_size: usize) -> Self {
86        Self {
87            tabu_size,
88            tabu_list: Vec::with_capacity(tabu_size),
89            aspiration_enabled: false,
90            best_score: None,
91        }
92    }
93
94    /// Returns true if the given score is in the tabu list.
95    fn is_tabu(&self, score: &S::Score) -> bool {
96        self.tabu_list.iter().any(|s| s == score)
97    }
98
99    /// Adds a score to the tabu list, removing the oldest if at capacity.
100    fn add_to_tabu(&mut self, score: S::Score) {
101        if self.tabu_list.len() >= self.tabu_size {
102            self.tabu_list.remove(0);
103        }
104        self.tabu_list.push(score);
105    }
106}
107
108impl<S: PlanningSolution> Default for TabuSearchAcceptor<S> {
109    fn default() -> Self {
110        Self::new(7) // Default tabu tenure of 7
111    }
112}
113
114impl<S: PlanningSolution> Acceptor<S> for TabuSearchAcceptor<S> {
115    fn is_accepted(&self, last_step_score: &S::Score, move_score: &S::Score) -> bool {
116        // Check aspiration criterion: accept if this would be a new best score
117        if self.aspiration_enabled {
118            if let Some(best) = &self.best_score {
119                if move_score > best {
120                    return true; // Aspiration: accept new best even if tabu
121                }
122            }
123        }
124
125        // Reject if the move leads to a tabu solution
126        if self.is_tabu(move_score) {
127            return false;
128        }
129
130        // Accept improving moves
131        if move_score > last_step_score {
132            return true;
133        }
134
135        // Accept equal moves (allows exploration on plateaus)
136        if move_score >= last_step_score {
137            return true;
138        }
139
140        // Reject worsening moves that aren't tabu-breaking
141        false
142    }
143
144    fn phase_started(&mut self, initial_score: &S::Score) {
145        self.tabu_list.clear();
146        self.best_score = Some(*initial_score);
147    }
148
149    fn phase_ended(&mut self) {
150        self.tabu_list.clear();
151    }
152
153    fn step_ended(&mut self, step_score: &S::Score) {
154        // Add the step score to the tabu list
155        self.add_to_tabu(*step_score);
156
157        // Update best score
158        if let Some(best) = &self.best_score {
159            if step_score > best {
160                self.best_score = Some(*step_score);
161            }
162        } else {
163            self.best_score = Some(*step_score);
164        }
165    }
166}
solverforge_solver/phase/localsearch/acceptor/tabu_search.rs

solverforge_solver/phase/localsearch/acceptor/
tabu_search.rs
