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