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 += 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 += 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            },
162        )]);
163        let best_after_nan = comparable_fitness(alg.best().expect("best must exist").fitness);
164
165        alg.submit_evaluations(vec![(2, OracleVerdict::from_bool(true))]);
166        let best_after_valid = comparable_fitness(alg.best().expect("best must exist").fitness);
167        assert!(best_after_valid > best_after_nan);
168    }
169}
wafrift_evolution/search/hill_climb.rs

wafrift_evolution/search/
hill_climb.rs
