1 package net.bmahe.genetics4j.moo;
2
3 import java.util.ArrayList;
4 import java.util.Comparator;
5 import java.util.HashMap;
6 import java.util.HashSet;
7 import java.util.List;
8 import java.util.Map;
9 import java.util.Objects;
10 import java.util.Set;
11
12 import org.apache.commons.lang3.Validate;
13
14 public class ParetoUtils {
15
16 private ParetoUtils() {
17
18 }
19
20 public static <T> List<Set<Integer>> rankedPopulation(final Comparator<T> dominance, final List<T> fitnessScore) {
21 Objects.requireNonNull(dominance);
22 Objects.requireNonNull(fitnessScore);
23 Validate.isTrue(fitnessScore.isEmpty() == false, "Fitness score list must not be empty");
24
25 final Map<Integer, Set<Integer>> dominating = new HashMap<>();
26 final Map<Integer, Integer> dominatedCount = new HashMap<>();
27
28 final List<Set<Integer>> rankedPopulation = new ArrayList<>();
29 rankedPopulation.add(new HashSet<>());
30 final Set<Integer> firstFront = rankedPopulation.getFirst();
31
32 for (int i = 0; i < fitnessScore.size(); i++) {
33
34 final T individualFitness = fitnessScore.get(i);
35 int dominated = 0;
36
37 for (int otherIndex = 0; otherIndex < fitnessScore.size(); otherIndex++) {
38 if (otherIndex != i) {
39 final T otherFitness = fitnessScore.get(otherIndex);
40
41 final int comparison = dominance.compare(individualFitness, otherFitness);
42 if (comparison > 0) {
43 dominating.computeIfAbsent(i, k -> new HashSet<>());
44 dominating.get(i).add(otherIndex);
45 } else if (comparison < 0) {
46 dominated++;
47 }
48 }
49 }
50 dominatedCount.put(i, dominated);
51
52
53 if (dominated == 0) {
54 firstFront.add(i);
55 }
56 }
57
58 int frontIndex = 0;
59 while (frontIndex < rankedPopulation.size() && rankedPopulation.get(frontIndex).isEmpty() == false) {
60 final Set<Integer> currentFront = rankedPopulation.get(frontIndex);
61
62 final Set<Integer> nextFront = new HashSet<>();
63
64 for (final int i : currentFront) {
65 if (dominating.containsKey(i)) {
66 for (final Integer dominatedByI : dominating.get(i)) {
67 final Integer updatedDominatedCount = dominatedCount.computeIfPresent(dominatedByI, (k, v) -> v - 1);
68
69 if (updatedDominatedCount != null && updatedDominatedCount == 0) {
70 nextFront.add(dominatedByI);
71 }
72 }
73
74 }
75 }
76
77 rankedPopulation.add(nextFront);
78 frontIndex++;
79 }
80
81 return rankedPopulation;
82 }
83 }