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}
40
41impl<S: PlanningSolution> Debug for LateAcceptanceAcceptor<S> {
42    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
43        f.debug_struct("LateAcceptanceAcceptor")
44            .field("late_acceptance_size", &self.late_acceptance_size)
45            .field("current_index", &self.current_index)
46            .finish()
47    }
48}
49
50impl<S: PlanningSolution> Clone for LateAcceptanceAcceptor<S> {
51    fn clone(&self) -> Self {
52        Self {
53            late_acceptance_size: self.late_acceptance_size,
54            score_history: self.score_history.clone(),
55            current_index: self.current_index,
56        }
57    }
58}
59
60impl<S: PlanningSolution> LateAcceptanceAcceptor<S> {
61    /// Creates a new late acceptance acceptor.
62    ///
63    /// # Arguments
64    /// * `late_acceptance_size` - Number of historical scores to keep. Must be > 0.
65    ///
66    /// # Panics
67    ///
68    /// Panics if `late_acceptance_size` is 0.
69    pub fn new(late_acceptance_size: usize) -> Self {
70        assert!(
71            late_acceptance_size > 0,
72            "late_acceptance_size must be > 0, got 0"
73        );
74        Self {
75            late_acceptance_size,
76            score_history: vec![None; late_acceptance_size],
77            current_index: 0,
78        }
79    }
80}
81
82impl<S: PlanningSolution> Default for LateAcceptanceAcceptor<S> {
83    fn default() -> Self {
84        Self::new(400)
85    }
86}
87
88impl<S: PlanningSolution> Acceptor<S> for LateAcceptanceAcceptor<S> {
89    fn is_accepted(
90        &mut self,
91        last_step_score: &S::Score,
92        move_score: &S::Score,
93        _move_signature: Option<&MoveTabuSignature>,
94    ) -> bool {
95        // Always accept improving or equal moves
96        if move_score >= last_step_score {
97            return true;
98        }
99
100        // Accept if better than the late score
101        if let Some(late_score) = &self.score_history[self.current_index] {
102            move_score >= late_score
103        } else {
104            // No history yet, accept
105            true
106        }
107    }
108
109    fn phase_started(&mut self, initial_score: &S::Score) {
110        // Initialize history with the initial score
111        for slot in &mut self.score_history {
112            *slot = Some(*initial_score);
113        }
114        self.current_index = 0;
115    }
116
117    fn step_ended(
118        &mut self,
119        step_score: &S::Score,
120        _accepted_move_signature: Option<&MoveTabuSignature>,
121    ) {
122        // Record the step score in the history
123        self.score_history[self.current_index] = Some(*step_score);
124        self.current_index = (self.current_index + 1) % self.late_acceptance_size;
125    }
126}
solverforge_solver/phase/localsearch/acceptor/late_acceptance.rs

solverforge_solver/phase/localsearch/acceptor/
late_acceptance.rs
