puggles 0.3.0

Multi-objective evolutionary optimization: NSGA-II and NSGA-III over continuous, integer, and binary variables, with constraint handling, Rayon parallelism, and optional GPU evaluation.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
//! NSGA-III — reference-point-based many-objective optimizer (Deb & Jain, 2014).
//!
//! Same variation machinery as [`crate::genetic_algorithms_v2::NSGAII`], but survival
//! selection replaces crowding distance with **structured reference points**: solutions
//! are associated to reference directions and the least-represented directions are
//! preferred. This keeps diversity in problems with >3 objectives, where crowding
//! distance loses discriminating power.
//!
//! ponytail: normalization uses ideal-point translation + per-objective range (a common
//! simplification), not the full achievement-scalarizing hyperplane-intercept method.
//! Good enough for typical use; swap in exact intercepts if a benchmark needs it.

use crate::core::{EvalFn, Problem, Solution};
use crate::dominance::{crowding_distance, fast_non_dominated_sort, ParetoDominance};
use crate::genetic_algorithms_v2::{evaluate_population_shared, ExecutionInfo, ExecutionMode, GenerationTimes};
use crate::genetic_operators::crossover::CrossoverManager;
use crate::genetic_operators::mutation::MutationManager;
use crate::genetic_operators::selectors::CrowdingTournamentSelector;
use rand::rngs::SmallRng;
use rand::SeedableRng;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::Arc;
use std::time::Instant;

/// Structured reference points on the unit simplex (Das & Dennis): every point has
/// non-negative coordinates summing to 1, on a grid of `divisions` steps. For `m`
/// objectives the count is C(m + divisions - 1, divisions).
pub fn das_dennis(m: usize, divisions: usize) -> Vec<Vec<f64>> {
    fn rec(m: usize, idx: usize, left: usize, div: usize, point: &mut Vec<usize>, out: &mut Vec<Vec<usize>>) {
        if idx == m - 1 {
            point[idx] = left;
            out.push(point.clone());
            return;
        }
        for i in 0..=left {
            point[idx] = i;
            rec(m, idx + 1, left - i, div, point, out);
        }
    }
    let mut out = Vec::new();
    let mut point = vec![0usize; m];
    rec(m, 0, divisions, divisions, &mut point, &mut out);
    out.into_iter()
        .map(|p| p.iter().map(|&v| v as f64 / divisions as f64).collect())
        .collect()
}

pub struct NSGAIII {
    pub problem: Arc<Problem>,
    pub population_size: usize,
    pub population: Vec<Solution>,
    pub archive: Vec<Solution>,
    nfe: AtomicUsize,
    execution_mode: ExecutionMode,
    selector: CrowdingTournamentSelector,
    dominance: ParetoDominance,
    mutation_manager: MutationManager,
    crossover_manager: CrossoverManager,
    rng: SmallRng,
    reference_points: Vec<Vec<f64>>,
    /// The uniform Das–Dennis grid, kept so a focus can be cleared.
    base_reference_points: Vec<Vec<f64>>,
    ranks: Vec<usize>,
    crowding: Vec<f64>,
    /// Each population member's front, as survival found it — exact for the population, since
    /// it is whole fronts 0..k-1 plus part of front k — so the next generation's parent
    /// selection and the archive need no second sort. `None` once the population may have been
    /// changed from outside (an observer's `&mut Self`, a new `run`).
    survivor_ranks: Option<Vec<usize>>,
    generation_times: GenerationTimes,
    /// Optional GPU evaluator. When set and execution_mode == GPU, population evaluation is
    /// offloaded to the GPU, matching NSGA-II. Without one, GPU downgrades to multi-threaded
    /// with a warning instead of silently running on the CPU.
    #[cfg(feature = "gpu")]
    pub gpu_evaluator: Option<crate::gpu_evaluator::GpuEvaluator>,
}

impl NSGAIII {
    /// `divisions` controls reference-point density (e.g. 12 for 3 objectives → 91 points).
    /// The population size is taken as the reference-point count rounded up to a multiple
    /// of 4 if you pass 0, otherwise your value is used as-is.
    pub fn new(problem: Arc<Problem>, population_size: usize, divisions: usize, execution_mode: ExecutionMode) -> Self {
        let n = problem.solution_length;
        let m = problem.number_of_objectives;
        let mutation_manager = MutationManager::new(n);
        let reference_points = das_dennis(m, divisions);
        let population_size = if population_size == 0 {
            (reference_points.len() + 3) / 4 * 4
        } else {
            population_size
        };
        assert!(
            population_size > 0,
            "population_size must be > 0 (a zero population produces no offspring, so a run \
             can never spend its evaluation budget)"
        );
        Self {
            problem,
            population_size,
            population: Vec::with_capacity(population_size),
            archive: Vec::new(),
            nfe: AtomicUsize::new(0),
            execution_mode,
            selector: CrowdingTournamentSelector::new(2, None),
            dominance: ParetoDominance,
            mutation_manager,
            crossover_manager: CrossoverManager::new(),
            rng: SmallRng::from_entropy(),
            base_reference_points: reference_points.clone(),
            reference_points,
            ranks: Vec::new(),
            crowding: Vec::new(),
            survivor_ranks: None,
            generation_times: GenerationTimes::default(),
            #[cfg(feature = "gpu")]
            gpu_evaluator: None,
        }
    }

    /// Attach a GPU evaluator for use when `execution_mode == GPU`.
    /// Builder method — call before `run()`.
    #[cfg(feature = "gpu")]
    pub fn with_gpu_evaluator(mut self, evaluator: crate::gpu_evaluator::GpuEvaluator) -> Self {
        self.gpu_evaluator = Some(evaluator);
        self
    }

    /// Seed all randomness for a reproducible run. Builder-style; call before `run`.
    pub fn with_seed(mut self, seed: u64) -> Self {
        self.rng = SmallRng::seed_from_u64(seed);
        self.selector = CrowdingTournamentSelector::new(2, Some(seed));
        self
    }

    /// Move the archive out (leaving it empty), e.g. when the optimizer is about to be dropped.
    pub fn take_archive(&mut self) -> Vec<Solution> {
        std::mem::take(&mut self.archive)
    }

    pub fn get_archive(&self) -> &[Solution] {
        &self.archive
    }
    pub fn get_nfe(&self) -> usize {
        self.nfe.load(Ordering::Relaxed)
    }
    pub fn reference_points(&self) -> &[Vec<f64>] {
        &self.reference_points
    }

    /// Concentrate the search near `aspiration` (one target value per objective, in objective
    /// space; `NaN` = no preference, use the best value found). The reference grid is shrunk
    /// around the aspiration's direction from the current ideal point (as in R-NSGA-III);
    /// `spread` in (0, 1] sets how tightly (1 = the full front). Takes effect from the next
    /// generation; safe to call mid-run from `run_with`.
    pub fn focus_on(&mut self, aspiration: &[f64], spread: f64) {
        let m = self.problem.number_of_objectives;
        if self.population.is_empty() || aspiration.len() != m {
            return;
        }
        let dirs = self.problem.direction.clone().unwrap_or_else(|| vec![-1; m]);
        let idx: Vec<usize> = (0..self.population.len()).collect();
        let val = |i: usize, o: usize| {
            let v = self.population[i].objective_fitness_values[o];
            if dirs[o] == 1 { -v } else { v }
        };
        let (mut ideal, mut nadir) = (vec![f64::INFINITY; m], vec![f64::NEG_INFINITY; m]);
        for &i in &idx {
            for o in 0..m {
                ideal[o] = ideal[o].min(val(i, o));
                nadir[o] = nadir[o].max(val(i, o));
            }
        }
        // The aspiration in the same normalized minimization space the niching uses.
        let mut d: Vec<f64> = (0..m)
            .map(|o| {
                let z = aspiration[o];
                if !z.is_finite() {
                    return 0.0;
                }
                let z = if dirs[o] == 1 { -z } else { z };
                let range = nadir[o] - ideal[o];
                if range > f64::EPSILON { ((z - ideal[o]) / range).max(0.0) } else { 0.0 }
            })
            .collect();
        let sum: f64 = d.iter().sum();
        if sum > f64::EPSILON {
            d.iter_mut().for_each(|v| *v /= sum);
        } else {
            d = vec![1.0 / m as f64; m];
        }
        let spread = spread.clamp(0.01, 1.0);
        let centroid = 1.0 / m as f64;
        self.reference_points = self
            .base_reference_points
            .iter()
            .map(|p| {
                let mut q: Vec<f64> = p.iter().zip(&d).map(|(pi, di)| (di + spread * (pi - centroid)).max(0.0)).collect();
                let s: f64 = q.iter().sum();
                if s > f64::EPSILON {
                    q.iter_mut().for_each(|v| *v /= s);
                }
                q
            })
            .collect();
    }

    /// Back to the uniform reference grid (the whole front).
    pub fn clear_focus(&mut self) {
        self.reference_points = self.base_reference_points.clone();
    }

    /// Where evaluations run. NSGA-III has no GPU path: `GPU` runs on CPU threads.
    pub fn execution_info(&self) -> ExecutionInfo {
        let effective = self.effective_mode();
        #[cfg(feature = "gpu")]
        if effective == ExecutionMode::GPU {
            let gpu = self.gpu_evaluator.as_ref().expect("effective GPU implies an evaluator");
            return ExecutionInfo {
                requested: self.execution_mode,
                effective,
                cpu_threads: None,
                device: Some(gpu.device_description()),
                note: None,
            };
        }
        let note = if matches!(self.problem.eval_fn, EvalFn::Batch(_)) {
            Some("batch objective: called once per generation on the calling thread".to_string())
        } else if self.execution_mode == ExecutionMode::GPU {
            Some(if cfg!(feature = "gpu") {
                "GPU requested but no GpuEvaluator attached; evaluating on CPU threads".to_string()
            } else {
                "GPU requested but puggles was built without the `gpu` feature; evaluating on CPU threads".to_string()
            })
        } else {
            None
        };
        ExecutionInfo::cpu(self.execution_mode, effective, note)
    }

    /// The path evaluation will actually take: a batch objective runs once per generation on
    /// the calling thread, and `GPU` needs an attached evaluator (see `NSGAII::effective_mode`).
    pub fn effective_mode(&self) -> ExecutionMode {
        if matches!(self.problem.eval_fn, EvalFn::Batch(_)) {
            return ExecutionMode::Sequential;
        }
        if self.execution_mode == ExecutionMode::GPU {
            #[cfg(feature = "gpu")]
            let gpu_ready = self.gpu_evaluator.is_some();
            #[cfg(not(feature = "gpu"))]
            let gpu_ready = false;
            return if gpu_ready { ExecutionMode::GPU } else { ExecutionMode::MultiThreaded };
        }
        self.execution_mode
    }

    /// Solutions evaluated on the GPU so far, when a GPU evaluator is attached.
    pub fn gpu_evaluations(&self) -> Option<usize> {
        #[cfg(feature = "gpu")]
        if let Some(gpu) = &self.gpu_evaluator {
            return Some(gpu.evaluated_count());
        }
        None
    }

    fn initialize(&mut self) {
        let problem = Arc::clone(&self.problem);
        let mut pop = Vec::with_capacity(self.population_size);
        for _ in 0..self.population_size {
            let solution = problem.generate_solution(&mut self.rng);
            pop.push(Solution {
                problem: Arc::clone(&problem),
                solution,
                objective_fitness_values: Default::default(),
                constraint_values: Default::default(),
                evaluated: false,
                constraint_violation: 0,
                constraint_violation_magnitude: 0.0,
                feasible: false,
            });
        }
        self.population = pop;
    }

    /// Evaluate via the shared routine, so NSGA-III gets the same batch-objective and GPU
    /// support as NSGA-II rather than silently running everything on the CPU.
    fn evaluate(&self, population: &mut Vec<Solution>) -> usize {
        #[cfg(feature = "gpu")]
        {
            if let Some(gpu) = self.gpu_evaluator.as_ref() {
                let run_gpu = |inputs: &Vec<Vec<f64>>| gpu.evaluate_batch(inputs);
                let n = evaluate_population_shared(
                    population,
                    &self.problem,
                    self.execution_mode,
                    Some(&run_gpu),
                );
                self.nfe.fetch_add(n, Ordering::Relaxed);
                return n;
            }
        }
        let n = evaluate_population_shared(population, &self.problem, self.execution_mode, None);
        self.nfe.fetch_add(n, Ordering::Relaxed);
        n
    }

    /// Run until the NFE budget is spent. Auto-initializes.
    pub fn run(&mut self, max_nfe: usize) {
        self.run_inner(max_nfe, false, |_| true);
    }

    /// `run`, calling `on_generation` after every generation with the archive refreshed to the
    /// current non-dominated front. Return `false` from it to stop early. Used for live
    /// progress / dashboards.
    ///
    /// The closure gets `&mut Self`, so it can steer between generations (e.g. [`focus_on`](Self::focus_on)).
    pub fn run_with(&mut self, max_nfe: usize, on_generation: impl FnMut(&mut Self) -> bool) {
        self.run_inner(max_nfe, true, on_generation);
    }

    /// `run` skips the per-generation archive refresh (a full non-dominated sort) that only
    /// an observer needs, so plain runs cost exactly what they did before `run_with` existed.
    fn run_inner(&mut self, max_nfe: usize, refresh_archive: bool, mut on_generation: impl FnMut(&mut Self) -> bool) {
        self.survivor_ranks = None;
        if self.population.is_empty() {
            self.initialize();
        }
        let mut pop = std::mem::take(&mut self.population);
        self.evaluate(&mut pop);
        self.population = pop;

        self.archive = self.nondominated(&self.population);
        while self.nfe.load(Ordering::Relaxed) < max_nfe {
            let remaining = max_nfe - self.nfe.load(Ordering::Relaxed);
            self.iterate_n(remaining.min(self.population_size));
            if refresh_archive {
                let started = Instant::now();
                self.archive = self.population_front0();
                self.generation_times.archive = started.elapsed().as_secs_f64();
            }
            if !on_generation(self) {
                break;
            }
            if refresh_archive {
                // An observer gets `&mut Self` and may have changed the population.
                self.survivor_ranks = None;
            }
        }
        self.archive = self.population_front0();
    }

    /// Run one generation, creating at most `max_offspring` new solutions, so `run` can honour
    /// its NFE budget exactly instead of overshooting by up to a full population.
    fn iterate_n(&mut self, max_offspring: usize) {
        let started = Instant::now();
        // Parent selection by rank + crowding tournament (crowding is cheap and harmless).
        self.assign_fitness();
        let parent_indices = self.selector.select_indices(self.population_size, &self.ranks, &self.crowding);
        // Index parents directly instead of cloning them all into a scratch Vec.
        let np = parent_indices.len();
        let mut offspring: Vec<Solution> = Vec::with_capacity(max_offspring);
        let mut i = 0;
        while offspring.len() < max_offspring {
            let p1 = &self.population[parent_indices[i % np]];
            let p2 = &self.population[parent_indices[(i + 1) % np]];
            i += 2;
            let (c1, c2) = self.crossover_manager.perform_crossover_pair(p1, p2, &mut self.rng);
            for child in [c1, c2] {
                if offspring.len() < max_offspring {
                    offspring.push(self.mutation_manager.mutate_owned(child, &mut self.rng));
                }
            }
        }
        let varied = Instant::now();
        self.evaluate(&mut offspring);
        let evaluated = Instant::now();

        let mut combined = std::mem::take(&mut self.population);
        combined.extend(offspring);
        let (survivors, ranks) = self.environmental_selection(combined);
        self.population = survivors;
        self.survivor_ranks = Some(ranks);

        let t = &mut self.generation_times;
        t.variation = (varied - started).as_secs_f64();
        t.evaluation = (evaluated - varied).as_secs_f64();
        t.selection = evaluated.elapsed().as_secs_f64();
    }

    /// Time spent in each phase of the most recent generation. `archive` is only measured
    /// under `run_with` (plain `run` skips the per-generation archive refresh).
    pub fn last_generation_times(&self) -> GenerationTimes {
        self.generation_times
    }

    fn assign_fitness(&mut self) {
        let n = self.population.len();
        self.ranks.resize(n, 0);
        self.crowding.resize(n, 0.0);
        let fronts = match self.survivor_ranks.take() {
            Some(ranks) if ranks.len() == n => fronts_from_ranks(&ranks),
            _ => fast_non_dominated_sort(&self.population, &self.dominance),
        };
        for (rank, front) in fronts.iter().enumerate() {
            let cd = crowding_by_index(&self.population, front);
            for (local, &global) in front.iter().enumerate() {
                self.ranks[global] = rank;
                self.crowding[global] = cd[local];
            }
        }
    }

    /// The population's first front, from the survival ranks when they're current.
    fn population_front0(&self) -> Vec<Solution> {
        match &self.survivor_ranks {
            Some(ranks) if ranks.len() == self.population.len() => {
                let front0: Vec<usize> = (0..ranks.len()).filter(|&i| ranks[i] == 0).collect();
                let pop = &self.population;
                crate::core::first_of_each_genome(pop, &front0).into_iter().map(|i| pop[i].clone()).collect()
            }
            _ => self.nondominated(&self.population),
        }
    }

    /// The first front, without repeated genomes (identical copies never dominate each other).
    fn nondominated(&self, pop: &[Solution]) -> Vec<Solution> {
        let fronts = fast_non_dominated_sort(pop, &self.dominance);
        match fronts.into_iter().next() {
            Some(mut f) => {
                f.sort_unstable(); // population order, as `population_front0` gives it
                crate::core::first_of_each_genome(pop, &f).into_iter().map(|i| pop[i].clone()).collect()
            }
            None => Vec::new(),
        }
    }

    /// NSGA-III survival: fill by front, then niche the splitting front against reference points.
    /// Returns the survivors and each one's front.
    fn environmental_selection(&self, combined: Vec<Solution>) -> (Vec<Solution>, Vec<usize>) {
        let target = self.population_size;
        let fronts = fast_non_dominated_sort(&combined, &self.dominance);

        let mut selected: Vec<usize> = Vec::new();
        let mut ranks: Vec<usize> = Vec::with_capacity(target);
        let mut splitting: Vec<usize> = Vec::new();
        for (rank, front) in fronts.iter().enumerate() {
            if selected.len() + front.len() <= target {
                selected.extend(front.iter().copied());
                ranks.resize(selected.len(), rank);
            } else {
                splitting = front.clone();
                break;
            }
        }
        if selected.len() == target || splitting.is_empty() {
            return (take_in_order(combined, &selected), ranks);
        }
        let splitting_rank = ranks.last().map_or(0, |r| r + 1);

        // Normalize objectives (minimization space) over selected ∪ splitting.
        let m = self.problem.number_of_objectives;
        let dirs = self.problem.direction.clone().unwrap_or_else(|| vec![-1; m]);
        let mut pool: Vec<usize> = selected.clone();
        pool.extend(splitting.iter().copied());
        let norm = normalize(&combined, &pool, m, &dirs);

        // Associate each pool member with its nearest reference point (perpendicular distance).
        let ref_norms: Vec<f64> = self.reference_points.iter().map(|r| r.iter().map(|x| x * x).sum()).collect();
        let (assoc, dist): (Vec<usize>, Vec<f64>) =
            norm.iter().map(|p| associate(p, &self.reference_points, &ref_norms)).unzip();

        // Niche counts from the already-selected members (pool[0..selected.len()]).
        let mut niche = vec![0usize; self.reference_points.len()];
        for k in 0..selected.len() {
            niche[assoc[k]] += 1;
        }

        // Candidate splitting members = pool indices selected.len()..pool.len().
        let mut avail: Vec<usize> = (selected.len()..pool.len()).collect();
        let need = target - selected.len();
        let mut chosen: Vec<usize> = Vec::new();

        while chosen.len() < need {
            // The reference point with the smallest niche count that still has candidates
            // (ties: smallest index), found in one pass with no scratch Vecs.
            let j = avail.iter().map(|&k| (niche[assoc[k]], assoc[k])).min().expect("candidates left").1;

            // Its closest candidate (ties: the first in `avail`).
            let mut pos = None::<usize>;
            for (p, &k) in avail.iter().enumerate() {
                if assoc[k] != j {
                    continue;
                }
                match pos {
                    Some(b) if dist[avail[b]].partial_cmp(&dist[k]) != Some(std::cmp::Ordering::Greater) => {}
                    _ => pos = Some(p),
                }
            }
            let pick = avail.remove(pos.expect("reference point has a candidate"));

            chosen.push(pool[pick]);
            niche[j] += 1;
        }

        ranks.resize(selected.len() + chosen.len(), splitting_rank);
        selected.extend(chosen);
        (take_in_order(combined, &selected), ranks)
    }
}

/// Crowding distance with ties broken by population index, so it doesn't depend on the order of
/// `front` — a front from survival ranks and one from a fresh sort give the same values, which
/// keeps `run_with` (which must re-sort after its observer) identical to `run`.
fn crowding_by_index(pop: &[Solution], front: &[usize]) -> Vec<f64> {
    let mut sorted = front.to_vec();
    sorted.sort_unstable();
    let by_index = crowding_distance(pop, &sorted);
    front.iter().map(|i| by_index[sorted.binary_search(i).expect("member of front")]).collect()
}

/// Fronts (lists of indices, in order) from each member's front number.
fn fronts_from_ranks(ranks: &[usize]) -> Vec<Vec<usize>> {
    let mut fronts: Vec<Vec<usize>> = vec![Vec::new(); ranks.iter().max().map_or(0, |r| r + 1)];
    for (i, &r) in ranks.iter().enumerate() {
        fronts[r].push(i);
    }
    fronts
}

/// Move `pop[i]` for each (distinct) `i` in `idx` out of `pop`, in that order — no clones.
fn take_in_order(pop: Vec<Solution>, idx: &[usize]) -> Vec<Solution> {
    let mut slots: Vec<Option<Solution>> = pop.into_iter().map(Some).collect();
    idx.iter().map(|&i| slots[i].take().expect("distinct survivor indices")).collect()
}

/// Translate by the ideal point and divide by the per-objective range, in minimization space.
fn normalize(pop: &[Solution], idx: &[usize], m: usize, dirs: &[i8]) -> Vec<Vec<f64>> {
    let val = |i: usize, o: usize| {
        let v = pop[i].objective_fitness_values[o];
        if dirs[o] == 1 { -v } else { v } // maximize → negate into minimization space
    };
    let mut ideal = vec![f64::INFINITY; m];
    let mut nadir = vec![f64::NEG_INFINITY; m];
    for &i in idx {
        for o in 0..m {
            let v = val(i, o);
            ideal[o] = ideal[o].min(v);
            nadir[o] = nadir[o].max(v);
        }
    }
    idx.iter()
        .map(|&i| {
            (0..m)
                .map(|o| {
                    let range = nadir[o] - ideal[o];
                    if range > f64::EPSILON { (val(i, o) - ideal[o]) / range } else { 0.0 }
                })
                .collect()
        })
        .collect()
}

/// Nearest reference point by perpendicular distance from `point` to the line through the origin
/// and the reference point. Returns (reference index, distance).
/// `ref_norms[j]` is the squared length of `refs[j]`.
fn associate(point: &[f64], refs: &[Vec<f64>], ref_norms: &[f64]) -> (usize, f64) {
    let mut best = (0usize, f64::INFINITY);
    for (j, (r, &rr)) in refs.iter().zip(ref_norms).enumerate() {
        if rr < f64::EPSILON {
            continue;
        }
        let dot: f64 = point.iter().zip(r).map(|(p, x)| p * x).sum();
        let t = dot / rr;
        let perp: f64 = point.iter().zip(r).map(|(p, x)| (p - t * x).powi(2)).sum::<f64>().sqrt();
        if perp < best.1 {
            best = (j, perp);
        }
    }
    best
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::core::{EvalFn, Problem};
    use crate::gatypes::{Real, SolutionDataTypes};

    fn dtlz_like() -> Problem {
        // 3-objective, 6-variable toy problem, minimize all.
        Problem {
            solution_length: 6,
            number_of_objectives: 3,
            objective_constraint: None,
            objective_constraint_operands: None,
            direction: Some(vec![-1, -1, -1]),
            solution_data_types: (0..6).map(|_| SolutionDataTypes::Real(Real::new(Some(0.0), Some(1.0)))).collect(),
            variable_constraints: None,
            encoding: crate::core::Encoding::PerGene,
            eval_fn: EvalFn::Single(|x| {
                let g: f64 = x[2..].iter().map(|v| (v - 0.5).powi(2)).sum();
                vec![(1.0 + g) * x[0], (1.0 + g) * (1.0 - x[0]) * x[1], (1.0 + g) * (1.0 - x[0]) * (1.0 - x[1])]
            }),
        }
    }

    #[test]
    fn test_das_dennis_count() {
        // 3 objectives, 4 divisions → C(3+4-1, 4) = C(6,4) = 15 points, all summing to 1.
        let pts = das_dennis(3, 4);
        assert_eq!(pts.len(), 15);
        for p in &pts {
            assert!((p.iter().sum::<f64>() - 1.0).abs() < 1e-9);
        }
    }

    #[test]
    fn test_nsga3_runs_and_keeps_size() {
        let problem = Arc::new(dtlz_like());
        let mut ga = NSGAIII::new(Arc::clone(&problem), 24, 4, ExecutionMode::Sequential).with_seed(1);
        ga.run(2_000);
        assert!(ga.get_nfe() >= 2_000);
        assert_eq!(ga.population.len(), 24);
        assert!(!ga.get_archive().is_empty());
        for s in ga.get_archive() {
            assert!(s.evaluated);
        }
    }

    #[test]
    fn test_nsga3_reproducible() {
        let problem = Arc::new(dtlz_like());
        let run = || {
            let mut ga = NSGAIII::new(Arc::clone(&problem), 24, 4, ExecutionMode::Sequential).with_seed(42);
            ga.run(1_200);
            ga.get_archive().iter().map(|s| s.objective_fitness_values.clone()).collect::<Vec<_>>()
        };
        assert_eq!(run(), run());
    }

    #[test]
    fn test_nsga3_run_with_matches_run_and_stops_early() {
        let problem = Arc::new(dtlz_like());
        let front = |ga: &NSGAIII| {
            ga.get_archive().iter().map(|s| s.objective_fitness_values.clone()).collect::<Vec<_>>()
        };
        let mut plain = NSGAIII::new(Arc::clone(&problem), 24, 4, ExecutionMode::Sequential).with_seed(3);
        plain.run(1_200);
        let mut observed = NSGAIII::new(Arc::clone(&problem), 24, 4, ExecutionMode::Sequential).with_seed(3);
        observed.run_with(1_200, |ga| {
            assert!(!ga.get_archive().is_empty(), "archive must be current during the run");
            true
        });
        assert_eq!(front(&plain), front(&observed), "observing a run must not change it");

        let mut stopped = NSGAIII::new(Arc::clone(&problem), 24, 4, ExecutionMode::Sequential);
        stopped.run_with(1_000_000, |ga| ga.get_nfe() < 200);
        assert!(stopped.get_nfe() < 1_000, "returning false must stop the run");
    }

    #[test]
    fn test_nsga3_execution_info_reports_the_gpu_fallback() {
        let problem = Arc::new(dtlz_like());
        let info = NSGAIII::new(problem, 24, 4, ExecutionMode::GPU).execution_info();
        assert_eq!(info.effective, ExecutionMode::MultiThreaded, "no evaluator attached");
        assert!(info.note.unwrap().contains("GPU requested"));
    }

    #[test]
    fn test_focus_concentrates_the_front_near_the_aspiration() {
        let problem = Arc::new(dtlz_like());
        let spread_of = |focus: bool| {
            let mut ga = NSGAIII::new(Arc::clone(&problem), 48, 6, ExecutionMode::Sequential).with_seed(5);
            ga.run_with(6_000, |ga| {
                if focus && ga.get_nfe() == 48 * 2 {
                    ga.focus_on(&[0.1, 0.1, 0.8], 0.15);
                }
                true
            });
            // Mean distance of the front from the aspiration (in objective space).
            let f = ga.get_archive();
            f.iter().map(|s| {
                let v = &s.objective_fitness_values;
                ((v[0] - 0.1).powi(2) + (v[1] - 0.1).powi(2) + (v[2] - 0.8).powi(2)).sqrt()
            }).sum::<f64>() / f.len() as f64
        };
        let (uniform, focused) = (spread_of(false), spread_of(true));
        assert!(focused < uniform * 0.7, "focused front should crowd the aspiration: {focused} vs {uniform}");
    }

    #[test]
    fn test_archive_has_no_repeated_genomes() {
        let problem = Arc::new(dtlz_like());
        let mut ga = NSGAIII::new(Arc::clone(&problem), 24, 4, ExecutionMode::Sequential).with_seed(2);
        ga.run(2_000);
        let keys: std::collections::HashSet<_> = ga.get_archive().iter().map(|s| crate::core::GenomeKey(&s.solution)).collect();
        assert_eq!(keys.len(), ga.get_archive().len());
    }
}