forge_core/algo/
mod.rs

1//! Optimization algorithms.
2//!
3//! Each algorithm is a small `Config` struct plus a runner that takes a
4//! [`Problem`] and a [`Termination`] and returns a [`Report`]. All of them
5//! minimize, count objective evaluations as the budget unit, reject non-finite
6//! candidates, and are deterministic for a given seed.
7//!
8//! - [`Dds`] — Dynamically Dimensioned Search (Tolson & Shoemaker 2007).
9//! - [`Sce`] — Shuffled Complex Evolution, SCE-UA (Duan et al. 1992).
10//! - [`De`] — Differential Evolution (Storn & Price 1997).
11//! - [`LShade`] — Success-History adaptive DE + LPSR (Tanabe & Fukunaga 2014).
12//! - [`LSrtde`] — Success-Rate adaptive DE, CEC 2024 winner (Stanovov & Semenkin).
13//! - [`Pso`] — Particle Swarm Optimization (Kennedy & Eberhart 1995).
14//! - [`CmaEs`] — Covariance Matrix Adaptation ES (Hansen & Ostermeier 2001).
15//! - [`NsgaII`] — multi-objective NSGA-II (Deb et al. 2002).
16//! - [`NsgaIII`] — reference-point many-objective NSGA-III (Deb & Jain 2014).
17//! - [`SmsEmoa`] — hypervolume-indicator MOEA for 2-3 objectives (Beume et al. 2007).
18//! - [`Sa`] — Simulated Annealing for combinatorial problems (via [`Anneal`]).
19//! - [`ParallelTempering`] — replica-exchange annealing (via [`Anneal`]).
20//! - [`Glue`] — Generalized Likelihood Uncertainty Estimation (Beven & Binley 1992).
21//!
22//! [`Problem`]: crate::problem::Problem
23//! [`Termination`]: crate::termination::Termination
24//! [`Report`]: crate::solution::Report
25//! [`Anneal`]: sa::Anneal
26
27pub mod cmaes;
28pub mod dds;
29pub mod de;
30pub mod epsilon_lshade;
31pub mod glue;
32pub mod lshade;
33pub mod lsrtde;
34pub mod moead;
35pub mod nsga2;
36pub mod nsga3;
37pub mod padds;
38pub mod parallel;
39pub mod pso;
40pub mod pt;
41pub mod sa;
42pub mod sce;
43pub mod sms_emoa;
44
45pub use cmaes::{CmaEs, Restart, RestartCmaEs};
46pub use dds::Dds;
47pub use de::De;
48pub use epsilon_lshade::EpsilonLShade;
49pub use glue::{Behavioral, Glue, GlueResult, GlueSample};
50pub use lshade::LShade;
51pub use lsrtde::LSrtde;
52pub use moead::Moead;
53pub use nsga2::NsgaII;
54pub use nsga3::NsgaIII;
55pub use padds::{Padds, PaddsSelection};
56pub use parallel::ensemble;
57pub use pso::Pso;
58pub use pt::{ParallelTempering, TemperingResult};
59pub use sa::{Anneal, Sa, SaResult, Schedule};
60pub use sce::Sce;
61pub use sms_emoa::SmsEmoa;
62
63use crate::problem::{Bound, Problem};
64use crate::rng::Rng;
65use crate::solution::{Report, Solution, StopReason};
66use crate::termination::Termination;
67
68/// The uniform interface every optimizer implements: run on a [`Problem`]
69/// under a [`Termination`], and produce a copy of itself with a different RNG
70/// seed (the hook ensembles use to give each island an independent stream).
71///
72/// `Sync` is a supertrait so optimizers can be shared across island workers.
73pub trait Optimizer: Sync {
74    /// Minimizes `problem` within its bounds under `term`.
75    fn optimize(&self, problem: &dyn Problem, term: &Termination) -> Report;
76
77    /// Returns the same configuration with its RNG seed replaced.
78    fn with_seed(&self, seed: u64) -> Self
79    where
80        Self: Sized;
81}
82
83/// A configured algorithm, for code that selects one at runtime (mirrors the
84/// CLI / client use where the optimizer is chosen by a flag).
85///
86/// Marked `#[non_exhaustive]`: new algorithms are added over time, so matches
87/// need a wildcard arm and adding a variant is not a breaking change.
88#[derive(Debug, Clone, Copy)]
89#[non_exhaustive]
90pub enum Algorithm {
91    /// Dynamically Dimensioned Search (Tolson & Shoemaker 2007).
92    Dds(Dds),
93    /// Shuffled Complex Evolution, SCE-UA (Duan et al. 1992).
94    Sce(Sce),
95    /// Differential Evolution `rand/1/bin` (Storn & Price 1997).
96    De(De),
97    /// Success-history adaptive DE with LPSR (Tanabe & Fukunaga 2014).
98    LShade(LShade),
99    /// Success-rate adaptive DE, CEC 2024 winner (Stanovov & Semenkin 2024).
100    LSrtde(LSrtde),
101    /// Particle Swarm Optimization (Kennedy & Eberhart 1995).
102    Pso(Pso),
103    /// Covariance Matrix Adaptation ES (Hansen & Ostermeier 2001).
104    CmaEs(CmaEs),
105    /// CMA-ES with IPOP/BIPOP restarts (Auger & Hansen 2005; Hansen 2009).
106    RestartCmaEs(RestartCmaEs),
107}
108
109impl Optimizer for Algorithm {
110    /// Runs the selected algorithm.
111    fn optimize(&self, problem: &dyn Problem, term: &Termination) -> Report {
112        match self {
113            Algorithm::Dds(c) => c.optimize(problem, term),
114            Algorithm::Sce(c) => c.optimize(problem, term),
115            Algorithm::De(c) => c.optimize(problem, term),
116            Algorithm::LShade(c) => c.optimize(problem, term),
117            Algorithm::LSrtde(c) => c.optimize(problem, term),
118            Algorithm::Pso(c) => c.optimize(problem, term),
119            Algorithm::CmaEs(c) => c.optimize(problem, term),
120            Algorithm::RestartCmaEs(c) => c.optimize(problem, term),
121        }
122    }
123
124    fn with_seed(&self, seed: u64) -> Self {
125        match self {
126            Algorithm::Dds(c) => Algorithm::Dds(c.with_seed(seed)),
127            Algorithm::Sce(c) => Algorithm::Sce(c.with_seed(seed)),
128            Algorithm::De(c) => Algorithm::De(c.with_seed(seed)),
129            Algorithm::LShade(c) => Algorithm::LShade(c.with_seed(seed)),
130            Algorithm::LSrtde(c) => Algorithm::LSrtde(c.with_seed(seed)),
131            Algorithm::Pso(c) => Algorithm::Pso(c.with_seed(seed)),
132            Algorithm::CmaEs(c) => Algorithm::CmaEs(c.with_seed(seed)),
133            Algorithm::RestartCmaEs(c) => Algorithm::RestartCmaEs(c.with_seed(seed)),
134        }
135    }
136}
137
138/// Draws a uniform random point inside the bounds.
139pub(crate) fn sample(bounds: &[Bound], rng: &mut Rng) -> Vec<f64> {
140    bounds
141        .iter()
142        .map(|&(lo, hi)| rng.uniform_in(lo, hi))
143        .collect()
144}
145
146/// Clamps `x` into `[lo, hi]`.
147#[inline]
148pub(crate) fn clamp(x: f64, lo: f64, hi: f64) -> f64 {
149    x.max(lo).min(hi)
150}
151
152/// A budget-aware objective wrapper: counts evaluations and tracks the running
153/// best, so every algorithm shares one consistent accounting and stop policy.
154pub(crate) struct Evaluator<'a> {
155    problem: &'a dyn Problem,
156    term: &'a Termination,
157    pub evaluations: usize,
158    pub best: Solution,
159}
160
161impl<'a> Evaluator<'a> {
162    /// Starts accounting with an already-evaluated initial solution.
163    pub fn new(problem: &'a dyn Problem, term: &'a Termination, first: Solution) -> Self {
164        Evaluator {
165            problem,
166            term,
167            evaluations: 1,
168            best: first,
169        }
170    }
171
172    /// Evaluates `x`, counts it, and updates the best when it is at least as
173    /// good (ties are accepted, matching the DDS/SCE-UA papers, so greedy
174    /// searches may drift along plateaus; a non-finite value never wins).
175    /// Returns the objective value.
176    pub fn eval(&mut self, x: &[f64]) -> f64 {
177        let v = self.problem.objective(x);
178        self.evaluations += 1;
179        if v.is_finite() && v <= self.best.value {
180            self.best = Solution {
181                x: x.to_vec(),
182                value: v,
183            };
184        }
185        v
186    }
187
188    /// True once the budget is spent or the target is met.
189    #[inline]
190    pub fn done(&self) -> bool {
191        self.term
192            .reason(self.evaluations, self.best.value)
193            .is_some()
194    }
195
196    /// Builds the final report.
197    pub fn finish(self) -> Report {
198        let stop = self
199            .term
200            .reason(self.evaluations, self.best.value)
201            .unwrap_or(StopReason::BudgetExhausted);
202        Report {
203            solution: self.best,
204            stop,
205            evaluations: self.evaluations,
206        }
207    }
208}
forge_core/algo/mod.rs

forge_core/algo/
mod.rs
