genetic_algorithms 2.2.0

//! Island Model for parallel multi-population genetic algorithm evolution.
//!
//! The island model runs multiple independent populations (islands) that
//! evolve in parallel using `rayon`. Periodically, the best individuals
//! from each island migrate to neighboring islands according to a
//! configurable topology.
//!
//! # Example
//!
//! ```ignore
//! use genetic_algorithms::island::configuration::IslandConfiguration;
//! use genetic_algorithms::island::topology::MigrationTopology;
//! use genetic_algorithms::island::IslandGa;
//!
//! let island_config = IslandConfiguration::new()
//!     .with_num_islands(4)
//!     .with_migration_interval(10)
//!     .with_migration_count(2)
//!     .with_topology(MigrationTopology::Ring);
//! ```

pub mod configuration;
pub mod migration;
pub mod nsga2;
pub mod topology;

use crate::configuration::{GaConfiguration, ProblemSolving};
use crate::error::GaError;
use crate::island::configuration::IslandConfiguration;
use crate::island::migration::migrate;
use crate::observer::IslandGaObserver;
use crate::operations::mutation;
use crate::population::Population;
use crate::stats::GenerationStats;
use crate::traits::{ChromosomeT, FitnessFn, InitializationFn};
use std::sync::Arc;

/// Island Model Genetic Algorithm orchestrator.
///
/// Runs multiple GA populations in parallel with periodic migration.
///
/// Each island can use a different `GaConfiguration` for heterogeneous evolution
/// strategies. When `ga_configs` has fewer entries than the number of islands,
/// the last entry is reused for the remaining islands.
///
/// # Type Parameters
///
/// * `U` - Chromosome type implementing `ChromosomeT`.
pub struct IslandGa<U>
where
    U: ChromosomeT,
{
    /// Island model configuration.
    pub island_config: IslandConfiguration,
    /// Per-island GA configurations. If fewer than `num_islands`, the last entry
    /// is cycled for the remaining islands.
    pub ga_configs: Vec<GaConfiguration>,
    /// The populations for each island.
    pub islands: Vec<Population<U>>,
    /// Alleles template for initialization.
    pub alleles: Vec<U::Gene>,
    /// Initialization function.
    pub initialization_fn: Option<Arc<InitializationFn<U::Gene>>>,
    /// Fitness function.
    pub fitness_fn: Option<Arc<FitnessFn<U::Gene>>>,
    /// Optional lifecycle observer for island-specific events.
    observer: Option<Arc<dyn IslandGaObserver<U> + Send + Sync>>,
}

impl<U> IslandGa<U>
where
    U: ChromosomeT,
{
    /// Creates a new `IslandGa` with a single shared GA configuration for all islands.
    ///
    /// # Arguments
    ///
    /// * `island_config` - Configuration for the island model.
    /// * `ga_config` - Base GA configuration applied to each island.
    ///
    /// # Returns
    ///
    /// A new `IslandGa` instance.
    pub fn new(island_config: IslandConfiguration, ga_config: GaConfiguration) -> Self {
        IslandGa {
            island_config,
            ga_configs: vec![ga_config],
            islands: Vec::new(),
            alleles: Vec::new(),
            initialization_fn: None,
            fitness_fn: None,
            observer: None,
        }
    }

    /// Creates a new `IslandGa` with per-island GA configurations.
    ///
    /// When `configs` has fewer entries than `num_islands`, the last entry is
    /// repeated for the remaining islands. This allows heterogeneous evolution
    /// strategies — e.g. different mutation rates or selection methods per island.
    ///
    /// # Arguments
    ///
    /// * `island_config` - Configuration for the island model.
    /// * `configs` - One or more GA configurations. Must not be empty.
    ///
    /// # Returns
    ///
    /// A new `IslandGa` instance.
    pub fn with_heterogeneous_configs(
        island_config: IslandConfiguration,
        configs: Vec<GaConfiguration>,
    ) -> Self {
        IslandGa {
            island_config,
            ga_configs: configs,
            islands: Vec::new(),
            alleles: Vec::new(),
            initialization_fn: None,
            fitness_fn: None,
            observer: None,
        }
    }

    /// Returns the effective GA configuration for a given island index.
    ///
    /// If `ga_configs` has fewer entries than the number of islands, the last
    /// entry is returned for out-of-range indices.
    pub fn config_for_island(&self, island_index: usize) -> &GaConfiguration {
        if island_index < self.ga_configs.len() {
            &self.ga_configs[island_index]
        } else {
            self.ga_configs
                .last()
                .expect("ga_configs must not be empty")
        }
    }

    /// Sets the alleles template.
    pub fn with_alleles(mut self, alleles: Vec<U::Gene>) -> Self {
        self.alleles = alleles;
        self
    }

    /// Sets the initialization function.
    pub fn with_initialization_fn<F>(mut self, f: F) -> Self
    where
        F: Fn(usize, Option<&[U::Gene]>, Option<bool>) -> Vec<U::Gene> + Send + Sync + 'static,
    {
        self.initialization_fn = Some(Arc::new(f));
        self
    }

    /// Sets the fitness function.
    pub fn with_fitness_fn<F>(mut self, f: F) -> Self
    where
        F: Fn(&[U::Gene]) -> f64 + Send + Sync + 'static,
    {
        self.fitness_fn = Some(Arc::new(f));
        self
    }

    /// Attaches a lifecycle observer that receives island-specific hooks during execution.
    ///
    /// The observer is stored as an `Arc` for thread-safe sharing across rayon island threads.
    /// All hooks receive `&self`, so observers that need interior mutability should use
    /// `Mutex`, `AtomicU64`, or similar.
    ///
    /// See [`IslandGaObserver`](crate::observer::IslandGaObserver) for the hook contract.
    pub fn with_observer(mut self, obs: Arc<dyn IslandGaObserver<U> + Send + Sync>) -> Self {
        self.observer = Some(obs);
        self
    }

    /// Dispatches an island observer hook if an observer is attached. No-op when `self.observer` is `None`.
    #[inline]
    fn notify<F: FnOnce(&dyn IslandGaObserver<U>)>(&self, f: F) {
        if let Some(ref obs) = self.observer {
            f(obs.as_ref());
        }
    }

    /// Validates configuration and returns a ready-to-run instance.
    ///
    /// Call this after setting all builder options and before calling `run()`.
    ///
    /// # Errors
    ///
    /// Returns `GaError` if validation fails (see [`validate`](Self::validate)).
    pub fn build(self) -> Result<Self, GaError> {
        self.validate()?;
        Ok(self)
    }

    /// Validates the island configuration.
    ///
    /// # Returns
    ///
    /// `Ok(())` if valid, `Err(GaError)` otherwise.
    ///
    /// # Errors
    ///
    /// Returns `GaError::InvalidIslandConfiguration` if parameters are invalid.
    pub fn validate(&self) -> Result<(), GaError> {
        if self.island_config.num_islands == 0 {
            return Err(GaError::InvalidIslandConfiguration(
                "num_islands must be > 0".to_string(),
            ));
        }
        if self.island_config.migration_interval == 0 {
            return Err(GaError::InvalidIslandConfiguration(
                "migration_interval must be > 0".to_string(),
            ));
        }
        if self.island_config.migration_count == 0 {
            return Err(GaError::InvalidIslandConfiguration(
                "migration_count must be > 0".to_string(),
            ));
        }
        if self.ga_configs.is_empty() {
            return Err(GaError::InvalidIslandConfiguration(
                "ga_configs must not be empty".to_string(),
            ));
        }
        if self.initialization_fn.is_none() {
            return Err(GaError::InvalidIslandConfiguration(
                "initialization_fn is required".to_string(),
            ));
        }
        if self.fitness_fn.is_none() {
            return Err(GaError::InvalidIslandConfiguration(
                "fitness_fn is required".to_string(),
            ));
        }
        // Check migration count against the smallest population size across all configs
        for (i, config) in self.ga_configs.iter().enumerate() {
            let pop_size = config.limit_configuration.population_size;
            if self.island_config.migration_count >= pop_size {
                return Err(GaError::InvalidIslandConfiguration(format!(
                    "migration_count ({}) must be < population_size ({}) for config index {}",
                    self.island_config.migration_count, pop_size, i
                )));
            }
        }
        Ok(())
    }

    /// Initializes all islands with random populations.
    ///
    /// Each island uses its own `GaConfiguration` (from `ga_configs`) to determine
    /// population size and gene parameters.
    ///
    /// # Errors
    ///
    /// Returns `GaError::InitializationError` if initialization fails.
    pub fn initialize(&mut self) -> Result<(), GaError> {
        let init_fn = self.initialization_fn.as_ref().ok_or_else(|| {
            GaError::InitializationError("No initialization function set".to_string())
        })?;
        let fitness_fn = self
            .fitness_fn
            .as_ref()
            .ok_or_else(|| GaError::InitializationError("No fitness function set".to_string()))?;

        let num_islands = self.island_config.num_islands;

        let alleles = if self.alleles.is_empty() {
            None
        } else {
            Some(self.alleles.as_slice())
        };

        self.islands = Vec::with_capacity(num_islands);

        for island_idx in 0..num_islands {
            let cfg = self.config_for_island(island_idx);
            let pop_size = cfg.limit_configuration.population_size;
            let genes_per_chrom = cfg.limit_configuration.genes_per_chromosome;
            let alleles_can_repeat = cfg.limit_configuration.alleles_can_be_repeated;

            let chromosomes = crate::traits::initialize_chromosomes::<U>(
                pop_size,
                genes_per_chrom,
                alleles,
                Some(alleles_can_repeat),
                init_fn,
                Some(fitness_fn),
                0,
            );

            self.islands.push(Population::new(chromosomes));
        }

        Ok(())
    }

    /// Returns the best chromosome across all islands.
    fn global_best(&self, problem_solving: ProblemSolving) -> U {
        let mut best: Option<&U> = None;

        for island in &self.islands {
            for chrom in &island.chromosomes {
                let is_better = match best {
                    None => true,
                    Some(current_best) => match problem_solving {
                        ProblemSolving::Minimization | ProblemSolving::FixedFitness => {
                            chrom.fitness() < current_best.fitness()
                        }
                        ProblemSolving::Maximization => chrom.fitness() > current_best.fitness(),
                    },
                };
                if is_better {
                    best = Some(chrom);
                }
            }
        }

        // Safety: we always initialize at least one island with at least one chromosome
        best.expect("Islands should not be empty after initialization")
            .clone()
    }
}

impl<U> IslandGa<U>
where
    U: ChromosomeT + mutation::ValueMutable,
{
    /// Runs the island model GA and returns the best chromosome found across all islands.
    ///
    /// # Returns
    ///
    /// `Ok(U)` - The best chromosome found across all islands.
    ///
    /// # Errors
    ///
    /// Returns `GaError` if validation, initialization, or migration fails.
    pub fn run(&mut self) -> Result<U, GaError> {
        self.validate()?;
        self.initialize()?;

        // Apply RNG seed from the first island config if configured
        let base_config = self.config_for_island(0);
        crate::rng::set_seed(base_config.rng_seed);

        // Use the first config's limit settings for the global run parameters
        let max_generations = base_config.limit_configuration.max_generations;
        let problem_solving = base_config.limit_configuration.problem_solving;
        let fitness_target = base_config.limit_configuration.fitness_target;

        self.notify(|obs| obs.on_island_run_start(0));

        for gen in 0..max_generations {
            // Evolve each island for one generation
            self.evolve_islands_one_generation(gen, problem_solving)?;

            // Check fitness target
            if let Some(target) = fitness_target {
                let best = self.global_best(problem_solving);
                let dist = (best.fitness() - target).abs();
                if dist < 1e-10 {
                    self.notify(|obs| obs.on_island_run_end(0));
                    return Ok(best);
                }
            }

            // Migration
            if gen > 0
                && self.island_config.migration_interval > 0
                && gen % self.island_config.migration_interval == 0
            {
                let migration_count = self.island_config.migration_count;
                migrate(&mut self.islands, &self.island_config, problem_solving)?;
                self.notify(|obs| obs.on_migration_triggered(gen, migration_count));
            }
        }

        self.notify(|obs| obs.on_island_run_end(0));
        Ok(self.global_best(problem_solving))
    }

    /// Performs one generation of evolution on each island.
    ///
    /// Each island uses its own `GaConfiguration` for operator parameters.
    fn evolve_islands_one_generation(
        &mut self,
        gen: usize,
        problem_solving: ProblemSolving,
    ) -> Result<(), GaError> {
        use crate::operations::{crossover, mutation, selection, survivor};
        use rand::Rng;
        use rayon::prelude::*;

        let fitness_fn = self
            .fitness_fn
            .as_ref()
            .ok_or_else(|| GaError::ConfigurationError("No fitness function set".to_string()))?;

        let fitness_fn = Arc::clone(fitness_fn);

        // Clone observer Arc once before entering the parallel region.
        let observer_clone: Option<Arc<dyn IslandGaObserver<U> + Send + Sync>> =
            self.observer.as_ref().map(Arc::clone);

        let is_maximization = matches!(problem_solving, ProblemSolving::Maximization);

        // Build a per-island config snapshot so we can move into the parallel closure.
        // Each tuple holds (selection, crossover, mutation, survivor, limit, num_threads).
        let island_configs: Vec<_> = (0..self.islands.len())
            .map(|i| {
                let cfg = self.config_for_island(i);
                (
                    cfg.selection_configuration,
                    cfg.crossover_configuration,
                    cfg.mutation_configuration,
                    cfg.survivor,
                    cfg.limit_configuration,
                    cfg.number_of_threads,
                )
            })
            .collect();

        self.islands
            .par_iter_mut()
            .enumerate()
            .try_for_each(|(idx, island)| {
                let (
                    selection_config,
                    crossover_config,
                    mutation_config,
                    survivor_method,
                    limit_config,
                    num_threads,
                ) = island_configs[idx];
                let pop_size = limit_config.population_size;

                // Selection: returns Vec<(usize, usize)> parent index pairs
                let parent_pairs =
                    selection::factory(&island.chromosomes, selection_config, num_threads)?;

                // Crossover: iterate over parent pairs
                let mut rng = crate::rng::make_rng();
                let crossover_prob = crossover_config.probability_max.unwrap_or(1.0);

                let mut offspring: Vec<U> = Vec::new();
                for &(idx_a, idx_b) in &parent_pairs {
                    let p: f64 = rng.random();
                    if p <= crossover_prob {
                        let children = crossover::factory(
                            &island.chromosomes[idx_a],
                            &island.chromosomes[idx_b],
                            crossover_config,
                        )?;
                        offspring.extend(children);
                    } else {
                        offspring.push(island.chromosomes[idx_a].clone());
                        offspring.push(island.chromosomes[idx_b].clone());
                    }
                }

                // Mutation
                let mut_prob = mutation_config.probability_max.unwrap_or(0.1);
                for child in offspring.iter_mut() {
                    let p: f64 = rng.random();
                    if p <= mut_prob {
                        mutation::factory_with_params(
                            mutation_config.method,
                            child,
                            mutation_config.step,
                            mutation_config.sigma,
                        )?;
                    }
                }

                // Assign fitness to offspring
                for child in offspring.iter_mut() {
                    let ff = Arc::clone(&fitness_fn);
                    child.set_fitness_fn(move |genes| ff(genes));
                    child.calculate_fitness();
                }

                // Combine parent population with offspring
                island.chromosomes.append(&mut offspring);

                // Survivor selection: trims in-place to pop_size
                survivor::factory(
                    survivor_method,
                    &mut island.chromosomes,
                    pop_size,
                    limit_config,
                )?;

                // Fire per-island generation hook if an observer is attached
                if let Some(ref obs) = observer_clone {
                    let fitness_values: Vec<f64> =
                        island.chromosomes.iter().map(|c| c.fitness()).collect();
                    let stats = GenerationStats::from_fitness_values(
                        gen,
                        &fitness_values,
                        is_maximization,
                    );
                    obs.on_island_generation_end(idx, gen, &stats);
                }

                Ok(())
            })
    }
}