solverforge_solver/phase/localsearch/acceptor/
diversified_late_acceptance.rs

1//! Diversified late acceptance acceptor.
2
3use std::fmt::Debug;
4
5use solverforge_core::domain::PlanningSolution;
6use solverforge_core::Score;
7
8use super::Acceptor;
9
10/// Diversified late acceptance acceptor - combines late acceptance with best score tracking.
11///
12/// Extends [`LateAcceptanceAcceptor`] by also tracking the best score found.
13/// Accepts a move if it:
14/// 1. Improves the last step score (always accepted), OR
15/// 2. Is at least as good as the score from N steps ago, OR
16/// 3. Is within a tolerance of the best score found so far
17///
18/// The third condition allows escaping from local optima by accepting
19/// moves that don't regress too far from the best known solution.
20///
21/// # Example
22///
23/// ```
24/// use solverforge_solver::phase::localsearch::DiversifiedLateAcceptanceAcceptor;
25/// use solverforge_core::score::SimpleScore;
26/// use solverforge_core::domain::PlanningSolution;
27///
28/// #[derive(Clone)]
29/// struct MySolution;
30/// impl PlanningSolution for MySolution {
31///     type Score = SimpleScore;
32///     fn score(&self) -> Option<Self::Score> { None }
33///     fn set_score(&mut self, _: Option<Self::Score>) {}
34/// }
35///
36/// // Accept if better than 400-step-old score OR within 5% of best
37/// let acceptor = DiversifiedLateAcceptanceAcceptor::<MySolution>::new(400, 0.05);
38/// ```
39pub struct DiversifiedLateAcceptanceAcceptor<S: PlanningSolution> {
40    /// Size of the late acceptance list.
41    late_acceptance_size: usize,
42    /// Circular buffer of historical scores.
43    score_history: Vec<Option<S::Score>>,
44    /// Current index in the buffer.
45    current_index: usize,
46    /// Best score found so far in this phase.
47    best_score: Option<S::Score>,
48    /// Tolerance as a fraction (0.05 = 5% worse than best is acceptable).
49    tolerance: f64,
50}
51
52impl<S: PlanningSolution> Debug for DiversifiedLateAcceptanceAcceptor<S> {
53    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
54        f.debug_struct("DiversifiedLateAcceptanceAcceptor")
55            .field("late_acceptance_size", &self.late_acceptance_size)
56            .field("current_index", &self.current_index)
57            .field("tolerance", &self.tolerance)
58            .finish()
59    }
60}
61
62impl<S: PlanningSolution> Clone for DiversifiedLateAcceptanceAcceptor<S> {
63    fn clone(&self) -> Self {
64        Self {
65            late_acceptance_size: self.late_acceptance_size,
66            score_history: self.score_history.clone(),
67            current_index: self.current_index,
68            best_score: self.best_score,
69            tolerance: self.tolerance,
70        }
71    }
72}
73
74impl<S: PlanningSolution> DiversifiedLateAcceptanceAcceptor<S> {
75    /// Creates a new diversified late acceptance acceptor.
76    ///
77    /// # Arguments
78    /// * `late_acceptance_size` - Number of historical scores to keep
79    /// * `tolerance` - Fraction of best score to accept (0.05 = 5% tolerance)
80    pub fn new(late_acceptance_size: usize, tolerance: f64) -> Self {
81        Self {
82            late_acceptance_size,
83            score_history: vec![None; late_acceptance_size],
84            current_index: 0,
85            best_score: None,
86            tolerance,
87        }
88    }
89
90    /// Creates with default tolerance of 0.01 (1%).
91    pub fn with_default_tolerance(late_acceptance_size: usize) -> Self {
92        Self::new(late_acceptance_size, 0.01)
93    }
94}
95
96impl<S: PlanningSolution> Default for DiversifiedLateAcceptanceAcceptor<S> {
97    fn default() -> Self {
98        Self::new(400, 0.01)
99    }
100}
101
102impl<S: PlanningSolution> Acceptor<S> for DiversifiedLateAcceptanceAcceptor<S> {
103    fn is_accepted(&self, last_step_score: &S::Score, move_score: &S::Score) -> bool {
104        // Always accept improving moves
105        if move_score > last_step_score {
106            return true;
107        }
108
109        // Accept if better than or equal to the late score
110        if let Some(late_score) = &self.score_history[self.current_index] {
111            if move_score >= late_score {
112                return true;
113            }
114        } else {
115            // No history yet, accept
116            return true;
117        }
118
119        // Diversification: accept if within tolerance of best score
120        if let Some(best) = &self.best_score {
121            // Calculate threshold: best - tolerance * |best|
122            let abs_best = best.abs();
123            let threshold = *best - abs_best.multiply(self.tolerance);
124            if move_score >= &threshold {
125                return true;
126            }
127        }
128
129        false
130    }
131
132    fn phase_started(&mut self, initial_score: &S::Score) {
133        // Initialize history with the initial score
134        for slot in &mut self.score_history {
135            *slot = Some(*initial_score);
136        }
137        self.current_index = 0;
138        self.best_score = Some(*initial_score);
139    }
140
141    fn step_ended(&mut self, step_score: &S::Score) {
142        // Update best score if improved
143        if let Some(best) = &self.best_score {
144            if step_score > best {
145                self.best_score = Some(*step_score);
146            }
147        } else {
148            self.best_score = Some(*step_score);
149        }
150
151        // Record the step score in the history
152        self.score_history[self.current_index] = Some(*step_score);
153        self.current_index = (self.current_index + 1) % self.late_acceptance_size;
154    }
155}
156
157#[cfg(test)]
158mod tests {
159    use super::*;
160    use solverforge_core::score::SimpleScore;
161
162    #[derive(Clone)]
163    struct TestSolution;
164
165    impl PlanningSolution for TestSolution {
166        type Score = SimpleScore;
167        fn score(&self) -> Option<Self::Score> {
168            None
169        }
170        fn set_score(&mut self, _: Option<Self::Score>) {}
171    }
172
173    #[test]
174    fn test_accepts_improving_moves() {
175        let mut acceptor = DiversifiedLateAcceptanceAcceptor::<TestSolution>::new(5, 0.1);
176        acceptor.phase_started(&SimpleScore::of(-100));
177
178        // Improving move always accepted
179        assert!(acceptor.is_accepted(&SimpleScore::of(-100), &SimpleScore::of(-90)));
180    }
181
182    #[test]
183    fn test_accepts_late_equal() {
184        let mut acceptor = DiversifiedLateAcceptanceAcceptor::<TestSolution>::new(3, 0.1);
185        acceptor.phase_started(&SimpleScore::of(-100));
186
187        // Equal to late score should be accepted
188        assert!(acceptor.is_accepted(&SimpleScore::of(-90), &SimpleScore::of(-100)));
189    }
190
191    #[test]
192    fn test_diversification_accepts_within_tolerance() {
193        let mut acceptor = DiversifiedLateAcceptanceAcceptor::<TestSolution>::new(3, 0.1);
194        acceptor.phase_started(&SimpleScore::of(-100));
195
196        // Improve the best score
197        acceptor.step_ended(&SimpleScore::of(-80));
198        acceptor.step_ended(&SimpleScore::of(-70));
199        acceptor.step_ended(&SimpleScore::of(-60));
200
201        // Now history is filled with newer scores
202        // Best is -60
203        // Threshold = -60 - 0.1 * 60 = -60 - 6 = -66
204
205        // -65 is within tolerance of best (-60) and worse than late score (-60)
206        // But -65 >= -66, so should be accepted
207        assert!(acceptor.is_accepted(&SimpleScore::of(-60), &SimpleScore::of(-65)));
208    }
209
210    #[test]
211    fn test_rejects_outside_tolerance() {
212        let mut acceptor = DiversifiedLateAcceptanceAcceptor::<TestSolution>::new(3, 0.05);
213        acceptor.phase_started(&SimpleScore::of(-100));
214
215        // Improve significantly, all to same good score
216        acceptor.step_ended(&SimpleScore::of(-40));
217        acceptor.step_ended(&SimpleScore::of(-40));
218        acceptor.step_ended(&SimpleScore::of(-40));
219
220        // History is now [-40, -40, -40], best = -40
221        // Late score at index 0 = -40
222        // Threshold = -40 - 0.05 * 40 = -42
223        // -50 is worse than late (-40) AND outside tolerance (-42)
224        assert!(!acceptor.is_accepted(&SimpleScore::of(-40), &SimpleScore::of(-50)));
225    }
226
227    #[test]
228    fn test_history_cycles() {
229        let mut acceptor = DiversifiedLateAcceptanceAcceptor::<TestSolution>::new(3, 0.1);
230        acceptor.phase_started(&SimpleScore::of(-100));
231
232        // Fill history: index 0=-80, 1=-70, 2=-60, next write at 0
233        acceptor.step_ended(&SimpleScore::of(-80));
234        acceptor.step_ended(&SimpleScore::of(-70));
235        acceptor.step_ended(&SimpleScore::of(-60));
236
237        // Now index is 0, late score is -80
238        // -75 is better than -80, should accept
239        assert!(acceptor.is_accepted(&SimpleScore::of(-60), &SimpleScore::of(-75)));
240    }
241}
solverforge_solver/phase/localsearch/acceptor/diversified_late_acceptance.rs

solverforge_solver/phase/localsearch/acceptor/
diversified_late_acceptance.rs
