solverforge_solver/phase/localsearch/acceptor/
late_acceptance.rs

1//! Late acceptance acceptor.
2
3use std::fmt::Debug;
4
5use solverforge_core::domain::PlanningSolution;
6
7use super::Acceptor;
8
9/// Late acceptance acceptor - accepts moves that improve on a historical score.
10///
11/// Maintains a circular buffer of recent scores and accepts moves that
12/// are better than a score from N steps ago.
13///
14/// # Example
15///
16/// ```
17/// use solverforge_solver::phase::localsearch::LateAcceptanceAcceptor;
18/// use solverforge_core::score::SimpleScore;
19/// use solverforge_core::domain::PlanningSolution;
20///
21/// #[derive(Clone)]
22/// struct MySolution;
23/// impl PlanningSolution for MySolution {
24///     type Score = SimpleScore;
25///     fn score(&self) -> Option<Self::Score> { None }
26///     fn set_score(&mut self, _: Option<Self::Score>) {}
27/// }
28///
29/// let acceptor = LateAcceptanceAcceptor::<MySolution>::new(400);
30/// ```
31pub struct LateAcceptanceAcceptor<S: PlanningSolution> {
32    /// Size of the late acceptance list.
33    late_acceptance_size: usize,
34    /// Circular buffer of historical scores.
35    score_history: Vec<Option<S::Score>>,
36    /// Current index in the buffer.
37    current_index: usize,
38}
39
40impl<S: PlanningSolution> Debug for LateAcceptanceAcceptor<S> {
41    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
42        f.debug_struct("LateAcceptanceAcceptor")
43            .field("late_acceptance_size", &self.late_acceptance_size)
44            .field("current_index", &self.current_index)
45            .finish()
46    }
47}
48
49impl<S: PlanningSolution> Clone for LateAcceptanceAcceptor<S> {
50    fn clone(&self) -> Self {
51        Self {
52            late_acceptance_size: self.late_acceptance_size,
53            score_history: self.score_history.clone(),
54            current_index: self.current_index,
55        }
56    }
57}
58
59impl<S: PlanningSolution> LateAcceptanceAcceptor<S> {
60    /// Creates a new late acceptance acceptor.
61    ///
62    /// # Arguments
63    /// * `late_acceptance_size` - Number of historical scores to keep
64    pub fn new(late_acceptance_size: usize) -> Self {
65        Self {
66            late_acceptance_size,
67            score_history: vec![None; late_acceptance_size],
68            current_index: 0,
69        }
70    }
71}
72
73impl<S: PlanningSolution> Default for LateAcceptanceAcceptor<S> {
74    fn default() -> Self {
75        Self::new(400)
76    }
77}
78
79impl<S: PlanningSolution> Acceptor<S> for LateAcceptanceAcceptor<S> {
80    fn is_accepted(&self, last_step_score: &S::Score, move_score: &S::Score) -> bool {
81        // Always accept improving moves
82        if move_score > last_step_score {
83            return true;
84        }
85
86        // Accept if better than the late score
87        if let Some(late_score) = &self.score_history[self.current_index] {
88            move_score >= late_score
89        } else {
90            // No history yet, accept
91            true
92        }
93    }
94
95    fn phase_started(&mut self, initial_score: &S::Score) {
96        // Initialize history with the initial score
97        for slot in &mut self.score_history {
98            *slot = Some(*initial_score);
99        }
100        self.current_index = 0;
101    }
102
103    fn step_ended(&mut self, step_score: &S::Score) {
104        // Record the step score in the history
105        self.score_history[self.current_index] = Some(*step_score);
106        self.current_index = (self.current_index + 1) % self.late_acceptance_size;
107    }
108}
solverforge_solver/phase/localsearch/acceptor/late_acceptance.rs

solverforge_solver/phase/localsearch/acceptor/
late_acceptance.rs
