fugue_evo/algorithms/
island.rs

1//! Island Model Parallelism
2//!
3//! Implements a distributed evolutionary algorithm where multiple populations
4//! (islands) evolve independently with periodic migration of individuals.
5//!
6//! Note: This module requires the `parallel` feature to be enabled.
7
8use rand::rngs::StdRng;
9use rand::SeedableRng;
10#[cfg(feature = "parallel")]
11use rayon::prelude::*;
12use serde::{Deserialize, Serialize};
13use std::sync::Arc;
14
15use crate::error::{EvoResult, EvolutionError, OperatorResult};
16use crate::fitness::traits::{Fitness, FitnessValue};
17use crate::genome::bounds::MultiBounds;
18use crate::genome::traits::EvolutionaryGenome;
19use crate::operators::traits::{CrossoverOperator, MutationOperator, SelectionOperator};
20use crate::population::individual::Individual;
21use crate::population::population::Population;
22
23/// Migration topology determines which islands exchange individuals
24#[derive(Clone, Debug, Serialize, Deserialize)]
25pub enum MigrationTopology {
26    /// Ring topology: each island sends to the next
27    Ring,
28    /// Fully connected: every island can send to any other
29    FullyConnected,
30    /// Random: each island sends to a randomly chosen island
31    Random,
32    /// Star: all islands send to/receive from a central hub
33    Star { hub_index: usize },
34}
35
36impl Default for MigrationTopology {
37    fn default() -> Self {
38        Self::Ring
39    }
40}
41
42impl MigrationTopology {
43    /// Get the target islands for migration from a given source island
44    pub fn targets(&self, source: usize, num_islands: usize) -> Vec<usize> {
45        match self {
46            Self::Ring => vec![(source + 1) % num_islands],
47            Self::FullyConnected => (0..num_islands).filter(|&i| i != source).collect(),
48            Self::Random => (0..num_islands).filter(|&i| i != source).collect(),
49            Self::Star { hub_index } => {
50                if source == *hub_index {
51                    (0..num_islands).filter(|&i| i != source).collect()
52                } else {
53                    vec![*hub_index]
54                }
55            }
56        }
57    }
58}
59
60/// Migration policy determines which and how many individuals migrate
61#[derive(Clone, Debug, Serialize, Deserialize)]
62pub enum MigrationPolicy {
63    /// Best k individuals migrate
64    Best(usize),
65    /// Random k individuals migrate
66    Random(usize),
67    /// Best k individuals replace worst k on target
68    BestReplaceWorst(usize),
69}
70
71impl Default for MigrationPolicy {
72    fn default() -> Self {
73        Self::Best(1)
74    }
75}
76
77/// Configuration for the island model
78#[derive(Clone, Debug)]
79pub struct IslandModelConfig {
80    /// Number of islands
81    pub num_islands: usize,
82    /// Population size per island
83    pub island_population_size: usize,
84    /// Migration interval (generations between migrations)
85    pub migration_interval: usize,
86    /// Migration topology
87    pub topology: MigrationTopology,
88    /// Migration policy
89    pub policy: MigrationPolicy,
90    /// Bounds for genome generation
91    pub bounds: MultiBounds,
92    /// Number of elites to preserve per island
93    pub elitism: usize,
94}
95
96impl Default for IslandModelConfig {
97    fn default() -> Self {
98        Self {
99            num_islands: 4,
100            island_population_size: 50,
101            migration_interval: 10,
102            topology: MigrationTopology::Ring,
103            policy: MigrationPolicy::Best(1),
104            bounds: MultiBounds::symmetric(5.0, 10),
105            elitism: 1,
106        }
107    }
108}
109
110/// State of a single island
111pub struct Island<G, F = f64>
112where
113    G: EvolutionaryGenome,
114    F: FitnessValue,
115{
116    /// Island index
117    pub index: usize,
118    /// Current population
119    pub population: Population<G, F>,
120    /// Best individual found on this island
121    pub best: Option<Individual<G, F>>,
122    /// Current generation (local to island)
123    pub generation: usize,
124    /// Total fitness evaluations on this island
125    pub evaluations: usize,
126}
127
128impl<G, F> Island<G, F>
129where
130    G: EvolutionaryGenome,
131    F: FitnessValue,
132{
133    /// Create a new island with a random population
134    pub fn new<R: rand::Rng>(index: usize, size: usize, bounds: &MultiBounds, rng: &mut R) -> Self {
135        Self {
136            index,
137            population: Population::random(size, bounds, rng),
138            best: None,
139            generation: 0,
140            evaluations: 0,
141        }
142    }
143
144    /// Create an island with an existing population
145    pub fn with_population(index: usize, population: Population<G, F>) -> Self {
146        Self {
147            index,
148            population,
149            best: None,
150            generation: 0,
151            evaluations: 0,
152        }
153    }
154
155    /// Run one generation of evolution on this island
156    pub fn evolve_one_generation<Fit, Sel, Cross, Mut, R>(
157        &mut self,
158        fitness: &Fit,
159        selection: &Sel,
160        crossover: &Cross,
161        mutation: &Mut,
162        elitism: usize,
163        rng: &mut R,
164    ) -> EvoResult<()>
165    where
166        Fit: Fitness<Genome = G, Value = F>,
167        Sel: SelectionOperator<G>,
168        Cross: CrossoverOperator<G>,
169        Mut: MutationOperator<G>,
170        R: rand::Rng,
171    {
172        // Evaluate population. EV-82: count only individuals that actually needed
173        // evaluating — carried-over elites are already scored and are skipped by
174        // Population::evaluate, so adding the full population length over-counts.
175        let newly_evaluated = self.population.len() - self.population.count_evaluated();
176        self.population.evaluate(fitness);
177        self.evaluations += newly_evaluated;
178
179        // Update best
180        if let Some(current_best) = self.population.best() {
181            match &self.best {
182                None => self.best = Some(current_best.clone()),
183                Some(best) if current_best.is_better_than(best) => {
184                    self.best = Some(current_best.clone());
185                }
186                _ => {}
187            }
188        }
189
190        // Preserve elites. EV-83: cap the elite count at the population size so an
191        // over-large `elitism` cannot cause a usize underflow below.
192        self.population.sort_by_fitness();
193        let pop_len = self.population.len();
194        let elite_count = elitism.min(pop_len);
195        let target_offspring = pop_len - elite_count;
196        let elites: Vec<_> = self.population.iter().take(elite_count).cloned().collect();
197
198        // Prepare selection pool: (genome, fitness) pairs
199        let selection_pool: Vec<(G, f64)> = self
200            .population
201            .iter()
202            .filter_map(|ind| {
203                ind.fitness
204                    .as_ref()
205                    .map(|f| (ind.genome.clone(), f.to_f64()))
206            })
207            .collect();
208
209        if selection_pool.len() < 2 {
210            return Err(EvolutionError::EmptyPopulation);
211        }
212
213        // Selection and reproduction
214        let mut offspring = Vec::with_capacity(target_offspring);
215
216        while offspring.len() < target_offspring {
217            // Select parents
218            let idx1 = selection.select(&selection_pool, rng);
219            let idx2 = selection.select(&selection_pool, rng);
220            let parent1 = &selection_pool[idx1].0;
221            let parent2 = &selection_pool[idx2].0;
222
223            // Crossover
224            let (mut child1, mut child2) = match crossover.crossover(parent1, parent2, rng) {
225                OperatorResult::Success((c1, c2)) | OperatorResult::Repaired((c1, c2), _) => {
226                    (c1, c2)
227                }
228                OperatorResult::Failed(_) => (parent1.clone(), parent2.clone()),
229            };
230
231            // Mutation
232            mutation.mutate(&mut child1, rng);
233            mutation.mutate(&mut child2, rng);
234
235            offspring.push(Individual::new(child1));
236            if offspring.len() < target_offspring {
237                offspring.push(Individual::new(child2));
238            }
239        }
240
241        // Replace population with elites + offspring
242        let mut new_population = Population::new();
243        for elite in elites {
244            new_population.push(elite);
245        }
246        for child in offspring {
247            new_population.push(child);
248        }
249        self.population = new_population;
250
251        self.generation += 1;
252        Ok(())
253    }
254
255    /// Get emigrants for migration (individuals leaving this island)
256    pub fn get_emigrants<R: rand::Rng>(
257        &self,
258        policy: &MigrationPolicy,
259        rng: &mut R,
260    ) -> Vec<Individual<G, F>> {
261        match policy {
262            MigrationPolicy::Best(k) => {
263                let mut sorted: Vec<_> = self.population.iter().cloned().collect();
264                sorted.sort_by(|a, b| match (a.fitness.as_ref(), b.fitness.as_ref()) {
265                    (Some(fa), Some(fb)) => fb.partial_cmp(fa).unwrap_or(std::cmp::Ordering::Equal),
266                    (Some(_), None) => std::cmp::Ordering::Less,
267                    (None, Some(_)) => std::cmp::Ordering::Greater,
268                    (None, None) => std::cmp::Ordering::Equal,
269                });
270                sorted.into_iter().take(*k).collect()
271            }
272            MigrationPolicy::Random(k) => {
273                use rand::seq::SliceRandom;
274                let mut individuals: Vec<_> = self.population.iter().cloned().collect();
275                individuals.shuffle(rng);
276                individuals.into_iter().take(*k).collect()
277            }
278            MigrationPolicy::BestReplaceWorst(k) => {
279                let mut sorted: Vec<_> = self.population.iter().cloned().collect();
280                sorted.sort_by(|a, b| match (a.fitness.as_ref(), b.fitness.as_ref()) {
281                    (Some(fa), Some(fb)) => fb.partial_cmp(fa).unwrap_or(std::cmp::Ordering::Equal),
282                    (Some(_), None) => std::cmp::Ordering::Less,
283                    (None, Some(_)) => std::cmp::Ordering::Greater,
284                    (None, None) => std::cmp::Ordering::Equal,
285                });
286                sorted.into_iter().take(*k).collect()
287            }
288        }
289    }
290
291    /// Accept immigrants (individuals coming to this island).
292    ///
293    /// EV-41: immigrants always replace the island's WORST members, regardless of
294    /// the migration policy, so an island's best individual is never overwritten
295    /// by an arriving (possibly worse) migrant. `sort_by_fitness` orders the
296    /// population best-first, so the worst members occupy the tail.
297    pub fn accept_immigrants(&mut self, immigrants: Vec<Individual<G, F>>) {
298        if immigrants.is_empty() || self.population.is_empty() {
299            return;
300        }
301
302        self.population.sort_by_fitness();
303        let pop_len = self.population.len();
304        for (i, immigrant) in immigrants.into_iter().enumerate() {
305            if i >= pop_len {
306                break;
307            }
308            self.population[pop_len - 1 - i] = immigrant;
309        }
310    }
311}
312
313/// Island Model Evolutionary Algorithm
314pub struct IslandModel<G, Fit, Sel, Cross, Mut, F = f64>
315where
316    G: EvolutionaryGenome,
317    F: FitnessValue,
318{
319    /// Configuration
320    pub config: IslandModelConfig,
321    /// Islands
322    pub islands: Vec<Island<G, F>>,
323    /// One persistent RNG per island, derived once from the caller's master RNG
324    /// (EV-12). Reusing these across generations makes seeded runs bit-reproducible
325    /// even though islands are evolved in parallel.
326    island_rngs: Vec<StdRng>,
327    /// Fitness function (shared)
328    pub fitness: Arc<Fit>,
329    /// Selection operator
330    pub selection: Sel,
331    /// Crossover operator
332    pub crossover: Cross,
333    /// Mutation operator
334    pub mutation: Mut,
335    /// Global best individual
336    pub global_best: Option<Individual<G, F>>,
337    /// Total generations (global)
338    pub generation: usize,
339    /// Total evaluations across all islands
340    pub total_evaluations: usize,
341}
342
343impl<G, Fit, Sel, Cross, Mut, F> IslandModel<G, Fit, Sel, Cross, Mut, F>
344where
345    G: EvolutionaryGenome,
346    F: FitnessValue,
347    Fit: Fitness<Genome = G, Value = F> + Send + Sync,
348    Sel: SelectionOperator<G> + Clone + Send + Sync,
349    Cross: CrossoverOperator<G> + Clone + Send + Sync,
350    Mut: MutationOperator<G> + Clone + Send + Sync,
351{
352    /// Create a new island model
353    pub fn new<R: rand::Rng>(
354        config: IslandModelConfig,
355        fitness: Fit,
356        selection: Sel,
357        crossover: Cross,
358        mutation: Mut,
359        rng: &mut R,
360    ) -> Self {
361        let islands: Vec<_> = (0..config.num_islands)
362            .map(|i| {
363                let mut island_rng = StdRng::from_seed(rng.gen());
364                Island::new(
365                    i,
366                    config.island_population_size,
367                    &config.bounds,
368                    &mut island_rng,
369                )
370            })
371            .collect();
372
373        // EV-12: draw one persistent working RNG per island from the master RNG
374        // once, up front, so per-island search is deterministic under a fixed seed.
375        let island_rngs: Vec<StdRng> = (0..config.num_islands)
376            .map(|_| StdRng::seed_from_u64(rng.gen()))
377            .collect();
378
379        Self {
380            config,
381            islands,
382            island_rngs,
383            fitness: Arc::new(fitness),
384            selection,
385            crossover,
386            mutation,
387            global_best: None,
388            generation: 0,
389            total_evaluations: 0,
390        }
391    }
392
393    /// Run evolution for a specified number of generations
394    pub fn run<R: rand::Rng>(
395        &mut self,
396        max_generations: usize,
397        rng: &mut R,
398    ) -> EvoResult<&Individual<G, F>> {
399        for _ in 0..max_generations {
400            self.step(rng)?;
401        }
402
403        self.global_best
404            .as_ref()
405            .ok_or(EvolutionError::EmptyPopulation)
406    }
407
408    /// Perform one generation step on all islands
409    pub fn step<R: rand::Rng>(&mut self, rng: &mut R) -> EvoResult<()> {
410        // Evolve each island independently (can be parallelized)
411        let elitism = self.config.elitism;
412        let fitness = Arc::clone(&self.fitness);
413        let selection = self.selection.clone();
414        let crossover = self.crossover.clone();
415        let mutation = self.mutation.clone();
416
417        // Parallel evolution of islands. EV-12: each island uses its own
418        // persistent, master-seeded RNG (not OS entropy), so a seeded run is
419        // bit-reproducible whether islands evolve in parallel (feature
420        // "parallel") or sequentially (e.g. wasm32 builds).
421        #[cfg(feature = "parallel")]
422        self.islands
423            .par_iter_mut()
424            .zip(self.island_rngs.par_iter_mut())
425            .for_each(|(island, island_rng)| {
426                let _ = island.evolve_one_generation(
427                    fitness.as_ref(),
428                    &selection,
429                    &crossover,
430                    &mutation,
431                    elitism,
432                    island_rng,
433                );
434            });
435        #[cfg(not(feature = "parallel"))]
436        self.islands
437            .iter_mut()
438            .zip(self.island_rngs.iter_mut())
439            .for_each(|(island, island_rng)| {
440                let _ = island.evolve_one_generation(
441                    fitness.as_ref(),
442                    &selection,
443                    &crossover,
444                    &mutation,
445                    elitism,
446                    island_rng,
447                );
448            });
449
450        // Update global best
451        for island in &self.islands {
452            if let Some(island_best) = &island.best {
453                match &self.global_best {
454                    None => self.global_best = Some(island_best.clone()),
455                    Some(global) if island_best.is_better_than(global) => {
456                        self.global_best = Some(island_best.clone());
457                    }
458                    _ => {}
459                }
460            }
461        }
462
463        self.generation += 1;
464        self.total_evaluations = self.islands.iter().map(|i| i.evaluations).sum();
465
466        // Migration
467        if self
468            .generation
469            .is_multiple_of(self.config.migration_interval)
470        {
471            self.migrate(rng);
472        }
473
474        Ok(())
475    }
476
477    /// Perform migration between islands
478    fn migrate<R: rand::Rng>(&mut self, rng: &mut R) {
479        let num_islands = self.islands.len();
480        let policy = self.config.policy.clone();
481        let topology = self.config.topology.clone();
482
483        // Collect emigrants from each island using that island's persistent RNG
484        // (EV-12), so random-emigrant selection is reproducible under a seed.
485        let emigrants: Vec<Vec<Individual<G, F>>> = self
486            .islands
487            .iter()
488            .zip(self.island_rngs.iter_mut())
489            .map(|(island, island_rng)| island.get_emigrants(&policy, island_rng))
490            .collect();
491
492        // Route emigrants to target islands
493        for (source, source_emigrants) in emigrants.into_iter().enumerate() {
494            let targets = topology.targets(source, num_islands);
495
496            if targets.is_empty() {
497                continue;
498            }
499
500            match topology {
501                MigrationTopology::Random => {
502                    // Pick one random target
503                    let target = targets[rng.gen_range(0..targets.len())];
504                    self.islands[target].accept_immigrants(source_emigrants);
505                }
506                _ => {
507                    // EV-11: broadcast to EVERY target the topology defines
508                    // (FullyConnected reaches all peers; a Star hub reaches all
509                    // spokes), not just the first one.
510                    for &target in &targets {
511                        self.islands[target].accept_immigrants(source_emigrants.clone());
512                    }
513                }
514            }
515        }
516    }
517
518    /// Get a combined population from all islands
519    pub fn combined_population(&self) -> Population<G, F> {
520        let mut combined = Population::new();
521        for island in &self.islands {
522            for individual in island.population.iter() {
523                combined.push(individual.clone());
524            }
525        }
526        combined
527    }
528
529    /// Get statistics about each island
530    pub fn island_statistics(&self) -> Vec<IslandStats<F>> {
531        self.islands
532            .iter()
533            .map(|island| {
534                let (sum, best) = island
535                    .population
536                    .iter()
537                    .filter_map(|i| i.fitness.clone())
538                    .fold((0.0, None::<F>), |(sum, best), f| {
539                        let new_best = match best {
540                            None => Some(f.clone()),
541                            Some(b) if f.is_better_than(&b) => Some(f.clone()),
542                            b => b,
543                        };
544                        (sum + f.to_f64(), new_best)
545                    });
546
547                let count = island
548                    .population
549                    .iter()
550                    .filter(|i| i.fitness.is_some())
551                    .count();
552
553                IslandStats {
554                    index: island.index,
555                    generation: island.generation,
556                    evaluations: island.evaluations,
557                    population_size: island.population.len(),
558                    mean_fitness: if count > 0 { sum / count as f64 } else { 0.0 },
559                    best_fitness: best,
560                }
561            })
562            .collect()
563    }
564}
565
566/// Statistics for a single island
567#[derive(Clone, Debug)]
568pub struct IslandStats<F: FitnessValue> {
569    /// Island index
570    pub index: usize,
571    /// Current generation
572    pub generation: usize,
573    /// Total evaluations
574    pub evaluations: usize,
575    /// Population size
576    pub population_size: usize,
577    /// Mean fitness
578    pub mean_fitness: f64,
579    /// Best fitness on this island
580    pub best_fitness: Option<F>,
581}
582
583/// Builder for IslandModel
584pub struct IslandModelBuilder<G, Fit, Sel, Cross, Mut, F = f64>
585where
586    G: EvolutionaryGenome,
587    F: FitnessValue,
588{
589    config: IslandModelConfig,
590    fitness: Option<Fit>,
591    selection: Option<Sel>,
592    crossover: Option<Cross>,
593    mutation: Option<Mut>,
594    _phantom: std::marker::PhantomData<(G, F)>,
595}
596
597impl<G, Fit, Sel, Cross, Mut, F> IslandModelBuilder<G, Fit, Sel, Cross, Mut, F>
598where
599    G: EvolutionaryGenome,
600    F: FitnessValue,
601    Fit: Fitness<Genome = G, Value = F> + Send + Sync,
602    Sel: SelectionOperator<G> + Clone + Send + Sync,
603    Cross: CrossoverOperator<G> + Clone + Send + Sync,
604    Mut: MutationOperator<G> + Clone + Send + Sync,
605{
606    /// Create a new builder
607    pub fn new() -> Self {
608        Self {
609            config: IslandModelConfig::default(),
610            fitness: None,
611            selection: None,
612            crossover: None,
613            mutation: None,
614            _phantom: std::marker::PhantomData,
615        }
616    }
617
618    /// Set number of islands
619    pub fn num_islands(mut self, n: usize) -> Self {
620        self.config.num_islands = n;
621        self
622    }
623
624    /// Set population size per island
625    pub fn island_population_size(mut self, size: usize) -> Self {
626        self.config.island_population_size = size;
627        self
628    }
629
630    /// Set migration interval
631    pub fn migration_interval(mut self, interval: usize) -> Self {
632        self.config.migration_interval = interval;
633        self
634    }
635
636    /// Set migration topology
637    pub fn topology(mut self, topology: MigrationTopology) -> Self {
638        self.config.topology = topology;
639        self
640    }
641
642    /// Set migration policy
643    pub fn migration_policy(mut self, policy: MigrationPolicy) -> Self {
644        self.config.policy = policy;
645        self
646    }
647
648    /// Set bounds
649    pub fn bounds(mut self, bounds: MultiBounds) -> Self {
650        self.config.bounds = bounds;
651        self
652    }
653
654    /// Set elitism
655    pub fn elitism(mut self, n: usize) -> Self {
656        self.config.elitism = n;
657        self
658    }
659
660    /// Set fitness function
661    pub fn fitness(mut self, fitness: Fit) -> Self {
662        self.fitness = Some(fitness);
663        self
664    }
665
666    /// Set selection operator
667    pub fn selection(mut self, selection: Sel) -> Self {
668        self.selection = Some(selection);
669        self
670    }
671
672    /// Set crossover operator
673    pub fn crossover(mut self, crossover: Cross) -> Self {
674        self.crossover = Some(crossover);
675        self
676    }
677
678    /// Set mutation operator
679    pub fn mutation(mut self, mutation: Mut) -> Self {
680        self.mutation = Some(mutation);
681        self
682    }
683
684    /// Build the island model
685    pub fn build<R: rand::Rng>(
686        self,
687        rng: &mut R,
688    ) -> EvoResult<IslandModel<G, Fit, Sel, Cross, Mut, F>> {
689        let fitness = self.fitness.ok_or(EvolutionError::Configuration(
690            "Fitness function is required".to_string(),
691        ))?;
692        let selection = self.selection.ok_or(EvolutionError::Configuration(
693            "Selection operator is required".to_string(),
694        ))?;
695        let crossover = self.crossover.ok_or(EvolutionError::Configuration(
696            "Crossover operator is required".to_string(),
697        ))?;
698        let mutation = self.mutation.ok_or(EvolutionError::Configuration(
699            "Mutation operator is required".to_string(),
700        ))?;
701
702        Ok(IslandModel::new(
703            self.config,
704            fitness,
705            selection,
706            crossover,
707            mutation,
708            rng,
709        ))
710    }
711}
712
713impl<G, Fit, Sel, Cross, Mut, F> Default for IslandModelBuilder<G, Fit, Sel, Cross, Mut, F>
714where
715    G: EvolutionaryGenome,
716    F: FitnessValue,
717    Fit: Fitness<Genome = G, Value = F> + Send + Sync,
718    Sel: SelectionOperator<G> + Clone + Send + Sync,
719    Cross: CrossoverOperator<G> + Clone + Send + Sync,
720    Mut: MutationOperator<G> + Clone + Send + Sync,
721{
722    fn default() -> Self {
723        Self::new()
724    }
725}
726
727#[cfg(test)]
728mod tests {
729    use super::*;
730    use crate::fitness::benchmarks::Sphere;
731    use crate::genome::real_vector::RealVector;
732    use crate::operators::crossover::BlxAlphaCrossover;
733    use crate::operators::mutation::GaussianMutation;
734    use crate::operators::selection::TournamentSelection;
735    use rand::SeedableRng;
736
737    #[test]
738    fn test_migration_topology_ring() {
739        let topology = MigrationTopology::Ring;
740        assert_eq!(topology.targets(0, 4), vec![1]);
741        assert_eq!(topology.targets(1, 4), vec![2]);
742        assert_eq!(topology.targets(3, 4), vec![0]);
743    }
744
745    #[test]
746    fn test_migration_topology_fully_connected() {
747        let topology = MigrationTopology::FullyConnected;
748        let targets = topology.targets(0, 4);
749        assert_eq!(targets.len(), 3);
750        assert!(!targets.contains(&0));
751    }
752
753    #[test]
754    fn test_migration_topology_star() {
755        let topology = MigrationTopology::Star { hub_index: 0 };
756        // Non-hub sends to hub
757        assert_eq!(topology.targets(1, 4), vec![0]);
758        assert_eq!(topology.targets(2, 4), vec![0]);
759        // Hub sends to all
760        let hub_targets = topology.targets(0, 4);
761        assert_eq!(hub_targets.len(), 3);
762    }
763
764    #[test]
765    fn test_island_creation() {
766        let mut rng = rand::rngs::StdRng::seed_from_u64(42);
767        let bounds = MultiBounds::symmetric(5.0, 5);
768        let island: Island<RealVector> = Island::new(0, 10, &bounds, &mut rng);
769
770        assert_eq!(island.index, 0);
771        assert_eq!(island.population.len(), 10);
772        assert_eq!(island.generation, 0);
773    }
774
775    #[test]
776    fn test_island_model_builder() {
777        let mut rng = rand::rngs::StdRng::seed_from_u64(42);
778        let bounds = MultiBounds::symmetric(5.0, 5);
779
780        let result = IslandModelBuilder::<RealVector, _, _, _, _>::new()
781            .num_islands(4)
782            .island_population_size(20)
783            .migration_interval(5)
784            .topology(MigrationTopology::Ring)
785            .migration_policy(MigrationPolicy::Best(2))
786            .bounds(bounds)
787            .elitism(1)
788            .fitness(Sphere::new(5))
789            .selection(TournamentSelection::new(3))
790            .crossover(BlxAlphaCrossover::new(0.5))
791            .mutation(GaussianMutation::new(0.1))
792            .build(&mut rng);
793
794        assert!(result.is_ok());
795        let model = result.unwrap();
796        assert_eq!(model.islands.len(), 4);
797    }
798
799    #[test]
800    fn test_island_model_evolution() {
801        let mut rng = rand::rngs::StdRng::seed_from_u64(42);
802        let bounds = MultiBounds::symmetric(5.0, 5);
803
804        let mut model = IslandModelBuilder::<RealVector, _, _, _, _>::new()
805            .num_islands(2)
806            .island_population_size(20)
807            .migration_interval(5)
808            .topology(MigrationTopology::Ring)
809            .migration_policy(MigrationPolicy::Best(1))
810            .bounds(bounds)
811            .elitism(1)
812            .fitness(Sphere::new(5))
813            .selection(TournamentSelection::new(2))
814            .crossover(BlxAlphaCrossover::new(0.5))
815            .mutation(GaussianMutation::new(0.1))
816            .build(&mut rng)
817            .unwrap();
818
819        // Run for 10 generations
820        let result = model.run(10, &mut rng);
821        assert!(result.is_ok());
822
823        assert_eq!(model.generation, 10);
824        assert!(model.global_best.is_some());
825    }
826
827    #[test]
828    fn test_island_statistics() {
829        let mut rng = rand::rngs::StdRng::seed_from_u64(42);
830        let bounds = MultiBounds::symmetric(5.0, 5);
831
832        let mut model = IslandModelBuilder::<RealVector, _, _, _, _>::new()
833            .num_islands(3)
834            .island_population_size(10)
835            .migration_interval(10)
836            .bounds(bounds)
837            .fitness(Sphere::new(5))
838            .selection(TournamentSelection::new(2))
839            .crossover(BlxAlphaCrossover::new(0.5))
840            .mutation(GaussianMutation::new(0.1))
841            .build(&mut rng)
842            .unwrap();
843
844        model.run(5, &mut rng).unwrap();
845
846        let stats = model.island_statistics();
847        assert_eq!(stats.len(), 3);
848        for stat in &stats {
849            assert_eq!(stat.generation, 5);
850            assert_eq!(stat.population_size, 10);
851        }
852    }
853
854    // regression: EV-12 — two runs with the same master seed must produce
855    // identical best-fitness trajectories, even with parallel island evaluation.
856    #[test]
857    fn test_island_model_reproducible_under_seed() {
858        fn trajectory(seed: u64) -> Vec<f64> {
859            let mut rng = rand::rngs::StdRng::seed_from_u64(seed);
860            let bounds = MultiBounds::symmetric(5.0, 5);
861            let mut model = IslandModelBuilder::<RealVector, _, _, _, _>::new()
862                .num_islands(3)
863                .island_population_size(20)
864                .migration_interval(3)
865                .topology(MigrationTopology::Ring)
866                .migration_policy(MigrationPolicy::Best(1))
867                .bounds(bounds)
868                .elitism(1)
869                .fitness(Sphere::new(5))
870                .selection(TournamentSelection::new(2))
871                .crossover(BlxAlphaCrossover::new(0.5))
872                .mutation(GaussianMutation::new(0.1))
873                .build(&mut rng)
874                .unwrap();
875
876            let mut traj = Vec::new();
877            for _ in 0..15 {
878                model.step(&mut rng).unwrap();
879                traj.push(*model.global_best.as_ref().unwrap().fitness_value());
880            }
881            traj
882        }
883
884        let a = trajectory(12345);
885        let b = trajectory(12345);
886        assert_eq!(a, b, "seeded island runs must be bit-reproducible");
887
888        let c = trajectory(99999);
889        assert_ne!(
890            a, c,
891            "different seeds should produce different trajectories"
892        );
893    }
894
895    // regression: EV-11 — FullyConnected migration must broadcast each island's
896    // emigrant to EVERY other island. With N islands and Best(1) that yields
897    // N + N*(N-1) champions in total (N home + N*(N-1) arrivals); the pre-fix code
898    // only sent to the first target, giving N + N.
899    #[test]
900    fn test_fully_connected_broadcasts_to_all_targets() {
901        let mut rng = rand::rngs::StdRng::seed_from_u64(1);
902        let bounds = MultiBounds::symmetric(100.0, 1);
903
904        let num_islands = 4;
905        let pop = 8;
906        let mut model = IslandModelBuilder::<RealVector, _, _, _, _>::new()
907            .num_islands(num_islands)
908            .island_population_size(pop)
909            .topology(MigrationTopology::FullyConnected)
910            .migration_policy(MigrationPolicy::Best(1))
911            .bounds(bounds)
912            .fitness(Sphere::new(1))
913            .selection(TournamentSelection::new(2))
914            .crossover(BlxAlphaCrossover::new(0.5))
915            .mutation(GaussianMutation::new(0.1))
916            .build(&mut rng)
917            .unwrap();
918
919        // One clearly-best "champion" per island plus clearly-worst filler.
920        for (i, island) in model.islands.iter_mut().enumerate() {
921            let mut new_pop: Population<RealVector> = Population::new();
922            new_pop.push(Individual::with_fitness(
923                RealVector::new(vec![i as f64]),
924                1000.0,
925            ));
926            for _ in 1..pop {
927                new_pop.push(Individual::with_fitness(
928                    RealVector::new(vec![-1.0]),
929                    -1000.0,
930                ));
931            }
932            island.population = new_pop;
933        }
934
935        model.migrate(&mut rng);
936
937        let champions: usize = model
938            .islands
939            .iter()
940            .flat_map(|isl| isl.population.iter())
941            .filter(|ind| (*ind.fitness_value() - 1000.0).abs() < 1e-9)
942            .count();
943
944        assert_eq!(champions, num_islands + num_islands * (num_islands - 1));
945    }
946
947    // regression: EV-41 — an arriving (worse) migrant must replace a WORST member,
948    // never the island best. Pre-fix code replaced a uniformly random member.
949    #[test]
950    fn test_immigrants_replace_worst_not_best() {
951        let mut island_pop: Population<RealVector> = Population::new();
952        island_pop.push(Individual::with_fitness(RealVector::new(vec![0.0]), 500.0)); // best
953        for _ in 0..9 {
954            island_pop.push(Individual::with_fitness(RealVector::new(vec![9.0]), 1.0));
955            // worst
956        }
957        let mut island: Island<RealVector> = Island::with_population(3, island_pop);
958
959        // A migrant worse than the best but better than the worst.
960        let migrant = Individual::with_fitness(RealVector::new(vec![7.0]), 50.0);
961        island.accept_immigrants(vec![migrant]);
962
963        let best = island
964            .population
965            .iter()
966            .map(|ind| *ind.fitness_value())
967            .fold(f64::NEG_INFINITY, f64::max);
968        assert_eq!(best, 500.0, "the island best must survive migration");
969
970        let migrant_present = island
971            .population
972            .iter()
973            .any(|ind| (*ind.fitness_value() - 50.0).abs() < 1e-9);
974        assert!(migrant_present, "migrant should have been accepted");
975
976        let worst_count = island
977            .population
978            .iter()
979            .filter(|ind| (*ind.fitness_value() - 1.0).abs() < 1e-9)
980            .count();
981        assert_eq!(
982            worst_count, 8,
983            "exactly one worst member should be replaced"
984        );
985    }
986
987    // regression: EV-82 — the evaluation counter must count only genuine fitness
988    // calls. From generation 2 on, carried-over elites are already scored, so only
989    // (pop - elites) individuals are evaluated, not the whole population.
990    #[test]
991    fn test_island_evaluation_counter_counts_actual_evaluations() {
992        let mut rng = rand::rngs::StdRng::seed_from_u64(7);
993        let bounds = MultiBounds::symmetric(5.0, 5);
994        let mut island: Island<RealVector> = Island::new(0, 20, &bounds, &mut rng);
995
996        let fitness = Sphere::new(5);
997        let selection = TournamentSelection::new(2);
998        let crossover = BlxAlphaCrossover::new(0.5);
999        let mutation = GaussianMutation::new(0.1);
1000        let elitism = 2;
1001        let pop = 20;
1002        let generations = 5;
1003
1004        for _ in 0..generations {
1005            island
1006                .evolve_one_generation(
1007                    &fitness, &selection, &crossover, &mutation, elitism, &mut rng,
1008                )
1009                .unwrap();
1010        }
1011
1012        // gen 1 evaluates all `pop`; gens 2..=G evaluate only (pop - elitism).
1013        let expected = pop + (generations - 1) * (pop - elitism);
1014        assert_eq!(island.evaluations, expected);
1015    }
1016
1017    // regression: EV-83 — `evolve_one_generation` with `elitism` greater than the
1018    // population size must not panic. The pre-fix `population.len() - elitism` was
1019    // an unguarded usize subtraction that underflowed and panicked; the clamp
1020    // (`elite_count = elitism.min(pop_len)`, `target_offspring = pop_len -
1021    // elite_count`) makes it carry all members as elites and produce zero
1022    // offspring, returning a valid same-size population.
1023    #[test]
1024    fn test_island_elitism_exceeding_population_does_not_underflow() {
1025        let mut rng = StdRng::seed_from_u64(99);
1026        let pop = 20;
1027        let bounds = MultiBounds::symmetric(5.0, 5);
1028        let mut island: Island<RealVector> = Island::new(0, pop, &bounds, &mut rng);
1029
1030        let fitness = Sphere::new(5);
1031        let selection = TournamentSelection::new(2);
1032        let crossover = BlxAlphaCrossover::new(0.5);
1033        let mutation = GaussianMutation::new(0.1);
1034
1035        // Snapshot the whole population's genomes so we can prove every member is
1036        // carried over unchanged when everyone is an elite.
1037        island.population.evaluate(&fitness);
1038        island.population.sort_by_fitness();
1039        let before: Vec<RealVector> = island
1040            .population
1041            .iter()
1042            .map(|ind| ind.genome.clone())
1043            .collect();
1044
1045        // elitism (25) deliberately exceeds pop (20); this panicked pre-fix.
1046        let elitism = 25;
1047        let result = island.evolve_one_generation(
1048            &fitness, &selection, &crossover, &mutation, elitism, &mut rng,
1049        );
1050        assert!(
1051            result.is_ok(),
1052            "over-large elitism must return Ok, got {result:?}"
1053        );
1054
1055        // Population size is preserved: all members carried as elites, zero
1056        // offspring produced.
1057        assert_eq!(
1058            island.population.len(),
1059            pop,
1060            "population size must be preserved when everyone is an elite"
1061        );
1062
1063        // Every original genome survives (elitism == whole population => no
1064        // reproduction). Order is preserved because elites are pushed in sorted
1065        // order and no offspring follow.
1066        let after: Vec<RealVector> = island
1067            .population
1068            .iter()
1069            .map(|ind| ind.genome.clone())
1070            .collect();
1071        assert_eq!(
1072            after.len(),
1073            before.len(),
1074            "no offspring should be created when elite_count == pop_len"
1075        );
1076        for (a, b) in after.iter().zip(before.iter()) {
1077            assert_eq!(
1078                a.as_vec(),
1079                b.as_vec(),
1080                "all elites must be carried unchanged"
1081            );
1082        }
1083    }
1084}
fugue_evo/algorithms/island.rs

fugue_evo/algorithms/
island.rs
