scirs2_optimize/multi_objective/algorithms/
nsga2.rs

1//! NSGA-II (Non-dominated Sorting Genetic Algorithm II) implementation
2//!
3//! This module provides a complete implementation of the NSGA-II algorithm
4//! for multi-objective optimization problems.
5
6use super::{utils, MultiObjectiveConfig, MultiObjectiveOptimizer};
7use crate::error::OptimizeError;
8use crate::multi_objective::crossover::{CrossoverOperator, SimulatedBinaryCrossover};
9use crate::multi_objective::mutation::{MutationOperator, PolynomialMutation};
10use crate::multi_objective::selection::{SelectionOperator, TournamentSelection};
11use crate::multi_objective::solutions::{MultiObjectiveResult, MultiObjectiveSolution, Population};
12use ndarray::{s, Array1, ArrayView1};
13use rand::rngs::StdRng;
14use rand::{prelude::*, SeedableRng};
15
16/// NSGA-II (Non-dominated Sorting Genetic Algorithm II) implementation
17pub struct NSGAII {
18    config: MultiObjectiveConfig,
19    n_objectives: usize,
20    n_variables: usize,
21    population: Population,
22    generation: usize,
23    n_evaluations: usize,
24    rng: StdRng,
25    crossover: SimulatedBinaryCrossover,
26    mutation: PolynomialMutation,
27    selection: TournamentSelection,
28    convergence_history: Vec<f64>,
29}
30
31impl NSGAII {
32    /// Create a new NSGA-II optimizer
33    pub fn new(
34        config: MultiObjectiveConfig,
35        n_objectives: usize,
36        n_variables: usize,
37    ) -> Result<Self, OptimizeError> {
38        if n_objectives == 0 {
39            return Err(OptimizeError::InvalidInput(
40                "Number of objectives must be > 0".to_string(),
41            ));
42        }
43        if n_variables == 0 {
44            return Err(OptimizeError::InvalidInput(
45                "Number of variables must be > 0".to_string(),
46            ));
47        }
48        if config.population_size == 0 {
49            return Err(OptimizeError::InvalidInput(
50                "Population size must be > 0".to_string(),
51            ));
52        }
53
54        let seed = config.random_seed.unwrap_or_else(|| {
55            use std::time::{SystemTime, UNIX_EPOCH};
56            SystemTime::now()
57                .duration_since(UNIX_EPOCH)
58                .unwrap()
59                .as_secs()
60        });
61
62        let rng = StdRng::seed_from_u64(seed);
63
64        let crossover =
65            SimulatedBinaryCrossover::new(config.crossover_eta, config.crossover_probability);
66
67        let mutation = PolynomialMutation::new(config.mutation_probability, config.mutation_eta);
68
69        let selection = TournamentSelection::new(2);
70
71        Ok(Self {
72            config,
73            n_objectives,
74            n_variables,
75            population: Population::new(),
76            generation: 0,
77            n_evaluations: 0,
78            rng,
79            crossover,
80            mutation,
81            selection,
82            convergence_history: Vec::new(),
83        })
84    }
85
86    /// Evaluate a single individual
87    fn evaluate_individual<F>(
88        &mut self,
89        variables: &Array1<f64>,
90        objective_function: &F,
91    ) -> Result<Array1<f64>, OptimizeError>
92    where
93        F: Fn(&ArrayView1<f64>) -> Array1<f64> + Send + Sync,
94    {
95        self.n_evaluations += 1;
96
97        // Check evaluation limit
98        if let Some(max_evals) = self.config.max_evaluations {
99            if self.n_evaluations > max_evals {
100                return Err(OptimizeError::MaxEvaluationsReached);
101            }
102        }
103
104        let objectives = objective_function(&variables.view());
105
106        if objectives.len() != self.n_objectives {
107            return Err(OptimizeError::InvalidInput(format!(
108                "Expected {} objectives, got {}",
109                self.n_objectives,
110                objectives.len()
111            )));
112        }
113
114        Ok(objectives)
115    }
116
117    /// Create offspring through crossover and mutation
118    fn create_offspring<F>(
119        &mut self,
120        objective_function: &F,
121    ) -> Result<Vec<MultiObjectiveSolution>, OptimizeError>
122    where
123        F: Fn(&ArrayView1<f64>) -> Array1<f64> + Send + Sync,
124    {
125        let mut offspring = Vec::new();
126
127        while offspring.len() < self.config.population_size {
128            // Select parents using tournament selection (clone to avoid borrowing issues)
129            let population_solutions = self.population.solutions().to_vec();
130            let selected_parents = self.selection.select(&population_solutions, 2);
131            if selected_parents.len() < 2 {
132                break;
133            }
134
135            let parent1 = &selected_parents[0];
136            let parent2 = &selected_parents[1];
137
138            // Perform crossover
139            let (mut child1_vars, mut child2_vars) = self.crossover.crossover(
140                parent1.variables.as_slice().unwrap(),
141                parent2.variables.as_slice().unwrap(),
142            );
143
144            // Apply mutation (need bounds for mutation)
145            let bounds: Vec<(f64, f64)> = if let Some((lower, upper)) = &self.config.bounds {
146                lower
147                    .iter()
148                    .zip(upper.iter())
149                    .map(|(&l, &u)| (l, u))
150                    .collect()
151            } else {
152                vec![(-1.0, 1.0); child1_vars.len()]
153            };
154
155            self.mutation.mutate(&mut child1_vars, &bounds);
156            self.mutation.mutate(&mut child2_vars, &bounds);
157
158            // Convert to Array1 for evaluation
159            let child1_array = Array1::from_vec(child1_vars);
160            let child2_array = Array1::from_vec(child2_vars);
161
162            // Evaluate offspring
163            let child1_objs = self.evaluate_individual(&child1_array, objective_function)?;
164            let child2_objs = self.evaluate_individual(&child2_array, objective_function)?;
165
166            offspring.push(MultiObjectiveSolution::new(child1_array, child1_objs));
167
168            if offspring.len() < self.config.population_size {
169                offspring.push(MultiObjectiveSolution::new(child2_array, child2_objs));
170            }
171        }
172
173        Ok(offspring)
174    }
175
176    /// Environmental selection using NSGA-II procedure
177    fn environmental_selection(
178        &mut self,
179        combined_population: Vec<MultiObjectiveSolution>,
180    ) -> Vec<MultiObjectiveSolution> {
181        let mut temp_population = Population::from_solutions(combined_population);
182        temp_population.select_best(self.config.population_size)
183    }
184
185    /// Calculate generation metrics
186    fn calculate_metrics(&mut self) {
187        if let Some(ref_point) = &self.config.reference_point {
188            let pareto_front = self.population.extract_pareto_front();
189            let hypervolume = utils::calculate_hypervolume(&pareto_front, ref_point);
190            self.convergence_history.push(hypervolume);
191        }
192    }
193}
194
195impl MultiObjectiveOptimizer for NSGAII {
196    fn optimize<F>(&mut self, objective_function: F) -> Result<MultiObjectiveResult, OptimizeError>
197    where
198        F: Fn(&ArrayView1<f64>) -> Array1<f64> + Send + Sync,
199    {
200        // Initialize population
201        self.initialize_population()?;
202
203        // Evaluate initial population
204        let initial_variables = utils::generate_random_population(
205            self.config.population_size,
206            self.n_variables,
207            &self.config.bounds,
208        );
209
210        let mut initial_solutions = Vec::new();
211        for variables in initial_variables {
212            let objectives = self.evaluate_individual(&variables, &objective_function)?;
213            initial_solutions.push(MultiObjectiveSolution::new(variables, objectives));
214        }
215
216        self.population = Population::from_solutions(initial_solutions);
217
218        // Main evolution loop
219        while self.generation < self.config.max_generations {
220            if self.check_convergence() {
221                break;
222            }
223
224            self.evolve_generation(&objective_function)?;
225        }
226
227        // Extract final results
228        let pareto_front = self.population.extract_pareto_front();
229        let hypervolume = if let Some(ref_point) = &self.config.reference_point {
230            Some(utils::calculate_hypervolume(&pareto_front, ref_point))
231        } else {
232            None
233        };
234
235        let mut result = MultiObjectiveResult::new(
236            pareto_front,
237            self.population.solutions().to_vec(),
238            self.n_evaluations,
239            self.generation,
240        );
241
242        result.hypervolume = hypervolume;
243        result.metrics.convergence_history = self.convergence_history.clone();
244        result.metrics.population_stats = self.population.calculate_statistics();
245
246        Ok(result)
247    }
248
249    fn initialize_population(&mut self) -> Result<(), OptimizeError> {
250        self.population.clear();
251        self.generation = 0;
252        self.n_evaluations = 0;
253        self.convergence_history.clear();
254        Ok(())
255    }
256
257    fn evolve_generation<F>(&mut self, objective_function: &F) -> Result<(), OptimizeError>
258    where
259        F: Fn(&ArrayView1<f64>) -> Array1<f64> + Send + Sync,
260    {
261        // Create offspring
262        let offspring = self.create_offspring(objective_function)?;
263
264        // Combine parent and offspring populations
265        let mut combined = self.population.solutions().to_vec();
266        combined.extend(offspring);
267
268        // Environmental selection
269        let next_population = self.environmental_selection(combined);
270        self.population = Population::from_solutions(next_population);
271
272        // Update generation counter
273        self.generation += 1;
274
275        // Calculate metrics
276        self.calculate_metrics();
277
278        Ok(())
279    }
280
281    fn check_convergence(&self) -> bool {
282        // Check maximum evaluations
283        if let Some(max_evals) = self.config.max_evaluations {
284            if self.n_evaluations >= max_evals {
285                return true;
286            }
287        }
288
289        // Check hypervolume convergence
290        if self.convergence_history.len() >= 10 {
291            let recent_history = &self.convergence_history[self.convergence_history.len() - 10..];
292            let max_hv = recent_history
293                .iter()
294                .fold(f64::NEG_INFINITY, |a, &b| a.max(b));
295            let min_hv = recent_history.iter().fold(f64::INFINITY, |a, &b| a.min(b));
296
297            if (max_hv - min_hv) < self.config.tolerance {
298                return true;
299            }
300        }
301
302        false
303    }
304
305    fn get_population(&self) -> &Population {
306        &self.population
307    }
308
309    fn get_generation(&self) -> usize {
310        self.generation
311    }
312
313    fn get_evaluations(&self) -> usize {
314        self.n_evaluations
315    }
316
317    fn name(&self) -> &str {
318        "NSGA-II"
319    }
320}
321
322#[cfg(test)]
323mod tests {
324    use super::*;
325    use ndarray::array;
326
327    // Simple test problem (ZDT1)
328    fn zdt1(x: &ArrayView1<f64>) -> Array1<f64> {
329        let f1 = x[0];
330        let g = 1.0 + 9.0 * x.slice(s![1..]).sum() / (x.len() - 1) as f64;
331        let f2 = g * (1.0 - (f1 / g).sqrt());
332        array![f1, f2]
333    }
334
335    #[test]
336    fn test_nsga2_creation() {
337        let config = MultiObjectiveConfig::default();
338        let nsga2 = NSGAII::new(config, 2, 3);
339        assert!(nsga2.is_ok());
340
341        let nsga2 = nsga2.unwrap();
342        assert_eq!(nsga2.n_objectives, 2);
343        assert_eq!(nsga2.n_variables, 3);
344        assert_eq!(nsga2.generation, 0);
345    }
346
347    #[test]
348    fn test_nsga2_invalid_parameters() {
349        let config = MultiObjectiveConfig::default();
350
351        // Zero objectives
352        let nsga2 = NSGAII::new(config.clone(), 0, 3);
353        assert!(nsga2.is_err());
354
355        // Zero variables
356        let nsga2 = NSGAII::new(config.clone(), 2, 0);
357        assert!(nsga2.is_err());
358
359        // Zero population size
360        let mut config_zero_pop = config;
361        config_zero_pop.population_size = 0;
362        let nsga2 = NSGAII::new(config_zero_pop, 2, 3);
363        assert!(nsga2.is_err());
364    }
365
366    #[test]
367    fn test_nsga2_optimization() {
368        let mut config = MultiObjectiveConfig::default();
369        config.max_generations = 10;
370        config.population_size = 20;
371        config.bounds = Some((Array1::zeros(2), Array1::ones(2)));
372        config.random_seed = Some(42);
373
374        let mut nsga2 = NSGAII::new(config, 2, 2).unwrap();
375        let result = nsga2.optimize(zdt1);
376
377        assert!(result.is_ok());
378        let result = result.unwrap();
379        assert!(result.success);
380        assert!(!result.pareto_front.is_empty());
381        assert_eq!(result.n_generations, 10);
382        assert!(result.n_evaluations > 0);
383    }
384
385    #[test]
386    fn test_nsga2_with_max_evaluations() {
387        let mut config = MultiObjectiveConfig::default();
388        config.max_generations = 1000; // High value
389        config.max_evaluations = Some(50); // Low evaluation limit
390        config.population_size = 10;
391        config.bounds = Some((Array1::zeros(2), Array1::ones(2)));
392
393        let mut nsga2 = NSGAII::new(config, 2, 2).unwrap();
394        let result = nsga2.optimize(zdt1);
395
396        assert!(result.is_ok());
397        let result = result.unwrap();
398        assert!(result.n_evaluations <= 50);
399    }
400
401    #[test]
402    fn test_nsga2_hypervolume_calculation() {
403        let mut config = MultiObjectiveConfig::default();
404        config.max_generations = 5;
405        config.population_size = 10;
406        config.bounds = Some((Array1::zeros(2), Array1::ones(2)));
407        config.reference_point = Some(array![2.0, 2.0]);
408
409        let mut nsga2 = NSGAII::new(config, 2, 2).unwrap();
410        let result = nsga2.optimize(zdt1).unwrap();
411
412        assert!(result.hypervolume.is_some());
413        assert!(result.hypervolume.unwrap() >= 0.0);
414        assert!(!result.metrics.convergence_history.is_empty());
415    }
416
417    #[test]
418    fn test_nsga2_convergence_check() {
419        let mut config = MultiObjectiveConfig::default();
420        config.tolerance = 1e-10; // Very tight tolerance
421        config.max_generations = 2; // Few generations
422        config.population_size = 10;
423
424        let nsga2 = NSGAII::new(config, 2, 2).unwrap();
425
426        // With empty convergence history, should not converge
427        assert!(!nsga2.check_convergence());
428    }
429
430    #[test]
431    fn test_nsga2_name() {
432        let config = MultiObjectiveConfig::default();
433        let nsga2 = NSGAII::new(config, 2, 2).unwrap();
434        assert_eq!(nsga2.name(), "NSGA-II");
435    }
436}
scirs2_optimize/multi_objective/algorithms/nsga2.rs

scirs2_optimize/multi_objective/algorithms/
nsga2.rs
