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. Must be > 0.
64    ///
65    /// # Panics
66    ///
67    /// Panics if `late_acceptance_size` is 0.
68    pub fn new(late_acceptance_size: usize) -> Self {
69        assert!(
70            late_acceptance_size > 0,
71            "late_acceptance_size must be > 0, got 0"
72        );
73        Self {
74            late_acceptance_size,
75            score_history: vec![None; late_acceptance_size],
76            current_index: 0,
77        }
78    }
79}
80
81impl<S: PlanningSolution> Default for LateAcceptanceAcceptor<S> {
82    fn default() -> Self {
83        Self::new(400)
84    }
85}
86
87impl<S: PlanningSolution> Acceptor<S> for LateAcceptanceAcceptor<S> {
88    fn is_accepted(&mut self, last_step_score: &S::Score, move_score: &S::Score) -> bool {
89        // Always accept improving or equal moves
90        if move_score >= last_step_score {
91            return true;
92        }
93
94        // Accept if better than the late score
95        if let Some(late_score) = &self.score_history[self.current_index] {
96            move_score >= late_score
97        } else {
98            // No history yet, accept
99            true
100        }
101    }
102
103    fn phase_started(&mut self, initial_score: &S::Score) {
104        // Initialize history with the initial score
105        for slot in &mut self.score_history {
106            *slot = Some(*initial_score);
107        }
108        self.current_index = 0;
109    }
110
111    fn step_ended(&mut self, step_score: &S::Score) {
112        // Record the step score in the history
113        self.score_history[self.current_index] = Some(*step_score);
114        self.current_index = (self.current_index + 1) % self.late_acceptance_size;
115    }
116}
solverforge_solver/phase/localsearch/acceptor/late_acceptance.rs

solverforge_solver/phase/localsearch/acceptor/
late_acceptance.rs
