metalforge 0.1.4

//! Ensemble / island parallelism.
//!
//! [`ensemble`] runs several independent instances of an optimizer — *islands*
//! — each with a deterministically derived seed, and returns the single best
//! result. This is the robust-restart pattern: many global optimizers benefit
//! far more from a handful of independent runs than from one long run, and the
//! islands are embarrassingly parallel.
//!
//! **Determinism is preserved regardless of scheduling.** Island `i` always
//! uses seed [`mix_seed`]`(seed, i)`, and ties are broken by the lowest island
//! index, so the winner is a pure function of `(algorithm, problem, term,
//! islands, seed)` — identical whether the islands run sequentially or across
//! Rayon threads, and identical between builds with and without the `rayon`
//! feature. (v0.1 has no inter-island migration; that is a later addition.)
//!
//! With the `rayon` feature enabled the islands run on a thread pool; without
//! it they run sequentially. The API is the same either way.
//!
//! [`mix_seed`]: crate::rng::mix_seed

use super::Optimizer;
use crate::problem::Problem;
use crate::rng::mix_seed;
use crate::solution::Report;
use crate::termination::Termination;

/// Runs `islands` independent instances of `algo` on `problem` and returns the
/// best [`Report`]. Each island `i` is seeded with `mix_seed(seed, i)`, so the
/// per-island RNG seed embedded in `algo` is ignored in favor of these derived
/// seeds. `islands` is clamped to at least 1.
///
/// The `problem` must be `Sync` so islands can share it across threads.
pub fn ensemble<O: Optimizer>(
    algo: &O,
    problem: &(dyn Problem + Sync),
    term: &Termination,
    islands: usize,
    seed: u64,
) -> Report {
    let n = islands.max(1);

    let run = |id: usize| -> (usize, Report) {
        let island = algo.with_seed(mix_seed(seed, id as u64));
        (id, island.optimize(problem, term))
    };

    // Collect (id, report) in island order. Rayon's indexed collect preserves
    // order, and the tie-break below makes the result order-independent anyway.
    #[cfg(feature = "rayon")]
    let results: Vec<(usize, Report)> = {
        use rayon::prelude::*;
        (0..n).into_par_iter().map(run).collect()
    };
    #[cfg(not(feature = "rayon"))]
    let results: Vec<(usize, Report)> = (0..n).map(run).collect();

    results
        .into_iter()
        .reduce(|best, cand| {
            // Lower objective wins; equal objectives break to the lower id.
            if cand.1.best_value() < best.1.best_value()
                || (cand.1.best_value() == best.1.best_value() && cand.0 < best.0)
            {
                cand
            } else {
                best
            }
        })
        .map(|(_, report)| report)
        .expect("at least one island always runs")
}