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                    self.best = self.current.clone();
93                }
94            }
95        }
96        self.generation += 1;
97    }
98
99    fn should_terminate(&self, stats: &SearchStats, budget: &Budget) -> bool {
100        stats.evaluations >= budget.max_requests
101            || stats.generation >= budget.max_generations
102            || stats.stagnation_counter >= budget.stagnation_limit
103    }
104
105    fn best(&self) -> Option<&Chromosome> {
106        Some(&self.best)
107    }
108
109    fn checkpoint(&self) -> Result<Vec<u8>, EvolutionError> {
110        serde_json::to_vec(self).map_err(|e| EvolutionError::SerializationFailed(e.to_string()))
111    }
112
113    fn restore(&mut self, bytes: &[u8]) -> Result<(), EvolutionError> {
114        *self = serde_json::from_slice(bytes)
115            .map_err(|e| EvolutionError::DeserializationFailed(e.to_string()))?;
116        Ok(())
117    }
118}
119
120fn baseline(gene_pool: &GenePool) -> Chromosome {
121    let genes = gene_pool
122        .gene_names()
123        .into_iter()
124        .map(|name| (name.to_string(), String::from("None")))
125        .collect();
126    Chromosome::new(genes)
127}
128
129#[cfg(test)]
130mod tests {
131    use super::*;
132    use rand::SeedableRng;
133
134    #[test]
135    fn non_finite_verdict_fitness_does_not_poison_acceptance() {
136        let mut alg = HillClimbing::new();
137        let pool = GenePool::default_wafrift();
138        let mut rng = StdRng::seed_from_u64(7);
139        alg.initialize(vec![Chromosome::new(vec![])], &pool, &mut rng);
140
141        alg.submit_evaluations(vec![(
142            1,
143            OracleVerdict {
144                passed: false,
145                status_delta: 0,
146                body_delta: 0,
147                latency_ms: 0,
148                confidence: f64::NAN,
149                triggered_rules: 1,
150            },
151        )]);
152        let best_after_nan = comparable_fitness(alg.best().expect("best must exist").fitness);
153
154        alg.submit_evaluations(vec![(2, OracleVerdict::from_bool(true))]);
155        let best_after_valid = comparable_fitness(alg.best().expect("best must exist").fitness);
156        assert!(best_after_valid > best_after_nan);
157    }
158}
wafrift_evolution/search/hill_climb.rs

wafrift_evolution/search/
hill_climb.rs
