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;
8use crate::heuristic::r#move::MoveTabuSignature;
9
10/// Late acceptance acceptor - accepts moves that improve on a historical score.
11///
12/// Maintains a circular buffer of recent scores and accepts moves that
13/// are better than a score from N steps ago.
14///
15/// # Example
16///
17/// ```
18/// use solverforge_solver::phase::localsearch::LateAcceptanceAcceptor;
19/// use solverforge_core::score::SoftScore;
20/// use solverforge_core::domain::PlanningSolution;
21///
22/// #[derive(Clone)]
23/// struct MySolution;
24/// impl PlanningSolution for MySolution {
25///     type Score = SoftScore;
26///     fn score(&self) -> Option<Self::Score> { None }
27///     fn set_score(&mut self, _: Option<Self::Score>) {}
28/// }
29///
30/// let acceptor = LateAcceptanceAcceptor::<MySolution>::new(400);
31/// ```
32pub struct LateAcceptanceAcceptor<S: PlanningSolution> {
33    // Size of the late acceptance list.
34    late_acceptance_size: usize,
35    // Circular buffer of historical scores.
36    score_history: Vec<Option<S::Score>>,
37    // Current index in the buffer.
38    current_index: usize,
39    // Best score seen so far in this phase; the buffer resets to it whenever a
40    // new best is committed, re-anchoring the acceptance window.
41    best_score: Option<S::Score>,
42}
43
44impl<S: PlanningSolution> Debug for LateAcceptanceAcceptor<S> {
45    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
46        f.debug_struct("LateAcceptanceAcceptor")
47            .field("late_acceptance_size", &self.late_acceptance_size)
48            .field("current_index", &self.current_index)
49            .finish()
50    }
51}
52
53impl<S: PlanningSolution> Clone for LateAcceptanceAcceptor<S> {
54    fn clone(&self) -> Self {
55        Self {
56            late_acceptance_size: self.late_acceptance_size,
57            score_history: self.score_history.clone(),
58            current_index: self.current_index,
59            best_score: self.best_score,
60        }
61    }
62}
63
64impl<S: PlanningSolution> LateAcceptanceAcceptor<S> {
65    /// Creates a new late acceptance acceptor.
66    ///
67    /// # Arguments
68    /// * `late_acceptance_size` - Number of historical scores to keep. Must be > 0.
69    ///
70    /// # Panics
71    ///
72    /// Panics if `late_acceptance_size` is 0.
73    pub fn new(late_acceptance_size: usize) -> Self {
74        assert!(
75            late_acceptance_size > 0,
76            "late_acceptance_size must be > 0, got 0"
77        );
78        Self {
79            late_acceptance_size,
80            score_history: vec![None; late_acceptance_size],
81            current_index: 0,
82            best_score: None,
83        }
84    }
85}
86
87impl<S: PlanningSolution> Default for LateAcceptanceAcceptor<S> {
88    fn default() -> Self {
89        Self::new(400)
90    }
91}
92
93impl<S: PlanningSolution> Acceptor<S> for LateAcceptanceAcceptor<S> {
94    fn is_accepted(
95        &mut self,
96        last_step_score: &S::Score,
97        move_score: &S::Score,
98        _move_signature: Option<&MoveTabuSignature>,
99    ) -> bool {
100        // Always accept improving or equal moves
101        if move_score >= last_step_score {
102            return true;
103        }
104
105        // Accept if better than the late score
106        if let Some(late_score) = &self.score_history[self.current_index] {
107            move_score >= late_score
108        } else {
109            // No history yet, accept
110            true
111        }
112    }
113
114    fn phase_started(&mut self, initial_score: &S::Score) {
115        // Initialize history with the initial score
116        self.score_history.fill(Some(*initial_score));
117        self.current_index = 0;
118        self.best_score = Some(*initial_score);
119    }
120
121    fn step_ended(
122        &mut self,
123        step_score: &S::Score,
124        _accepted_move_signature: Option<&MoveTabuSignature>,
125    ) {
126        // Record the step score in the history
127        self.score_history[self.current_index] = Some(*step_score);
128        self.current_index = (self.current_index + 1) % self.late_acceptance_size;
129
130        // Re-anchor the whole window on a new best so the acceptance bar does
131        // not still quote pre-improvement scores.
132        let new_best = self.best_score.is_none_or(|best| step_score > &best);
133        if new_best {
134            self.best_score = Some(*step_score);
135            self.score_history.fill(Some(*step_score));
136        }
137    }
138}
solverforge_solver/phase/localsearch/acceptor/late_acceptance.rs

solverforge_solver/phase/localsearch/acceptor/
late_acceptance.rs
