rlevo-evolution 0.3.0

//! Determinism integration test.
//!
//! On the Flex backend, running a strategy twice with the same
//! `base_seed` must produce a bit-identical fitness trajectory.
//!
//! # Why this file runs a single test
//!
//! The Burn Flex backend seeds its RNG through a process-wide
//! `Mutex<Option<FlexRng>>`. Multiple tests that race on that mutex
//! will interleave `Tensor::random` draws and destroy bit-equality. This
//! file therefore contains exactly one `#[test]` function so the cargo
//! runner cannot execute anything in parallel with it — within the
//! single test body, the two runs are strictly sequential and compare
//! byte-for-byte.

use burn::backend::Flex;
use burn::tensor::backend::{Backend, BackendTypes};
use burn::tensor::{Int, Tensor, TensorData};
use rlevo_core::bounds::Bounds;
use rlevo_core::fitness::FitnessEvaluable;
use rlevo_core::objective::ObjectiveSense;
use rlevo_core::probability::Probability;
use rlevo_core::rate::NonNegativeRate;

use rlevo_evolution::algorithms::de::{DeConfig, DifferentialEvolution};
use rlevo_evolution::algorithms::es_classical::{EsConfig, EsKind, EvolutionStrategy};
use rlevo_evolution::algorithms::ga::{
    GaConfig, GaCrossover, GaReplacement, GaSelection, GeneticAlgorithm,
};
use rlevo_evolution::algorithms::ga_binary::{BinaryGaConfig, BinaryGeneticAlgorithm};
use rlevo_evolution::algorithms::memetic::{
    CoveragePolicy, MemeticParams, MemeticWrapper, WritebackPolicy,
};
use rlevo_evolution::algorithms::metaheuristic::abc::{AbcConfig, ArtificialBeeColony};
use rlevo_evolution::algorithms::metaheuristic::aco_r::{AcoRConfig, AntColonyReal};
use rlevo_evolution::algorithms::metaheuristic::bat::{BatAlgorithm, BatConfig};
use rlevo_evolution::algorithms::metaheuristic::cuckoo::{CuckooConfig, CuckooSearch};
use rlevo_evolution::algorithms::metaheuristic::firefly::{FireflyAlgorithm, FireflyConfig};
use rlevo_evolution::algorithms::metaheuristic::gwo::{GreyWolfOptimizer, GwoConfig};
use rlevo_evolution::algorithms::metaheuristic::pso::{ParticleSwarm, PsoConfig};
use rlevo_evolution::algorithms::metaheuristic::salp::{SalpConfig, SalpSwarm};
use rlevo_evolution::algorithms::metaheuristic::woa::{WhaleOptimization, WoaConfig};
use rlevo_evolution::fitness::{BatchFitnessFn, FromFitnessEvaluable};
use rlevo_evolution::local_search::{
    HillClimbing, HillClimbingParams, SimulatedAnnealing, SimulatedAnnealingParams,
};
use rlevo_evolution::strategy::{EvolutionaryHarness, Strategy};

type B = Flex;

struct Sphere;
struct SphereFit;
impl FitnessEvaluable for SphereFit {
    type Individual = Vec<f64>;
    type Landscape = Sphere;
    fn evaluate(&self, x: &Self::Individual, _: &Self::Landscape) -> f64 {
        x.iter().map(|v| v * v).sum()
    }
}

/// Drive a strategy through `gens` generations and collect the
/// per-generation best-fitness trajectory.
fn run<S>(strategy: S, params: S::Params, seed: u64, gens: usize) -> Vec<f32>
where
    S: Strategy<B>,
    S::Params: rlevo_core::config::Validate,
    <S as Strategy<B>>::Genome: 'static,
    FromFitnessEvaluable<SphereFit, Sphere>: BatchFitnessFn<B, S::Genome>,
{
    let device = Default::default();
    let mut harness = EvolutionaryHarness::<B, _, _>::new(
        strategy,
        params,
        FromFitnessEvaluable::new(SphereFit, Sphere),
        seed,
        device,
        gens,
    )
    .expect("valid params");
    harness.reset();
    let mut trajectory = Vec::with_capacity(gens);
    loop {
        let step = harness.step(());
        trajectory.push(harness.latest_metrics().unwrap().best_fitness());
        if step.done {
            break;
        }
    }
    trajectory
}

/// `OneMax` batch fitness over a binary genome (`count_ones`, native
/// maximise). The [`BinaryGeneticAlgorithm`]'s `Tensor<B, 2, Int>` genome is
/// not covered by the real-valued [`FromFitnessEvaluable`] adapter used by the
/// generic [`run`] path, so binary-GA determinism is checked with a dedicated
/// integer fitness driven inline.
struct OneMaxBatch {
    dim: usize,
}

impl<Bk: Backend> BatchFitnessFn<Bk, Tensor<Bk, 2, Int>> for OneMaxBatch {
    fn evaluate_batch(
        &mut self,
        population: &Tensor<Bk, 2, Int>,
        device: &<Bk as BackendTypes>::Device,
    ) -> Tensor<Bk, 1> {
        let pop_size = population.dims()[0];
        let data = population
            .clone()
            .into_data()
            .into_vec::<i32>()
            .expect("genome host-read of a tensor this test just built");
        let mut fitness = Vec::with_capacity(pop_size);
        for row in 0..pop_size {
            #[allow(clippy::cast_precision_loss)]
            let ones = (0..self.dim)
                .filter(|&col| data[row * self.dim + col] != 0)
                .count() as f32;
            fitness.push(ones);
        }
        Tensor::<Bk, 1>::from_data(TensorData::new(fitness, [pop_size]), device)
    }

    fn sense(&self) -> ObjectiveSense {
        ObjectiveSense::Maximize
    }
}

fn run_binary_ga(seed: u64, gens: usize) -> Vec<f32> {
    let device = Default::default();
    let dim = 16usize;
    let params = BinaryGaConfig::default_for(32, dim);
    let mut harness = EvolutionaryHarness::<B, _, _>::new(
        BinaryGeneticAlgorithm::<B>::new(),
        params,
        OneMaxBatch { dim },
        seed,
        device,
        gens,
    )
    .expect("valid params");
    harness.reset();
    let mut trajectory = Vec::with_capacity(gens);
    loop {
        let step = harness.step(());
        trajectory.push(harness.latest_metrics().unwrap().best_fitness());
        if step.done {
            break;
        }
    }
    trajectory
}

fn run_ga(seed: u64, gens: usize) -> Vec<f32> {
    let params = GaConfig {
        pop_size: 32,
        genome_dim: 5,
        bounds: Bounds::new(-5.0, 5.0),
        mutation_sigma: NonNegativeRate::new(0.2),
        selection: GaSelection::Tournament { size: 2 },
        crossover: GaCrossover::BlxAlpha {
            alpha: NonNegativeRate::new(0.5),
        },
        replacement: GaReplacement::Elitist { elitism_k: 1 },
    };
    run(GeneticAlgorithm::<B>::new(), params, seed, gens)
}

fn run_es(seed: u64, gens: usize, kind: EsKind) -> Vec<f32> {
    let params = EsConfig::default_for(kind, 5);
    run(EvolutionStrategy::<B>::new(), params, seed, gens)
}

fn run_pso(seed: u64, gens: usize) -> Vec<f32> {
    let params = PsoConfig::default_for(16, 5);
    run(ParticleSwarm::<B>::new(), params, seed, gens)
}

fn run_gwo(seed: u64, gens: usize) -> Vec<f32> {
    let params = GwoConfig::default_for(16, 5);
    run(GreyWolfOptimizer::<B>::new(), params, seed, gens)
}

fn run_woa(seed: u64, gens: usize) -> Vec<f32> {
    let params = WoaConfig::default_for(16, 5);
    run(WhaleOptimization::<B>::new(), params, seed, gens)
}

fn run_salp(seed: u64, gens: usize) -> Vec<f32> {
    let params = SalpConfig::default_for(16, 5);
    run(SalpSwarm::<B>::new(), params, seed, gens)
}

fn run_abc(seed: u64, gens: usize) -> Vec<f32> {
    let params = AbcConfig::default_for(12, 5);
    run(ArtificialBeeColony::<B>::new(), params, seed, gens)
}

fn run_bat(seed: u64, gens: usize) -> Vec<f32> {
    let params = BatConfig::default_for(16, 5);
    run(BatAlgorithm::<B>::new(), params, seed, gens)
}

fn run_aco_r(seed: u64, gens: usize) -> Vec<f32> {
    let params = AcoRConfig::default_for(16, 8, 5);
    run(AntColonyReal::<B>::new(), params, seed, gens)
}

fn run_cuckoo(seed: u64, gens: usize) -> Vec<f32> {
    let params = CuckooConfig::default_for(16, 5);
    run(CuckooSearch::<B>::new(), params, seed, gens)
}

fn run_firefly(seed: u64, gens: usize) -> Vec<f32> {
    let params = FireflyConfig::default_for(16, 5);
    run(FireflyAlgorithm::<B>::new(), params, seed, gens)
}

/// Drive a `MemeticWrapper<DE, HillClimbing>` for `gens` generations and
/// collect the per-generation best-fitness trajectory.
///
/// Unlike [`run`], this builds the harness inline: a `MemeticWrapper` holds its
/// *own* fitness instance (used to score local-search probes) in addition to
/// the harness's, so it cannot go through the generic [`run`] path that supplies
/// a single fitness. Both instances are independent `FromFitnessEvaluable`
/// values over the same stateless [`SphereFit`], so they never diverge.
fn run_memetic_de(seed: u64, gens: usize) -> Vec<f32> {
    let device: <B as burn::tensor::backend::BackendTypes>::Device = Default::default();
    let dim: usize = 5;
    let bounds: Bounds = Bounds::new(-5.12, 5.12);
    let strategy: MemeticWrapper<B, _, _, _> = MemeticWrapper::<B, _, _, _>::new(
        DifferentialEvolution::<B>::new(),
        HillClimbing,
        FromFitnessEvaluable::new(SphereFit, Sphere),
    );
    let params: MemeticParams<DeConfig, HillClimbingParams> = MemeticParams {
        inner: DeConfig::default_for(16, dim),
        local: HillClimbingParams::default_for(bounds),
        writeback: WritebackPolicy::Partial(Probability::new(0.5)),
        coverage: CoveragePolicy::TopK { k: 2 },
    };
    let mut harness = EvolutionaryHarness::<B, _, _>::new(
        strategy,
        params,
        FromFitnessEvaluable::new(SphereFit, Sphere),
        seed,
        device,
        gens,
    )
    .expect("valid params");
    harness.reset();
    let mut trajectory: Vec<f32> = Vec::with_capacity(gens);
    loop {
        let step = harness.step(());
        trajectory.push(harness.latest_metrics().unwrap().best_fitness());
        if step.done {
            break;
        }
    }
    trajectory
}

/// Drive a `MemeticWrapper<DE, SimulatedAnnealing>` for `gens` generations and
/// collect the per-generation best-fitness trajectory.
///
/// Exercises the stochastic-searcher determinism path: SA draws Gaussian
/// proposals and Metropolis acceptance probabilities through the wrapper's
/// `seed_stream`-derived `ls_rng`, so a same-seed replay must still be
/// bit-identical. See [`run_memetic_de`] for the two-fitness-instance note.
fn run_memetic_sa(seed: u64, gens: usize) -> Vec<f32> {
    let device: <B as burn::tensor::backend::BackendTypes>::Device = Default::default();
    let dim: usize = 5;
    let bounds: Bounds = Bounds::new(-5.12, 5.12);
    let strategy: MemeticWrapper<B, _, _, _> = MemeticWrapper::<B, _, _, _>::new(
        DifferentialEvolution::<B>::new(),
        SimulatedAnnealing,
        FromFitnessEvaluable::new(SphereFit, Sphere),
    );
    let params: MemeticParams<DeConfig, SimulatedAnnealingParams> = MemeticParams {
        inner: DeConfig::default_for(16, dim),
        local: SimulatedAnnealingParams::default_for(bounds),
        writeback: WritebackPolicy::Partial(Probability::new(0.5)),
        coverage: CoveragePolicy::TopK { k: 2 },
    };
    let mut harness = EvolutionaryHarness::<B, _, _>::new(
        strategy,
        params,
        FromFitnessEvaluable::new(SphereFit, Sphere),
        seed,
        device,
        gens,
    )
    .expect("valid params");
    harness.reset();
    let mut trajectory: Vec<f32> = Vec::with_capacity(gens);
    loop {
        let step = harness.step(());
        trajectory.push(harness.latest_metrics().unwrap().best_fitness());
        if step.done {
            break;
        }
    }
    trajectory
}

#[test]
fn same_seed_same_generations() {
    const SEED: u64 = 1_234_567;
    const GENS: usize = 30;

    // Classical EAs.
    let ga_a = run_ga(SEED, GENS);
    let ga_b = run_ga(SEED, GENS);
    assert_eq!(ga_a, ga_b, "GA trajectories diverge under the same seed");

    let bga_a = run_binary_ga(SEED, GENS);
    let bga_b = run_binary_ga(SEED, GENS);
    assert_eq!(
        bga_a, bga_b,
        "Binary GA trajectories diverge under the same seed"
    );

    for kind in [
        EsKind::OnePlusOne,
        EsKind::OnePlusLambda { lambda: 6 },
        EsKind::MuPlusLambda { mu: 3, lambda: 9 },
        EsKind::MuCommaLambda { mu: 3, lambda: 9 },
    ] {
        let a = run_es(SEED, GENS, kind);
        let b = run_es(SEED, GENS, kind);
        assert_eq!(
            a, b,
            "ES trajectories diverge under the same seed for {kind:?}"
        );
    }

    // Swarm strategies. ACO-Permutation excluded (stub).
    macro_rules! check {
        ($fn:ident, $name:expr) => {
            let a = $fn(SEED, GENS);
            let b = $fn(SEED, GENS);
            assert_eq!(a, b, "{} trajectories diverge under the same seed", $name);
        };
    }
    check!(run_pso, "PSO");
    check!(run_gwo, "GWO");
    check!(run_woa, "WOA");
    check!(run_salp, "SSA");
    check!(run_abc, "ABC");
    check!(run_bat, "Bat");
    check!(run_aco_r, "ACO_R");
    check!(run_cuckoo, "Cuckoo");
    check!(run_firefly, "Firefly");

    // Memetic wrappers. `MemeticWrapper<DE, HillClimbing>` and
    // `MemeticWrapper<DE, SimulatedAnnealing>` route all refinement randomness
    // through `seed_stream`, so same-seed runs must be bit-identical too — even
    // for the stochastic SA searcher, whose Gaussian proposals and Metropolis
    // acceptance draws flow through the wrapper's deterministic `ls_rng`.
    let mem_de_a = run_memetic_de(SEED, GENS);
    let mem_de_b = run_memetic_de(SEED, GENS);
    assert_eq!(
        mem_de_a, mem_de_b,
        "MemeticWrapper<DE, HillClimbing> trajectories diverge under the same seed"
    );

    let mem_sa_a = run_memetic_sa(SEED, GENS);
    let mem_sa_b = run_memetic_sa(SEED, GENS);
    assert_eq!(
        mem_sa_a, mem_sa_b,
        "MemeticWrapper<DE, SimulatedAnnealing> trajectories diverge under the same seed"
    );
}