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 & Pollack (1998), *Challenges in coevolutionary learning:
49//!   arms-race dynamics, open-endedness, and mediocre stable states*
50//!   (Artificial Life VI) — first identifies the cycling pathology.
51//! - Watson & Pollack (2001), *Coevolutionary dynamics in a minimal
52//!   substrate* (GECCO) — analyzes intransitive cycling dynamics.
53//! - Ficici (2004), *Solution concepts in coevolutionary algorithms* (cycling
54//!   / intransitive dominance).
55
56pub mod competitive;
57pub mod cooperative;
58pub mod fitness;
59pub mod harness;
60pub mod hof;
61
62pub use competitive::{CompetitiveCoEA, CompetitiveCoEAParams};
63pub use cooperative::{
64    CooperativeCoEA, CooperativeCoEAParams, CooperativeState, RepresentativePolicy,
65};
66pub use fitness::CoupledFitness;
67pub use harness::{CoEAMetrics, CoEvolutionaryHarness};
68pub use hof::{HallOfFame, HallOfFameFitness};
69
70use std::fmt::Debug;
71
72use burn::tensor::backend::Backend;
73use rand::Rng;
74
75/// A co-evolutionary algorithm driving two populations under simultaneous
76/// updates.
77///
78/// The analogue of [`Strategy`](crate::strategy::Strategy) for the coupled
79/// case: [`init`](Self::init) builds the joint state and [`step`](Self::step)
80/// advances one simultaneous-update generation (both populations `ask` → one
81/// [`CoupledFitness`] evaluation → both `tell`). Implementors hold their inner
82/// strategies and a [`CoupledFitness`] by value and carry no PRNG state — all
83/// randomness flows through the explicit `rng` argument, per the crate's
84/// host-RNG convention.
85///
86/// v1 ships [`CompetitiveCoEA`] and [`CooperativeCoEA`]; Stackelberg
87/// (alternating) turn order is deferred.
88pub trait CoEvolutionaryAlgorithm<B: Backend>: Send + Sync {
89    /// Static parameters for a run (inner strategy params plus any coupling
90    /// configuration).
91    type Params: Clone + Debug + Send + Sync;
92
93    /// Generation-to-generation joint state.
94    type State: Clone + Debug + Send;
95
96    /// Build the initial joint state (initializes both inner strategies).
97    fn init(
98        &self,
99        params: &Self::Params,
100        rng: &mut dyn Rng,
101        device: &<B as burn::tensor::backend::BackendTypes>::Device,
102    ) -> Self::State;
103
104    /// Advance one simultaneous-update generation, returning the next state
105    /// and this generation's [`CoEAMetrics`].
106    fn step(
107        &self,
108        params: &Self::Params,
109        state: Self::State,
110        rng: &mut dyn Rng,
111        device: &<B as burn::tensor::backend::BackendTypes>::Device,
112    ) -> (Self::State, CoEAMetrics);
113
114    /// Snapshot the current metrics without advancing a generation.
115    fn metrics(&self, state: &Self::State) -> CoEAMetrics;
116}
117
118/// Joined state carrying both sub-strategy states plus per-population
119/// best/mean trackers.
120///
121/// Generic over the two inner strategy *state* types (`StA`, `StB`) rather
122/// than the strategies themselves, so it derives [`Clone`]/[`Debug`] without
123/// spurious bounds on the strategy types. Used by [`CompetitiveCoEA`];
124/// [`CooperativeCoEA`] wraps it in [`CooperativeState`] to add
125/// representative archives.
126#[derive(Debug, Clone)]
127pub struct CoEAState<StA, StB> {
128    /// Inner state of population A's strategy.
129    pub state_a: StA,
130    /// Inner state of population B's strategy.
131    pub state_b: StB,
132    /// Number of completed simultaneous-update generations.
133    pub generation: u64,
134    /// Best (highest, canonical maximise) fitness population A has seen across
135    /// all generations.
136    pub best_a: f32,
137    /// Best (highest, canonical maximise) fitness population B has seen across
138    /// all generations.
139    pub best_b: f32,
140    /// Mean fitness of population A in the most recent generation.
141    pub mean_a: f32,
142    /// Mean fitness of population B in the most recent generation.
143    pub mean_b: f32,
144}
145
146impl<StA, StB> CoEAState<StA, StB> {
147    /// Build the initial joint state with empty best/mean trackers.
148    pub(crate) fn new(state_a: StA, state_b: StB) -> Self {
149        Self {
150            state_a,
151            state_b,
152            generation: 0,
153            best_a: f32::NEG_INFINITY,
154            best_b: f32::NEG_INFINITY,
155            mean_a: f32::NAN,
156            mean_b: f32::NAN,
157        }
158    }
159}
rlevo_evolution/coevolution/mod.rs

rlevo_evolution/coevolution/
mod.rs
