qualia_core_db/solvers/optimization/
metaheuristics.rs1pub struct Rng(pub u64);
12impl Rng {
13 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 pub fn below(&mut self, b: usize) -> usize {
23 (self.unit() * b as f64) as usize % b.max(1)
24 }
25 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
33pub 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(¤t);
44 for _ in 0..max_iter {
45 let mut best: Option<(S, f64)> = None;
46 for cand in neighbors(¤t) {
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, }
59 }
60 (current, current_val)
61}
62
63pub 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(¤t);
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(¤t, &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
103pub 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 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 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 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 let f = |s: &Vec<f64>| {
202 let x = s[0];
203 0.1 * (x * x - 4.0).powi(2) - 0.5 * x };
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 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}