rlevo_evolution/coevolution/
mod.rs

1//! Co-evolutionary algorithms.
2//!
3//! Two populations evolve **simultaneously**, and each individual's fitness
4//! depends on the *other* population. Two regimes ship in v1:
5//!
6//! - **Competitive** ([`CompetitiveCoEA`]) — populations are adversaries
7//!   (predator vs. prey, Hillis 1990). Each is scored by how well it does
8//!   against the other; the dynamic is an arms race.
9//! - **Cooperative** ([`CooperativeCoEA`], CCGA — Potter & De Jong 1994) — a
10//!   high-dimensional problem is decomposed across populations whose
11//!   individuals combine (via *representatives*) into a full candidate.
12//!
13//! # Why not [`Strategy`](crate::strategy::Strategy)?
14//!
15//! [`Strategy::tell`](crate::strategy::Strategy::tell) accepts a single
16//! fitness vector, but co-evolutionary fitness is inherently paired — each
17//! population receives a vector computed relative to the other. Rather than
18//! distort that contract, co-evolution gets its own [`CoEvolutionaryAlgorithm`]
19//! trait and a dedicated [`CoEvolutionaryHarness`] that adapts to the existing
20//! `rlevo-core::evaluation::BenchEnv` surface, exactly as
21//! [`EvolutionaryHarness`](crate::strategy::EvolutionaryHarness) does. Both
22//! co-evolutionary algorithms are built from ordinary inner
23//! [`Strategy`](crate::strategy::Strategy) instances, so every phase-1/2/3a/3b
24//! algorithm composes in unchanged.
25//!
26//! # Pathology mitigation
27//!
28//! Competitive co-evolution is prone to **cycling**; [`HallOfFameFitness`]
29//! wraps any [`CoupledFitness`] to anchor scores against an archive of past
30//! champions (Rosin & Belew 1997). It composes at construction — algorithms
31//! are hall-of-fame-agnostic.
32//!
33//! # Coupling shape
34//!
35//! [`CoupledFitness`] takes a slice of populations and is N-population-ready;
36//! v1 algorithms always pass exactly two. The harness exposes
37//! `min(best_a, best_b)` (canonical maximise) as the benchmark reward (the
38//! weaker population — lower canonical fitness — is the binding constraint).
39//!
40//! # References
41//!
42//! - Hillis (1990), *Co-evolving parasites improve simulated evolution as an
43//!   optimization procedure.*
44//! - Potter & De Jong (1994), *A cooperative coevolutionary approach to
45//!   function optimization* (CCGA).
46//! - Rosin & Belew (1997), *New methods for competitive coevolution* (hall of
47//!   fame).
48//! - Ficici (2004), *Solution concepts in coevolutionary algorithms* (cycling
49//!   / intransitive dominance).
50
51pub mod competitive;
52pub mod cooperative;
53pub mod fitness;
54pub mod harness;
55pub mod hof;
56
57pub use competitive::{CompetitiveCoEA, CompetitiveCoEAParams};
58pub use cooperative::{
59    CooperativeCoEA, CooperativeCoEAParams, CooperativeState, RepresentativePolicy,
60};
61pub use fitness::CoupledFitness;
62pub use harness::{CoEAMetrics, CoEvolutionaryHarness};
63pub use hof::{HallOfFame, HallOfFameFitness};
64
65use std::fmt::Debug;
66
67use burn::tensor::backend::Backend;
68use rand::Rng;
69
70/// A co-evolutionary algorithm driving two populations under simultaneous
71/// updates.
72///
73/// The analogue of [`Strategy`](crate::strategy::Strategy) for the coupled
74/// case: [`init`](Self::init) builds the joint state and [`step`](Self::step)
75/// advances one simultaneous-update generation (both populations `ask` → one
76/// [`CoupledFitness`] evaluation → both `tell`). Implementors hold their inner
77/// strategies and a [`CoupledFitness`] by value and carry no PRNG state — all
78/// randomness flows through the explicit `rng` argument, per the crate's
79/// host-RNG convention.
80///
81/// v1 ships [`CompetitiveCoEA`] and [`CooperativeCoEA`]; Stackelberg
82/// (alternating) turn order is deferred.
83pub trait CoEvolutionaryAlgorithm<B: Backend>: Send + Sync {
84    /// Static parameters for a run (inner strategy params plus any coupling
85    /// configuration).
86    type Params: Clone + Debug + Send + Sync;
87
88    /// Generation-to-generation joint state.
89    type State: Clone + Debug + Send;
90
91    /// Build the initial joint state (initializes both inner strategies).
92    fn init(
93        &self,
94        params: &Self::Params,
95        rng: &mut dyn Rng,
96        device: &<B as burn::tensor::backend::BackendTypes>::Device,
97    ) -> Self::State;
98
99    /// Advance one simultaneous-update generation, returning the next state
100    /// and this generation's [`CoEAMetrics`].
101    fn step(
102        &self,
103        params: &Self::Params,
104        state: Self::State,
105        rng: &mut dyn Rng,
106        device: &<B as burn::tensor::backend::BackendTypes>::Device,
107    ) -> (Self::State, CoEAMetrics);
108
109    /// Snapshot the current metrics without advancing a generation.
110    fn metrics(&self, state: &Self::State) -> CoEAMetrics;
111}
112
113/// Joined state carrying both sub-strategy states plus per-population
114/// best/mean trackers.
115///
116/// Generic over the two inner strategy *state* types (`StA`, `StB`) rather
117/// than the strategies themselves, so it derives [`Clone`]/[`Debug`] without
118/// spurious bounds on the strategy types. Used by [`CompetitiveCoEA`];
119/// [`CooperativeCoEA`] wraps it in [`CooperativeState`] to add
120/// representative archives.
121#[derive(Debug, Clone)]
122pub struct CoEAState<StA, StB> {
123    /// Inner state of population A's strategy.
124    pub state_a: StA,
125    /// Inner state of population B's strategy.
126    pub state_b: StB,
127    /// Number of completed simultaneous-update generations.
128    pub generation: u64,
129    /// Best (highest, canonical maximise) fitness population A has seen across
130    /// all generations.
131    pub best_a: f32,
132    /// Best (highest, canonical maximise) fitness population B has seen across
133    /// all generations.
134    pub best_b: f32,
135    /// Mean fitness of population A in the most recent generation.
136    pub mean_a: f32,
137    /// Mean fitness of population B in the most recent generation.
138    pub mean_b: f32,
139}
140
141impl<StA, StB> CoEAState<StA, StB> {
142    /// Build the initial joint state with empty best/mean trackers.
143    pub(crate) fn new(state_a: StA, state_b: StB) -> Self {
144        Self {
145            state_a,
146            state_b,
147            generation: 0,
148            best_a: f32::NEG_INFINITY,
149            best_b: f32::NEG_INFINITY,
150            mean_a: f32::NAN,
151            mean_b: f32::NAN,
152        }
153    }
154}
rlevo_evolution/coevolution/mod.rs

rlevo_evolution/coevolution/
mod.rs
