wafrift_evolution/search/
hill_climb.rs

1use crate::evolution::crossover::mutation::mutate_with_log;
2use crate::evolution::{Chromosome, GenePool};
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};
8
9/// Simple hill-climbing search.
10///
11/// Maintains a current best and greedily moves to better neighbors.
12#[derive(Debug, Clone, Serialize, Deserialize)]
13pub struct HillClimbing {
14    current: Chromosome,
15    gene_pool: GenePool,
16    generation: u32,
17    eval_counter: u64,
18    best: Chromosome,
19}
20
21impl HillClimbing {
22    #[must_use]
23    pub fn new() -> Self {
24        Self {
25            current: Chromosome::new(vec![]),
26            gene_pool: GenePool::default_wafrift(),
27            generation: 0,
28            eval_counter: 0,
29            best: Chromosome::new(vec![]),
30        }
31    }
32
33    fn neighbor(&self, rng: &mut StdRng) -> Chromosome {
34        let mut child = self.current.clone();
35        let log = mutate_with_log(&mut child, &self.gene_pool, 0.25, rng);
36        child.lineage = Lineage::mutation(&self.current, log, self.generation);
37        child
38    }
39}
40
41impl Default for HillClimbing {
42    fn default() -> Self {
43        Self::new()
44    }
45}
46
47impl SearchAlgorithm for HillClimbing {
48    fn name(&self) -> &'static str {
49        "hill_climbing"
50    }
51
52    fn initialize(&mut self, population: Vec<Chromosome>, gene_pool: &GenePool, _rng: &mut StdRng) {
53        self.gene_pool = gene_pool.clone();
54        if let Some(best) = population
55            .iter()
56            .max_by(|a, b| fitness_cmp(a.fitness, b.fitness))
57        {
58            self.current = best.clone();
59            self.best = best.clone();
60        } else {
61            self.current = baseline(gene_pool);
62            self.best = self.current.clone();
63        }
64    }
65
66    fn request_evaluations(&mut self, n: usize, rng: &mut StdRng) -> Vec<EvalCandidate> {
67        let mut out = Vec::with_capacity(n);
68        for _ in 0..n {
69            self.eval_counter = self.eval_counter.saturating_add(1);
70            out.push(EvalCandidate {
71                id: self.eval_counter,
72                chromosome: self.neighbor(rng),
73            });
74        }
75        out
76    }
77
78    fn submit_evaluations(&mut self, results: Vec<(u64, OracleVerdict)>) {
79        for (_id, verdict) in results {
80            // Record the verdict on a clone first, then compare the
81            // resulting EMA-smoothed fitness — this keeps both sides
82            // of the comparison in the same units. The earlier
83            // approach compared raw verdict.to_fitness() against
84            // self.current.fitness (an EMA), which made the
85            // accept threshold drift higher as `current` accumulated
86            // evaluations and rejected good candidates arbitrarily.
87            let mut next = self.current.clone();
88            next.record_verdict(&verdict);
89            if comparable_fitness(next.fitness) >= comparable_fitness(self.current.fitness) {
90                self.current = next;
91                if comparable_fitness(self.current.fitness) > comparable_fitness(self.best.fitness)
92                {
93                    self.best = self.current.clone();
94                }
95            }
96        }
97        self.generation = self.generation.saturating_add(1);
98    }
99
100    fn should_terminate(&self, stats: &SearchStats, budget: &Budget) -> bool {
101        stats.evaluations >= budget.max_requests
102            || stats.generation >= budget.max_generations
103            || stats.stagnation_counter >= budget.stagnation_limit
104    }
105
106    fn best(&self) -> Option<&Chromosome> {
107        Some(&self.best)
108    }
109
110    fn checkpoint(&self) -> Result<Vec<u8>, EvolutionError> {
111        serde_json::to_vec(self).map_err(EvolutionError::SerializationFailed)
112    }
113
114    fn restore(&mut self, bytes: &[u8]) -> Result<(), EvolutionError> {
115        if bytes.len() > crate::types::MAX_CHECKPOINT_BYTES {
116            return Err(EvolutionError::OversizedData {
117                context: "hill_climb checkpoint restore".into(),
118                size: bytes.len(),
119                max: crate::types::MAX_CHECKPOINT_BYTES,
120            });
121        }
122        *self = serde_json::from_slice(bytes).map_err(EvolutionError::DeserializationFailed)?;
123        Ok(())
124    }
125
126    fn clone_box(&self) -> Box<dyn SearchAlgorithm> {
127        Box::new(self.clone())
128    }
129}
130
131fn baseline(gene_pool: &GenePool) -> Chromosome {
132    let genes = gene_pool
133        .gene_names()
134        .into_iter()
135        .map(|name| (name.to_string(), String::from("None")))
136        .collect();
137    Chromosome::new(genes)
138}
139
140#[cfg(test)]
141mod tests {
142    use super::*;
143    use rand::SeedableRng;
144
145    #[test]
146    fn non_finite_verdict_fitness_does_not_poison_acceptance() {
147        let mut alg = HillClimbing::new();
148        let pool = GenePool::default_wafrift();
149        let mut rng = StdRng::seed_from_u64(7);
150        alg.initialize(vec![Chromosome::new(vec![])], &pool, &mut rng);
151
152        alg.submit_evaluations(vec![(
153            1,
154            OracleVerdict {
155                passed: false,
156                status_delta: 0,
157                body_delta: 0,
158                latency_ms: 0,
159                confidence: f64::NAN,
160                triggered_rules: 1,
161                ..Default::default()
162            },
163        )]);
164        let best_after_nan = comparable_fitness(alg.best().expect("best must exist").fitness);
165
166        alg.submit_evaluations(vec![(2, OracleVerdict::from_bool(true))]);
167        let best_after_valid = comparable_fitness(alg.best().expect("best must exist").fitness);
168        assert!(best_after_valid > best_after_nan);
169    }
170
171    // ── Saturating-arithmetic regression tests ────────────────────────────────
172
173    /// `eval_counter` must saturate at `u64::MAX` instead of wrapping to 0.
174    #[test]
175    fn eval_counter_saturates_at_u64_max() {
176        let mut alg = HillClimbing::new();
177        let pool = GenePool::default_wafrift();
178        let mut rng = StdRng::seed_from_u64(20);
179        alg.initialize(vec![Chromosome::new(vec![])], &pool, &mut rng);
180        alg.eval_counter = u64::MAX;
181        let _ = alg.request_evaluations(1, &mut rng);
182        assert_eq!(
183            alg.eval_counter,
184            u64::MAX,
185            "eval_counter must saturate at u64::MAX, not wrap to 0"
186        );
187    }
188
189    /// `generation` must saturate at `u32::MAX` instead of wrapping to 0.
190    #[test]
191    fn generation_saturates_at_u32_max() {
192        let mut alg = HillClimbing::new();
193        let pool = GenePool::default_wafrift();
194        let mut rng = StdRng::seed_from_u64(21);
195        alg.initialize(vec![Chromosome::new(vec![])], &pool, &mut rng);
196        alg.generation = u32::MAX;
197        alg.submit_evaluations(vec![(0, OracleVerdict::from_bool(false))]);
198        assert_eq!(
199            alg.generation,
200            u32::MAX,
201            "generation must saturate at u32::MAX, not wrap to 0"
202        );
203    }
204
205    /// Over many rounds, `eval_counter`-derived IDs must be strictly increasing
206    /// (no reuse that could cause the engine's `in_flight` map to collide).
207    #[test]
208    fn eval_counter_ids_are_unique_across_generations() {
209        let mut alg = HillClimbing::new();
210        let pool = GenePool::default_wafrift();
211        let mut rng = StdRng::seed_from_u64(22);
212        alg.initialize(vec![Chromosome::new(vec![])], &pool, &mut rng);
213        let mut ids: Vec<u64> = Vec::new();
214        for _ in 0..10 {
215            let batch = alg.request_evaluations(2, &mut rng);
216            for c in &batch {
217                ids.push(c.id);
218            }
219            let verdicts: Vec<_> = batch
220                .into_iter()
221                .map(|c| (c.id, OracleVerdict::from_bool(false)))
222                .collect();
223            alg.submit_evaluations(verdicts);
224        }
225        let unique: std::collections::HashSet<_> = ids.iter().copied().collect();
226        assert_eq!(unique.len(), ids.len(), "eval IDs must never collide");
227    }
228}
wafrift_evolution/search/hill_climb.rs

wafrift_evolution/search/
hill_climb.rs
