wafrift_evolution/search/
sim_anneal.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};
5use crate::types::{Budget, EvolutionError, OracleVerdict, SearchStats};
6use rand::rngs::StdRng;
7use serde::{Deserialize, Serialize};
8
9/// Simulated annealing search.
10///
11/// Uses a temperature schedule to occasionally accept worse candidates,
12/// helping escape local optima.
13#[derive(Debug, Clone, Serialize, Deserialize)]
14pub struct SimulatedAnnealing {
15    current: Chromosome,
16    best: Chromosome,
17    gene_pool: GenePool,
18    generation: u32,
19    eval_counter: u64,
20    temperature: f64,
21    cooling_rate: f64,
22    min_temperature: f64,
23}
24
25impl SimulatedAnnealing {
26    #[must_use]
27    pub fn new() -> Self {
28        Self {
29            current: Chromosome::new(vec![]),
30            best: Chromosome::new(vec![]),
31            gene_pool: GenePool::default_wafrift(),
32            generation: 0,
33            eval_counter: 0,
34            temperature: 1.0,
35            cooling_rate: 0.95,
36            min_temperature: 0.01,
37        }
38    }
39
40    fn neighbor(&self, rng: &mut StdRng) -> Chromosome {
41        let mut child = self.current.clone();
42        let log = mutate_with_log(&mut child, &self.gene_pool, 0.25, rng);
43        child.lineage = Lineage::mutation(&self.current, log, self.generation);
44        child
45    }
46}
47
48impl Default for SimulatedAnnealing {
49    fn default() -> Self {
50        Self::new()
51    }
52}
53
54impl SearchAlgorithm for SimulatedAnnealing {
55    fn name(&self) -> &'static str {
56        "simulated_annealing"
57    }
58
59    fn initialize(&mut self, population: Vec<Chromosome>, gene_pool: &GenePool, rng: &mut StdRng) {
60        self.gene_pool = gene_pool.clone();
61        if let Some(best) = population.iter().max_by(|a, b| {
62            a.fitness
63                .partial_cmp(&b.fitness)
64                .unwrap_or(std::cmp::Ordering::Equal)
65        }) {
66            self.current = best.clone();
67            self.best = best.clone();
68        } else {
69            self.current = random_chromosome(gene_pool, rng);
70            self.best = self.current.clone();
71        }
72    }
73
74    fn request_evaluations(&mut self, n: usize, rng: &mut StdRng) -> Vec<EvalCandidate> {
75        let mut out = Vec::with_capacity(n);
76        for _ in 0..n {
77            self.eval_counter += 1;
78            out.push(EvalCandidate {
79                id: self.eval_counter,
80                chromosome: self.neighbor(rng),
81            });
82        }
83        out
84    }
85
86    fn submit_evaluations(&mut self, results: Vec<(u64, OracleVerdict)>) {
87        for (_id, verdict) in results {
88            let mut candidate = self.current.clone();
89            candidate.record_verdict(&verdict);
90            let delta = candidate.fitness - self.current.fitness;
91            let accepted = if delta > 0.0 {
92                true
93            } else {
94                let p = (delta / self.temperature.max(1e-9)).exp();
95                // Deterministic acceptance using eval_counter as jitter source
96                let threshold = ((self.eval_counter % 1000) as f64) / 1000.0;
97                p > threshold
98            };
99            if accepted {
100                self.current = candidate;
101                if self.current.fitness > self.best.fitness {
102                    self.best = self.current.clone();
103                }
104            }
105        }
106        self.generation += 1;
107        self.temperature = (self.temperature * self.cooling_rate).max(self.min_temperature);
108    }
109
110    fn should_terminate(&self, stats: &SearchStats, budget: &Budget) -> bool {
111        stats.evaluations >= budget.max_requests
112            || stats.generation >= budget.max_generations
113            || stats.stagnation_counter >= budget.stagnation_limit
114            || self.temperature <= self.min_temperature
115    }
116
117    fn best(&self) -> Option<&Chromosome> {
118        Some(&self.best)
119    }
120
121    fn checkpoint(&self) -> Result<Vec<u8>, EvolutionError> {
122        serde_json::to_vec(self).map_err(|e| EvolutionError::SerializationFailed(e.to_string()))
123    }
124
125    fn restore(&mut self, bytes: &[u8]) -> Result<(), EvolutionError> {
126        *self = serde_json::from_slice(bytes)
127            .map_err(|e| EvolutionError::DeserializationFailed(e.to_string()))?;
128        Ok(())
129    }
130}
wafrift_evolution/search/sim_anneal.rs

wafrift_evolution/search/
sim_anneal.rs
