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};
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.iter().max_by(|a, b| {
55            a.fitness
56                .partial_cmp(&b.fitness)
57                .unwrap_or(std::cmp::Ordering::Equal)
58        }) {
59            self.current = best.clone();
60            self.best = best.clone();
61        } else {
62            self.current = baseline(gene_pool);
63            self.best = self.current.clone();
64        }
65    }
66
67    fn request_evaluations(&mut self, n: usize, rng: &mut StdRng) -> Vec<EvalCandidate> {
68        let mut out = Vec::with_capacity(n);
69        for _ in 0..n {
70            self.eval_counter += 1;
71            out.push(EvalCandidate {
72                id: self.eval_counter,
73                chromosome: self.neighbor(rng),
74            });
75        }
76        out
77    }
78
79    fn submit_evaluations(&mut self, results: Vec<(u64, OracleVerdict)>) {
80        for (_id, verdict) in results {
81            let fitness = verdict.to_fitness();
82            if fitness >= self.current.fitness {
83                let mut next = self.current.clone();
84                next.record_verdict(&verdict);
85                self.current = next;
86                if self.current.fitness > self.best.fitness {
87                    self.best = self.current.clone();
88                }
89            }
90        }
91        self.generation += 1;
92    }
93
94    fn should_terminate(&self, stats: &SearchStats, budget: &Budget) -> bool {
95        stats.evaluations >= budget.max_requests
96            || stats.generation >= budget.max_generations
97            || stats.stagnation_counter >= budget.stagnation_limit
98    }
99
100    fn best(&self) -> Option<&Chromosome> {
101        Some(&self.best)
102    }
103
104    fn checkpoint(&self) -> Result<Vec<u8>, EvolutionError> {
105        serde_json::to_vec(self).map_err(|e| EvolutionError::SerializationFailed(e.to_string()))
106    }
107
108    fn restore(&mut self, bytes: &[u8]) -> Result<(), EvolutionError> {
109        *self = serde_json::from_slice(bytes)
110            .map_err(|e| EvolutionError::DeserializationFailed(e.to_string()))?;
111        Ok(())
112    }
113}
114
115fn baseline(gene_pool: &GenePool) -> Chromosome {
116    let genes = gene_pool
117        .gene_names()
118        .into_iter()
119        .map(|name| (name.to_string(), String::from("None")))
120        .collect();
121    Chromosome::new(genes)
122}
wafrift_evolution/search/hill_climb.rs

wafrift_evolution/search/
hill_climb.rs
