1 files changed, 217 insertions, 0 deletions

diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/ObjectiveComparatorHelper.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/ObjectiveComparatorHelper.java
new file mode 100644
index 00000000..39139bb0
--- /dev/null
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/ObjectiveComparatorHelper.java
@@ -0,0 +1,217 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package org.eclipse.viatra.dse.objectives;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Random;
+
+import org.eclipse.viatra.query.runtime.matchers.util.Preconditions;
+
+/**
+ * This class is responsible to compare and sort fitness values. {@link TrajectoryFitness} instances can be added to an
+ * instance of this class, that it can sort them.
+ * 
+ * @author András Szabolcs Nagy
+ */
+public class ObjectiveComparatorHelper {
+
+    private IObjective[][] leveledObjectives;
+    private List<TrajectoryFitness> trajectoryFitnesses = new ArrayList<TrajectoryFitness>();
+    private Random random = new Random();
+    private boolean computeCrowdingDistance = false;
+
+    public ObjectiveComparatorHelper(IObjective[][] leveledObjectives) {
+        this.leveledObjectives = leveledObjectives;
+    }
+
+    public void setComputeCrowdingDistance(boolean computeCrowdingDistance) {
+        this.computeCrowdingDistance = computeCrowdingDistance;
+    }
+
+    /**
+     * Compares two fitnesses based on hierarchical dominance. Returns -1 if the second parameter {@code o2} is a better
+     * solution ({@code o2} dominates {@code o1}), 1 if the first parameter {@code o1} is better ({@code o1} dominates
+     * {@code o2}) and returns 0 if they are non-dominating each other.
+     */
+    public int compare(Fitness o1, Fitness o2) {
+
+        levelsLoop: for (int i = 0; i < leveledObjectives.length; i++) {
+
+            boolean o1HasBetterFitness = false;
+            boolean o2HasBetterFitness = false;
+
+            for (IObjective objective : leveledObjectives[i]) {
+                String objectiveName = objective.getName();
+                int sgn = objective.getComparator().compare(o1.get(objectiveName), o2.get(objectiveName));
+
+                if (sgn < 0) {
+                    o2HasBetterFitness = true;
+                }
+                if (sgn > 0) {
+                    o1HasBetterFitness = true;
+                }
+                if (o1HasBetterFitness && o2HasBetterFitness) {
+                    continue levelsLoop;
+                }
+            }
+            if (o2HasBetterFitness && !o1HasBetterFitness) {
+                return -1;
+            } else if (!o2HasBetterFitness && o1HasBetterFitness) {
+                return 1;
+            }
+        }
+
+        return 0;
+
+    }
+
+    /**
+     * Adds a {@link TrajectoryFitness} to an inner list to compare later.
+     * 
+     * @param trajectoryFitness
+     */
+    public void addTrajectoryFitness(TrajectoryFitness trajectoryFitness) {
+        trajectoryFitnesses.add(trajectoryFitness);
+    }
+
+    /**
+     * Clears the inner {@link TrajectoryFitness} list.
+     */
+    public void clearTrajectoryFitnesses() {
+        trajectoryFitnesses.clear();
+    }
+
+    /**
+     * Returns the inner {@link TrajectoryFitness} list.
+     */
+    public List<TrajectoryFitness> getTrajectoryFitnesses() {
+        return trajectoryFitnesses;
+    }
+
+    /**
+     * Returns a random {@link TrajectoryFitness} from the pareto front.
+     */
+    public TrajectoryFitness getRandomBest() {
+        List<TrajectoryFitness> paretoFront = getParetoFront();
+        int randomIndex = random.nextInt(paretoFront.size());
+        return paretoFront.get(randomIndex);
+    }
+
+    /**
+     * Returns the pareto front of the previously added {@link TrajectoryFitness}.
+     */
+    public List<TrajectoryFitness> getParetoFront() {
+        return getFronts().get(0);
+    }
+
+    /**
+     * Returns the previously added {@link TrajectoryFitness} instances in fronts.
+     */
+    public List<? extends List<TrajectoryFitness>> getFronts() {
+        Preconditions.checkArgument(!trajectoryFitnesses.isEmpty(), "No trajectory fitnesses were added.");
+        List<ArrayList<TrajectoryFitness>> fronts = new ArrayList<ArrayList<TrajectoryFitness>>();
+
+        Map<TrajectoryFitness, ArrayList<TrajectoryFitness>> dominatedInstances = new HashMap<TrajectoryFitness, ArrayList<TrajectoryFitness>>();
+        Map<TrajectoryFitness, Integer> dominatingInstances = new HashMap<TrajectoryFitness, Integer>();
+
+        // calculate dominations
+        for (TrajectoryFitness TrajectoryFitnessP : trajectoryFitnesses) {
+            dominatedInstances.put(TrajectoryFitnessP, new ArrayList<TrajectoryFitness>());
+            dominatingInstances.put(TrajectoryFitnessP, 0);
+
+            for (TrajectoryFitness TrajectoryFitnessQ : trajectoryFitnesses) {
+                int dominates = compare(TrajectoryFitnessP.fitness, TrajectoryFitnessQ.fitness);
+                if (dominates > 0) {
+                    dominatedInstances.get(TrajectoryFitnessP).add(TrajectoryFitnessQ);
+                } else if (dominates < 0) {
+                    dominatingInstances.put(TrajectoryFitnessP, dominatingInstances.get(TrajectoryFitnessP) + 1);
+                }
+            }
+
+            if (dominatingInstances.get(TrajectoryFitnessP) == 0) {
+                // p belongs to the first front
+                TrajectoryFitnessP.rank = 1;
+                if (fronts.isEmpty()) {
+                    ArrayList<TrajectoryFitness> firstDominationFront = new ArrayList<TrajectoryFitness>();
+                    firstDominationFront.add(TrajectoryFitnessP);
+                    fronts.add(firstDominationFront);
+                } else {
+                    List<TrajectoryFitness> firstDominationFront = fronts.get(0);
+                    firstDominationFront.add(TrajectoryFitnessP);
+                }
+            }
+        }
+
+        // create fronts
+        int i = 1;
+        while (fronts.size() == i) {
+            ArrayList<TrajectoryFitness> nextDominationFront = new ArrayList<TrajectoryFitness>();
+            for (TrajectoryFitness TrajectoryFitnessP : fronts.get(i - 1)) {
+                for (TrajectoryFitness TrajectoryFitnessQ : dominatedInstances.get(TrajectoryFitnessP)) {
+                    dominatingInstances.put(TrajectoryFitnessQ, dominatingInstances.get(TrajectoryFitnessQ) - 1);
+                    if (dominatingInstances.get(TrajectoryFitnessQ) == 0) {
+                        TrajectoryFitnessQ.rank = i + 1;
+                        nextDominationFront.add(TrajectoryFitnessQ);
+                    }
+                }
+            }
+            i++;
+            if (!nextDominationFront.isEmpty()) {
+                if (computeCrowdingDistance) {
+                    crowdingDistanceAssignment(nextDominationFront, leveledObjectives);
+                }
+                fronts.add(nextDominationFront);
+            }
+        }
+
+        return fronts;
+    }
+
+    /**
+     * Executes the crowding distance assignment for the specified front.
+     * 
+     * @param front
+     */
+    public static void crowdingDistanceAssignment(List<TrajectoryFitness> front, IObjective[][] leveledObjectives) {
+
+        for (TrajectoryFitness InstanceData : front) {
+            // initialize crowding distance
+            InstanceData.crowdingDistance = 0;
+        }
+
+        for (final IObjective[] objectives : leveledObjectives) {
+            for (final IObjective objective : objectives) {
+
+                final String m = objective.getName();
+                TrajectoryFitness[] sortedFront = front.toArray(new TrajectoryFitness[0]);
+                // sort using m-th objective value
+                Arrays.sort(sortedFront, (o1, o2) -> objective.getComparator().compare(o1.fitness.get(m), o2.fitness.get(m)));
+                // so that boundary points are always selected
+                sortedFront[0].crowdingDistance = Double.POSITIVE_INFINITY;
+                sortedFront[sortedFront.length - 1].crowdingDistance = Double.POSITIVE_INFINITY;
+                // If minimal and maximal fitness value for this objective are
+                // equal, then do not change crowding distance
+                if (sortedFront[0].fitness.get(m) != sortedFront[sortedFront.length - 1].fitness.get(m)) {
+                    for (int i = 1; i < sortedFront.length - 1; i++) {
+                        double newCrowdingDistance = sortedFront[i].crowdingDistance;
+                        newCrowdingDistance += (sortedFront[i + 1].fitness.get(m) - sortedFront[i - 1].fitness.get(m))
+                                / (sortedFront[sortedFront.length - 1].fitness.get(m) - sortedFront[0].fitness.get(m));
+
+                        sortedFront[i].crowdingDistance = newCrowdingDistance;
+                    }
+                }
+            }
+        }
+    }
+
+}