solverforge_solver/phase/localsearch/acceptor/
step_counting.rs

1// Step Counting Hill Climbing acceptor.
2
3use std::fmt::Debug;
4
5use solverforge_core::domain::PlanningSolution;
6
7use super::Acceptor;
8use crate::heuristic::r#move::MoveTabuSignature;
9
10/// Step Counting Hill Climbing acceptor - allows limited non-improving moves.
11///
12/// This acceptor combines hill climbing with a step limit that resets whenever
13/// an improving move is made. It accepts:
14/// 1. Any improving move (resets the step counter)
15/// 2. Non-improving moves if step count since last improvement is below threshold
16///
17/// This enables exploration while still requiring eventual improvement.
18///
19/// # Example
20///
21/// ```
22/// use solverforge_solver::phase::localsearch::StepCountingHillClimbingAcceptor;
23/// use solverforge_core::score::SoftScore;
24/// use solverforge_core::domain::PlanningSolution;
25///
26/// #[derive(Clone)]
27/// struct MySolution;
28/// impl PlanningSolution for MySolution {
29///     type Score = SoftScore;
30///     fn score(&self) -> Option<Self::Score> { None }
31///     fn set_score(&mut self, _: Option<Self::Score>) {}
32/// }
33///
34/// // Allow up to 100 non-improving steps before requiring improvement
35/// let acceptor = StepCountingHillClimbingAcceptor::<MySolution>::new(100);
36/// ```
37pub struct StepCountingHillClimbingAcceptor<S: PlanningSolution> {
38    // Maximum steps allowed without improvement.
39    step_count_limit: u64,
40    // Current steps since last improvement.
41    steps_since_improvement: u64,
42    // Best score seen so far.
43    best_score: Option<S::Score>,
44}
45
46impl<S: PlanningSolution> Debug for StepCountingHillClimbingAcceptor<S> {
47    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
48        f.debug_struct("StepCountingHillClimbingAcceptor")
49            .field("step_count_limit", &self.step_count_limit)
50            .field("steps_since_improvement", &self.steps_since_improvement)
51            .finish()
52    }
53}
54
55impl<S: PlanningSolution> Clone for StepCountingHillClimbingAcceptor<S> {
56    fn clone(&self) -> Self {
57        Self {
58            step_count_limit: self.step_count_limit,
59            steps_since_improvement: self.steps_since_improvement,
60            best_score: self.best_score,
61        }
62    }
63}
64
65impl<S: PlanningSolution> StepCountingHillClimbingAcceptor<S> {
66    /// Creates a new Step Counting Hill Climbing acceptor.
67    ///
68    /// # Arguments
69    /// * `step_count_limit` - Maximum steps allowed without finding improvement
70    pub fn new(step_count_limit: u64) -> Self {
71        Self {
72            step_count_limit,
73            steps_since_improvement: 0,
74            best_score: None,
75        }
76    }
77}
78
79impl<S: PlanningSolution> Default for StepCountingHillClimbingAcceptor<S> {
80    fn default() -> Self {
81        Self::new(100)
82    }
83}
84
85impl<S: PlanningSolution> Acceptor<S> for StepCountingHillClimbingAcceptor<S> {
86    fn is_accepted(
87        &mut self,
88        last_step_score: &S::Score,
89        move_score: &S::Score,
90        _move_signature: Option<&MoveTabuSignature>,
91    ) -> bool {
92        // Always accept improving moves
93        if move_score > last_step_score {
94            return true;
95        }
96
97        // Accept non-improving moves if within step count limit
98        self.steps_since_improvement < self.step_count_limit
99    }
100
101    fn phase_started(&mut self, initial_score: &S::Score) {
102        self.best_score = Some(*initial_score);
103        self.steps_since_improvement = 0;
104    }
105
106    fn step_ended(
107        &mut self,
108        step_score: &S::Score,
109        _accepted_move_signature: Option<&MoveTabuSignature>,
110    ) {
111        // Check if this step improved on the best score
112        let improved = match &self.best_score {
113            Some(best) => step_score > best,
114            None => true,
115        };
116
117        if improved {
118            self.best_score = Some(*step_score);
119            self.steps_since_improvement = 0;
120        } else {
121            self.steps_since_improvement += 1;
122        }
123    }
124
125    fn phase_ended(&mut self) {
126        self.best_score = None;
127        self.steps_since_improvement = 0;
128    }
129}
130
131#[cfg(test)]
132mod tests;
solverforge_solver/phase/localsearch/acceptor/step_counting.rs

solverforge_solver/phase/localsearch/acceptor/
step_counting.rs
