use std::num::NonZeroU32;
use crate::rng::SeededRng;
use crate::error::GprError;
use crate::objective::Objective;
use crate::param::Interval;
use crate::rng::{open_unit, seeded_rng};
use super::adapter::keep_better;
use super::{OptResult, Optimizer, Restarts};
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
#[non_exhaustive]
pub enum BoundaryPolicy {
#[default]
Clamp,
Periodic,
}
#[derive(Clone, Debug, PartialEq)]
pub struct FastSimulatedAnnealing {
max_iterations: u64,
restarts: Option<Restarts>,
initial_temperature: f64,
cooling_rate: f64,
seed: u64,
boundary: BoundaryPolicy,
}
impl Default for FastSimulatedAnnealing {
fn default() -> Self {
Self {
max_iterations: 100,
restarts: None,
initial_temperature: 1.0,
cooling_rate: 3.0,
seed: 0,
boundary: BoundaryPolicy::Clamp,
}
}
}
impl FastSimulatedAnnealing {
pub fn new() -> Self {
Self::default()
}
pub fn with_max_iterations(mut self, max_iterations: u64) -> Self {
self.max_iterations = max_iterations;
self
}
pub fn with_restarts(mut self, n: NonZeroU32, seed: u64) -> Self {
self.restarts = Some(Restarts { n, seed });
self
}
pub fn with_initial_temperature(mut self, temperature: f64) -> Result<Self, GprError> {
if !temperature.is_finite() || temperature <= 0.0 {
return Err(GprError::InvalidConfig {
reason: "FSA initial temperature must be finite and > 0".to_owned(),
});
}
self.initial_temperature = temperature;
Ok(self)
}
pub fn with_cooling_rate(mut self, cooling_rate: f64) -> Result<Self, GprError> {
if !cooling_rate.is_finite() || cooling_rate <= 0.0 {
return Err(GprError::InvalidConfig {
reason: "FSA cooling rate must be finite and > 0".to_owned(),
});
}
self.cooling_rate = cooling_rate;
Ok(self)
}
pub fn with_seed(mut self, seed: u64) -> Self {
self.seed = seed;
self
}
pub fn with_boundary(mut self, boundary: BoundaryPolicy) -> Self {
self.boundary = boundary;
self
}
}
impl<P: Objective> Optimizer<P> for FastSimulatedAnnealing {
const USES_CHANGE_INDICES: bool = true;
fn minimize(&self, objective: &mut P, init: &[f64]) -> Result<OptResult, GprError> {
if objective.num_params() == 0 {
return Err(GprError::LengthMismatch {
reason: "FSA requires at least one parameter".to_owned(),
});
}
super::minimize_with_restarts(
objective,
init,
self.restarts,
|init, _| Ok(init.to_vec()),
|intervals, rng| Ok(sample_in_param_space(intervals, rng, self.boundary)),
|objective, intervals, start, restart, best| {
let seed = match restart {
None => self.seed,
Some(restart) => restart_seed(self.seed, restart),
};
keep_better(best, anneal(self, objective, start, intervals, seed)?);
Ok(())
},
)
}
}
fn restart_seed(seed: u64, restart: u64) -> u64 {
let mut z = seed ^ restart.wrapping_mul(0x9E37_79B9_7F4A_7C15);
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^ (z >> 31)
}
fn anneal<P: Objective>(
fsa: &FastSimulatedAnnealing,
objective: &mut P,
init: &[f64],
intervals: &[Interval],
seed: u64,
) -> Result<OptResult, GprError> {
let n = init.len();
let bounds: Vec<(f64, f64)> = intervals.iter().copied().map(param_bounds).collect();
let mut current = init.to_vec();
for (slot, &(lo, hi)) in current.iter_mut().zip(bounds.iter()) {
*slot = apply_boundary(*slot, lo, hi, fsa.boundary);
}
let mut current_energy = objective.value(¤t)?;
if !current_energy.is_finite() {
return Err(GprError::InvalidConfig {
reason: "FSA initial objective value must be finite".to_owned(),
});
}
let mut best = current.clone();
let mut best_energy = current_energy;
let mut proposed = current.clone();
let mut rng = seeded_rng(seed);
let dim = n as f64;
let mut reverted: Option<usize> = None;
for iteration in 0..fsa.max_iterations {
let temperature = fsa.temperature(iteration, dim);
for i in 0..n {
proposed.copy_from_slice(¤t);
let (lo, hi) = bounds[i];
let step = cauchy_step(&mut rng, temperature) * (hi - lo);
proposed[i] = apply_boundary(current[i] + step, lo, hi, fsa.boundary);
let changes = match reverted {
Some(r) if r != i => [r, i],
_ => [i, i],
};
let changed = if changes[0] == changes[1] {
&changes[..1]
} else {
&changes[..]
};
let proposed_energy = match objective.value_at_changes(&proposed, changed) {
Ok(value) => value,
Err(
GprError::CholeskyFailed { .. }
| GprError::NonFiniteKernelValue
| GprError::NonPositiveDefiniteMatrix,
) => f64::INFINITY,
Err(err) => return Err(err),
};
reverted = Some(i);
if !proposed_energy.is_finite() {
continue;
}
if metropolis_accept(&mut rng, proposed_energy - current_energy, temperature) {
reverted = None;
current.copy_from_slice(&proposed);
current_energy = proposed_energy;
if current_energy < best_energy {
best.copy_from_slice(¤t);
best_energy = current_energy;
}
}
}
}
Ok(OptResult {
params: best,
value: best_energy,
iterations: fsa.max_iterations,
})
}
impl FastSimulatedAnnealing {
fn temperature(&self, iteration: u64, dim: f64) -> f64 {
let k = iteration as f64;
(self.initial_temperature * (-self.cooling_rate * k.powf(1.0 / dim)).exp()).max(1e-12)
}
}
fn param_bounds(interval: Interval) -> (f64, f64) {
if interval.lo() > 0.0 {
(interval.lo().ln(), interval.hi().ln())
} else {
(interval.lo(), interval.hi())
}
}
fn apply_boundary(x: f64, lo: f64, hi: f64, policy: BoundaryPolicy) -> f64 {
let width = hi - lo;
debug_assert!(width > 0.0);
let eps = (width * f64::EPSILON).max(f64::MIN_POSITIVE);
let lo_in = lo + eps;
let hi_in = hi - eps;
match policy {
BoundaryPolicy::Clamp => x.clamp(lo_in, hi_in),
BoundaryPolicy::Periodic => {
let mut t = (x - lo) % width;
if t < 0.0 {
t += width;
}
(lo + t).clamp(lo_in, hi_in)
}
}
}
fn cauchy_step(rng: &mut SeededRng, temperature: f64) -> f64 {
let u = open_unit(rng);
let sign = if u >= 0.5 { 1.0 } else { -1.0 };
let t = temperature.max(1e-12);
sign * t * ((1.0 + 1.0 / t).powf((2.0 * u - 1.0).abs()) - 1.0)
}
fn metropolis_accept(rng: &mut SeededRng, delta: f64, temperature: f64) -> bool {
if delta <= 0.0 {
true
} else {
let t = temperature.max(1e-12);
open_unit(rng) < (-delta / t).exp()
}
}
fn sample_in_param_space(
intervals: &[Interval],
rng: &mut SeededRng,
boundary: BoundaryPolicy,
) -> Vec<f64> {
intervals
.iter()
.copied()
.map(|interval| {
let (lo, hi) = param_bounds(interval);
apply_boundary(lo + open_unit(rng) * (hi - lo), lo, hi, boundary)
})
.collect()
}
#[cfg(test)]
mod tests {
use super::{BoundaryPolicy, FastSimulatedAnnealing, apply_boundary, metropolis_accept};
use crate::error::GprError;
use crate::gpr::Gpr;
use crate::kernel::{KernelSpec, RbfKernel};
use crate::likelihood::GaussianLikelihood;
use crate::objective::Objective;
use crate::optimizer::{Fixed, Optimizer};
use crate::param::Interval;
use crate::rng::seeded_rng;
struct Rosenbrock;
impl Objective for Rosenbrock {
fn fill_intervals(&self, out: &mut [Interval]) -> Result<(), GprError> {
if out.len() != 2 {
return Err(GprError::ShapeMismatch {
reason: "Rosenbrock is 2-D".to_owned(),
});
}
let interval = Interval::new(-5.0, 5.0).expect("finite");
out[0] = interval;
out[1] = interval;
Ok(())
}
fn num_params(&self) -> usize {
2
}
fn value(&mut self, params: &[f64]) -> Result<f64, GprError> {
if params.len() != 2 {
return Err(GprError::ShapeMismatch {
reason: "Rosenbrock is 2-D".to_owned(),
});
}
let a = 1.0 - params[0];
let b = params[1] - params[0] * params[0];
Ok(a * a + 100.0 * b * b)
}
}
struct Bowl1d {
target: f64,
}
impl Objective for Bowl1d {
fn fill_intervals(&self, out: &mut [Interval]) -> Result<(), GprError> {
if out.len() != 1 {
return Err(GprError::ShapeMismatch {
reason: "bowl is 1-D".to_owned(),
});
}
out[0] = Interval::new(-2.0, 2.0).expect("finite");
Ok(())
}
fn num_params(&self) -> usize {
1
}
fn value(&mut self, params: &[f64]) -> Result<f64, GprError> {
if params.len() != 1 {
return Err(GprError::ShapeMismatch {
reason: "bowl is 1-D".to_owned(),
});
}
let d = params[0] - self.target;
Ok(d * d)
}
}
#[test]
fn metropolis_accepts_improvement_and_rejects_huge_increase() {
let mut rng = seeded_rng(1);
assert!(metropolis_accept(&mut rng, -0.25, 1.0));
assert!(!metropolis_accept(&mut rng, 1.0e9, 1.0e-12));
}
#[test]
fn clamp_stays_strictly_inside() {
let y = apply_boundary(5.0, 0.0, 1.0, BoundaryPolicy::Clamp);
assert!(y > 0.0 && y < 1.0);
assert!(y > 0.9);
let z = apply_boundary(-3.0, 0.0, 1.0, BoundaryPolicy::Clamp);
assert!(z > 0.0 && z < 1.0);
assert!(z < 0.1);
}
#[test]
fn periodic_wraps_into_open_interval() {
let y = apply_boundary(1.25, 0.0, 1.0, BoundaryPolicy::Periodic);
assert!(y > 0.0 && y < 1.0);
assert!((y - 0.25).abs() <= 1e-12);
let z = apply_boundary(-0.25, 0.0, 1.0, BoundaryPolicy::Periodic);
assert!(z > 0.0 && z < 1.0);
assert!((z - 0.75).abs() <= 1e-12);
}
#[test]
fn rosenbrock_lands_in_loose_box() {
let mut obj = Rosenbrock;
let result = FastSimulatedAnnealing::new()
.with_max_iterations(400)
.with_initial_temperature(2.0)
.expect("T")
.with_seed(1234)
.minimize(&mut obj, &[0.0, 0.0])
.expect("fsa");
assert!(
result.params[0] > -0.5
&& result.params[0] < 2.5
&& result.params[1] > -0.5
&& result.params[1] < 2.5,
"params={:?}",
result.params
);
}
#[test]
fn gpr_fit_returns_fitted_and_lowers_nlml() {
let kernel = KernelSpec::from(RbfKernel::new(4.0).expect("valid"));
let likelihood = GaussianLikelihood::new(1.0).expect("valid");
let fsa = FastSimulatedAnnealing::new().with_seed(7);
let gpr = Gpr::new(kernel, likelihood).with_optimizer(fsa);
let x = [0.0, 1.0];
let y = [0.5, -0.25];
let start = gpr
.clone()
.with_optimizer(Fixed)
.factor(&x, 2, 1, &y)
.unwrap_or_else(|(_, e)| panic!("{e}"))
.neg_log_marginal_likelihood()
.expect("start");
let fitted = gpr.fit(&x, 2, 1, &y).unwrap_or_else(|(_, e)| panic!("{e}"));
let best = fitted.neg_log_marginal_likelihood().expect("fitted nlml");
assert!(best < start, "start={start}, best={best}");
}
#[test]
fn one_d_bowl_moves_toward_target() {
let mut obj = Bowl1d { target: 0.5 };
let start = obj.value(&[-1.0]).expect("start");
let result = FastSimulatedAnnealing::new()
.with_seed(3)
.minimize(&mut obj, &[-1.0])
.expect("fsa");
assert!(result.value < start, "start={start}, best={}", result.value);
}
struct Unevaluable;
impl Objective for Unevaluable {
fn fill_intervals(&self, out: &mut [Interval]) -> Result<(), GprError> {
out[0] = Interval::new(-2.0, 2.0).expect("finite");
Ok(())
}
fn num_params(&self) -> usize {
1
}
fn value(&mut self, params: &[f64]) -> Result<f64, GprError> {
if params[0] > 0.5 {
return Err(GprError::NonPositiveDefiniteMatrix);
}
Ok(params[0] * params[0])
}
}
#[test]
fn a_proposal_that_cannot_be_evaluated_is_rejected_not_fatal() {
let result = FastSimulatedAnnealing::new()
.with_seed(3)
.minimize(&mut Unevaluable, &[0.4])
.expect("annealing survives unevaluable proposals");
assert!(result.params[0] <= 0.5);
assert!(result.value <= 0.16 + 1e-12);
}
struct FlatRecorder {
calls: Vec<(bool, Vec<f64>)>,
}
impl Objective for FlatRecorder {
fn fill_intervals(&self, out: &mut [Interval]) -> Result<(), GprError> {
out.fill(Interval::new(-5.0, 5.0).expect("finite"));
Ok(())
}
fn num_params(&self) -> usize {
2
}
fn value(&mut self, params: &[f64]) -> Result<f64, GprError> {
self.calls.push((true, params.to_vec()));
Ok(0.0)
}
fn value_at_changes(
&mut self,
params: &[f64],
_indices: &[usize],
) -> Result<f64, GprError> {
self.calls.push((false, params.to_vec()));
Ok(0.0)
}
}
#[test]
fn restarts_anneal_with_different_random_steps() {
let mut objective = FlatRecorder { calls: Vec::new() };
FastSimulatedAnnealing::new()
.with_max_iterations(20)
.with_boundary(BoundaryPolicy::Periodic)
.with_restarts(std::num::NonZeroU32::new(2).expect("2"), 5)
.minimize(&mut objective, &[0.5, -0.5])
.expect("minimize");
let width = 10.0;
let mut walks: Vec<Vec<f64>> = Vec::new();
let mut previous: Option<Vec<f64>> = None;
for (starts_walk, point) in objective.calls {
if starts_walk {
walks.push(Vec::new());
} else if let (Some(prev), Some(walk)) = (&previous, walks.last_mut()) {
for (a, b) in point.iter().zip(prev) {
let step = (a - b).rem_euclid(width);
if step > 0.0 {
walk.push(step);
}
}
}
previous = Some(point);
}
assert_eq!(walks.len(), 3, "first run and two restarts");
for (i, a) in walks.iter().enumerate() {
for b in &walks[i + 1..] {
let same = a
.iter()
.zip(b)
.filter(|(x, y)| (*x - *y).abs() < 1e-9)
.count();
assert!(
same * 2 < a.len().min(b.len()),
"two walks share {same} of {} steps",
a.len().min(b.len())
);
}
}
}
}