solverforge_solver/phase/localsearch/acceptor/
entity_tabu.rs

1//! Entity tabu acceptor.
2
3use std::fmt::Debug;
4
5use solverforge_core::domain::PlanningSolution;
6
7use super::Acceptor;
8
9/// Entity tabu acceptor - maintains a tabu list based on entity identifiers.
10///
11/// This is a more sophisticated tabu search that tracks which entities
12/// have been recently modified rather than just tracking scores.
13/// It requires entities to have a stable hash/identifier.
14///
15/// # Example
16///
17/// ```
18/// use solverforge_solver::phase::localsearch::EntityTabuAcceptor;
19///
20/// let acceptor = EntityTabuAcceptor::new(7);
21/// assert!(!acceptor.is_entity_tabu(42));
22/// ```
23pub struct EntityTabuAcceptor {
24    /// Maximum number of entity changes to remember.
25    entity_tabu_size: usize,
26    /// List of tabu entity identifiers (as u64 hashes).
27    entity_tabu_list: Vec<u64>,
28    /// Current step's moved entities.
29    current_step_entities: Vec<u64>,
30}
31
32impl Debug for EntityTabuAcceptor {
33    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
34        f.debug_struct("EntityTabuAcceptor")
35            .field("entity_tabu_size", &self.entity_tabu_size)
36            .field("tabu_list_len", &self.entity_tabu_list.len())
37            .finish()
38    }
39}
40
41impl Clone for EntityTabuAcceptor {
42    fn clone(&self) -> Self {
43        Self {
44            entity_tabu_size: self.entity_tabu_size,
45            entity_tabu_list: self.entity_tabu_list.clone(),
46            current_step_entities: self.current_step_entities.clone(),
47        }
48    }
49}
50
51impl EntityTabuAcceptor {
52    /// Creates a new entity tabu acceptor.
53    pub fn new(entity_tabu_size: usize) -> Self {
54        Self {
55            entity_tabu_size,
56            entity_tabu_list: Vec::with_capacity(entity_tabu_size),
57            current_step_entities: Vec::new(),
58        }
59    }
60
61    /// Records that an entity was moved in the current step.
62    pub fn record_entity_move(&mut self, entity_id: u64) {
63        self.current_step_entities.push(entity_id);
64    }
65
66    /// Returns true if the given entity is in the tabu list.
67    pub fn is_entity_tabu(&self, entity_id: u64) -> bool {
68        self.entity_tabu_list.contains(&entity_id)
69    }
70}
71
72impl Default for EntityTabuAcceptor {
73    fn default() -> Self {
74        Self::new(7)
75    }
76}
77
78impl<S: PlanningSolution> Acceptor<S> for EntityTabuAcceptor {
79    fn is_accepted(&self, last_step_score: &S::Score, move_score: &S::Score) -> bool {
80        // Accept improving moves
81        if move_score > last_step_score {
82            return true;
83        }
84
85        // Accept equal moves for exploration
86        if move_score >= last_step_score {
87            return true;
88        }
89
90        false
91    }
92
93    fn phase_started(&mut self, _initial_score: &S::Score) {
94        self.entity_tabu_list.clear();
95        self.current_step_entities.clear();
96    }
97
98    fn phase_ended(&mut self) {
99        self.entity_tabu_list.clear();
100    }
101
102    fn step_started(&mut self) {
103        self.current_step_entities.clear();
104    }
105
106    fn step_ended(&mut self, _step_score: &S::Score) {
107        // Add current step's entities to tabu list
108        for entity_id in &self.current_step_entities {
109            if self.entity_tabu_list.len() >= self.entity_tabu_size {
110                self.entity_tabu_list.remove(0);
111            }
112            self.entity_tabu_list.push(*entity_id);
113        }
114        self.current_step_entities.clear();
115    }
116}
solverforge_solver/phase/localsearch/acceptor/entity_tabu.rs

solverforge_solver/phase/localsearch/acceptor/
entity_tabu.rs
