1 package net.bmahe.genetics4j.moo.nsga2.impl;
2
3 import java.util.Comparator;
4 import java.util.List;
5 import java.util.Objects;
6 import java.util.function.Function;
7 import java.util.stream.IntStream;
8
9 import org.apache.commons.lang3.Validate;
10
11 import net.bmahe.genetics4j.moo.ObjectiveDistance;
12
13 public class NSGA2Utils {
14
15 private NSGA2Utils() {
16
17 }
18
19 public static <T> double[] crowdingDistanceAssignment(final int numberObjectives, final List<T> fitnessScore,
20 final Function<Integer, Comparator<T>> objectiveComparator, final ObjectiveDistance<T> objectiveDistance) {
21 Validate.isTrue(numberObjectives > 0);
22 Objects.requireNonNull(fitnessScore);
23 Validate.isTrue(fitnessScore.isEmpty() == false, "Fitness score list must not be empty");
24 Objects.requireNonNull(objectiveComparator);
25 Objects.requireNonNull(objectiveDistance);
26
27 final double[] distances = new double[fitnessScore.size()];
28
29 for (int m = 0; m < numberObjectives; m++) {
30 final Comparator<T> objective = objectiveComparator.apply(m);
31
32 final int[] sortedIndexes = IntStream.range(0, fitnessScore.size())
33 .boxed()
34 .sorted((a, b) -> objective.compare(fitnessScore.get(a), fitnessScore.get(b)))
35 .mapToInt(e -> e)
36 .toArray();
37
38 distances[sortedIndexes[0]] = Double.POSITIVE_INFINITY;
39 distances[sortedIndexes[sortedIndexes.length - 1]] = Double.POSITIVE_INFINITY;
40
41 final T minFitnessByObjective = fitnessScore.get(sortedIndexes[0]);
42 final T maxFitnessByObjective = fitnessScore.get(sortedIndexes[sortedIndexes.length - 1]);
43 final double maxDistance = objectiveDistance.distance(minFitnessByObjective, maxFitnessByObjective, m);
44
45 for (int i = 1; i < sortedIndexes.length - 1; i++) {
46 final T previousFitness = fitnessScore.get(sortedIndexes[i - 1]);
47 final T nextFitness = fitnessScore.get(sortedIndexes[i + 1]);
48
49 if (maxDistance > 0.0) {
50 distances[i] += objectiveDistance.distance(previousFitness, nextFitness, m) / maxDistance;
51 }
52 }
53 }
54
55 return distances;
56 }
57 }