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        let first = window[0];
109        let last = window[window.len() - 1];
110        let improvement = (last - first).abs();
111
112        improvement < self.epsilon
113    }
114
115    fn reason(&self) -> &'static str {
116        "Fitness stagnation detected"
117    }
118}
119
120/// Terminate when target fitness is reached
121#[derive(Clone, Debug)]
122pub struct TargetFitness {
123    /// Target fitness value
124    pub target: f64,
125    /// Tolerance for reaching target
126    pub tolerance: f64,
127}
128
129impl TargetFitness {
130    /// Create a new target fitness criterion
131    pub fn new(target: f64) -> Self {
132        Self {
133            target,
134            tolerance: 0.0,
135        }
136    }
137
138    /// Create with a tolerance
139    pub fn with_tolerance(target: f64, tolerance: f64) -> Self {
140        Self { target, tolerance }
141    }
142}
143
144impl<G: EvolutionaryGenome, F: FitnessValue> TerminationCriterion<G, F> for TargetFitness {
145    fn should_terminate(&self, state: &EvolutionState<G, F>) -> bool {
146        state.best_fitness >= self.target - self.tolerance
147    }
148
149    fn reason(&self) -> &'static str {
150        "Target fitness reached"
151    }
152}
153
154/// Terminate when population diversity drops below threshold
155#[derive(Clone, Debug)]
156pub struct DiversityThreshold {
157    /// Minimum diversity threshold
158    pub min_diversity: f64,
159}
160
161impl DiversityThreshold {
162    /// Create a new diversity threshold criterion
163    pub fn new(min_diversity: f64) -> Self {
164        Self { min_diversity }
165    }
166}
167
168impl<G: EvolutionaryGenome, F: FitnessValue> TerminationCriterion<G, F> for DiversityThreshold {
169    fn should_terminate(&self, state: &EvolutionState<G, F>) -> bool {
170        let diversity = state.population.diversity();
171        diversity < self.min_diversity
172    }
173
174    fn reason(&self) -> &'static str {
175        "Diversity threshold reached"
176    }
177}
178
179/// Combine criteria with OR logic (any one triggers termination)
180pub struct AnyOf<G: EvolutionaryGenome, F: FitnessValue = f64> {
181    criteria: Vec<Box<dyn TerminationCriterion<G, F>>>,
182}
183
184impl<G: EvolutionaryGenome, F: FitnessValue> AnyOf<G, F> {
185    /// Create a new AnyOf combinator
186    pub fn new(criteria: Vec<Box<dyn TerminationCriterion<G, F>>>) -> Self {
187        Self { criteria }
188    }
189}
190
191impl<G: EvolutionaryGenome, F: FitnessValue> TerminationCriterion<G, F> for AnyOf<G, F> {
192    fn should_terminate(&self, state: &EvolutionState<G, F>) -> bool {
193        self.criteria.iter().any(|c| c.should_terminate(state))
194    }
195
196    fn reason(&self) -> &'static str {
197        "One of multiple criteria met"
198    }
199}
200
201/// Combine criteria with AND logic (all must trigger for termination)
202pub struct AllOf<G: EvolutionaryGenome, F: FitnessValue = f64> {
203    criteria: Vec<Box<dyn TerminationCriterion<G, F>>>,
204}
205
206impl<G: EvolutionaryGenome, F: FitnessValue> AllOf<G, F> {
207    /// Create a new AllOf combinator
208    pub fn new(criteria: Vec<Box<dyn TerminationCriterion<G, F>>>) -> Self {
209        Self { criteria }
210    }
211}
212
213impl<G: EvolutionaryGenome, F: FitnessValue> TerminationCriterion<G, F> for AllOf<G, F> {
214    fn should_terminate(&self, state: &EvolutionState<G, F>) -> bool {
215        !self.criteria.is_empty() && self.criteria.iter().all(|c| c.should_terminate(state))
216    }
217
218    fn reason(&self) -> &'static str {
219        "All criteria met"
220    }
221}
222
223pub mod prelude {
224    pub use super::{
225        AllOf, AnyOf, DiversityThreshold, EvolutionState, FitnessStagnation, MaxEvaluations,
226        MaxGenerations, TargetFitness, TerminationCriterion,
227    };
228}
229
230#[cfg(test)]
231mod tests {
232    use super::*;
233    use crate::genome::real_vector::RealVector;
234    use crate::population::individual::Individual;
235    use crate::population::population::Population;
236
237    fn create_test_state<'a>(
238        generation: usize,
239        evaluations: usize,
240        best_fitness: f64,
241        population: &'a Population<RealVector>,
242        fitness_history: &'a [f64],
243    ) -> EvolutionState<'a, RealVector> {
244        EvolutionState {
245            generation,
246            evaluations,
247            best_fitness,
248            population,
249            fitness_history,
250        }
251    }
252
253    #[test]
254    fn test_max_generations() {
255        let individuals = vec![Individual::with_fitness(RealVector::new(vec![1.0]), 10.0)];
256        let pop = Population::from_individuals(individuals);
257        let history = vec![];
258
259        let criterion = MaxGenerations::new(100);
260
261        let state = create_test_state(50, 0, 10.0, &pop, &history);
262        assert!(!criterion.should_terminate(&state));
263
264        let state = create_test_state(100, 0, 10.0, &pop, &history);
265        assert!(criterion.should_terminate(&state));
266
267        let state = create_test_state(150, 0, 10.0, &pop, &history);
268        assert!(criterion.should_terminate(&state));
269    }
270
271    #[test]
272    fn test_max_evaluations() {
273        let individuals = vec![Individual::with_fitness(RealVector::new(vec![1.0]), 10.0)];
274        let pop = Population::from_individuals(individuals);
275        let history = vec![];
276
277        let criterion = MaxEvaluations::new(1000);
278
279        let state = create_test_state(0, 500, 10.0, &pop, &history);
280        assert!(!criterion.should_terminate(&state));
281
282        let state = create_test_state(0, 1000, 10.0, &pop, &history);
283        assert!(criterion.should_terminate(&state));
284    }
285
286    #[test]
287    fn test_fitness_stagnation() {
288        let individuals = vec![Individual::with_fitness(RealVector::new(vec![1.0]), 10.0)];
289        let pop = Population::from_individuals(individuals);
290
291        let criterion = FitnessStagnation::new(5, 0.01);
292
293        // Not enough history
294        let history = vec![1.0, 2.0, 3.0];
295        let state = create_test_state(0, 0, 3.0, &pop, &history);
296        assert!(!criterion.should_terminate(&state));
297
298        // Still improving
299        let history = vec![1.0, 2.0, 3.0, 4.0, 5.0];
300        let state = create_test_state(0, 0, 5.0, &pop, &history);
301        assert!(!criterion.should_terminate(&state));
302
303        // Stagnant
304        let history = vec![5.0, 5.0, 5.0, 5.0, 5.0];
305        let state = create_test_state(0, 0, 5.0, &pop, &history);
306        assert!(criterion.should_terminate(&state));
307    }
308
309    #[test]
310    fn test_target_fitness() {
311        let individuals = vec![Individual::with_fitness(RealVector::new(vec![1.0]), 10.0)];
312        let pop = Population::from_individuals(individuals);
313        let history = vec![];
314
315        let criterion = TargetFitness::new(0.0);
316
317        // Not at target (fitness is negative, we want 0)
318        let state = create_test_state(0, 0, -10.0, &pop, &history);
319        assert!(!criterion.should_terminate(&state));
320
321        // At target
322        let state = create_test_state(0, 0, 0.0, &pop, &history);
323        assert!(criterion.should_terminate(&state));
324
325        // With tolerance
326        let criterion = TargetFitness::with_tolerance(0.0, 0.1);
327        let state = create_test_state(0, 0, -0.05, &pop, &history);
328        assert!(criterion.should_terminate(&state));
329    }
330
331    #[test]
332    fn test_any_of() {
333        let individuals = vec![Individual::with_fitness(RealVector::new(vec![1.0]), 10.0)];
334        let pop = Population::from_individuals(individuals);
335        let history = vec![];
336
337        let criterion = AnyOf::new(vec![
338            Box::new(MaxGenerations::new(100)),
339            Box::new(TargetFitness::new(0.0)),
340        ]);
341
342        // Neither met
343        let state = create_test_state(50, 0, -10.0, &pop, &history);
344        assert!(!criterion.should_terminate(&state));
345
346        // First met
347        let state = create_test_state(100, 0, -10.0, &pop, &history);
348        assert!(criterion.should_terminate(&state));
349
350        // Second met
351        let state = create_test_state(50, 0, 0.0, &pop, &history);
352        assert!(criterion.should_terminate(&state));
353    }
354
355    #[test]
356    fn test_all_of() {
357        let individuals = vec![Individual::with_fitness(RealVector::new(vec![1.0]), 10.0)];
358        let pop = Population::from_individuals(individuals);
359        let history = vec![];
360
361        let criterion = AllOf::new(vec![
362            Box::new(MaxGenerations::new(100)),
363            Box::new(TargetFitness::new(0.0)),
364        ]);
365
366        // Neither met
367        let state = create_test_state(50, 0, -10.0, &pop, &history);
368        assert!(!criterion.should_terminate(&state));
369
370        // Only first met
371        let state = create_test_state(100, 0, -10.0, &pop, &history);
372        assert!(!criterion.should_terminate(&state));
373
374        // Only second met
375        let state = create_test_state(50, 0, 0.0, &pop, &history);
376        assert!(!criterion.should_terminate(&state));
377
378        // Both met
379        let state = create_test_state(100, 0, 0.0, &pop, &history);
380        assert!(criterion.should_terminate(&state));
381    }
382}
fugue_evo/termination/mod.rs

fugue_evo/termination/
mod.rs
