solverforge_solver/phase/localsearch/acceptor/
diversified_late_acceptance.rs

1// Diversified Late Acceptance Search with exact worst-score occurrence tracking.
2// Acceptance and ring updates advance for each evaluated candidate.
3
4use std::fmt::Debug;
5
6use solverforge_core::domain::PlanningSolution;
7use solverforge_core::Score;
8
9use super::Acceptor;
10use crate::heuristic::r#move::MoveTabuSignature;
11
12pub struct DiversifiedLateAcceptanceAcceptor<S: PlanningSolution> {
13    late_acceptance_size: usize,
14    previous_scores: Vec<S::Score>,
15    late_score_index: usize,
16    late_worse_score: S::Score,
17    late_worse_occurrences: usize,
18}
19
20impl<S: PlanningSolution> Debug for DiversifiedLateAcceptanceAcceptor<S> {
21    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
22        f.debug_struct("DiversifiedLateAcceptanceAcceptor")
23            .field("late_acceptance_size", &self.late_acceptance_size)
24            .field("late_score_index", &self.late_score_index)
25            .field("late_worse_occurrences", &self.late_worse_occurrences)
26            .finish()
27    }
28}
29
30impl<S: PlanningSolution> Clone for DiversifiedLateAcceptanceAcceptor<S> {
31    fn clone(&self) -> Self {
32        Self {
33            late_acceptance_size: self.late_acceptance_size,
34            previous_scores: self.previous_scores.clone(),
35            late_score_index: self.late_score_index,
36            late_worse_score: self.late_worse_score,
37            late_worse_occurrences: self.late_worse_occurrences,
38        }
39    }
40}
41
42impl<S: PlanningSolution> DiversifiedLateAcceptanceAcceptor<S> {
43    pub fn new(late_acceptance_size: usize) -> Self {
44        assert!(
45            late_acceptance_size > 0,
46            "late_acceptance_size must be > 0, got 0"
47        );
48        Self {
49            late_acceptance_size,
50            previous_scores: Vec::new(),
51            late_score_index: 0,
52            late_worse_score: S::Score::zero(),
53            late_worse_occurrences: late_acceptance_size,
54        }
55    }
56}
57
58impl<S: PlanningSolution> Default for DiversifiedLateAcceptanceAcceptor<S> {
59    fn default() -> Self {
60        Self::new(400)
61    }
62}
63
64impl<S: PlanningSolution> Acceptor<S> for DiversifiedLateAcceptanceAcceptor<S> {
65    fn is_accepted(
66        &mut self,
67        last_step_score: &S::Score,
68        move_score: &S::Score,
69        _move_signature: Option<&MoveTabuSignature>,
70    ) -> bool {
71        if self.previous_scores.is_empty() {
72            // phase_started has not run; defer to the plain late-acceptance
73            // behavior so uninitialized use cannot panic.
74            return *move_score >= *last_step_score;
75        }
76
77        // accept = (move == current) || (move > lateWorse)
78        let accepted = move_score == last_step_score || *move_score > self.late_worse_score;
79        let current = if accepted {
80            *move_score
81        } else {
82            *last_step_score
83        };
84
85        let late_score = self.previous_scores[self.late_score_index];
86        let current_score_worse = current < late_score;
87        let current_score_better = current > late_score && current > *last_step_score;
88        if current_score_worse || current_score_better {
89            self.update_late_score(current);
90        }
91        self.late_score_index = (self.late_score_index + 1) % self.late_acceptance_size;
92        accepted
93    }
94
95    fn phase_started(&mut self, initial_score: &S::Score) {
96        self.previous_scores = vec![*initial_score; self.late_acceptance_size];
97        self.late_score_index = 0;
98        self.late_worse_occurrences = self.late_acceptance_size;
99        self.late_worse_score = *initial_score;
100    }
101
102    fn step_ended(
103        &mut self,
104        _step_score: &S::Score,
105        _accepted_move_signature: Option<&MoveTabuSignature>,
106    ) {
107    }
108}
109
110impl<S: PlanningSolution> DiversifiedLateAcceptanceAcceptor<S> {
111    fn update_late_score(&mut self, new_score: S::Score) {
112        let slot_score = self.previous_scores[self.late_score_index];
113        let slot_equal_to_worse = slot_score == self.late_worse_score;
114
115        match new_score.cmp(&self.late_worse_score) {
116            std::cmp::Ordering::Less => {
117                self.late_worse_score = new_score;
118                self.late_worse_occurrences = 1;
119            }
120            std::cmp::Ordering::Equal => {
121                if !slot_equal_to_worse {
122                    self.late_worse_occurrences += 1;
123                }
124            }
125            std::cmp::Ordering::Greater => {
126                if slot_equal_to_worse {
127                    self.late_worse_occurrences -= 1;
128                }
129            }
130        }
131        self.previous_scores[self.late_score_index] = new_score;
132
133        if self.late_worse_occurrences == 0 {
134            let mut worse = self.previous_scores[0];
135            let mut occurrences = 1;
136            for score in self.previous_scores.iter().skip(1) {
137                match (*score).cmp(&worse) {
138                    std::cmp::Ordering::Less => {
139                        worse = *score;
140                        occurrences = 1;
141                    }
142                    std::cmp::Ordering::Equal => occurrences += 1,
143                    std::cmp::Ordering::Greater => {}
144                }
145            }
146            self.late_worse_score = worse;
147            self.late_worse_occurrences = occurrences;
148        }
149    }
150}
151
152#[cfg(test)]
153mod tests;
solverforge_solver/phase/localsearch/acceptor/diversified_late_acceptance.rs

solverforge_solver/phase/localsearch/acceptor/
diversified_late_acceptance.rs
