solverforge_solver/phase/localsearch/acceptor/
great_deluge.rs

1// Great Deluge acceptor.
2
3use std::fmt::Debug;
4
5use solverforge_core::domain::PlanningSolution;
6use solverforge_core::score::Score;
7
8use super::Acceptor;
9use crate::heuristic::r#move::MoveTabuSignature;
10
11/// Great Deluge acceptor - accepts moves above a rising water level.
12///
13/// The water level starts at the initial solution's score and rises over time.
14/// A move is accepted if its resulting score is at or above the current water level.
15/// This allows temporary score degradation while gradually tightening acceptance.
16///
17/// # Algorithm
18///
19/// 1. Water level starts at initial score
20/// 2. Each step, water level rises by `rain_speed * |initial_score|`
21/// 3. Accept if `move_score >= water_level`
22///
23/// # Example
24///
25/// ```
26/// use solverforge_solver::phase::localsearch::GreatDelugeAcceptor;
27/// use solverforge_core::score::SoftScore;
28/// use solverforge_core::domain::PlanningSolution;
29///
30/// #[derive(Clone)]
31/// struct MySolution;
32/// impl PlanningSolution for MySolution {
33///     type Score = SoftScore;
34///     fn score(&self) -> Option<Self::Score> { None }
35///     fn set_score(&mut self, _: Option<Self::Score>) {}
36/// }
37///
38/// // Rain speed of 0.001 means water level rises by 0.1% of |initial| per step
39/// let acceptor = GreatDelugeAcceptor::<MySolution>::new(0.001);
40/// ```
41pub struct GreatDelugeAcceptor<S: PlanningSolution> {
42    // Rain speed - ratio of |initial_score| to add per step.
43    rain_speed: f64,
44    // Current water level.
45    water_level: Option<S::Score>,
46    // Absolute value of initial score, used to compute increment.
47    initial_abs_score: Option<S::Score>,
48}
49
50impl<S: PlanningSolution> Debug for GreatDelugeAcceptor<S> {
51    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
52        f.debug_struct("GreatDelugeAcceptor")
53            .field("rain_speed", &self.rain_speed)
54            .finish()
55    }
56}
57
58impl<S: PlanningSolution> Clone for GreatDelugeAcceptor<S> {
59    fn clone(&self) -> Self {
60        Self {
61            rain_speed: self.rain_speed,
62            water_level: self.water_level,
63            initial_abs_score: self.initial_abs_score,
64        }
65    }
66}
67
68impl<S: PlanningSolution> GreatDelugeAcceptor<S> {
69    /// Creates a new Great Deluge acceptor.
70    ///
71    /// # Arguments
72    /// * `rain_speed` - Ratio of |initial_score| to raise water level per step.
73    ///   Typical values: 0.0001 to 0.01
74    pub fn new(rain_speed: f64) -> Self {
75        Self {
76            rain_speed,
77            water_level: None,
78            initial_abs_score: None,
79        }
80    }
81}
82
83impl<S: PlanningSolution> Default for GreatDelugeAcceptor<S> {
84    fn default() -> Self {
85        Self::new(0.001)
86    }
87}
88
89impl<S: PlanningSolution> Acceptor<S> for GreatDelugeAcceptor<S> {
90    fn is_accepted(
91        &mut self,
92        last_step_score: &S::Score,
93        move_score: &S::Score,
94        _move_signature: Option<&MoveTabuSignature>,
95    ) -> bool {
96        // Always accept improving moves
97        if move_score > last_step_score {
98            return true;
99        }
100
101        // Accept if at or above water level
102        match &self.water_level {
103            Some(water_level) => move_score >= water_level,
104            None => true, // No water level yet, accept
105        }
106    }
107
108    fn phase_started(&mut self, initial_score: &S::Score) {
109        self.water_level = Some(*initial_score);
110        self.initial_abs_score = Some(initial_score.abs());
111    }
112
113    fn step_ended(
114        &mut self,
115        _step_score: &S::Score,
116        _accepted_move_signature: Option<&MoveTabuSignature>,
117    ) {
118        // Raise water level by rain_speed * |initial_score|
119        if let (Some(water), Some(abs_score)) = (&self.water_level, &self.initial_abs_score) {
120            let increment = abs_score.multiply(self.rain_speed);
121            self.water_level = Some(*water + increment);
122        }
123    }
124
125    fn phase_ended(&mut self) {
126        self.water_level = None;
127        self.initial_abs_score = None;
128    }
129}
130
131#[cfg(test)]
132mod tests;
solverforge_solver/phase/localsearch/acceptor/great_deluge.rs

solverforge_solver/phase/localsearch/acceptor/
great_deluge.rs
