wafrift_evolution/search/
tabu.rs

1use crate::evolution::crossover::mutation::mutate_with_log;
2use crate::evolution::{Chromosome, GenePool, population::random_chromosome};
3use crate::lineage::Lineage;
4use crate::search::{EvalCandidate, SearchAlgorithm, comparable_fitness, fitness_cmp};
5use crate::types::{Budget, EvolutionError, OracleVerdict, SearchStats};
6use rand::rngs::StdRng;
7use serde::{Deserialize, Serialize};
8use std::collections::{HashSet, VecDeque};
9
10/// Tabu search with aspiration criteria.
11#[derive(Debug, Clone, Serialize, Deserialize)]
12pub struct TabuSearch {
13    current: Chromosome,
14    best: Chromosome,
15    gene_pool: GenePool,
16    generation: u32,
17    eval_counter: u64,
18    tabu_list: VecDeque<u64>,
19    tabu_tenure: usize,
20    tabu_set: HashSet<u64>,
21}
22
23impl TabuSearch {
24    #[must_use]
25    pub fn new(tabu_tenure: usize) -> Self {
26        Self {
27            current: Chromosome::new(vec![]),
28            best: Chromosome::new(vec![]),
29            gene_pool: GenePool::default_wafrift(),
30            generation: 0,
31            eval_counter: 0,
32            tabu_list: VecDeque::new(),
33            tabu_tenure,
34            tabu_set: HashSet::new(),
35        }
36    }
37
38    fn neighbor(&self, rng: &mut StdRng) -> Chromosome {
39        let mut child = self.current.clone();
40        let log = mutate_with_log(&mut child, &self.gene_pool, 0.25, rng);
41        child.lineage = Lineage::mutation(&self.current, log, self.generation);
42        child
43    }
44
45    fn add_tabu(&mut self, hash: u64) {
46        if self.tabu_set.insert(hash) {
47            self.tabu_list.push_back(hash);
48        }
49        while self.tabu_list.len() > self.tabu_tenure {
50            if let Some(old) = self.tabu_list.pop_front() {
51                self.tabu_set.remove(&old);
52            }
53        }
54    }
55}
56
57impl Default for TabuSearch {
58    fn default() -> Self {
59        Self::new(20)
60    }
61}
62
63impl SearchAlgorithm for TabuSearch {
64    fn name(&self) -> &'static str {
65        "tabu_search"
66    }
67
68    fn initialize(&mut self, population: Vec<Chromosome>, gene_pool: &GenePool, rng: &mut StdRng) {
69        self.gene_pool = gene_pool.clone();
70        if let Some(best) = population
71            .iter()
72            .max_by(|a, b| fitness_cmp(a.fitness, b.fitness))
73        {
74            self.current = best.clone();
75            self.best = best.clone();
76            self.add_tabu(best.hash());
77        } else {
78            self.current = random_chromosome(gene_pool, rng);
79            self.best = self.current.clone();
80            self.add_tabu(self.current.hash());
81        }
82    }
83
84    fn request_evaluations(&mut self, n: usize, rng: &mut StdRng) -> Vec<EvalCandidate> {
85        let mut out = Vec::with_capacity(n);
86        let mut attempts = 0;
87        while out.len() < n && attempts < n * 10 {
88            attempts += 1;
89            self.eval_counter = self.eval_counter.saturating_add(1);
90            let candidate = self.neighbor(rng);
91            let hash = candidate.hash();
92            // Tabu check. The aspiration criterion ("allow a tabu move
93            // if it beats the current best") is intentionally NOT
94            // applied here: candidate has fitness == 0.0 because it
95            // hasn't been evaluated yet, so the comparison would
96            // always be false and the algorithm would deadlock when
97            // every neighbour is tabu. Aspiration belongs in
98            // submit_evaluations, where fitness is real. Removing it
99            // here matches the SimulatedAnnealing/HillClimbing flow.
100            let is_tabu = self.tabu_set.contains(&hash);
101            if !is_tabu {
102                out.push(EvalCandidate {
103                    id: self.eval_counter,
104                    chromosome: candidate,
105                });
106            }
107        }
108        out
109    }
110
111    fn submit_evaluations(&mut self, results: Vec<(u64, OracleVerdict)>) {
112        for (_id, verdict) in results {
113            let mut candidate = self.current.clone();
114            candidate.record_verdict(&verdict);
115            self.add_tabu(candidate.hash());
116            if comparable_fitness(candidate.fitness) >= comparable_fitness(self.current.fitness) {
117                self.current = candidate;
118                if comparable_fitness(self.current.fitness) > comparable_fitness(self.best.fitness)
119                {
120                    self.best = self.current.clone();
121                }
122            }
123        }
124        self.generation = self.generation.saturating_add(1);
125    }
126
127    fn should_terminate(&self, stats: &SearchStats, budget: &Budget) -> bool {
128        stats.evaluations >= budget.max_requests
129            || stats.generation >= budget.max_generations
130            || stats.stagnation_counter >= budget.stagnation_limit
131    }
132
133    fn best(&self) -> Option<&Chromosome> {
134        Some(&self.best)
135    }
136
137    fn checkpoint(&self) -> Result<Vec<u8>, EvolutionError> {
138        serde_json::to_vec(self).map_err(EvolutionError::SerializationFailed)
139    }
140
141    fn restore(&mut self, bytes: &[u8]) -> Result<(), EvolutionError> {
142        if bytes.len() > crate::types::MAX_CHECKPOINT_BYTES {
143            return Err(EvolutionError::OversizedData {
144                context: "tabu checkpoint restore".into(),
145                size: bytes.len(),
146                max: crate::types::MAX_CHECKPOINT_BYTES,
147            });
148        }
149        *self = serde_json::from_slice(bytes).map_err(EvolutionError::DeserializationFailed)?;
150        Ok(())
151    }
152
153    fn clone_box(&self) -> Box<dyn SearchAlgorithm> {
154        Box::new(self.clone())
155    }
156}
157
158#[cfg(test)]
159mod tests {
160    use super::*;
161    use rand::SeedableRng;
162
163    #[test]
164    fn non_finite_fitness_does_not_block_future_updates() {
165        let mut alg = TabuSearch::new(10);
166        let pool = GenePool::default_wafrift();
167        let mut rng = StdRng::seed_from_u64(11);
168        alg.initialize(vec![Chromosome::new(vec![])], &pool, &mut rng);
169
170        alg.submit_evaluations(vec![(
171            1,
172            OracleVerdict {
173                passed: false,
174                status_delta: 0,
175                body_delta: 0,
176                latency_ms: 0,
177                confidence: f64::NAN,
178                triggered_rules: 1,
179                ..Default::default()
180            },
181        )]);
182        let best_after_nan = comparable_fitness(alg.best().expect("best must exist").fitness);
183
184        alg.submit_evaluations(vec![(2, OracleVerdict::from_bool(true))]);
185        let best_after_valid = comparable_fitness(alg.best().expect("best must exist").fitness);
186        assert!(best_after_valid > best_after_nan);
187    }
188
189    // ── Saturating-arithmetic regression tests ────────────────────────────────
190
191    /// `eval_counter` must saturate at `u64::MAX` instead of wrapping to 0.
192    #[test]
193    fn eval_counter_saturates_at_u64_max() {
194        let mut alg = TabuSearch::new(10);
195        let pool = GenePool::default_wafrift();
196        let mut rng = StdRng::seed_from_u64(40);
197        alg.initialize(vec![Chromosome::new(vec![])], &pool, &mut rng);
198        alg.eval_counter = u64::MAX;
199        let _ = alg.request_evaluations(1, &mut rng);
200        assert_eq!(
201            alg.eval_counter,
202            u64::MAX,
203            "eval_counter must saturate at u64::MAX, not wrap to 0"
204        );
205    }
206
207    /// `generation` must saturate at `u32::MAX` instead of wrapping to 0.
208    #[test]
209    fn generation_saturates_at_u32_max() {
210        let mut alg = TabuSearch::new(10);
211        let pool = GenePool::default_wafrift();
212        let mut rng = StdRng::seed_from_u64(41);
213        alg.initialize(vec![Chromosome::new(vec![])], &pool, &mut rng);
214        alg.generation = u32::MAX;
215        alg.submit_evaluations(vec![(0, OracleVerdict::from_bool(false))]);
216        assert_eq!(
217            alg.generation,
218            u32::MAX,
219            "generation must saturate at u32::MAX, not wrap to 0"
220        );
221    }
222
223    /// IDs returned by `request_evaluations` must be unique (no counter wrap).
224    #[test]
225    fn eval_counter_ids_are_unique_across_generations() {
226        let mut alg = TabuSearch::new(50);
227        let pool = GenePool::default_wafrift();
228        let mut rng = StdRng::seed_from_u64(42);
229        alg.initialize(vec![Chromosome::new(vec![])], &pool, &mut rng);
230        let mut ids: Vec<u64> = Vec::new();
231        for _ in 0..10 {
232            let batch = alg.request_evaluations(2, &mut rng);
233            for c in &batch {
234                ids.push(c.id);
235            }
236            let verdicts: Vec<_> = batch
237                .into_iter()
238                .map(|c| (c.id, OracleVerdict::from_bool(false)))
239                .collect();
240            alg.submit_evaluations(verdicts);
241        }
242        let unique: std::collections::HashSet<_> = ids.iter().copied().collect();
243        assert_eq!(unique.len(), ids.len(), "eval IDs must never collide");
244    }
245}
wafrift_evolution/search/tabu.rs

wafrift_evolution/search/
tabu.rs
