Skip to main content

qualia_core_db/solvers/optimization/
metaheuristics.rs

1//! General-dimension metaheuristic optimizers (CI-SKM ch 4/6) — global / non-convex
2//! search beyond the fixed-`[f64;4]` local solvers in this category. Generic local
3//! search + simulated annealing work over **any** state (continuous vectors or
4//! combinatorial structures via a neighbour closure — the engine ontology alignment
5//! consumes), plus a continuous population optimizer (Artificial Bee Colony).
6//!
7//! All minimize the objective. Kernel-class `Divergent` (branch-heavy search) with
8//! the CPU path always present (§13). Deterministic given the seed.
9
10/// Deterministic RNG (LCG + Box-Muller) so searches are reproducible.
11pub struct Rng(pub u64);
12impl Rng {
13    /// `Rng::unit`.
14    pub fn unit(&mut self) -> f64 {
15        self.0 = self
16            .0
17            .wrapping_mul(6364136223846793005)
18            .wrapping_add(1442695040888963407);
19        ((self.0 >> 11) as f64) / ((1u64 << 53) as f64)
20    }
21    /// `true` when below the bound.
22    pub fn below(&mut self, b: usize) -> usize {
23        (self.unit() * b as f64) as usize % b.max(1)
24    }
25    /// Gaussian step.
26    pub fn gaussian(&mut self) -> f64 {
27        let u1 = self.unit().max(1e-12);
28        let u2 = self.unit();
29        (-2.0 * u1.ln()).sqrt() * (std::f64::consts::TAU * u2).cos()
30    }
31}
32
33/// Generic hill-climbing: from `initial`, repeatedly move to the best improving
34/// neighbour until none improves (a local minimum) or `max_iter` is reached.
35/// `neighbors` enumerates candidate moves; `objective` is minimized.
36pub fn hill_climbing<S, N, O>(initial: S, neighbors: N, objective: O, max_iter: usize) -> (S, f64)
37where
38    S: Clone,
39    N: Fn(&S) -> Vec<S>,
40    O: Fn(&S) -> f64,
41{
42    let mut current = initial;
43    let mut current_val = objective(&current);
44    for _ in 0..max_iter {
45        let mut best: Option<(S, f64)> = None;
46        for cand in neighbors(&current) {
47            let v = objective(&cand);
48            if v < current_val && best.as_ref().map(|(_, bv)| v < *bv).unwrap_or(true) {
49                best = Some((cand, v));
50            }
51        }
52        match best {
53            Some((s, v)) => {
54                current = s;
55                current_val = v;
56            }
57            None => break, // local optimum
58        }
59    }
60    (current, current_val)
61}
62
63/// Generic simulated annealing: accept worsening moves with probability
64/// `exp(−Δ/T)`, cooling `T ← cooling·T` each step, to escape local minima.
65/// `neighbor` proposes a single random move.
66pub fn simulated_annealing<S, NB, O>(
67    initial: S,
68    neighbor: NB,
69    objective: O,
70    t0: f64,
71    cooling: f64,
72    max_iter: usize,
73    seed: u64,
74) -> (S, f64)
75where
76    S: Clone,
77    NB: Fn(&S, &mut Rng) -> S,
78    O: Fn(&S) -> f64,
79{
80    let mut rng = Rng(seed ^ 0x9E3779B97F4A7C15);
81    let mut current = initial;
82    let mut current_val = objective(&current);
83    let mut best = current.clone();
84    let mut best_val = current_val;
85    let mut t = t0.max(1e-12);
86    for _ in 0..max_iter {
87        let cand = neighbor(&current, &mut rng);
88        let v = objective(&cand);
89        let delta = v - current_val;
90        if delta < 0.0 || rng.unit() < (-delta / t).exp() {
91            current = cand;
92            current_val = v;
93            if current_val < best_val {
94                best = current.clone();
95                best_val = current_val;
96            }
97        }
98        t *= cooling;
99    }
100    (best, best_val)
101}
102
103/// Artificial Bee Colony (continuous): a swarm explores a box `[lower, upper]^d`,
104/// exploiting good food sources and scouting new ones. Minimizes `objective`.
105pub fn artificial_bee_colony<O>(
106    objective: O,
107    lower: &[f64],
108    upper: &[f64],
109    n_bees: usize,
110    max_iter: usize,
111    seed: u64,
112) -> Option<(Vec<f64>, f64)>
113where
114    O: Fn(&[f64]) -> f64,
115{
116    let d = lower.len();
117    if d == 0 || upper.len() != d || n_bees < 2 {
118        return None;
119    }
120    let mut rng = Rng(seed ^ 0xD1B54A32D192ED03);
121    let sample = |rng: &mut Rng| -> Vec<f64> {
122        (0..d)
123            .map(|j| lower[j] + rng.unit() * (upper[j] - lower[j]))
124            .collect()
125    };
126    let mut foods: Vec<Vec<f64>> = (0..n_bees).map(|_| sample(&mut rng)).collect();
127    let mut vals: Vec<f64> = foods.iter().map(|f| objective(f)).collect();
128    let mut trials = vec![0usize; n_bees];
129    let limit = (n_bees * d).max(20);
130
131    let mut best = foods[0].clone();
132    let mut best_val = vals[0];
133    for (i, &v) in vals.iter().enumerate() {
134        if v < best_val {
135            best_val = v;
136            best = foods[i].clone();
137        }
138    }
139
140    for _ in 0..max_iter {
141        // Employed + onlooker phase: perturb one coordinate toward a partner.
142        for i in 0..n_bees {
143            let k = {
144                let mut k = rng.below(n_bees);
145                if k == i {
146                    k = (k + 1) % n_bees;
147                }
148                k
149            };
150            let j = rng.below(d);
151            let phi = 2.0 * rng.unit() - 1.0;
152            let mut cand = foods[i].clone();
153            cand[j] = (cand[j] + phi * (cand[j] - foods[k][j])).clamp(lower[j], upper[j]);
154            let cv = objective(&cand);
155            if cv < vals[i] {
156                foods[i] = cand;
157                vals[i] = cv;
158                trials[i] = 0;
159                if cv < best_val {
160                    best_val = cv;
161                    best = foods[i].clone();
162                }
163            } else {
164                trials[i] += 1;
165            }
166        }
167        // Scout phase: abandon exhausted sources.
168        for i in 0..n_bees {
169            if trials[i] > limit {
170                foods[i] = sample(&mut rng);
171                vals[i] = objective(&foods[i]);
172                trials[i] = 0;
173                if vals[i] < best_val {
174                    best_val = vals[i];
175                    best = foods[i].clone();
176                }
177            }
178        }
179    }
180    Some((best, best_val))
181}
182
183#[cfg(test)]
184mod tests {
185    use super::*;
186
187    #[test]
188    fn abc_minimizes_the_sphere() {
189        // f(x) = Σ x² has its global minimum 0 at the origin.
190        let f = |x: &[f64]| x.iter().map(|v| v * v).sum::<f64>();
191        let (x, val) =
192            artificial_bee_colony(f, &[-5.0, -5.0, -5.0], &[5.0, 5.0, 5.0], 30, 300, 1).unwrap();
193        assert!(val < 1e-2, "ABC sphere min {val}");
194        assert!(x.iter().all(|&xi| xi.abs() < 0.2));
195    }
196
197    #[test]
198    fn sa_escapes_a_local_minimum() {
199        // A 1-D double well with a *modest* barrier (×0.1 so the peak at x=0 is
200        // ~1.6, crossable by annealing): global min near x=2, local near x=-2.
201        let f = |s: &Vec<f64>| {
202            let x = s[0];
203            0.1 * (x * x - 4.0).powi(2) - 0.5 * x // right well (x≈2) is global
204        };
205        let neighbor = |s: &Vec<f64>, rng: &mut Rng| vec![s[0] + 0.5 * rng.gaussian()];
206        let (best, _) = simulated_annealing(vec![-2.0], neighbor, f, 5.0, 0.997, 8000, 3);
207        assert!(
208            best[0] > 0.0,
209            "SA should find the right well, got {}",
210            best[0]
211        );
212    }
213
214    #[test]
215    fn hill_climbing_reaches_a_discrete_optimum() {
216        // Combinatorial: maximize the number of 1s in a bit-vector (minimize its
217        // negative) by single-bit flips — proves the generic combinatorial path.
218        let objective = |s: &Vec<bool>| -(s.iter().filter(|&&b| b).count() as f64);
219        let neighbors = |s: &Vec<bool>| {
220            (0..s.len())
221                .map(|i| {
222                    let mut c = s.clone();
223                    c[i] = !c[i];
224                    c
225                })
226                .collect()
227        };
228        let (best, val) = hill_climbing(vec![false; 8], neighbors, objective, 100);
229        assert!(best.iter().all(|&b| b), "should turn on all bits");
230        assert_eq!(val, -8.0);
231    }
232
233    #[test]
234    fn guards() {
235        assert!(artificial_bee_colony(|_| 0.0, &[], &[], 10, 10, 0).is_none());
236    }
237}