fugue_evo/algorithms/
steady_state.rs

1//! Steady-State Genetic Algorithm
2//!
3//! This module implements a steady-state genetic algorithm where only a small
4//! number of individuals are replaced in each generation (typically 1 or 2),
5//! rather than replacing the entire population.
6
7use std::time::Instant;
8
9use rand::Rng;
10
11use crate::diagnostics::{EvolutionResult, EvolutionStats, GenerationStats, TimingStats};
12use crate::error::EvolutionError;
13use crate::fitness::traits::{Fitness, FitnessValue};
14use crate::genome::bounds::MultiBounds;
15use crate::genome::traits::EvolutionaryGenome;
16use crate::operators::traits::{
17    BoundedCrossoverOperator, BoundedMutationOperator, CrossoverOperator, MutationOperator,
18    SelectionOperator,
19};
20use crate::population::individual::Individual;
21use crate::population::population::Population;
22use crate::termination::{EvolutionState, MaxGenerations, TerminationCriterion};
23
24/// Replacement strategy for steady-state GA.
25///
26/// EV-42: only [`ReplacementStrategy::ReplaceIfBetter`] is elitist (it accepts an
27/// offspring only when it improves on the individual it would replace). Every
28/// other strategy performs its replacement **unconditionally**, matching its
29/// documented meaning — in particular `ReplaceRandom` is a genuine, diversity-
30/// preserving stochastic replacement and may accept a worse offspring.
31#[derive(Clone, Debug, Default)]
32pub enum ReplacementStrategy {
33    /// Replace the worst individual in the population, unconditionally. Because the
34    /// current best is never the replacement target, the population best is
35    /// preserved, but the population mean may temporarily worsen.
36    #[default]
37    ReplaceWorst,
38    /// Replace a uniformly-random individual, unconditionally (non-elitist). A
39    /// worse offspring can enter the population, preserving exploratory diversity.
40    ReplaceRandom,
41    /// Replace the worse parent, but only if the offspring beats it
42    /// (generational replacement).
43    ReplaceParent,
44    /// Replace the worst individual, but only if the offspring is strictly better
45    /// than it (the fully elitist, accept-if-better option).
46    ReplaceIfBetter,
47    /// Use an inverse tournament to choose a (likely poor) individual to replace,
48    /// then replace it unconditionally.
49    TournamentWorst(usize),
50}
51
52impl ReplacementStrategy {
53    /// Whether replacement is gated on the offspring improving on its target
54    /// (EV-42). Only `ReplaceIfBetter` is elitist here; `ReplaceParent` carries
55    /// its own acceptance test in the main loop.
56    fn requires_improvement(&self) -> bool {
57        matches!(self, ReplacementStrategy::ReplaceIfBetter)
58    }
59}
60
61/// Configuration for the Steady-State GA
62#[derive(Clone, Debug)]
63pub struct SteadyStateConfig {
64    /// Population size
65    pub population_size: usize,
66    /// Number of offspring to generate per step (typically 1 or 2)
67    pub offspring_count: usize,
68    /// Crossover probability
69    pub crossover_probability: f64,
70    /// Replacement strategy
71    pub replacement: ReplacementStrategy,
72    /// Whether to evaluate in parallel
73    pub parallel_evaluation: bool,
74    /// Number of steps per "generation" for statistics reporting
75    pub steps_per_generation: usize,
76    /// EV-44: when true, an offspring whose genome equals an existing population
77    /// member is rejected instead of inserted, preventing the population from
78    /// collapsing to duplicates. This costs an O(population_size) genome
79    /// comparison per candidate offspring.
80    pub prevent_duplicates: bool,
81}
82
83impl Default for SteadyStateConfig {
84    fn default() -> Self {
85        Self {
86            population_size: 100,
87            offspring_count: 2,
88            crossover_probability: 0.9,
89            replacement: ReplacementStrategy::ReplaceWorst,
90            parallel_evaluation: false,
91            steps_per_generation: 50, // Report stats every 50 replacements
92            prevent_duplicates: false,
93        }
94    }
95}
96
97/// Builder for SteadyStateGA
98pub struct SteadyStateBuilder<G, F, S, C, M, Fit, Term>
99where
100    G: EvolutionaryGenome,
101    F: FitnessValue,
102{
103    config: SteadyStateConfig,
104    bounds: Option<MultiBounds>,
105    selection: Option<S>,
106    crossover: Option<C>,
107    mutation: Option<M>,
108    fitness: Option<Fit>,
109    termination: Option<Term>,
110    _phantom: std::marker::PhantomData<(G, F)>,
111}
112
113impl<G, F> SteadyStateBuilder<G, F, (), (), (), (), ()>
114where
115    G: EvolutionaryGenome,
116    F: FitnessValue,
117{
118    /// Create a new builder with default configuration
119    pub fn new() -> Self {
120        Self {
121            config: SteadyStateConfig::default(),
122            bounds: None,
123            selection: None,
124            crossover: None,
125            mutation: None,
126            fitness: None,
127            termination: None,
128            _phantom: std::marker::PhantomData,
129        }
130    }
131}
132
133impl<G, F> Default for SteadyStateBuilder<G, F, (), (), (), (), ()>
134where
135    G: EvolutionaryGenome,
136    F: FitnessValue,
137{
138    fn default() -> Self {
139        Self::new()
140    }
141}
142
143impl<G, F, S, C, M, Fit, Term> SteadyStateBuilder<G, F, S, C, M, Fit, Term>
144where
145    G: EvolutionaryGenome,
146    F: FitnessValue,
147{
148    /// Set the population size
149    pub fn population_size(mut self, size: usize) -> Self {
150        self.config.population_size = size;
151        self
152    }
153
154    /// Set the number of offspring per step
155    pub fn offspring_count(mut self, count: usize) -> Self {
156        self.config.offspring_count = count;
157        self
158    }
159
160    /// Set the crossover probability
161    pub fn crossover_probability(mut self, probability: f64) -> Self {
162        self.config.crossover_probability = probability;
163        self
164    }
165
166    /// Set the replacement strategy
167    pub fn replacement(mut self, strategy: ReplacementStrategy) -> Self {
168        self.config.replacement = strategy;
169        self
170    }
171
172    /// Enable or disable parallel evaluation
173    pub fn parallel_evaluation(mut self, enabled: bool) -> Self {
174        self.config.parallel_evaluation = enabled;
175        self
176    }
177
178    /// Set the number of steps per generation (for statistics)
179    pub fn steps_per_generation(mut self, steps: usize) -> Self {
180        self.config.steps_per_generation = steps;
181        self
182    }
183
184    /// Enable or disable duplicate avoidance (EV-44).
185    ///
186    /// When enabled, an offspring whose genome equals any current population
187    /// member is rejected rather than inserted. This preserves diversity but adds
188    /// an O(population_size) genome comparison per candidate offspring, and
189    /// requires the genome type to implement [`PartialEq`].
190    pub fn prevent_duplicates(mut self, enabled: bool) -> Self {
191        self.config.prevent_duplicates = enabled;
192        self
193    }
194
195    /// Set the search space bounds
196    pub fn bounds(mut self, bounds: MultiBounds) -> Self {
197        self.bounds = Some(bounds);
198        self
199    }
200
201    /// Set the selection operator
202    pub fn selection<NewS>(self, selection: NewS) -> SteadyStateBuilder<G, F, NewS, C, M, Fit, Term>
203    where
204        NewS: SelectionOperator<G>,
205    {
206        SteadyStateBuilder {
207            config: self.config,
208            bounds: self.bounds,
209            selection: Some(selection),
210            crossover: self.crossover,
211            mutation: self.mutation,
212            fitness: self.fitness,
213            termination: self.termination,
214            _phantom: std::marker::PhantomData,
215        }
216    }
217
218    /// Set the crossover operator
219    pub fn crossover<NewC>(self, crossover: NewC) -> SteadyStateBuilder<G, F, S, NewC, M, Fit, Term>
220    where
221        NewC: CrossoverOperator<G>,
222    {
223        SteadyStateBuilder {
224            config: self.config,
225            bounds: self.bounds,
226            selection: self.selection,
227            crossover: Some(crossover),
228            mutation: self.mutation,
229            fitness: self.fitness,
230            termination: self.termination,
231            _phantom: std::marker::PhantomData,
232        }
233    }
234
235    /// Set the mutation operator
236    pub fn mutation<NewM>(self, mutation: NewM) -> SteadyStateBuilder<G, F, S, C, NewM, Fit, Term>
237    where
238        NewM: MutationOperator<G>,
239    {
240        SteadyStateBuilder {
241            config: self.config,
242            bounds: self.bounds,
243            selection: self.selection,
244            crossover: self.crossover,
245            mutation: Some(mutation),
246            fitness: self.fitness,
247            termination: self.termination,
248            _phantom: std::marker::PhantomData,
249        }
250    }
251
252    /// Set the fitness function
253    pub fn fitness<NewFit>(self, fitness: NewFit) -> SteadyStateBuilder<G, F, S, C, M, NewFit, Term>
254    where
255        NewFit: Fitness<Genome = G, Value = F>,
256    {
257        SteadyStateBuilder {
258            config: self.config,
259            bounds: self.bounds,
260            selection: self.selection,
261            crossover: self.crossover,
262            mutation: self.mutation,
263            fitness: Some(fitness),
264            termination: self.termination,
265            _phantom: std::marker::PhantomData,
266        }
267    }
268
269    /// Set the termination criterion
270    pub fn termination<NewTerm>(
271        self,
272        termination: NewTerm,
273    ) -> SteadyStateBuilder<G, F, S, C, M, Fit, NewTerm>
274    where
275        NewTerm: TerminationCriterion<G, F>,
276    {
277        SteadyStateBuilder {
278            config: self.config,
279            bounds: self.bounds,
280            selection: self.selection,
281            crossover: self.crossover,
282            mutation: self.mutation,
283            fitness: self.fitness,
284            termination: Some(termination),
285            _phantom: std::marker::PhantomData,
286        }
287    }
288
289    /// Set max generations (convenience method)
290    pub fn max_generations(
291        self,
292        max: usize,
293    ) -> SteadyStateBuilder<G, F, S, C, M, Fit, MaxGenerations> {
294        SteadyStateBuilder {
295            config: self.config,
296            bounds: self.bounds,
297            selection: self.selection,
298            crossover: self.crossover,
299            mutation: self.mutation,
300            fitness: self.fitness,
301            termination: Some(MaxGenerations::new(max)),
302            _phantom: std::marker::PhantomData,
303        }
304    }
305}
306
307impl<G, F, S, C, M, Fit, Term> SteadyStateBuilder<G, F, S, C, M, Fit, Term>
308where
309    G: EvolutionaryGenome + Send + Sync,
310    F: FitnessValue + Send,
311    S: SelectionOperator<G>,
312    C: CrossoverOperator<G>,
313    M: MutationOperator<G>,
314    Fit: Fitness<Genome = G, Value = F> + Sync,
315    Term: TerminationCriterion<G, F>,
316{
317    /// Build the SteadyStateGA instance
318    #[allow(clippy::type_complexity)]
319    pub fn build(self) -> Result<SteadyStateGA<G, F, S, C, M, Fit, Term>, EvolutionError> {
320        let bounds = self
321            .bounds
322            .ok_or_else(|| EvolutionError::Configuration("Bounds must be specified".to_string()))?;
323
324        let selection = self.selection.ok_or_else(|| {
325            EvolutionError::Configuration("Selection operator must be specified".to_string())
326        })?;
327
328        let crossover = self.crossover.ok_or_else(|| {
329            EvolutionError::Configuration("Crossover operator must be specified".to_string())
330        })?;
331
332        let mutation = self.mutation.ok_or_else(|| {
333            EvolutionError::Configuration("Mutation operator must be specified".to_string())
334        })?;
335
336        let fitness = self.fitness.ok_or_else(|| {
337            EvolutionError::Configuration("Fitness function must be specified".to_string())
338        })?;
339
340        let termination = self.termination.ok_or_else(|| {
341            EvolutionError::Configuration("Termination criterion must be specified".to_string())
342        })?;
343
344        Ok(SteadyStateGA {
345            config: self.config,
346            bounds,
347            selection,
348            crossover,
349            mutation,
350            fitness,
351            termination,
352            _phantom: std::marker::PhantomData,
353        })
354    }
355}
356
357/// Steady-State Genetic Algorithm
358///
359/// A GA variant that replaces only a few individuals per generation step,
360/// maintaining a more continuous population transition.
361pub struct SteadyStateGA<G, F, S, C, M, Fit, Term>
362where
363    G: EvolutionaryGenome,
364    F: FitnessValue,
365{
366    config: SteadyStateConfig,
367    bounds: MultiBounds,
368    selection: S,
369    crossover: C,
370    mutation: M,
371    fitness: Fit,
372    termination: Term,
373    _phantom: std::marker::PhantomData<(G, F)>,
374}
375
376impl<G, F, S, C, M, Fit, Term> SteadyStateGA<G, F, S, C, M, Fit, Term>
377where
378    G: EvolutionaryGenome + Send + Sync,
379    F: FitnessValue + Send,
380    S: SelectionOperator<G>,
381    C: CrossoverOperator<G>,
382    M: MutationOperator<G>,
383    Fit: Fitness<Genome = G, Value = F> + Sync,
384    Term: TerminationCriterion<G, F>,
385{
386    /// Create a builder for SteadyStateGA
387    pub fn builder() -> SteadyStateBuilder<G, F, (), (), (), (), ()> {
388        SteadyStateBuilder::new()
389    }
390
391    /// Find the index of the individual to replace for the configured strategy.
392    fn find_replacement_index<R: Rng>(&self, population: &Population<G, F>, rng: &mut R) -> usize {
393        match &self.config.replacement {
394            // Both worst-targeting strategies aim at the least-fit individual; the
395            // accept-if-better gate for `ReplaceIfBetter` is applied by the caller.
396            ReplacementStrategy::ReplaceWorst | ReplacementStrategy::ReplaceIfBetter => {
397                // Find index of worst fitness
398                population
399                    .iter()
400                    .enumerate()
401                    .min_by(|(_, a), (_, b)| {
402                        a.fitness_value()
403                            .partial_cmp(b.fitness_value())
404                            .unwrap_or(std::cmp::Ordering::Equal)
405                    })
406                    .map(|(i, _)| i)
407                    .unwrap_or(0)
408            }
409            ReplacementStrategy::ReplaceRandom => rng.gen_range(0..population.len()),
410            ReplacementStrategy::ReplaceParent => {
411                // This is handled specially in the main loop
412                0
413            }
414            ReplacementStrategy::TournamentWorst(tournament_size) => {
415                // Inverse tournament: select worst from tournament
416                let mut worst_idx = rng.gen_range(0..population.len());
417                let mut worst_fitness = population[worst_idx].fitness_value().to_f64();
418
419                for _ in 1..*tournament_size {
420                    let idx = rng.gen_range(0..population.len());
421                    let fitness = population[idx].fitness_value().to_f64();
422                    if fitness < worst_fitness {
423                        worst_idx = idx;
424                        worst_fitness = fitness;
425                    }
426                }
427                worst_idx
428            }
429        }
430    }
431
432    /// Generate exactly `offspring_count` evaluated children (EV-43).
433    ///
434    /// Each returned tuple is `(child, (parent1_idx, parent1_fitness),
435    /// (parent2_idx, parent2_fitness))`; the parent data drives `ReplaceParent`.
436    /// Fresh parents are selected per crossover pair, and only children that will
437    /// actually be considered are mutated and evaluated.
438    #[allow(clippy::type_complexity)]
439    fn generate_offspring<R: Rng>(
440        &self,
441        selection_pool: &[(G, f64)],
442        rng: &mut R,
443    ) -> Vec<(Individual<G, F>, (usize, f64), (usize, f64))> {
444        let target = self.config.offspring_count;
445        let mut offspring = Vec::with_capacity(target);
446
447        while offspring.len() < target {
448            let p1_idx = self.selection.select(selection_pool, rng);
449            let p2_idx = self.selection.select(selection_pool, rng);
450            let p1 = (p1_idx, selection_pool[p1_idx].1);
451            let p2 = (p2_idx, selection_pool[p2_idx].1);
452            let parent1 = &selection_pool[p1_idx].0;
453            let parent2 = &selection_pool[p2_idx].0;
454
455            let (mut child1, mut child2) = if rng.gen::<f64>() < self.config.crossover_probability {
456                match self.crossover.crossover(parent1, parent2, rng).genome() {
457                    Some((c1, c2)) => (c1, c2),
458                    None => (parent1.clone(), parent2.clone()),
459                }
460            } else {
461                (parent1.clone(), parent2.clone())
462            };
463
464            self.mutation.mutate(&mut child1, rng);
465            let mut ind1 = Individual::new(child1);
466            ind1.set_fitness(self.fitness.evaluate(ind1.genome()));
467            offspring.push((ind1, p1, p2));
468
469            if offspring.len() < target {
470                self.mutation.mutate(&mut child2, rng);
471                let mut ind2 = Individual::new(child2);
472                ind2.set_fitness(self.fitness.evaluate(ind2.genome()));
473                offspring.push((ind2, p1, p2));
474            }
475        }
476
477        offspring
478    }
479
480    /// Insert an already-evaluated `child` into `population` per the configured
481    /// replacement strategy (EV-42) and duplicate policy (EV-44).
482    ///
483    /// The population may be left unchanged: a duplicate is rejected when
484    /// `prevent_duplicates` is set, `ReplaceParent` skips when the child does not
485    /// beat its worse parent, and `ReplaceIfBetter` skips when the child does not
486    /// beat the individual it targets. All other strategies replace their chosen
487    /// index unconditionally.
488    fn place_offspring<R: Rng>(
489        &self,
490        population: &mut Population<G, F>,
491        child: Individual<G, F>,
492        parent1: (usize, f64),
493        parent2: (usize, f64),
494        rng: &mut R,
495    ) where
496        G: PartialEq,
497    {
498        // EV-44: reject an exact duplicate of an existing genome if configured
499        // (O(population_size) genome comparison).
500        if self.config.prevent_duplicates
501            && population.iter().any(|ind| ind.genome() == child.genome())
502        {
503            return;
504        }
505
506        let replace_idx = match &self.config.replacement {
507            ReplacementStrategy::ReplaceParent => {
508                let (p1_idx, p1_fit) = parent1;
509                let (p2_idx, p2_fit) = parent2;
510                let child_fit = child.fitness_value().to_f64();
511                if child_fit > p1_fit.min(p2_fit) {
512                    if p1_fit < p2_fit {
513                        p1_idx
514                    } else {
515                        p2_idx
516                    }
517                } else {
518                    return; // offspring did not beat its worse parent
519                }
520            }
521            _ => self.find_replacement_index(population, rng),
522        };
523
524        // EV-42: only the elitist ReplaceIfBetter gates on improvement. Every
525        // other strategy (ReplaceRandom, ReplaceWorst, TournamentWorst) replaces
526        // its chosen index unconditionally, as documented.
527        if self.config.replacement.requires_improvement()
528            && !child
529                .fitness_value()
530                .is_better_than(population[replace_idx].fitness_value())
531        {
532            return;
533        }
534
535        population[replace_idx] = child;
536    }
537
538    /// Run the steady-state genetic algorithm.
539    ///
540    /// Requires `G: PartialEq` so the optional duplicate-avoidance policy
541    /// (`prevent_duplicates`) can compare genomes; all built-in genome types
542    /// satisfy this.
543    pub fn run<R: Rng>(&self, rng: &mut R) -> Result<EvolutionResult<G, F>, EvolutionError>
544    where
545        G: PartialEq,
546    {
547        let start_time = Instant::now();
548
549        // Initialize population
550        let mut population: Population<G, F> =
551            Population::random(self.config.population_size, &self.bounds, rng);
552
553        // Evaluate initial population
554        if self.config.parallel_evaluation {
555            population.evaluate_parallel(&self.fitness);
556        } else {
557            population.evaluate(&self.fitness);
558        }
559
560        let mut stats = EvolutionStats::new();
561        let mut evaluations = population.len();
562        let mut fitness_history: Vec<f64> = Vec::new();
563        let mut step_count = 0usize;
564        let mut generation = 0usize;
565
566        // Track best individual
567        let mut best_individual = population
568            .best()
569            .ok_or(EvolutionError::EmptyPopulation)?
570            .clone();
571
572        // Record initial statistics
573        let gen_stats = GenerationStats::from_population(&population, 0, evaluations);
574        fitness_history.push(gen_stats.best_fitness);
575        stats.record(gen_stats);
576
577        // Main evolution loop
578        loop {
579            // Check termination
580            let state = EvolutionState {
581                generation,
582                evaluations,
583                best_fitness: best_individual.fitness_value().to_f64(),
584                population: &population,
585                fitness_history: &fitness_history,
586            };
587
588            if self.termination.should_terminate(&state) {
589                stats.set_termination_reason(self.termination.reason());
590                break;
591            }
592
593            let step_start = Instant::now();
594
595            // Selection pool
596            let selection_pool: Vec<(G, f64)> = population.as_fitness_pairs();
597
598            // EV-43: generate and evaluate EXACTLY offspring_count children — no
599            // more, no fewer — so wasted evaluations don't inflate the counter or
600            // trip MaxEvaluations early, and offspring_count > 2 is honored.
601            let offspring = self.generate_offspring(&selection_pool, rng);
602            evaluations += offspring.len();
603
604            // Replace individuals in the population.
605            for (child, parent1, parent2) in offspring {
606                self.place_offspring(&mut population, child, parent1, parent2, rng);
607            }
608
609            // Update best individual
610            if let Some(best) = population.best() {
611                if best.is_better_than(&best_individual) {
612                    best_individual = best.clone();
613                }
614            }
615
616            step_count += 1;
617
618            // Record statistics at generation boundaries
619            if step_count.is_multiple_of(self.config.steps_per_generation) {
620                generation += 1;
621                population.set_generation(generation);
622
623                let timing = TimingStats::new()
624                    .with_total(step_start.elapsed() * self.config.steps_per_generation as u32);
625
626                let gen_stats =
627                    GenerationStats::from_population(&population, generation, evaluations)
628                        .with_timing(timing);
629                fitness_history.push(gen_stats.best_fitness);
630                stats.record(gen_stats);
631            }
632        }
633
634        stats.set_runtime(start_time.elapsed());
635
636        Ok(EvolutionResult::new(
637            best_individual.genome,
638            best_individual.fitness.unwrap(),
639            generation,
640            evaluations,
641        )
642        .with_stats(stats))
643    }
644}
645
646// Implement bounded operators version
647impl<G, F, S, C, M, Fit, Term> SteadyStateGA<G, F, S, C, M, Fit, Term>
648where
649    G: EvolutionaryGenome + Send + Sync,
650    F: FitnessValue + Send,
651    S: SelectionOperator<G>,
652    C: BoundedCrossoverOperator<G>,
653    M: BoundedMutationOperator<G>,
654    Fit: Fitness<Genome = G, Value = F> + Sync,
655    Term: TerminationCriterion<G, F>,
656{
657    /// Generate exactly `offspring_count` evaluated children with bounded
658    /// operators (EV-43). See [`SteadyStateGA::generate_offspring`].
659    #[allow(clippy::type_complexity)]
660    fn generate_offspring_bounded<R: Rng>(
661        &self,
662        selection_pool: &[(G, f64)],
663        rng: &mut R,
664    ) -> Vec<(Individual<G, F>, (usize, f64), (usize, f64))> {
665        let target = self.config.offspring_count;
666        let mut offspring = Vec::with_capacity(target);
667
668        while offspring.len() < target {
669            let p1_idx = self.selection.select(selection_pool, rng);
670            let p2_idx = self.selection.select(selection_pool, rng);
671            let p1 = (p1_idx, selection_pool[p1_idx].1);
672            let p2 = (p2_idx, selection_pool[p2_idx].1);
673            let parent1 = &selection_pool[p1_idx].0;
674            let parent2 = &selection_pool[p2_idx].0;
675
676            let (mut child1, mut child2) = if rng.gen::<f64>() < self.config.crossover_probability {
677                match self
678                    .crossover
679                    .crossover_bounded(parent1, parent2, &self.bounds, rng)
680                    .genome()
681                {
682                    Some((c1, c2)) => (c1, c2),
683                    None => (parent1.clone(), parent2.clone()),
684                }
685            } else {
686                (parent1.clone(), parent2.clone())
687            };
688
689            self.mutation.mutate_bounded(&mut child1, &self.bounds, rng);
690            let mut ind1 = Individual::new(child1);
691            ind1.set_fitness(self.fitness.evaluate(ind1.genome()));
692            offspring.push((ind1, p1, p2));
693
694            if offspring.len() < target {
695                self.mutation.mutate_bounded(&mut child2, &self.bounds, rng);
696                let mut ind2 = Individual::new(child2);
697                ind2.set_fitness(self.fitness.evaluate(ind2.genome()));
698                offspring.push((ind2, p1, p2));
699            }
700        }
701
702        offspring
703    }
704
705    /// Run the steady-state genetic algorithm with bounded operators.
706    ///
707    /// Requires `G: PartialEq` for the optional `prevent_duplicates` policy.
708    pub fn run_bounded<R: Rng>(&self, rng: &mut R) -> Result<EvolutionResult<G, F>, EvolutionError>
709    where
710        G: PartialEq,
711    {
712        let start_time = Instant::now();
713
714        // Initialize population
715        let mut population: Population<G, F> =
716            Population::random(self.config.population_size, &self.bounds, rng);
717
718        // Evaluate initial population
719        if self.config.parallel_evaluation {
720            population.evaluate_parallel(&self.fitness);
721        } else {
722            population.evaluate(&self.fitness);
723        }
724
725        let mut stats = EvolutionStats::new();
726        let mut evaluations = population.len();
727        let mut fitness_history: Vec<f64> = Vec::new();
728        let mut step_count = 0usize;
729        let mut generation = 0usize;
730
731        // Track best individual
732        let mut best_individual = population
733            .best()
734            .ok_or(EvolutionError::EmptyPopulation)?
735            .clone();
736
737        // Record initial statistics
738        let gen_stats = GenerationStats::from_population(&population, 0, evaluations);
739        fitness_history.push(gen_stats.best_fitness);
740        stats.record(gen_stats);
741
742        // Main evolution loop
743        loop {
744            // Check termination
745            let state = EvolutionState {
746                generation,
747                evaluations,
748                best_fitness: best_individual.fitness_value().to_f64(),
749                population: &population,
750                fitness_history: &fitness_history,
751            };
752
753            if self.termination.should_terminate(&state) {
754                stats.set_termination_reason(self.termination.reason());
755                break;
756            }
757
758            // Selection pool
759            let selection_pool: Vec<(G, f64)> = population.as_fitness_pairs();
760
761            // EV-43: generate and evaluate EXACTLY offspring_count children with
762            // bounded operators.
763            let offspring = self.generate_offspring_bounded(&selection_pool, rng);
764            evaluations += offspring.len();
765
766            // Replace individuals in the population.
767            for (child, parent1, parent2) in offspring {
768                self.place_offspring(&mut population, child, parent1, parent2, rng);
769            }
770
771            // Update best individual
772            if let Some(best) = population.best() {
773                if best.is_better_than(&best_individual) {
774                    best_individual = best.clone();
775                }
776            }
777
778            step_count += 1;
779
780            // Record statistics at generation boundaries
781            if step_count.is_multiple_of(self.config.steps_per_generation) {
782                generation += 1;
783                population.set_generation(generation);
784
785                let gen_stats =
786                    GenerationStats::from_population(&population, generation, evaluations);
787                fitness_history.push(gen_stats.best_fitness);
788                stats.record(gen_stats);
789            }
790        }
791
792        stats.set_runtime(start_time.elapsed());
793
794        Ok(EvolutionResult::new(
795            best_individual.genome,
796            best_individual.fitness.unwrap(),
797            generation,
798            evaluations,
799        )
800        .with_stats(stats))
801    }
802}
803
804#[cfg(test)]
805mod tests {
806    use super::*;
807    use crate::fitness::benchmarks::{OneMax, Sphere};
808    use crate::genome::real_vector::RealVector;
809    use crate::genome::traits::RealValuedGenome;
810    use crate::operators::crossover::{SbxCrossover, UniformCrossover};
811    use crate::operators::mutation::{BitFlipMutation, PolynomialMutation};
812    use crate::operators::selection::TournamentSelection;
813    use crate::termination::MaxEvaluations;
814    use rand::SeedableRng;
815
816    #[test]
817    fn test_steady_state_builder() {
818        let bounds = MultiBounds::symmetric(5.0, 10);
819        let ga = SteadyStateBuilder::new()
820            .population_size(50)
821            .offspring_count(2)
822            .bounds(bounds)
823            .selection(TournamentSelection::new(3))
824            .crossover(SbxCrossover::new(20.0))
825            .mutation(PolynomialMutation::new(20.0))
826            .fitness(Sphere::new(10))
827            .max_generations(10)
828            .build();
829
830        assert!(ga.is_ok());
831    }
832
833    #[test]
834    fn test_steady_state_sphere() {
835        let mut rng = rand::thread_rng();
836        let bounds = MultiBounds::symmetric(5.12, 10);
837
838        let ga = SteadyStateBuilder::new()
839            .population_size(50)
840            .offspring_count(2)
841            .steps_per_generation(25)
842            .bounds(bounds)
843            .selection(TournamentSelection::new(3))
844            .crossover(SbxCrossover::new(20.0))
845            .mutation(PolynomialMutation::new(20.0))
846            .fitness(Sphere::new(10))
847            .termination(MaxEvaluations::new(2000))
848            .build()
849            .unwrap();
850
851        let result = ga.run(&mut rng).unwrap();
852
853        // Should find some improvement
854        assert!(
855            result.best_fitness > -200.0,
856            "Expected fitness > -200, got {}",
857            result.best_fitness
858        );
859        assert!(result.evaluations <= 2000);
860    }
861
862    #[test]
863    fn test_steady_state_onemax() {
864        let mut rng = rand::thread_rng();
865        let bounds = MultiBounds::uniform(crate::genome::bounds::Bounds::unit(), 20);
866
867        let ga = SteadyStateBuilder::new()
868            .population_size(50)
869            .offspring_count(2)
870            .steps_per_generation(25)
871            .bounds(bounds)
872            .selection(TournamentSelection::new(3))
873            .crossover(UniformCrossover::new())
874            .mutation(BitFlipMutation::new())
875            .fitness(OneMax::new(20))
876            .termination(MaxEvaluations::new(2000))
877            .build()
878            .unwrap();
879
880        let result = ga.run(&mut rng).unwrap();
881
882        // Should find good solution
883        assert!(result.best_fitness >= 15); // At least 75% ones
884    }
885
886    #[test]
887    fn test_replacement_strategies() {
888        let mut rng = rand::thread_rng();
889        let bounds = MultiBounds::symmetric(5.12, 5);
890
891        let strategies = vec![
892            ReplacementStrategy::ReplaceWorst,
893            ReplacementStrategy::ReplaceRandom,
894            ReplacementStrategy::TournamentWorst(3),
895        ];
896
897        for strategy in strategies {
898            let ga = SteadyStateBuilder::new()
899                .population_size(30)
900                .offspring_count(2)
901                .replacement(strategy)
902                .bounds(bounds.clone())
903                .selection(TournamentSelection::new(3))
904                .crossover(SbxCrossover::new(20.0))
905                .mutation(PolynomialMutation::new(20.0))
906                .fitness(Sphere::new(5))
907                .termination(MaxEvaluations::new(500))
908                .build()
909                .unwrap();
910
911            let result = ga.run(&mut rng);
912            assert!(result.is_ok());
913        }
914    }
915
916    #[test]
917    fn test_steady_state_bounded() {
918        let mut rng = rand::thread_rng();
919        let bounds = MultiBounds::symmetric(5.12, 10);
920
921        let ga = SteadyStateBuilder::new()
922            .population_size(50)
923            .bounds(bounds.clone())
924            .selection(TournamentSelection::new(3))
925            .crossover(SbxCrossover::new(20.0))
926            .mutation(PolynomialMutation::new(20.0))
927            .fitness(Sphere::new(10))
928            .termination(MaxEvaluations::new(1000))
929            .build()
930            .unwrap();
931
932        let result = ga.run_bounded(&mut rng).unwrap();
933
934        // All genes should be within bounds
935        for gene in result.best_genome.genes() {
936            assert!(*gene >= -5.12 && *gene <= 5.12);
937        }
938    }
939
940    // regression: EV-43 — with offspring_count = 1, exactly one child is evaluated
941    // per step. Starting from a pop of 10 (10 initial evals) under a budget of 15,
942    // the fixed code stops at exactly 15; the pre-fix code evaluated 2 per step and
943    // overshot to 16.
944    #[test]
945    fn test_offspring_count_one_evaluates_one_per_step() {
946        let mut rng = rand::rngs::StdRng::seed_from_u64(11);
947        let bounds = MultiBounds::symmetric(5.12, 5);
948        let ga = SteadyStateBuilder::new()
949            .population_size(10)
950            .offspring_count(1)
951            .steps_per_generation(1)
952            .bounds(bounds)
953            .selection(TournamentSelection::new(2))
954            .crossover(SbxCrossover::new(20.0))
955            .mutation(PolynomialMutation::new(20.0))
956            .fitness(Sphere::new(5))
957            .termination(MaxEvaluations::new(15))
958            .build()
959            .unwrap();
960
961        let result = ga.run(&mut rng).unwrap();
962        assert_eq!(result.evaluations, 15);
963    }
964
965    // regression: EV-42 — ReplaceRandom replaces unconditionally, so a worse
966    // offspring can enter and the population's WORST fitness can degrade across
967    // steps. The pre-fix accept-if-better guard kept the worst monotone, so no
968    // degradation could ever appear.
969    #[test]
970    fn test_replace_random_accepts_worse_offspring() {
971        let mut rng = rand::rngs::StdRng::seed_from_u64(20);
972        let bounds = MultiBounds::symmetric(5.12, 5);
973        let ga = SteadyStateBuilder::new()
974            .population_size(20)
975            .offspring_count(1)
976            .steps_per_generation(1)
977            .replacement(ReplacementStrategy::ReplaceRandom)
978            .bounds(bounds)
979            .selection(TournamentSelection::new(2))
980            .crossover(SbxCrossover::new(2.0))
981            .mutation(PolynomialMutation::new(2.0))
982            .fitness(Sphere::new(5))
983            .termination(MaxEvaluations::new(400))
984            .build()
985            .unwrap();
986
987        let result = ga.run(&mut rng).unwrap();
988        let worst: Vec<f64> = result
989            .stats
990            .generations
991            .iter()
992            .map(|g| g.worst_fitness)
993            .collect();
994        let degraded = worst.windows(2).any(|w| w[1] < w[0] - 1e-12);
995        assert!(
996            degraded,
997            "ReplaceRandom must let the population worst degrade at least once"
998        );
999    }
1000
1001    // regression: EV-44 — with prevent_duplicates, an offspring whose genome equals
1002    // an existing member is rejected instead of inserted, even if it is fitter.
1003    #[test]
1004    fn test_prevent_duplicates_rejects_existing_genome() {
1005        let mut rng = rand::rngs::StdRng::seed_from_u64(3);
1006        let bounds = MultiBounds::symmetric(5.0, 3);
1007        let ga = SteadyStateBuilder::new()
1008            .population_size(5)
1009            .offspring_count(1)
1010            .replacement(ReplacementStrategy::ReplaceRandom)
1011            .prevent_duplicates(true)
1012            .bounds(bounds)
1013            .selection(TournamentSelection::new(2))
1014            .crossover(SbxCrossover::new(20.0))
1015            .mutation(PolynomialMutation::new(20.0))
1016            .fitness(Sphere::new(3))
1017            .max_generations(1)
1018            .build()
1019            .unwrap();
1020
1021        // A population of distinct genomes.
1022        let mut pop: Population<RealVector, f64> = Population::new();
1023        for i in 0..5 {
1024            let mut ind = Individual::new(RealVector::new(vec![i as f64, 0.0, 0.0]));
1025            ind.set_fitness(-(i as f64));
1026            pop.push(ind);
1027        }
1028
1029        // A child equal to an existing member is rejected (population unchanged),
1030        // even though its fitness is better.
1031        let mut dup = Individual::new(RealVector::new(vec![2.0, 0.0, 0.0]));
1032        dup.set_fitness(100.0);
1033        let before: Vec<RealVector> = pop.iter().map(|i| i.genome().clone()).collect();
1034        ga.place_offspring(&mut pop, dup, (0, 0.0), (0, 0.0), &mut rng);
1035        let after: Vec<RealVector> = pop.iter().map(|i| i.genome().clone()).collect();
1036        assert_eq!(before, after, "duplicate offspring must be rejected");
1037
1038        // A novel genome is accepted (ReplaceRandom, unconditional).
1039        let mut novel = Individual::new(RealVector::new(vec![42.0, 0.0, 0.0]));
1040        novel.set_fitness(-999.0);
1041        let novel_genome = novel.genome().clone();
1042        ga.place_offspring(&mut pop, novel, (0, 0.0), (0, 0.0), &mut rng);
1043        assert!(
1044            pop.iter().any(|i| *i.genome() == novel_genome),
1045            "a novel genome should be inserted"
1046        );
1047    }
1048}
fugue_evo/algorithms/steady_state.rs

fugue_evo/algorithms/
steady_state.rs
