fugue_evo/termination/
mod.rs

1//! Termination criteria
2//!
3//! This module provides various termination criteria for evolutionary algorithms.
4
5use crate::fitness::traits::FitnessValue;
6use crate::genome::traits::EvolutionaryGenome;
7use crate::population::population::Population;
8
9/// Evolution state for termination checking
10#[derive(Clone, Debug)]
11pub struct EvolutionState<'a, G, F = f64>
12where
13    G: EvolutionaryGenome,
14    F: FitnessValue,
15{
16    /// Current generation number
17    pub generation: usize,
18    /// Total fitness evaluations so far
19    pub evaluations: usize,
20    /// Best fitness found so far
21    pub best_fitness: f64,
22    /// Reference to the current population
23    pub population: &'a Population<G, F>,
24    /// History of best fitness values per generation
25    pub fitness_history: &'a [f64],
26}
27
28/// Termination criterion trait
29pub trait TerminationCriterion<G: EvolutionaryGenome, F: FitnessValue = f64>: Send + Sync {
30    /// Check if evolution should terminate
31    fn should_terminate(&self, state: &EvolutionState<G, F>) -> bool;
32
33    /// Get a description of why termination occurred
34    fn reason(&self) -> &'static str;
35}
36
37/// Terminate after a maximum number of generations
38#[derive(Clone, Debug)]
39pub struct MaxGenerations(pub usize);
40
41impl MaxGenerations {
42    /// Create a new max generations criterion
43    pub fn new(max: usize) -> Self {
44        Self(max)
45    }
46}
47
48impl<G: EvolutionaryGenome, F: FitnessValue> TerminationCriterion<G, F> for MaxGenerations {
49    fn should_terminate(&self, state: &EvolutionState<G, F>) -> bool {
50        state.generation >= self.0
51    }
52
53    fn reason(&self) -> &'static str {
54        "Maximum generations reached"
55    }
56}
57
58/// Terminate after a maximum number of fitness evaluations
59#[derive(Clone, Debug)]
60pub struct MaxEvaluations(pub usize);
61
62impl MaxEvaluations {
63    /// Create a new max evaluations criterion
64    pub fn new(max: usize) -> Self {
65        Self(max)
66    }
67}
68
69impl<G: EvolutionaryGenome, F: FitnessValue> TerminationCriterion<G, F> for MaxEvaluations {
70    fn should_terminate(&self, state: &EvolutionState<G, F>) -> bool {
71        state.evaluations >= self.0
72    }
73
74    fn reason(&self) -> &'static str {
75        "Maximum evaluations reached"
76    }
77}
78
79/// Terminate when fitness improvement stagnates
80#[derive(Clone, Debug)]
81pub struct FitnessStagnation {
82    /// Number of generations to look back
83    pub window: usize,
84    /// Minimum improvement threshold
85    pub epsilon: f64,
86}
87
88impl FitnessStagnation {
89    /// Create a new fitness stagnation criterion
90    pub fn new(window: usize, epsilon: f64) -> Self {
91        Self { window, epsilon }
92    }
93}
94
95impl<G: EvolutionaryGenome, F: FitnessValue> TerminationCriterion<G, F> for FitnessStagnation {
96    fn should_terminate(&self, state: &EvolutionState<G, F>) -> bool {
97        if state.fitness_history.len() < self.window {
98            return false;
99        }
100
101        let start_idx = state.fitness_history.len() - self.window;
102        let window = &state.fitness_history[start_idx..];
103
104        if window.is_empty() {
105            return false;
106        }
107
108        // EV-73 / EV-105: measure the best-so-far improvement across the window
109        // (the largest gain over the window's starting value), not just the
110        // endpoint delta. `fitness_history` is the per-generation population best
111        // and is NOT guaranteed monotone (e.g. with elitism disabled), so a
112        // non-monotonic window such as [10, 90, 10] has zero endpoint delta yet
113        // clearly improved mid-window. Because `window[0]` is part of the window,
114        // `best_in_window - first` is always >= 0 and equals 0 exactly when the
115        // running best never rose above the window's opening value.
116        let first = window[0];
117        let best_in_window = window.iter().copied().fold(f64::NEG_INFINITY, f64::max);
118        let improvement = best_in_window - first;
119
120        improvement < self.epsilon
121    }
122
123    fn reason(&self) -> &'static str {
124        "Fitness stagnation detected"
125    }
126}
127
128/// Terminate when target fitness is reached
129#[derive(Clone, Debug)]
130pub struct TargetFitness {
131    /// Target fitness value
132    pub target: f64,
133    /// Tolerance for reaching target
134    pub tolerance: f64,
135}
136
137impl TargetFitness {
138    /// Create a new target fitness criterion
139    pub fn new(target: f64) -> Self {
140        Self {
141            target,
142            tolerance: 0.0,
143        }
144    }
145
146    /// Create with a tolerance
147    pub fn with_tolerance(target: f64, tolerance: f64) -> Self {
148        Self { target, tolerance }
149    }
150}
151
152impl<G: EvolutionaryGenome, F: FitnessValue> TerminationCriterion<G, F> for TargetFitness {
153    fn should_terminate(&self, state: &EvolutionState<G, F>) -> bool {
154        state.best_fitness >= self.target - self.tolerance
155    }
156
157    fn reason(&self) -> &'static str {
158        "Target fitness reached"
159    }
160}
161
162/// Terminate when population diversity drops below threshold
163#[derive(Clone, Debug)]
164pub struct DiversityThreshold {
165    /// Minimum diversity threshold
166    pub min_diversity: f64,
167}
168
169impl DiversityThreshold {
170    /// Create a new diversity threshold criterion
171    pub fn new(min_diversity: f64) -> Self {
172        Self { min_diversity }
173    }
174}
175
176impl<G: EvolutionaryGenome, F: FitnessValue> TerminationCriterion<G, F> for DiversityThreshold {
177    fn should_terminate(&self, state: &EvolutionState<G, F>) -> bool {
178        let diversity = state.population.diversity();
179        diversity < self.min_diversity
180    }
181
182    fn reason(&self) -> &'static str {
183        "Diversity threshold reached"
184    }
185}
186
187/// Combine criteria with OR logic (any one triggers termination)
188pub struct AnyOf<G: EvolutionaryGenome, F: FitnessValue = f64> {
189    criteria: Vec<Box<dyn TerminationCriterion<G, F>>>,
190}
191
192impl<G: EvolutionaryGenome, F: FitnessValue> AnyOf<G, F> {
193    /// Create a new AnyOf combinator
194    pub fn new(criteria: Vec<Box<dyn TerminationCriterion<G, F>>>) -> Self {
195        Self { criteria }
196    }
197}
198
199impl<G: EvolutionaryGenome, F: FitnessValue> TerminationCriterion<G, F> for AnyOf<G, F> {
200    fn should_terminate(&self, state: &EvolutionState<G, F>) -> bool {
201        self.criteria.iter().any(|c| c.should_terminate(state))
202    }
203
204    fn reason(&self) -> &'static str {
205        "One of multiple criteria met"
206    }
207}
208
209/// Combine criteria with AND logic (all must trigger for termination)
210pub struct AllOf<G: EvolutionaryGenome, F: FitnessValue = f64> {
211    criteria: Vec<Box<dyn TerminationCriterion<G, F>>>,
212}
213
214impl<G: EvolutionaryGenome, F: FitnessValue> AllOf<G, F> {
215    /// Create a new AllOf combinator
216    pub fn new(criteria: Vec<Box<dyn TerminationCriterion<G, F>>>) -> Self {
217        Self { criteria }
218    }
219}
220
221impl<G: EvolutionaryGenome, F: FitnessValue> TerminationCriterion<G, F> for AllOf<G, F> {
222    fn should_terminate(&self, state: &EvolutionState<G, F>) -> bool {
223        !self.criteria.is_empty() && self.criteria.iter().all(|c| c.should_terminate(state))
224    }
225
226    fn reason(&self) -> &'static str {
227        "All criteria met"
228    }
229}
230
231pub mod prelude {
232    pub use super::{
233        AllOf, AnyOf, DiversityThreshold, EvolutionState, FitnessStagnation, MaxEvaluations,
234        MaxGenerations, TargetFitness, TerminationCriterion,
235    };
236}
237
238#[cfg(test)]
239mod tests {
240    use super::*;
241    use crate::genome::real_vector::RealVector;
242    use crate::population::individual::Individual;
243    use crate::population::population::Population;
244
245    fn create_test_state<'a>(
246        generation: usize,
247        evaluations: usize,
248        best_fitness: f64,
249        population: &'a Population<RealVector>,
250        fitness_history: &'a [f64],
251    ) -> EvolutionState<'a, RealVector> {
252        EvolutionState {
253            generation,
254            evaluations,
255            best_fitness,
256            population,
257            fitness_history,
258        }
259    }
260
261    #[test]
262    fn test_max_generations() {
263        let individuals = vec![Individual::with_fitness(RealVector::new(vec![1.0]), 10.0)];
264        let pop = Population::from_individuals(individuals);
265        let history = vec![];
266
267        let criterion = MaxGenerations::new(100);
268
269        let state = create_test_state(50, 0, 10.0, &pop, &history);
270        assert!(!criterion.should_terminate(&state));
271
272        let state = create_test_state(100, 0, 10.0, &pop, &history);
273        assert!(criterion.should_terminate(&state));
274
275        let state = create_test_state(150, 0, 10.0, &pop, &history);
276        assert!(criterion.should_terminate(&state));
277    }
278
279    #[test]
280    fn test_max_evaluations() {
281        let individuals = vec![Individual::with_fitness(RealVector::new(vec![1.0]), 10.0)];
282        let pop = Population::from_individuals(individuals);
283        let history = vec![];
284
285        let criterion = MaxEvaluations::new(1000);
286
287        let state = create_test_state(0, 500, 10.0, &pop, &history);
288        assert!(!criterion.should_terminate(&state));
289
290        let state = create_test_state(0, 1000, 10.0, &pop, &history);
291        assert!(criterion.should_terminate(&state));
292    }
293
294    #[test]
295    fn test_fitness_stagnation() {
296        let individuals = vec![Individual::with_fitness(RealVector::new(vec![1.0]), 10.0)];
297        let pop = Population::from_individuals(individuals);
298
299        let criterion = FitnessStagnation::new(5, 0.01);
300
301        // Not enough history
302        let history = vec![1.0, 2.0, 3.0];
303        let state = create_test_state(0, 0, 3.0, &pop, &history);
304        assert!(!criterion.should_terminate(&state));
305
306        // Still improving
307        let history = vec![1.0, 2.0, 3.0, 4.0, 5.0];
308        let state = create_test_state(0, 0, 5.0, &pop, &history);
309        assert!(!criterion.should_terminate(&state));
310
311        // Stagnant
312        let history = vec![5.0, 5.0, 5.0, 5.0, 5.0];
313        let state = create_test_state(0, 0, 5.0, &pop, &history);
314        assert!(criterion.should_terminate(&state));
315    }
316
317    // regression: EV-73, EV-105 — a non-monotonic window must not be mistaken for
318    // stagnation. Endpoint-only logic ((last-first).abs()) reports [10, 90, 10] as
319    // "improvement == 0" and terminates; the best-so-far measure sees the mid-window
320    // rise to 90 and correctly reports progress.
321    #[test]
322    fn test_fitness_stagnation_nonmonotonic_window() {
323        let individuals = vec![Individual::with_fitness(RealVector::new(vec![1.0]), 10.0)];
324        let pop = Population::from_individuals(individuals);
325
326        let criterion = FitnessStagnation::new(3, 0.01);
327
328        // Rose then fell back: real improvement happened inside the window.
329        let history = vec![10.0, 90.0, 10.0];
330        let state = create_test_state(0, 0, 10.0, &pop, &history);
331        assert!(
332            !criterion.should_terminate(&state),
333            "non-monotonic window with a mid-window peak must not read as stagnant"
334        );
335
336        // Improve-then-regress must also not read as stagnant.
337        let history = vec![10.0, 90.0, 20.0];
338        let state = create_test_state(0, 0, 20.0, &pop, &history);
339        assert!(!criterion.should_terminate(&state));
340
341        // A monotone decline never rose above the opening value -> genuinely stagnant.
342        let history = vec![90.0, 50.0, 10.0];
343        let state = create_test_state(0, 0, 10.0, &pop, &history);
344        assert!(criterion.should_terminate(&state));
345    }
346
347    #[test]
348    fn test_target_fitness() {
349        let individuals = vec![Individual::with_fitness(RealVector::new(vec![1.0]), 10.0)];
350        let pop = Population::from_individuals(individuals);
351        let history = vec![];
352
353        let criterion = TargetFitness::new(0.0);
354
355        // Not at target (fitness is negative, we want 0)
356        let state = create_test_state(0, 0, -10.0, &pop, &history);
357        assert!(!criterion.should_terminate(&state));
358
359        // At target
360        let state = create_test_state(0, 0, 0.0, &pop, &history);
361        assert!(criterion.should_terminate(&state));
362
363        // With tolerance
364        let criterion = TargetFitness::with_tolerance(0.0, 0.1);
365        let state = create_test_state(0, 0, -0.05, &pop, &history);
366        assert!(criterion.should_terminate(&state));
367    }
368
369    #[test]
370    fn test_any_of() {
371        let individuals = vec![Individual::with_fitness(RealVector::new(vec![1.0]), 10.0)];
372        let pop = Population::from_individuals(individuals);
373        let history = vec![];
374
375        let criterion = AnyOf::new(vec![
376            Box::new(MaxGenerations::new(100)),
377            Box::new(TargetFitness::new(0.0)),
378        ]);
379
380        // Neither met
381        let state = create_test_state(50, 0, -10.0, &pop, &history);
382        assert!(!criterion.should_terminate(&state));
383
384        // First met
385        let state = create_test_state(100, 0, -10.0, &pop, &history);
386        assert!(criterion.should_terminate(&state));
387
388        // Second met
389        let state = create_test_state(50, 0, 0.0, &pop, &history);
390        assert!(criterion.should_terminate(&state));
391    }
392
393    #[test]
394    fn test_all_of() {
395        let individuals = vec![Individual::with_fitness(RealVector::new(vec![1.0]), 10.0)];
396        let pop = Population::from_individuals(individuals);
397        let history = vec![];
398
399        let criterion = AllOf::new(vec![
400            Box::new(MaxGenerations::new(100)),
401            Box::new(TargetFitness::new(0.0)),
402        ]);
403
404        // Neither met
405        let state = create_test_state(50, 0, -10.0, &pop, &history);
406        assert!(!criterion.should_terminate(&state));
407
408        // Only first met
409        let state = create_test_state(100, 0, -10.0, &pop, &history);
410        assert!(!criterion.should_terminate(&state));
411
412        // Only second met
413        let state = create_test_state(50, 0, 0.0, &pop, &history);
414        assert!(!criterion.should_terminate(&state));
415
416        // Both met
417        let state = create_test_state(100, 0, 0.0, &pop, &history);
418        assert!(criterion.should_terminate(&state));
419    }
420}
fugue_evo/termination/mod.rs

fugue_evo/termination/
mod.rs
