metalforge 0.3.0

//! Optimization algorithms.
//!
//! Each algorithm is a small `Config` struct plus a runner that takes a
//! [`Problem`] and a [`Termination`] and returns a [`Report`]. All of them
//! minimize, count objective evaluations as the budget unit, reject non-finite
//! candidates, and are deterministic for a given seed.
//!
//! - [`Dds`] — Dynamically Dimensioned Search (Tolson & Shoemaker 2007).
//! - [`Sce`] — Shuffled Complex Evolution, SCE-UA (Duan et al. 1992).
//! - [`De`] — Differential Evolution (Storn & Price 1997).
//! - [`LShade`] — Success-History adaptive DE + LPSR (Tanabe & Fukunaga 2014).
//! - [`LSrtde`] — Success-Rate adaptive DE, CEC 2024 winner (Stanovov & Semenkin).
//! - [`Pso`] — Particle Swarm Optimization (Kennedy & Eberhart 1995).
//! - [`CmaEs`] — Covariance Matrix Adaptation ES (Hansen & Ostermeier 2001).
//! - [`NsgaII`] — multi-objective NSGA-II (Deb et al. 2002).
//! - [`NsgaIII`] — reference-point many-objective NSGA-III (Deb & Jain 2014).
//! - [`SmsEmoa`] — hypervolume-indicator MOEA for 2-3 objectives (Beume et al. 2007).
//! - [`Sa`] — Simulated Annealing for combinatorial problems (via [`Anneal`]).
//! - [`ParallelTempering`] — replica-exchange annealing (via [`Anneal`]).
//! - [`Glue`] — Generalized Likelihood Uncertainty Estimation (Beven & Binley 1992).
//!
//! [`Problem`]: crate::problem::Problem
//! [`Termination`]: crate::termination::Termination
//! [`Report`]: crate::solution::Report
//! [`Anneal`]: sa::Anneal

pub mod cmaes;
pub mod dds;
pub mod de;
pub mod epsilon_lshade;
pub mod glue;
pub mod lshade;
pub mod lsrtde;
pub mod moead;
pub mod nsga2;
pub mod nsga3;
pub mod padds;
pub mod parallel;
pub mod pso;
pub mod pt;
pub mod sa;
pub mod sce;
pub mod sms_emoa;

pub use cmaes::{CmaEs, Restart, RestartCmaEs};
pub use dds::Dds;
pub use de::De;
pub use epsilon_lshade::EpsilonLShade;
pub use glue::{Behavioral, Glue, GlueResult, GlueSample};
pub use lshade::LShade;
pub use lsrtde::LSrtde;
pub use moead::Moead;
pub use nsga2::NsgaII;
pub use nsga3::NsgaIII;
pub use padds::{Padds, PaddsSelection};
pub use parallel::ensemble;
pub use pso::Pso;
pub use pt::{ParallelTempering, TemperingResult};
pub use sa::{Anneal, Sa, SaResult, Schedule};
pub use sce::Sce;
pub use sms_emoa::SmsEmoa;

use crate::problem::{Bound, Problem};
use crate::rng::Rng;
use crate::solution::{Report, Solution, StopReason};
use crate::termination::Termination;

/// The uniform interface every optimizer implements: run on a [`Problem`]
/// under a [`Termination`], and produce a copy of itself with a different RNG
/// seed (the hook ensembles use to give each island an independent stream).
///
/// `Sync` is a supertrait so optimizers can be shared across island workers.
pub trait Optimizer: Sync {
    /// Minimizes `problem` within its bounds under `term`.
    fn optimize(&self, problem: &dyn Problem, term: &Termination) -> Report;

    /// Returns the same configuration with its RNG seed replaced.
    fn with_seed(&self, seed: u64) -> Self
    where
        Self: Sized;
}

/// A configured algorithm, for code that selects one at runtime (mirrors the
/// CLI / client use where the optimizer is chosen by a flag).
///
/// Marked `#[non_exhaustive]`: new algorithms are added over time, so matches
/// need a wildcard arm and adding a variant is not a breaking change.
#[derive(Debug, Clone, Copy)]
#[non_exhaustive]
pub enum Algorithm {
    /// Dynamically Dimensioned Search (Tolson & Shoemaker 2007).
    Dds(Dds),
    /// Shuffled Complex Evolution, SCE-UA (Duan et al. 1992).
    Sce(Sce),
    /// Differential Evolution `rand/1/bin` (Storn & Price 1997).
    De(De),
    /// Success-history adaptive DE with LPSR (Tanabe & Fukunaga 2014).
    LShade(LShade),
    /// Success-rate adaptive DE, CEC 2024 winner (Stanovov & Semenkin 2024).
    LSrtde(LSrtde),
    /// Particle Swarm Optimization (Kennedy & Eberhart 1995).
    Pso(Pso),
    /// Covariance Matrix Adaptation ES (Hansen & Ostermeier 2001).
    CmaEs(CmaEs),
    /// CMA-ES with IPOP/BIPOP restarts (Auger & Hansen 2005; Hansen 2009).
    RestartCmaEs(RestartCmaEs),
}

impl Optimizer for Algorithm {
    /// Runs the selected algorithm.
    fn optimize(&self, problem: &dyn Problem, term: &Termination) -> Report {
        match self {
            Algorithm::Dds(c) => c.optimize(problem, term),
            Algorithm::Sce(c) => c.optimize(problem, term),
            Algorithm::De(c) => c.optimize(problem, term),
            Algorithm::LShade(c) => c.optimize(problem, term),
            Algorithm::LSrtde(c) => c.optimize(problem, term),
            Algorithm::Pso(c) => c.optimize(problem, term),
            Algorithm::CmaEs(c) => c.optimize(problem, term),
            Algorithm::RestartCmaEs(c) => c.optimize(problem, term),
        }
    }

    fn with_seed(&self, seed: u64) -> Self {
        match self {
            Algorithm::Dds(c) => Algorithm::Dds(c.with_seed(seed)),
            Algorithm::Sce(c) => Algorithm::Sce(c.with_seed(seed)),
            Algorithm::De(c) => Algorithm::De(c.with_seed(seed)),
            Algorithm::LShade(c) => Algorithm::LShade(c.with_seed(seed)),
            Algorithm::LSrtde(c) => Algorithm::LSrtde(c.with_seed(seed)),
            Algorithm::Pso(c) => Algorithm::Pso(c.with_seed(seed)),
            Algorithm::CmaEs(c) => Algorithm::CmaEs(c.with_seed(seed)),
            Algorithm::RestartCmaEs(c) => Algorithm::RestartCmaEs(c.with_seed(seed)),
        }
    }
}

/// Draws a uniform random point inside the bounds.
pub(crate) fn sample(bounds: &[Bound], rng: &mut Rng) -> Vec<f64> {
    bounds
        .iter()
        .map(|&(lo, hi)| rng.uniform_in(lo, hi))
        .collect()
}

/// Clamps `x` into `[lo, hi]`.
#[inline]
pub(crate) fn clamp(x: f64, lo: f64, hi: f64) -> f64 {
    x.max(lo).min(hi)
}

/// A budget-aware objective wrapper: counts evaluations and tracks the running
/// best, so every algorithm shares one consistent accounting and stop policy.
pub(crate) struct Evaluator<'a> {
    problem: &'a dyn Problem,
    term: &'a Termination,
    pub evaluations: usize,
    pub best: Solution,
}

impl<'a> Evaluator<'a> {
    /// Starts accounting with an already-evaluated initial solution.
    pub fn new(problem: &'a dyn Problem, term: &'a Termination, first: Solution) -> Self {
        Evaluator {
            problem,
            term,
            evaluations: 1,
            best: first,
        }
    }

    /// Evaluates `x`, counts it, and updates the best when it is at least as
    /// good (ties are accepted, matching the DDS/SCE-UA papers, so greedy
    /// searches may drift along plateaus; a non-finite value never wins).
    /// Returns the objective value.
    pub fn eval(&mut self, x: &[f64]) -> f64 {
        let v = self.problem.objective(x);
        self.evaluations += 1;
        if v.is_finite() && v <= self.best.value {
            self.best = Solution {
                x: x.to_vec(),
                value: v,
            };
        }
        v
    }

    /// True once the budget is spent or the target is met.
    #[inline]
    pub fn done(&self) -> bool {
        self.term
            .reason(self.evaluations, self.best.value)
            .is_some()
    }

    /// Builds the final report.
    pub fn finish(self) -> Report {
        let stop = self
            .term
            .reason(self.evaluations, self.best.value)
            .unwrap_or(StopReason::BudgetExhausted);
        Report {
            solution: self.best,
            stop,
            evaluations: self.evaluations,
        }
    }
}