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    ///
54    /// # Panics
55    ///
56    /// Panics if `entity_tabu_size` is 0.
57    pub fn new(entity_tabu_size: usize) -> Self {
58        assert!(entity_tabu_size > 0, "entity_tabu_size must be > 0, got 0");
59        Self {
60            entity_tabu_size,
61            entity_tabu_list: Vec::with_capacity(entity_tabu_size),
62            current_step_entities: Vec::new(),
63        }
64    }
65
66    /// Records that an entity was moved in the current step.
67    pub fn record_entity_move(&mut self, entity_id: u64) {
68        self.current_step_entities.push(entity_id);
69    }
70
71    pub fn is_entity_tabu(&self, entity_id: u64) -> bool {
72        self.entity_tabu_list.contains(&entity_id)
73    }
74}
75
76impl Default for EntityTabuAcceptor {
77    fn default() -> Self {
78        Self::new(7)
79    }
80}
81
82impl<S: PlanningSolution> Acceptor<S> for EntityTabuAcceptor {
83    fn is_accepted(&mut self, last_step_score: &S::Score, move_score: &S::Score) -> bool {
84        // Accept improving moves
85        if move_score > last_step_score {
86            return true;
87        }
88
89        // Accept equal moves for exploration
90        if move_score >= last_step_score {
91            return true;
92        }
93
94        false
95    }
96
97    fn phase_started(&mut self, _initial_score: &S::Score) {
98        self.entity_tabu_list.clear();
99        self.current_step_entities.clear();
100    }
101
102    fn phase_ended(&mut self) {
103        self.entity_tabu_list.clear();
104    }
105
106    fn step_started(&mut self) {
107        self.current_step_entities.clear();
108    }
109
110    fn step_ended(&mut self, _step_score: &S::Score) {
111        // Add current step's entities to tabu list
112        for entity_id in &self.current_step_entities {
113            if self.entity_tabu_list.len() >= self.entity_tabu_size {
114                self.entity_tabu_list.remove(0);
115            }
116            self.entity_tabu_list.push(*entity_id);
117        }
118        self.current_step_entities.clear();
119    }
120}
solverforge_solver/phase/localsearch/acceptor/entity_tabu.rs

solverforge_solver/phase/localsearch/acceptor/
entity_tabu.rs
