solverforge_solver/phase/localsearch/acceptor/

simulated_annealing.rs

// Simulated annealing acceptor with true Boltzmann distribution.

use std::fmt::Debug;

use rand::rngs::SmallRng;
use rand::{RngExt, SeedableRng};
use solverforge_core::domain::PlanningSolution;
use solverforge_core::score::Score;

use super::Acceptor;
use crate::heuristic::r#move::MoveTabuSignature;

/* Simulated annealing acceptor using the Boltzmann distribution.

Accepts improving moves unconditionally. For worsening moves, accepts with
probability `exp(-delta / T)` where `delta` is the score degradation and
`T` is the current temperature.

Temperature decays geometrically each step: `T *= decay_rate`.

# Example

```
use solverforge_solver::phase::localsearch::SimulatedAnnealingAcceptor;

// High initial temperature (explores broadly), slow cooling
let acceptor = SimulatedAnnealingAcceptor::new(1.0, 0.9999);
```
*/
#[derive(Debug, Clone)]
pub struct SimulatedAnnealingAcceptor {
    // Initial temperature.
    starting_temperature: f64,
    // Current temperature.
    current_temperature: f64,
    // Temperature decay rate per step.
    decay_rate: f64,
    // High-quality RNG for acceptance decisions.
    rng: SmallRng,
    // Number of score levels, cached after phase_started.
    level_count: usize,
}

impl SimulatedAnnealingAcceptor {
    /// Creates a new simulated annealing acceptor.
    ///
    /// # Arguments
    /// * `starting_temperature` - Initial temperature (higher = more exploration).
    ///   Calibrate to ~20% of the initial hard score magnitude for best results.
    /// * `decay_rate` - Multiplicative decay per step (e.g., 0.9999 for 30s runs
    ///   at ~10k steps/s gives final T ≈ 0.05 * starting T).
    pub fn new(starting_temperature: f64, decay_rate: f64) -> Self {
        Self {
            starting_temperature,
            current_temperature: starting_temperature,
            decay_rate,
            rng: SmallRng::from_rng(&mut rand::rng()),
            level_count: 0,
        }
    }

    pub fn with_seed(starting_temperature: f64, decay_rate: f64, seed: u64) -> Self {
        Self {
            starting_temperature,
            current_temperature: starting_temperature,
            decay_rate,
            rng: SmallRng::seed_from_u64(seed),
            level_count: 0,
        }
    }

    /// Auto-calibrates starting temperature from the initial score.
    ///
    /// Sets temperature to 20% of the absolute initial score magnitude,
    /// ensuring ~80% acceptance probability for moves with delta = |initial_score|.
    pub fn auto_calibrate(decay_rate: f64) -> Self {
        Self {
            starting_temperature: 0.0, // Will be set in phase_started
            current_temperature: 0.0,
            decay_rate,
            rng: SmallRng::from_rng(&mut rand::rng()),
            level_count: 0,
        }
    }

    pub(crate) fn auto_calibrate_with_seed(decay_rate: f64, seed: u64) -> Self {
        Self {
            starting_temperature: 0.0, // Will be set in phase_started
            current_temperature: 0.0,
            decay_rate,
            rng: SmallRng::seed_from_u64(seed),
            level_count: 0,
        }
    }
}

impl Default for SimulatedAnnealingAcceptor {
    fn default() -> Self {
        // Auto-calibrate with a decay rate tuned for ~300k steps in 30s.
        // At 300k steps, decay_rate^300000 ≈ 0.01 when decay_rate ≈ 0.999985.
        Self::auto_calibrate(0.999985)
    }
}

/* Converts a multi-level score difference to a single scalar for SA.

Hard levels are weighted exponentially more than soft levels so that
hard constraint improvements always dominate the acceptance probability.

NOTE: This is only used by `auto_calibrate` during `phase_started`.
The hot-path `is_accepted` uses `Score::to_scalar()` directly (zero alloc).
*/
fn score_delta_to_scalar(levels: &[i64]) -> f64 {
    if levels.is_empty() {
        return 0.0;
    }
    if levels.len() == 1 {
        return levels[0] as f64;
    }
    let n = levels.len();
    let mut scalar = 0.0f64;
    for (i, &level) in levels.iter().enumerate() {
        let weight = 10.0f64.powi(6 * (n - 1 - i) as i32);
        scalar += level as f64 * weight;
    }
    scalar
}

impl<S: PlanningSolution> Acceptor<S> for SimulatedAnnealingAcceptor
where
    S::Score: Score,
{
    fn is_accepted(
        &mut self,
        last_step_score: &S::Score,
        move_score: &S::Score,
        _move_signature: Option<&MoveTabuSignature>,
    ) -> bool {
        // Always accept improving or equal moves
        if *move_score >= *last_step_score {
            return true;
        }

        if self.current_temperature <= 0.0 {
            return false;
        }

        // Compute score difference: move_score - last_step_score (negative for worsening).
        // Uses Score::to_scalar() directly — no Vec allocation.
        let delta = move_score.to_scalar() - last_step_score.to_scalar();

        // delta is negative (worsening move). Acceptance probability = exp(delta / T).
        let probability = (delta / self.current_temperature).exp();
        let roll: f64 = self.rng.random::<f64>();

        roll < probability
    }

    fn phase_started(&mut self, initial_score: &S::Score) {
        self.level_count = S::Score::levels_count();

        // Auto-calibrate temperature if it was set to 0 (from auto_calibrate())
        if self.starting_temperature == 0.0 {
            let levels = initial_score.to_level_numbers();
            let magnitude = score_delta_to_scalar(&levels).abs();
            /* Set to 2% of score magnitude. For HardSoftScore, hard levels are
            weighted by 10^6, so this gives enough room to accept occasional
            hard-worsening moves at the start while cooling to pure hill-climbing.
            */
            self.starting_temperature = if magnitude > 0.0 {
                magnitude * 0.02
            } else {
                1.0
            };
        }

        self.current_temperature = self.starting_temperature;
    }

    fn step_ended(
        &mut self,
        _step_score: &S::Score,
        _accepted_move_signature: Option<&MoveTabuSignature>,
    ) {
        self.current_temperature *= self.decay_rate;
    }
}

#[cfg(test)]
mod tests;