solverforge_solver/phase/localsearch/acceptor/
tabu_search.rs

1use std::fmt::Debug;
2
3use smallvec::SmallVec;
4use solverforge_core::domain::PlanningSolution;
5
6use super::Acceptor;
7use crate::heuristic::r#move::{
8    metadata::{MoveIdentity, ScopedEntityTabuToken, ScopedValueTabuToken},
9    MoveTabuSignature,
10};
11
12#[derive(Clone, Copy, Debug, PartialEq, Eq)]
13pub(crate) struct TabuSearchPolicy {
14    pub entity_tabu_size: Option<usize>,
15    pub value_tabu_size: Option<usize>,
16    pub move_tabu_size: Option<usize>,
17    pub undo_move_tabu_size: Option<usize>,
18    pub aspiration_enabled: bool,
19}
20
21impl TabuSearchPolicy {
22    pub(crate) fn move_only(move_tabu_size: usize) -> Self {
23        Self {
24            entity_tabu_size: None,
25            value_tabu_size: None,
26            move_tabu_size: Some(move_tabu_size),
27            undo_move_tabu_size: None,
28            aspiration_enabled: true,
29        }
30        .validated()
31    }
32
33    pub(crate) fn validated(self) -> Self {
34        let entity_tabu_size = validate_tabu_size("entity_tabu_size", self.entity_tabu_size);
35        let value_tabu_size = validate_tabu_size("value_tabu_size", self.value_tabu_size);
36        let move_tabu_size = validate_tabu_size("move_tabu_size", self.move_tabu_size);
37        let undo_move_tabu_size =
38            validate_tabu_size("undo_move_tabu_size", self.undo_move_tabu_size);
39
40        assert!(
41            entity_tabu_size.is_some()
42                || value_tabu_size.is_some()
43                || move_tabu_size.is_some()
44                || undo_move_tabu_size.is_some(),
45            "tabu_search requires at least one tabu dimension"
46        );
47
48        Self {
49            entity_tabu_size,
50            value_tabu_size,
51            move_tabu_size,
52            undo_move_tabu_size,
53            aspiration_enabled: self.aspiration_enabled,
54        }
55    }
56}
57
58fn validate_tabu_size(field_name: &str, value: Option<usize>) -> Option<usize> {
59    match value {
60        Some(0) => panic!("tabu_search field `{field_name}` must be greater than 0"),
61        _ => value,
62    }
63}
64
65#[derive(Clone, Debug, Default)]
66struct TabuMemory<T> {
67    tenure: Option<usize>,
68    entries: Vec<T>,
69}
70
71impl<T: PartialEq> TabuMemory<T> {
72    fn new(tenure: Option<usize>) -> Self {
73        Self {
74            tenure,
75            entries: Vec::new(),
76        }
77    }
78
79    fn contains(&self, entry: &T) -> bool {
80        self.entries.iter().any(|item| item == entry)
81    }
82
83    fn record(&mut self, entry: T) {
84        let Some(tenure) = self.tenure else {
85            return;
86        };
87        if self.entries.len() >= tenure {
88            self.entries.remove(0);
89        }
90        self.entries.push(entry);
91    }
92
93    fn record_drained(&mut self, entries: &mut SmallVec<[T; 2]>) {
94        for entry in entries.drain(..) {
95            self.record(entry);
96        }
97    }
98
99    fn clear(&mut self) {
100        self.entries.clear();
101    }
102}
103
104/// Canonical metadata-based tabu search acceptor.
105///
106/// Unlike the previous score-tabu placeholder, this implementation uses the
107/// actual move signature emitted by the canonical move system. The score layer
108/// only participates through aspiration and phase-best tracking; admissible
109/// moves are left to the forager to rank.
110pub struct TabuSearchAcceptor<S: PlanningSolution> {
111    entity_memory: TabuMemory<ScopedEntityTabuToken>,
112    value_memory: TabuMemory<ScopedValueTabuToken>,
113    move_memory: TabuMemory<MoveIdentity>,
114    // Stores undo identities emitted by accepted moves; future reverse moves
115    // match this memory through their candidate move identity.
116    reverse_move_memory: TabuMemory<MoveIdentity>,
117    aspiration_enabled: bool,
118    best_score: Option<S::Score>,
119}
120
121impl<S: PlanningSolution> Debug for TabuSearchAcceptor<S> {
122    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
123        f.debug_struct("TabuSearchAcceptor")
124            .field("entity_tabu_size", &self.entity_memory.tenure)
125            .field("value_tabu_size", &self.value_memory.tenure)
126            .field("move_tabu_size", &self.move_memory.tenure)
127            .field("undo_move_tabu_size", &self.reverse_move_memory.tenure)
128            .field("aspiration_enabled", &self.aspiration_enabled)
129            .finish()
130    }
131}
132
133impl<S: PlanningSolution> Clone for TabuSearchAcceptor<S> {
134    fn clone(&self) -> Self {
135        Self {
136            entity_memory: self.entity_memory.clone(),
137            value_memory: self.value_memory.clone(),
138            move_memory: self.move_memory.clone(),
139            reverse_move_memory: self.reverse_move_memory.clone(),
140            aspiration_enabled: self.aspiration_enabled,
141            best_score: self.best_score,
142        }
143    }
144}
145
146impl<S: PlanningSolution> TabuSearchAcceptor<S> {
147    pub(crate) fn new(policy: TabuSearchPolicy) -> Self {
148        let policy = policy.validated();
149
150        Self {
151            entity_memory: TabuMemory::new(policy.entity_tabu_size),
152            value_memory: TabuMemory::new(policy.value_tabu_size),
153            move_memory: TabuMemory::new(policy.move_tabu_size),
154            reverse_move_memory: TabuMemory::new(policy.undo_move_tabu_size),
155            aspiration_enabled: policy.aspiration_enabled,
156            best_score: None,
157        }
158    }
159
160    fn is_tabu(&self, signature: &MoveTabuSignature) -> bool {
161        signature
162            .entity_tokens
163            .iter()
164            .any(|entity_token| self.entity_memory.contains(entity_token))
165            || signature
166                .destination_value_tokens
167                .iter()
168                .any(|value_token| self.value_memory.contains(value_token))
169            || self.move_memory.contains(&signature.move_id)
170            || self.reverse_move_memory.contains(&signature.move_id)
171    }
172}
173
174impl<S: PlanningSolution> Acceptor<S> for TabuSearchAcceptor<S> {
175    fn requires_move_signatures(&self) -> bool {
176        true
177    }
178
179    fn is_accepted(
180        &mut self,
181        _last_step_score: &S::Score,
182        move_score: &S::Score,
183        move_signature: Option<&MoveTabuSignature>,
184    ) -> bool {
185        let signature = move_signature.expect("tabu search requires move signatures");
186        let aspirational = self
187            .best_score
188            .as_ref()
189            .is_some_and(|best| self.aspiration_enabled && move_score > best);
190        if !aspirational && self.is_tabu(signature) {
191            return false;
192        }
193        true
194    }
195
196    fn phase_started(&mut self, initial_score: &S::Score) {
197        self.entity_memory.clear();
198        self.value_memory.clear();
199        self.move_memory.clear();
200        self.reverse_move_memory.clear();
201        self.best_score = Some(*initial_score);
202    }
203
204    fn phase_ended(&mut self) {
205        self.entity_memory.clear();
206        self.value_memory.clear();
207        self.move_memory.clear();
208        self.reverse_move_memory.clear();
209        self.best_score = None;
210    }
211
212    fn step_ended(
213        &mut self,
214        step_score: &S::Score,
215        accepted_move_signature: Option<MoveTabuSignature>,
216    ) {
217        if let Some(mut signature) = accepted_move_signature {
218            // Ownership transfer: retained tokens move out of the delivered
219            // signature; eviction in the ring drops them by value.
220            let mut entity_tokens = std::mem::take(&mut signature.entity_tokens);
221            let mut value_tokens = std::mem::take(&mut signature.destination_value_tokens);
222            self.entity_memory.record_drained(&mut entity_tokens);
223            self.value_memory.record_drained(&mut value_tokens);
224            let move_id = std::mem::take(&mut signature.move_id);
225            match &mut signature.undo_move_id {
226                /* A self-undoing move's reverse identity IS its move identity:
227                both memories hold the same id (one owned copy each, matching
228                the pre-undo-identity-enum semantics). */
229                crate::heuristic::r#move::metadata::MoveUndoIdentity::SameAsMoveId => {
230                    self.reverse_move_memory.record(move_id.clone());
231                    self.move_memory.record(move_id);
232                }
233                crate::heuristic::r#move::metadata::MoveUndoIdentity::Explicit(id) => {
234                    self.move_memory.record(move_id);
235                    self.reverse_move_memory.record(std::mem::take(id));
236                }
237            }
238        }
239
240        if let Some(best) = &self.best_score {
241            if step_score > best {
242                self.best_score = Some(*step_score);
243            }
244        } else {
245            self.best_score = Some(*step_score);
246        }
247    }
248}
solverforge_solver/phase/localsearch/acceptor/tabu_search.rs

solverforge_solver/phase/localsearch/acceptor/
tabu_search.rs
