fugue_evo/algorithms/
simple_ga.rs

1//! Simple Genetic Algorithm
2//!
3//! This module implements a standard generational genetic algorithm.
4
5use std::time::Instant;
6
7use rand::Rng;
8
9use crate::diagnostics::{EvolutionResult, EvolutionStats, GenerationStats, TimingStats};
10use crate::error::EvolutionError;
11use crate::fitness::traits::{Fitness, FitnessValue};
12use crate::genome::bounds::MultiBounds;
13use crate::genome::traits::EvolutionaryGenome;
14use crate::operators::traits::{
15    BoundedCrossoverOperator, BoundedMutationOperator, CrossoverOperator, MutationOperator,
16    SelectionOperator,
17};
18use crate::population::individual::Individual;
19use crate::population::population::Population;
20use crate::termination::{EvolutionState, MaxGenerations, TerminationCriterion};
21
22/// Configuration for the Simple GA
23#[derive(Clone, Debug)]
24pub struct SimpleGAConfig {
25    /// Population size
26    pub population_size: usize,
27    /// Whether to use elitism (preserve best individual)
28    pub elitism: bool,
29    /// Number of elite individuals to preserve
30    pub elite_count: usize,
31    /// Crossover probability
32    pub crossover_probability: f64,
33    /// Whether to evaluate in parallel
34    pub parallel_evaluation: bool,
35}
36
37impl Default for SimpleGAConfig {
38    fn default() -> Self {
39        Self {
40            population_size: 100,
41            elitism: true,
42            elite_count: 1,
43            crossover_probability: 0.9,
44            parallel_evaluation: true,
45        }
46    }
47}
48
49/// Builder for SimpleGA
50pub struct SimpleGABuilder<G, F, S, C, M, Fit, Term>
51where
52    G: EvolutionaryGenome,
53    F: FitnessValue,
54{
55    config: SimpleGAConfig,
56    bounds: Option<MultiBounds>,
57    selection: Option<S>,
58    crossover: Option<C>,
59    mutation: Option<M>,
60    fitness: Option<Fit>,
61    termination: Option<Term>,
62    _phantom: std::marker::PhantomData<(G, F)>,
63}
64
65impl<G, F> SimpleGABuilder<G, F, (), (), (), (), ()>
66where
67    G: EvolutionaryGenome,
68    F: FitnessValue,
69{
70    /// Create a new builder with default configuration
71    pub fn new() -> Self {
72        Self {
73            config: SimpleGAConfig::default(),
74            bounds: None,
75            selection: None,
76            crossover: None,
77            mutation: None,
78            fitness: None,
79            termination: None,
80            _phantom: std::marker::PhantomData,
81        }
82    }
83}
84
85impl<G, F> Default for SimpleGABuilder<G, F, (), (), (), (), ()>
86where
87    G: EvolutionaryGenome,
88    F: FitnessValue,
89{
90    fn default() -> Self {
91        Self::new()
92    }
93}
94
95impl<G, F, S, C, M, Fit, Term> SimpleGABuilder<G, F, S, C, M, Fit, Term>
96where
97    G: EvolutionaryGenome,
98    F: FitnessValue,
99{
100    /// Set the population size
101    pub fn population_size(mut self, size: usize) -> Self {
102        self.config.population_size = size;
103        self
104    }
105
106    /// Enable or disable elitism
107    pub fn elitism(mut self, enabled: bool) -> Self {
108        self.config.elitism = enabled;
109        self
110    }
111
112    /// Set the number of elite individuals to preserve
113    pub fn elite_count(mut self, count: usize) -> Self {
114        self.config.elite_count = count;
115        self
116    }
117
118    /// Set the crossover probability
119    pub fn crossover_probability(mut self, probability: f64) -> Self {
120        self.config.crossover_probability = probability;
121        self
122    }
123
124    /// Enable or disable parallel evaluation
125    pub fn parallel_evaluation(mut self, enabled: bool) -> Self {
126        self.config.parallel_evaluation = enabled;
127        self
128    }
129
130    /// Set the search space bounds
131    pub fn bounds(mut self, bounds: MultiBounds) -> Self {
132        self.bounds = Some(bounds);
133        self
134    }
135
136    /// Set the selection operator
137    pub fn selection<NewS>(self, selection: NewS) -> SimpleGABuilder<G, F, NewS, C, M, Fit, Term>
138    where
139        NewS: SelectionOperator<G>,
140    {
141        SimpleGABuilder {
142            config: self.config,
143            bounds: self.bounds,
144            selection: Some(selection),
145            crossover: self.crossover,
146            mutation: self.mutation,
147            fitness: self.fitness,
148            termination: self.termination,
149            _phantom: std::marker::PhantomData,
150        }
151    }
152
153    /// Set the crossover operator
154    pub fn crossover<NewC>(self, crossover: NewC) -> SimpleGABuilder<G, F, S, NewC, M, Fit, Term>
155    where
156        NewC: CrossoverOperator<G>,
157    {
158        SimpleGABuilder {
159            config: self.config,
160            bounds: self.bounds,
161            selection: self.selection,
162            crossover: Some(crossover),
163            mutation: self.mutation,
164            fitness: self.fitness,
165            termination: self.termination,
166            _phantom: std::marker::PhantomData,
167        }
168    }
169
170    /// Set the mutation operator
171    pub fn mutation<NewM>(self, mutation: NewM) -> SimpleGABuilder<G, F, S, C, NewM, Fit, Term>
172    where
173        NewM: MutationOperator<G>,
174    {
175        SimpleGABuilder {
176            config: self.config,
177            bounds: self.bounds,
178            selection: self.selection,
179            crossover: self.crossover,
180            mutation: Some(mutation),
181            fitness: self.fitness,
182            termination: self.termination,
183            _phantom: std::marker::PhantomData,
184        }
185    }
186
187    /// Set the fitness function
188    pub fn fitness<NewFit>(self, fitness: NewFit) -> SimpleGABuilder<G, F, S, C, M, NewFit, Term>
189    where
190        NewFit: Fitness<Genome = G, Value = F>,
191    {
192        SimpleGABuilder {
193            config: self.config,
194            bounds: self.bounds,
195            selection: self.selection,
196            crossover: self.crossover,
197            mutation: self.mutation,
198            fitness: Some(fitness),
199            termination: self.termination,
200            _phantom: std::marker::PhantomData,
201        }
202    }
203
204    /// Set the termination criterion
205    pub fn termination<NewTerm>(
206        self,
207        termination: NewTerm,
208    ) -> SimpleGABuilder<G, F, S, C, M, Fit, NewTerm>
209    where
210        NewTerm: TerminationCriterion<G, F>,
211    {
212        SimpleGABuilder {
213            config: self.config,
214            bounds: self.bounds,
215            selection: self.selection,
216            crossover: self.crossover,
217            mutation: self.mutation,
218            fitness: self.fitness,
219            termination: Some(termination),
220            _phantom: std::marker::PhantomData,
221        }
222    }
223
224    /// Set max generations (convenience method)
225    pub fn max_generations(
226        self,
227        max: usize,
228    ) -> SimpleGABuilder<G, F, S, C, M, Fit, MaxGenerations> {
229        SimpleGABuilder {
230            config: self.config,
231            bounds: self.bounds,
232            selection: self.selection,
233            crossover: self.crossover,
234            mutation: self.mutation,
235            fitness: self.fitness,
236            termination: Some(MaxGenerations::new(max)),
237            _phantom: std::marker::PhantomData,
238        }
239    }
240}
241
242// Builder build() method - parallel version with Send + Sync bounds
243#[cfg(feature = "parallel")]
244impl<G, F, S, C, M, Fit, Term> SimpleGABuilder<G, F, S, C, M, Fit, Term>
245where
246    G: EvolutionaryGenome + Send + Sync,
247    F: FitnessValue + Send,
248    S: SelectionOperator<G>,
249    C: CrossoverOperator<G>,
250    M: MutationOperator<G>,
251    Fit: Fitness<Genome = G, Value = F> + Sync,
252    Term: TerminationCriterion<G, F>,
253{
254    /// Build the SimpleGA instance
255    #[allow(clippy::type_complexity)]
256    pub fn build(self) -> Result<SimpleGA<G, F, S, C, M, Fit, Term>, EvolutionError> {
257        let bounds = self
258            .bounds
259            .ok_or_else(|| EvolutionError::Configuration("Bounds must be specified".to_string()))?;
260
261        let selection = self.selection.ok_or_else(|| {
262            EvolutionError::Configuration("Selection operator must be specified".to_string())
263        })?;
264
265        let crossover = self.crossover.ok_or_else(|| {
266            EvolutionError::Configuration("Crossover operator must be specified".to_string())
267        })?;
268
269        let mutation = self.mutation.ok_or_else(|| {
270            EvolutionError::Configuration("Mutation operator must be specified".to_string())
271        })?;
272
273        let fitness = self.fitness.ok_or_else(|| {
274            EvolutionError::Configuration("Fitness function must be specified".to_string())
275        })?;
276
277        let termination = self.termination.ok_or_else(|| {
278            EvolutionError::Configuration("Termination criterion must be specified".to_string())
279        })?;
280
281        Ok(SimpleGA {
282            config: self.config,
283            bounds,
284            selection,
285            crossover,
286            mutation,
287            fitness,
288            termination,
289            _phantom: std::marker::PhantomData,
290        })
291    }
292}
293
294// Builder build() method - non-parallel version without Send + Sync bounds
295#[cfg(not(feature = "parallel"))]
296impl<G, F, S, C, M, Fit, Term> SimpleGABuilder<G, F, S, C, M, Fit, Term>
297where
298    G: EvolutionaryGenome,
299    F: FitnessValue,
300    S: SelectionOperator<G>,
301    C: CrossoverOperator<G>,
302    M: MutationOperator<G>,
303    Fit: Fitness<Genome = G, Value = F>,
304    Term: TerminationCriterion<G, F>,
305{
306    /// Build the SimpleGA instance
307    #[allow(clippy::type_complexity)]
308    pub fn build(self) -> Result<SimpleGA<G, F, S, C, M, Fit, Term>, EvolutionError> {
309        let bounds = self
310            .bounds
311            .ok_or_else(|| EvolutionError::Configuration("Bounds must be specified".to_string()))?;
312
313        let selection = self.selection.ok_or_else(|| {
314            EvolutionError::Configuration("Selection operator must be specified".to_string())
315        })?;
316
317        let crossover = self.crossover.ok_or_else(|| {
318            EvolutionError::Configuration("Crossover operator must be specified".to_string())
319        })?;
320
321        let mutation = self.mutation.ok_or_else(|| {
322            EvolutionError::Configuration("Mutation operator must be specified".to_string())
323        })?;
324
325        let fitness = self.fitness.ok_or_else(|| {
326            EvolutionError::Configuration("Fitness function must be specified".to_string())
327        })?;
328
329        let termination = self.termination.ok_or_else(|| {
330            EvolutionError::Configuration("Termination criterion must be specified".to_string())
331        })?;
332
333        Ok(SimpleGA {
334            config: self.config,
335            bounds,
336            selection,
337            crossover,
338            mutation,
339            fitness,
340            termination,
341            _phantom: std::marker::PhantomData,
342        })
343    }
344}
345
346/// Simple Genetic Algorithm
347///
348/// A standard generational GA with configurable operators.
349pub struct SimpleGA<G, F, S, C, M, Fit, Term>
350where
351    G: EvolutionaryGenome,
352    F: FitnessValue,
353{
354    config: SimpleGAConfig,
355    bounds: MultiBounds,
356    selection: S,
357    crossover: C,
358    mutation: M,
359    fitness: Fit,
360    termination: Term,
361    _phantom: std::marker::PhantomData<(G, F)>,
362}
363
364// Parallel version with Send + Sync bounds
365#[cfg(feature = "parallel")]
366impl<G, F, S, C, M, Fit, Term> SimpleGA<G, F, S, C, M, Fit, Term>
367where
368    G: EvolutionaryGenome + Send + Sync,
369    F: FitnessValue + Send,
370    S: SelectionOperator<G>,
371    C: CrossoverOperator<G>,
372    M: MutationOperator<G>,
373    Fit: Fitness<Genome = G, Value = F> + Sync,
374    Term: TerminationCriterion<G, F>,
375{
376    /// Create a builder for SimpleGA
377    pub fn builder() -> SimpleGABuilder<G, F, (), (), (), (), ()> {
378        SimpleGABuilder::new()
379    }
380
381    /// Run the genetic algorithm
382    pub fn run<R: Rng>(&self, rng: &mut R) -> Result<EvolutionResult<G, F>, EvolutionError> {
383        let start_time = Instant::now();
384
385        // Initialize population
386        let mut population: Population<G, F> =
387            Population::random(self.config.population_size, &self.bounds, rng);
388
389        // Evaluate initial population
390        let eval_start = Instant::now();
391        if self.config.parallel_evaluation {
392            population.evaluate_parallel(&self.fitness);
393        } else {
394            population.evaluate(&self.fitness);
395        }
396        let eval_time = eval_start.elapsed();
397
398        let mut stats = EvolutionStats::new();
399        let mut evaluations = population.len();
400        let mut fitness_history: Vec<f64> = Vec::new();
401
402        // Track best individual
403        let mut best_individual = population
404            .best()
405            .ok_or(EvolutionError::EmptyPopulation)?
406            .clone();
407
408        // Record initial statistics
409        let gen_stats = GenerationStats::from_population(&population, 0, evaluations)
410            .with_timing(TimingStats::new().with_evaluation(eval_time));
411        fitness_history.push(gen_stats.best_fitness);
412        stats.record(gen_stats);
413
414        // Main evolution loop
415        loop {
416            // Check termination
417            let state = EvolutionState {
418                generation: population.generation(),
419                evaluations,
420                best_fitness: best_individual.fitness_value().to_f64(),
421                population: &population,
422                fitness_history: &fitness_history,
423            };
424
425            if self.termination.should_terminate(&state) {
426                stats.set_termination_reason(self.termination.reason());
427                break;
428            }
429
430            let gen_start = Instant::now();
431
432            // Create new generation
433            let mut new_population: Population<G, F> =
434                Population::with_capacity(self.config.population_size);
435
436            // Elitism: copy best individuals
437            if self.config.elitism {
438                let mut sorted = population.clone();
439                sorted.sort_by_fitness();
440                for i in 0..self.config.elite_count.min(sorted.len()) {
441                    new_population.push(sorted[i].clone());
442                }
443            }
444
445            // Selection pool
446            let selection_pool: Vec<(G, f64)> = population.as_fitness_pairs();
447
448            // Generate offspring
449            let _selection_start = Instant::now();
450            let mut selection_time = std::time::Duration::ZERO;
451            let mut crossover_time = std::time::Duration::ZERO;
452            let mut mutation_time = std::time::Duration::ZERO;
453
454            while new_population.len() < self.config.population_size {
455                // Selection
456                let sel_start = Instant::now();
457                let parent1_idx = self.selection.select(&selection_pool, rng);
458                let parent2_idx = self.selection.select(&selection_pool, rng);
459                selection_time += sel_start.elapsed();
460
461                let parent1 = &selection_pool[parent1_idx].0;
462                let parent2 = &selection_pool[parent2_idx].0;
463
464                // Crossover
465                let cross_start = Instant::now();
466                let (mut child1, mut child2) =
467                    if rng.gen::<f64>() < self.config.crossover_probability {
468                        match self.crossover.crossover(parent1, parent2, rng).genome() {
469                            Some((c1, c2)) => (c1, c2),
470                            None => (parent1.clone(), parent2.clone()),
471                        }
472                    } else {
473                        (parent1.clone(), parent2.clone())
474                    };
475                crossover_time += cross_start.elapsed();
476
477                // Mutation
478                let mut_start = Instant::now();
479                self.mutation.mutate(&mut child1, rng);
480                self.mutation.mutate(&mut child2, rng);
481                mutation_time += mut_start.elapsed();
482
483                // Add to new population
484                new_population.push(Individual::with_generation(
485                    child1,
486                    population.generation() + 1,
487                ));
488                if new_population.len() < self.config.population_size {
489                    new_population.push(Individual::with_generation(
490                        child2,
491                        population.generation() + 1,
492                    ));
493                }
494            }
495
496            // Truncate to exact size
497            while new_population.len() > self.config.population_size {
498                new_population.pop();
499            }
500
501            // Evaluate new population
502            let eval_start = Instant::now();
503            if self.config.parallel_evaluation {
504                new_population.evaluate_parallel(&self.fitness);
505            } else {
506                new_population.evaluate(&self.fitness);
507            }
508            let eval_time = eval_start.elapsed();
509            evaluations += new_population.len()
510                - (if self.config.elitism {
511                    self.config.elite_count
512                } else {
513                    0
514                });
515
516            // Update generation counter
517            new_population.set_generation(population.generation() + 1);
518            population = new_population;
519
520            // Update best individual
521            if let Some(best) = population.best() {
522                if best.is_better_than(&best_individual) {
523                    best_individual = best.clone();
524                }
525            }
526
527            // Record statistics
528            let timing = TimingStats::new()
529                .with_selection(selection_time)
530                .with_crossover(crossover_time)
531                .with_mutation(mutation_time)
532                .with_evaluation(eval_time)
533                .with_total(gen_start.elapsed());
534
535            let gen_stats =
536                GenerationStats::from_population(&population, population.generation(), evaluations)
537                    .with_timing(timing);
538            fitness_history.push(gen_stats.best_fitness);
539            stats.record(gen_stats);
540        }
541
542        stats.set_runtime(start_time.elapsed());
543
544        Ok(EvolutionResult::new(
545            best_individual.genome,
546            best_individual.fitness.unwrap(),
547            population.generation(),
548            evaluations,
549        )
550        .with_stats(stats))
551    }
552}
553
554// Bounded operators version - parallel with Send + Sync
555#[cfg(feature = "parallel")]
556impl<G, F, S, C, M, Fit, Term> SimpleGA<G, F, S, C, M, Fit, Term>
557where
558    G: EvolutionaryGenome + Send + Sync,
559    F: FitnessValue + Send,
560    S: SelectionOperator<G>,
561    C: BoundedCrossoverOperator<G>,
562    M: BoundedMutationOperator<G>,
563    Fit: Fitness<Genome = G, Value = F> + Sync,
564    Term: TerminationCriterion<G, F>,
565{
566    /// Run the genetic algorithm with bounded operators
567    pub fn run_bounded<R: Rng>(
568        &self,
569        rng: &mut R,
570    ) -> Result<EvolutionResult<G, F>, EvolutionError> {
571        let start_time = Instant::now();
572
573        // Initialize population
574        let mut population: Population<G, F> =
575            Population::random(self.config.population_size, &self.bounds, rng);
576
577        // Evaluate initial population
578        if self.config.parallel_evaluation {
579            population.evaluate_parallel(&self.fitness);
580        } else {
581            population.evaluate(&self.fitness);
582        }
583
584        let mut stats = EvolutionStats::new();
585        let mut evaluations = population.len();
586        let mut fitness_history: Vec<f64> = Vec::new();
587
588        // Track best individual
589        let mut best_individual = population
590            .best()
591            .ok_or(EvolutionError::EmptyPopulation)?
592            .clone();
593
594        // Record initial statistics
595        let gen_stats = GenerationStats::from_population(&population, 0, evaluations);
596        fitness_history.push(gen_stats.best_fitness);
597        stats.record(gen_stats);
598
599        // Main evolution loop
600        loop {
601            // Check termination
602            let state = EvolutionState {
603                generation: population.generation(),
604                evaluations,
605                best_fitness: best_individual.fitness_value().to_f64(),
606                population: &population,
607                fitness_history: &fitness_history,
608            };
609
610            if self.termination.should_terminate(&state) {
611                stats.set_termination_reason(self.termination.reason());
612                break;
613            }
614
615            // Create new generation
616            let mut new_population: Population<G, F> =
617                Population::with_capacity(self.config.population_size);
618
619            // Elitism
620            if self.config.elitism {
621                let mut sorted = population.clone();
622                sorted.sort_by_fitness();
623                for i in 0..self.config.elite_count.min(sorted.len()) {
624                    new_population.push(sorted[i].clone());
625                }
626            }
627
628            let selection_pool: Vec<(G, f64)> = population.as_fitness_pairs();
629
630            while new_population.len() < self.config.population_size {
631                let parent1_idx = self.selection.select(&selection_pool, rng);
632                let parent2_idx = self.selection.select(&selection_pool, rng);
633
634                let parent1 = &selection_pool[parent1_idx].0;
635                let parent2 = &selection_pool[parent2_idx].0;
636
637                let (mut child1, mut child2) =
638                    if rng.gen::<f64>() < self.config.crossover_probability {
639                        match self
640                            .crossover
641                            .crossover_bounded(parent1, parent2, &self.bounds, rng)
642                            .genome()
643                        {
644                            Some((c1, c2)) => (c1, c2),
645                            None => (parent1.clone(), parent2.clone()),
646                        }
647                    } else {
648                        (parent1.clone(), parent2.clone())
649                    };
650
651                self.mutation.mutate_bounded(&mut child1, &self.bounds, rng);
652                self.mutation.mutate_bounded(&mut child2, &self.bounds, rng);
653
654                new_population.push(Individual::with_generation(
655                    child1,
656                    population.generation() + 1,
657                ));
658                if new_population.len() < self.config.population_size {
659                    new_population.push(Individual::with_generation(
660                        child2,
661                        population.generation() + 1,
662                    ));
663                }
664            }
665
666            while new_population.len() > self.config.population_size {
667                new_population.pop();
668            }
669
670            if self.config.parallel_evaluation {
671                new_population.evaluate_parallel(&self.fitness);
672            } else {
673                new_population.evaluate(&self.fitness);
674            }
675            evaluations += new_population.len()
676                - (if self.config.elitism {
677                    self.config.elite_count
678                } else {
679                    0
680                });
681
682            new_population.set_generation(population.generation() + 1);
683            population = new_population;
684
685            if let Some(best) = population.best() {
686                if best.is_better_than(&best_individual) {
687                    best_individual = best.clone();
688                }
689            }
690
691            let gen_stats =
692                GenerationStats::from_population(&population, population.generation(), evaluations);
693            fitness_history.push(gen_stats.best_fitness);
694            stats.record(gen_stats);
695        }
696
697        stats.set_runtime(start_time.elapsed());
698
699        Ok(EvolutionResult::new(
700            best_individual.genome,
701            best_individual.fitness.unwrap(),
702            population.generation(),
703            evaluations,
704        )
705        .with_stats(stats))
706    }
707}
708
709// Non-parallel version without Send + Sync bounds
710#[cfg(not(feature = "parallel"))]
711impl<G, F, S, C, M, Fit, Term> SimpleGA<G, F, S, C, M, Fit, Term>
712where
713    G: EvolutionaryGenome,
714    F: FitnessValue,
715    S: SelectionOperator<G>,
716    C: CrossoverOperator<G>,
717    M: MutationOperator<G>,
718    Fit: Fitness<Genome = G, Value = F>,
719    Term: TerminationCriterion<G, F>,
720{
721    /// Create a builder for SimpleGA
722    pub fn builder() -> SimpleGABuilder<G, F, (), (), (), (), ()> {
723        SimpleGABuilder::new()
724    }
725
726    /// Run the genetic algorithm
727    pub fn run<R: Rng>(&self, rng: &mut R) -> Result<EvolutionResult<G, F>, EvolutionError> {
728        let start_time = Instant::now();
729
730        // Initialize population
731        let mut population: Population<G, F> =
732            Population::random(self.config.population_size, &self.bounds, rng);
733
734        // Evaluate initial population (sequential only)
735        let eval_start = Instant::now();
736        population.evaluate(&self.fitness);
737        let eval_time = eval_start.elapsed();
738
739        let mut stats = EvolutionStats::new();
740        let mut evaluations = population.len();
741        let mut fitness_history: Vec<f64> = Vec::new();
742
743        // Track best individual
744        let mut best_individual = population
745            .best()
746            .ok_or(EvolutionError::EmptyPopulation)?
747            .clone();
748
749        // Record initial statistics
750        let gen_stats = GenerationStats::from_population(&population, 0, evaluations)
751            .with_timing(TimingStats::new().with_evaluation(eval_time));
752        fitness_history.push(gen_stats.best_fitness);
753        stats.record(gen_stats);
754
755        // Main evolution loop
756        loop {
757            // Check termination
758            let state = EvolutionState {
759                generation: population.generation(),
760                evaluations,
761                best_fitness: best_individual.fitness_value().to_f64(),
762                population: &population,
763                fitness_history: &fitness_history,
764            };
765
766            if self.termination.should_terminate(&state) {
767                stats.set_termination_reason(self.termination.reason());
768                break;
769            }
770
771            let gen_start = Instant::now();
772
773            // Create new generation
774            let mut new_population: Population<G, F> =
775                Population::with_capacity(self.config.population_size);
776
777            // Elitism: copy best individuals
778            if self.config.elitism {
779                let mut sorted = population.clone();
780                sorted.sort_by_fitness();
781                for i in 0..self.config.elite_count.min(sorted.len()) {
782                    new_population.push(sorted[i].clone());
783                }
784            }
785
786            // Selection pool
787            let selection_pool: Vec<(G, f64)> = population.as_fitness_pairs();
788
789            // Generate offspring
790            let _selection_start = Instant::now();
791            let mut selection_time = std::time::Duration::ZERO;
792            let mut crossover_time = std::time::Duration::ZERO;
793            let mut mutation_time = std::time::Duration::ZERO;
794
795            while new_population.len() < self.config.population_size {
796                // Selection
797                let sel_start = Instant::now();
798                let parent1_idx = self.selection.select(&selection_pool, rng);
799                let parent2_idx = self.selection.select(&selection_pool, rng);
800                selection_time += sel_start.elapsed();
801
802                let parent1 = &selection_pool[parent1_idx].0;
803                let parent2 = &selection_pool[parent2_idx].0;
804
805                // Crossover
806                let cross_start = Instant::now();
807                let (mut child1, mut child2) =
808                    if rng.gen::<f64>() < self.config.crossover_probability {
809                        match self.crossover.crossover(parent1, parent2, rng).genome() {
810                            Some((c1, c2)) => (c1, c2),
811                            None => (parent1.clone(), parent2.clone()),
812                        }
813                    } else {
814                        (parent1.clone(), parent2.clone())
815                    };
816                crossover_time += cross_start.elapsed();
817
818                // Mutation
819                let mut_start = Instant::now();
820                self.mutation.mutate(&mut child1, rng);
821                self.mutation.mutate(&mut child2, rng);
822                mutation_time += mut_start.elapsed();
823
824                // Add to new population
825                new_population.push(Individual::with_generation(
826                    child1,
827                    population.generation() + 1,
828                ));
829                if new_population.len() < self.config.population_size {
830                    new_population.push(Individual::with_generation(
831                        child2,
832                        population.generation() + 1,
833                    ));
834                }
835            }
836
837            // Truncate to exact size
838            while new_population.len() > self.config.population_size {
839                new_population.pop();
840            }
841
842            // Evaluate new population (sequential only)
843            let eval_start = Instant::now();
844            new_population.evaluate(&self.fitness);
845            let eval_time = eval_start.elapsed();
846            evaluations += new_population.len()
847                - (if self.config.elitism {
848                    self.config.elite_count
849                } else {
850                    0
851                });
852
853            // Update generation counter
854            new_population.set_generation(population.generation() + 1);
855            population = new_population;
856
857            // Update best individual
858            if let Some(best) = population.best() {
859                if best.is_better_than(&best_individual) {
860                    best_individual = best.clone();
861                }
862            }
863
864            // Record statistics
865            let timing = TimingStats::new()
866                .with_selection(selection_time)
867                .with_crossover(crossover_time)
868                .with_mutation(mutation_time)
869                .with_evaluation(eval_time)
870                .with_total(gen_start.elapsed());
871
872            let gen_stats =
873                GenerationStats::from_population(&population, population.generation(), evaluations)
874                    .with_timing(timing);
875            fitness_history.push(gen_stats.best_fitness);
876            stats.record(gen_stats);
877        }
878
879        stats.set_runtime(start_time.elapsed());
880
881        Ok(EvolutionResult::new(
882            best_individual.genome,
883            best_individual.fitness.unwrap(),
884            population.generation(),
885            evaluations,
886        )
887        .with_stats(stats))
888    }
889}
890
891// Bounded operators version - non-parallel without Send + Sync
892#[cfg(not(feature = "parallel"))]
893impl<G, F, S, C, M, Fit, Term> SimpleGA<G, F, S, C, M, Fit, Term>
894where
895    G: EvolutionaryGenome,
896    F: FitnessValue,
897    S: SelectionOperator<G>,
898    C: BoundedCrossoverOperator<G>,
899    M: BoundedMutationOperator<G>,
900    Fit: Fitness<Genome = G, Value = F>,
901    Term: TerminationCriterion<G, F>,
902{
903    /// Run the genetic algorithm with bounded operators
904    pub fn run_bounded<R: Rng>(
905        &self,
906        rng: &mut R,
907    ) -> Result<EvolutionResult<G, F>, EvolutionError> {
908        let start_time = Instant::now();
909
910        // Initialize population
911        let mut population: Population<G, F> =
912            Population::random(self.config.population_size, &self.bounds, rng);
913
914        // Evaluate initial population (sequential only)
915        population.evaluate(&self.fitness);
916
917        let mut stats = EvolutionStats::new();
918        let mut evaluations = population.len();
919        let mut fitness_history: Vec<f64> = Vec::new();
920
921        // Track best individual
922        let mut best_individual = population
923            .best()
924            .ok_or(EvolutionError::EmptyPopulation)?
925            .clone();
926
927        // Record initial statistics
928        let gen_stats = GenerationStats::from_population(&population, 0, evaluations);
929        fitness_history.push(gen_stats.best_fitness);
930        stats.record(gen_stats);
931
932        // Main evolution loop
933        loop {
934            // Check termination
935            let state = EvolutionState {
936                generation: population.generation(),
937                evaluations,
938                best_fitness: best_individual.fitness_value().to_f64(),
939                population: &population,
940                fitness_history: &fitness_history,
941            };
942
943            if self.termination.should_terminate(&state) {
944                stats.set_termination_reason(self.termination.reason());
945                break;
946            }
947
948            // Create new generation
949            let mut new_population: Population<G, F> =
950                Population::with_capacity(self.config.population_size);
951
952            // Elitism
953            if self.config.elitism {
954                let mut sorted = population.clone();
955                sorted.sort_by_fitness();
956                for i in 0..self.config.elite_count.min(sorted.len()) {
957                    new_population.push(sorted[i].clone());
958                }
959            }
960
961            let selection_pool: Vec<(G, f64)> = population.as_fitness_pairs();
962
963            while new_population.len() < self.config.population_size {
964                let parent1_idx = self.selection.select(&selection_pool, rng);
965                let parent2_idx = self.selection.select(&selection_pool, rng);
966
967                let parent1 = &selection_pool[parent1_idx].0;
968                let parent2 = &selection_pool[parent2_idx].0;
969
970                let (mut child1, mut child2) =
971                    if rng.gen::<f64>() < self.config.crossover_probability {
972                        match self
973                            .crossover
974                            .crossover_bounded(parent1, parent2, &self.bounds, rng)
975                            .genome()
976                        {
977                            Some((c1, c2)) => (c1, c2),
978                            None => (parent1.clone(), parent2.clone()),
979                        }
980                    } else {
981                        (parent1.clone(), parent2.clone())
982                    };
983
984                self.mutation.mutate_bounded(&mut child1, &self.bounds, rng);
985                self.mutation.mutate_bounded(&mut child2, &self.bounds, rng);
986
987                new_population.push(Individual::with_generation(
988                    child1,
989                    population.generation() + 1,
990                ));
991                if new_population.len() < self.config.population_size {
992                    new_population.push(Individual::with_generation(
993                        child2,
994                        population.generation() + 1,
995                    ));
996                }
997            }
998
999            while new_population.len() > self.config.population_size {
1000                new_population.pop();
1001            }
1002
1003            // Evaluate (sequential only)
1004            new_population.evaluate(&self.fitness);
1005            evaluations += new_population.len()
1006                - (if self.config.elitism {
1007                    self.config.elite_count
1008                } else {
1009                    0
1010                });
1011
1012            new_population.set_generation(population.generation() + 1);
1013            population = new_population;
1014
1015            if let Some(best) = population.best() {
1016                if best.is_better_than(&best_individual) {
1017                    best_individual = best.clone();
1018                }
1019            }
1020
1021            let gen_stats =
1022                GenerationStats::from_population(&population, population.generation(), evaluations);
1023            fitness_history.push(gen_stats.best_fitness);
1024            stats.record(gen_stats);
1025        }
1026
1027        stats.set_runtime(start_time.elapsed());
1028
1029        Ok(EvolutionResult::new(
1030            best_individual.genome,
1031            best_individual.fitness.unwrap(),
1032            population.generation(),
1033            evaluations,
1034        )
1035        .with_stats(stats))
1036    }
1037}
1038
1039#[cfg(test)]
1040mod tests {
1041    use super::*;
1042    use crate::fitness::benchmarks::{OneMax, Sphere};
1043    use crate::genome::traits::RealValuedGenome;
1044    use crate::operators::crossover::{SbxCrossover, UniformCrossover};
1045    use crate::operators::mutation::{BitFlipMutation, PolynomialMutation};
1046    use crate::operators::selection::TournamentSelection;
1047    use crate::termination::TargetFitness;
1048
1049    #[test]
1050    fn test_simple_ga_builder() {
1051        let bounds = MultiBounds::symmetric(5.0, 10);
1052        let ga = SimpleGABuilder::new()
1053            .population_size(50)
1054            .bounds(bounds)
1055            .selection(TournamentSelection::new(3))
1056            .crossover(SbxCrossover::new(20.0))
1057            .mutation(PolynomialMutation::new(20.0))
1058            .fitness(Sphere::new(10))
1059            .max_generations(10)
1060            .build();
1061
1062        assert!(ga.is_ok());
1063    }
1064
1065    #[test]
1066    fn test_simple_ga_missing_bounds() {
1067        // Test that build() returns an error when bounds are missing
1068        // Note: With the type-safe builder, operators must be provided to call build()
1069        // but bounds can be missing (they're an Option in the builder)
1070        let ga = SimpleGABuilder::new()
1071            .population_size(50)
1072            // bounds are missing
1073            .selection(TournamentSelection::new(3))
1074            .crossover(SbxCrossover::new(20.0))
1075            .mutation(PolynomialMutation::new(20.0))
1076            .fitness(Sphere::new(10))
1077            .max_generations(10)
1078            .build();
1079
1080        assert!(ga.is_err());
1081        if let Err(e) = ga {
1082            assert!(e.to_string().contains("Bounds"));
1083        }
1084    }
1085
1086    #[test]
1087    fn test_simple_ga_sphere() {
1088        let mut rng = rand::thread_rng();
1089        let bounds = MultiBounds::symmetric(5.12, 10);
1090
1091        let ga = SimpleGABuilder::new()
1092            .population_size(50)
1093            .bounds(bounds)
1094            .selection(TournamentSelection::new(3))
1095            .crossover(SbxCrossover::new(20.0))
1096            .mutation(PolynomialMutation::new(20.0))
1097            .fitness(Sphere::new(10))
1098            .max_generations(100)
1099            .build()
1100            .unwrap();
1101
1102        let result = ga.run(&mut rng).unwrap();
1103
1104        // Should find some improvement from random initialization
1105        // Initial random values in [-5.12, 5.12] have expected fitness around -52 per dimension
1106        // so total ~-520. Even modest improvement should get to -200 or better.
1107        assert!(
1108            result.best_fitness > -200.0,
1109            "Expected fitness > -200, got {}",
1110            result.best_fitness
1111        ); // Sphere is negated, so closer to 0 is better
1112        assert!(result.generations <= 100);
1113        assert!(result.evaluations > 0);
1114    }
1115
1116    #[test]
1117    fn test_simple_ga_onemax() {
1118        let mut rng = rand::thread_rng();
1119        let bounds = MultiBounds::uniform(crate::genome::bounds::Bounds::unit(), 20);
1120
1121        let ga = SimpleGABuilder::new()
1122            .population_size(50)
1123            .bounds(bounds)
1124            .selection(TournamentSelection::new(3))
1125            .crossover(UniformCrossover::new())
1126            .mutation(BitFlipMutation::new())
1127            .fitness(OneMax::new(20))
1128            .max_generations(50)
1129            .build()
1130            .unwrap();
1131
1132        let result = ga.run(&mut rng).unwrap();
1133
1134        // Should find perfect or near-perfect solution
1135        assert!(result.best_fitness >= 15); // At least 75% ones
1136    }
1137
1138    #[test]
1139    fn test_simple_ga_target_fitness() {
1140        let mut rng = rand::thread_rng();
1141        let bounds = MultiBounds::symmetric(5.12, 5);
1142
1143        let ga = SimpleGABuilder::new()
1144            .population_size(100)
1145            .bounds(bounds)
1146            .selection(TournamentSelection::new(5))
1147            .crossover(SbxCrossover::new(20.0))
1148            .mutation(PolynomialMutation::new(20.0))
1149            .fitness(Sphere::new(5))
1150            .termination(TargetFitness::with_tolerance(0.0, 0.1)) // Near 0 (optimal)
1151            .build()
1152            .unwrap();
1153
1154        let result = ga.run(&mut rng).unwrap();
1155
1156        // Should reach target
1157        assert!(result.best_fitness >= -0.1);
1158        assert_eq!(
1159            result.stats.termination_reason.as_deref(),
1160            Some("Target fitness reached")
1161        );
1162    }
1163
1164    #[test]
1165    fn test_simple_ga_bounded() {
1166        let mut rng = rand::thread_rng();
1167        let bounds = MultiBounds::symmetric(5.12, 10);
1168
1169        let ga = SimpleGABuilder::new()
1170            .population_size(50)
1171            .bounds(bounds.clone())
1172            .selection(TournamentSelection::new(3))
1173            .crossover(SbxCrossover::new(20.0))
1174            .mutation(PolynomialMutation::new(20.0))
1175            .fitness(Sphere::new(10))
1176            .max_generations(50)
1177            .build()
1178            .unwrap();
1179
1180        let result = ga.run_bounded(&mut rng).unwrap();
1181
1182        // All genes should be within bounds
1183        for gene in result.best_genome.genes() {
1184            assert!(*gene >= -5.12 && *gene <= 5.12);
1185        }
1186    }
1187
1188    #[test]
1189    fn test_simple_ga_elitism() {
1190        let mut rng = rand::thread_rng();
1191        let bounds = MultiBounds::symmetric(5.12, 5);
1192
1193        // Run without elitism
1194        let ga_no_elite = SimpleGABuilder::new()
1195            .population_size(20)
1196            .elitism(false)
1197            .bounds(bounds.clone())
1198            .selection(TournamentSelection::new(2))
1199            .crossover(SbxCrossover::new(20.0))
1200            .mutation(PolynomialMutation::new(20.0))
1201            .fitness(Sphere::new(5))
1202            .max_generations(20)
1203            .build()
1204            .unwrap();
1205
1206        // Run with elitism
1207        let ga_elite = SimpleGABuilder::new()
1208            .population_size(20)
1209            .elitism(true)
1210            .elite_count(2)
1211            .bounds(bounds)
1212            .selection(TournamentSelection::new(2))
1213            .crossover(SbxCrossover::new(20.0))
1214            .mutation(PolynomialMutation::new(20.0))
1215            .fitness(Sphere::new(5))
1216            .max_generations(20)
1217            .build()
1218            .unwrap();
1219
1220        // Both should run without error
1221        let result_no_elite = ga_no_elite.run(&mut rng);
1222        let result_elite = ga_elite.run(&mut rng);
1223
1224        assert!(result_no_elite.is_ok());
1225        assert!(result_elite.is_ok());
1226    }
1227
1228    #[test]
1229    fn test_simple_ga_statistics() {
1230        let mut rng = rand::thread_rng();
1231        let bounds = MultiBounds::symmetric(5.12, 5);
1232
1233        let ga = SimpleGABuilder::new()
1234            .population_size(20)
1235            .bounds(bounds)
1236            .selection(TournamentSelection::new(2))
1237            .crossover(SbxCrossover::new(20.0))
1238            .mutation(PolynomialMutation::new(20.0))
1239            .fitness(Sphere::new(5))
1240            .max_generations(10)
1241            .build()
1242            .unwrap();
1243
1244        let result = ga.run(&mut rng).unwrap();
1245
1246        // Check statistics were collected
1247        assert_eq!(result.stats.num_generations(), 11); // Initial + 10 generations
1248        assert!(result.stats.total_runtime_ms > 0.0);
1249
1250        // Best fitness should improve or stay the same
1251        let history = result.stats.best_fitness_history();
1252        for i in 1..history.len() {
1253            assert!(history[i] >= history[i - 1] - 0.001); // Allow small numerical error
1254        }
1255    }
1256}
fugue_evo/algorithms/simple_ga.rs

fugue_evo/algorithms/
simple_ga.rs
