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::SoftScore;
26/// use solverforge_core::domain::PlanningSolution;
27///
28/// #[derive(Clone)]
29/// struct MySolution;
30/// impl PlanningSolution for MySolution {
31///     type Score = SoftScore;
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. Must be > 0.
79    /// * `tolerance` - Fraction of best score to accept (0.05 = 5% tolerance)
80    ///
81    /// # Panics
82    ///
83    /// Panics if `late_acceptance_size` is 0.
84    pub fn new(late_acceptance_size: usize, tolerance: f64) -> Self {
85        assert!(
86            late_acceptance_size > 0,
87            "late_acceptance_size must be > 0, got 0"
88        );
89        Self {
90            late_acceptance_size,
91            score_history: vec![None; late_acceptance_size],
92            current_index: 0,
93            best_score: None,
94            tolerance,
95        }
96    }
97
98    /// Creates with default tolerance of 0.01 (1%).
99    pub fn with_default_tolerance(late_acceptance_size: usize) -> Self {
100        Self::new(late_acceptance_size, 0.01)
101    }
102}
103
104impl<S: PlanningSolution> Default for DiversifiedLateAcceptanceAcceptor<S> {
105    fn default() -> Self {
106        Self::new(400, 0.01)
107    }
108}
109
110impl<S: PlanningSolution> Acceptor<S> for DiversifiedLateAcceptanceAcceptor<S> {
111    fn is_accepted(&mut self, last_step_score: &S::Score, move_score: &S::Score) -> bool {
112        // Accept non-worsening moves (consistent with LateAcceptanceAcceptor which uses >=)
113        if move_score >= last_step_score {
114            return true;
115        }
116
117        // Accept if better than or equal to the late score
118        if let Some(late_score) = &self.score_history[self.current_index] {
119            if move_score >= late_score {
120                return true;
121            }
122        } else {
123            // No history yet, accept
124            return true;
125        }
126
127        // Diversification: accept if within tolerance of best score
128        if let Some(best) = &self.best_score {
129            // Calculate threshold: best - tolerance * |best|
130            let abs_best = best.abs();
131            let threshold = *best - abs_best.multiply(self.tolerance);
132            if move_score >= &threshold {
133                return true;
134            }
135        }
136
137        false
138    }
139
140    fn phase_started(&mut self, initial_score: &S::Score) {
141        // Initialize history with the initial score
142        for slot in &mut self.score_history {
143            *slot = Some(*initial_score);
144        }
145        self.current_index = 0;
146        self.best_score = Some(*initial_score);
147    }
148
149    fn step_ended(&mut self, step_score: &S::Score) {
150        // Update best score if improved
151        if let Some(best) = &self.best_score {
152            if step_score > best {
153                self.best_score = Some(*step_score);
154            }
155        } else {
156            self.best_score = Some(*step_score);
157        }
158
159        // Record the step score in the history
160        self.score_history[self.current_index] = Some(*step_score);
161        self.current_index = (self.current_index + 1) % self.late_acceptance_size;
162    }
163}
164
165#[cfg(test)]
166#[path = "diversified_late_acceptance_tests.rs"]
167mod tests;
solverforge_solver/phase/localsearch/acceptor/diversified_late_acceptance.rs

solverforge_solver/phase/localsearch/acceptor/
diversified_late_acceptance.rs
