diff options
author | Kristóf Marussy <marussy@mit.bme.hu> | 2020-06-30 18:03:48 +0200 |
---|---|---|
committer | Kristóf Marussy <marussy@mit.bme.hu> | 2020-06-30 18:03:48 +0200 |
commit | e11bce7ad3e803e80883499fec0ad6e4540ffe43 (patch) | |
tree | ca3ad9d5b9137e9455485e43350a4a353f487f22 /Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/ObjectiveComparatorHelper.java | |
parent | Disable unrepairable match scoping for now (diff) | |
download | VIATRA-Generator-e11bce7ad3e803e80883499fec0ad6e4540ffe43.tar.gz VIATRA-Generator-e11bce7ad3e803e80883499fec0ad6e4540ffe43.tar.zst VIATRA-Generator-e11bce7ad3e803e80883499fec0ad6e4540ffe43.zip |
Add modified VIATRA-DSE version
Diffstat (limited to 'Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/ObjectiveComparatorHelper.java')
-rw-r--r-- | Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/ObjectiveComparatorHelper.java | 217 |
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 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2015, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi and Daniel Varro | ||
3 | * This program and the accompanying materials are made available under the | ||
4 | * terms of the Eclipse Public License v. 2.0 which is available at | ||
5 | * http://www.eclipse.org/legal/epl-v20.html. | ||
6 | * | ||
7 | * SPDX-License-Identifier: EPL-2.0 | ||
8 | *******************************************************************************/ | ||
9 | package org.eclipse.viatra.dse.objectives; | ||
10 | |||
11 | import java.util.ArrayList; | ||
12 | import java.util.Arrays; | ||
13 | import java.util.HashMap; | ||
14 | import java.util.List; | ||
15 | import java.util.Map; | ||
16 | import java.util.Random; | ||
17 | |||
18 | import org.eclipse.viatra.query.runtime.matchers.util.Preconditions; | ||
19 | |||
20 | /** | ||
21 | * This class is responsible to compare and sort fitness values. {@link TrajectoryFitness} instances can be added to an | ||
22 | * instance of this class, that it can sort them. | ||
23 | * | ||
24 | * @author András Szabolcs Nagy | ||
25 | */ | ||
26 | public class ObjectiveComparatorHelper { | ||
27 | |||
28 | private IObjective[][] leveledObjectives; | ||
29 | private List<TrajectoryFitness> trajectoryFitnesses = new ArrayList<TrajectoryFitness>(); | ||
30 | private Random random = new Random(); | ||
31 | private boolean computeCrowdingDistance = false; | ||
32 | |||
33 | public ObjectiveComparatorHelper(IObjective[][] leveledObjectives) { | ||
34 | this.leveledObjectives = leveledObjectives; | ||
35 | } | ||
36 | |||
37 | public void setComputeCrowdingDistance(boolean computeCrowdingDistance) { | ||
38 | this.computeCrowdingDistance = computeCrowdingDistance; | ||
39 | } | ||
40 | |||
41 | /** | ||
42 | * Compares two fitnesses based on hierarchical dominance. Returns -1 if the second parameter {@code o2} is a better | ||
43 | * solution ({@code o2} dominates {@code o1}), 1 if the first parameter {@code o1} is better ({@code o1} dominates | ||
44 | * {@code o2}) and returns 0 if they are non-dominating each other. | ||
45 | */ | ||
46 | public int compare(Fitness o1, Fitness o2) { | ||
47 | |||
48 | levelsLoop: for (int i = 0; i < leveledObjectives.length; i++) { | ||
49 | |||
50 | boolean o1HasBetterFitness = false; | ||
51 | boolean o2HasBetterFitness = false; | ||
52 | |||
53 | for (IObjective objective : leveledObjectives[i]) { | ||
54 | String objectiveName = objective.getName(); | ||
55 | int sgn = objective.getComparator().compare(o1.get(objectiveName), o2.get(objectiveName)); | ||
56 | |||
57 | if (sgn < 0) { | ||
58 | o2HasBetterFitness = true; | ||
59 | } | ||
60 | if (sgn > 0) { | ||
61 | o1HasBetterFitness = true; | ||
62 | } | ||
63 | if (o1HasBetterFitness && o2HasBetterFitness) { | ||
64 | continue levelsLoop; | ||
65 | } | ||
66 | } | ||
67 | if (o2HasBetterFitness && !o1HasBetterFitness) { | ||
68 | return -1; | ||
69 | } else if (!o2HasBetterFitness && o1HasBetterFitness) { | ||
70 | return 1; | ||
71 | } | ||
72 | } | ||
73 | |||
74 | return 0; | ||
75 | |||
76 | } | ||
77 | |||
78 | /** | ||
79 | * Adds a {@link TrajectoryFitness} to an inner list to compare later. | ||
80 | * | ||
81 | * @param trajectoryFitness | ||
82 | */ | ||
83 | public void addTrajectoryFitness(TrajectoryFitness trajectoryFitness) { | ||
84 | trajectoryFitnesses.add(trajectoryFitness); | ||
85 | } | ||
86 | |||
87 | /** | ||
88 | * Clears the inner {@link TrajectoryFitness} list. | ||
89 | */ | ||
90 | public void clearTrajectoryFitnesses() { | ||
91 | trajectoryFitnesses.clear(); | ||
92 | } | ||
93 | |||
94 | /** | ||
95 | * Returns the inner {@link TrajectoryFitness} list. | ||
96 | */ | ||
97 | public List<TrajectoryFitness> getTrajectoryFitnesses() { | ||
98 | return trajectoryFitnesses; | ||
99 | } | ||
100 | |||
101 | /** | ||
102 | * Returns a random {@link TrajectoryFitness} from the pareto front. | ||
103 | */ | ||
104 | public TrajectoryFitness getRandomBest() { | ||
105 | List<TrajectoryFitness> paretoFront = getParetoFront(); | ||
106 | int randomIndex = random.nextInt(paretoFront.size()); | ||
107 | return paretoFront.get(randomIndex); | ||
108 | } | ||
109 | |||
110 | /** | ||
111 | * Returns the pareto front of the previously added {@link TrajectoryFitness}. | ||
112 | */ | ||
113 | public List<TrajectoryFitness> getParetoFront() { | ||
114 | return getFronts().get(0); | ||
115 | } | ||
116 | |||
117 | /** | ||
118 | * Returns the previously added {@link TrajectoryFitness} instances in fronts. | ||
119 | */ | ||
120 | public List<? extends List<TrajectoryFitness>> getFronts() { | ||
121 | Preconditions.checkArgument(!trajectoryFitnesses.isEmpty(), "No trajectory fitnesses were added."); | ||
122 | List<ArrayList<TrajectoryFitness>> fronts = new ArrayList<ArrayList<TrajectoryFitness>>(); | ||
123 | |||
124 | Map<TrajectoryFitness, ArrayList<TrajectoryFitness>> dominatedInstances = new HashMap<TrajectoryFitness, ArrayList<TrajectoryFitness>>(); | ||
125 | Map<TrajectoryFitness, Integer> dominatingInstances = new HashMap<TrajectoryFitness, Integer>(); | ||
126 | |||
127 | // calculate dominations | ||
128 | for (TrajectoryFitness TrajectoryFitnessP : trajectoryFitnesses) { | ||
129 | dominatedInstances.put(TrajectoryFitnessP, new ArrayList<TrajectoryFitness>()); | ||
130 | dominatingInstances.put(TrajectoryFitnessP, 0); | ||
131 | |||
132 | for (TrajectoryFitness TrajectoryFitnessQ : trajectoryFitnesses) { | ||
133 | int dominates = compare(TrajectoryFitnessP.fitness, TrajectoryFitnessQ.fitness); | ||
134 | if (dominates > 0) { | ||
135 | dominatedInstances.get(TrajectoryFitnessP).add(TrajectoryFitnessQ); | ||
136 | } else if (dominates < 0) { | ||
137 | dominatingInstances.put(TrajectoryFitnessP, dominatingInstances.get(TrajectoryFitnessP) + 1); | ||
138 | } | ||
139 | } | ||
140 | |||
141 | if (dominatingInstances.get(TrajectoryFitnessP) == 0) { | ||
142 | // p belongs to the first front | ||
143 | TrajectoryFitnessP.rank = 1; | ||
144 | if (fronts.isEmpty()) { | ||
145 | ArrayList<TrajectoryFitness> firstDominationFront = new ArrayList<TrajectoryFitness>(); | ||
146 | firstDominationFront.add(TrajectoryFitnessP); | ||
147 | fronts.add(firstDominationFront); | ||
148 | } else { | ||
149 | List<TrajectoryFitness> firstDominationFront = fronts.get(0); | ||
150 | firstDominationFront.add(TrajectoryFitnessP); | ||
151 | } | ||
152 | } | ||
153 | } | ||
154 | |||
155 | // create fronts | ||
156 | int i = 1; | ||
157 | while (fronts.size() == i) { | ||
158 | ArrayList<TrajectoryFitness> nextDominationFront = new ArrayList<TrajectoryFitness>(); | ||
159 | for (TrajectoryFitness TrajectoryFitnessP : fronts.get(i - 1)) { | ||
160 | for (TrajectoryFitness TrajectoryFitnessQ : dominatedInstances.get(TrajectoryFitnessP)) { | ||
161 | dominatingInstances.put(TrajectoryFitnessQ, dominatingInstances.get(TrajectoryFitnessQ) - 1); | ||
162 | if (dominatingInstances.get(TrajectoryFitnessQ) == 0) { | ||
163 | TrajectoryFitnessQ.rank = i + 1; | ||
164 | nextDominationFront.add(TrajectoryFitnessQ); | ||
165 | } | ||
166 | } | ||
167 | } | ||
168 | i++; | ||
169 | if (!nextDominationFront.isEmpty()) { | ||
170 | if (computeCrowdingDistance) { | ||
171 | crowdingDistanceAssignment(nextDominationFront, leveledObjectives); | ||
172 | } | ||
173 | fronts.add(nextDominationFront); | ||
174 | } | ||
175 | } | ||
176 | |||
177 | return fronts; | ||
178 | } | ||
179 | |||
180 | /** | ||
181 | * Executes the crowding distance assignment for the specified front. | ||
182 | * | ||
183 | * @param front | ||
184 | */ | ||
185 | public static void crowdingDistanceAssignment(List<TrajectoryFitness> front, IObjective[][] leveledObjectives) { | ||
186 | |||
187 | for (TrajectoryFitness InstanceData : front) { | ||
188 | // initialize crowding distance | ||
189 | InstanceData.crowdingDistance = 0; | ||
190 | } | ||
191 | |||
192 | for (final IObjective[] objectives : leveledObjectives) { | ||
193 | for (final IObjective objective : objectives) { | ||
194 | |||
195 | final String m = objective.getName(); | ||
196 | TrajectoryFitness[] sortedFront = front.toArray(new TrajectoryFitness[0]); | ||
197 | // sort using m-th objective value | ||
198 | Arrays.sort(sortedFront, (o1, o2) -> objective.getComparator().compare(o1.fitness.get(m), o2.fitness.get(m))); | ||
199 | // so that boundary points are always selected | ||
200 | sortedFront[0].crowdingDistance = Double.POSITIVE_INFINITY; | ||
201 | sortedFront[sortedFront.length - 1].crowdingDistance = Double.POSITIVE_INFINITY; | ||
202 | // If minimal and maximal fitness value for this objective are | ||
203 | // equal, then do not change crowding distance | ||
204 | if (sortedFront[0].fitness.get(m) != sortedFront[sortedFront.length - 1].fitness.get(m)) { | ||
205 | for (int i = 1; i < sortedFront.length - 1; i++) { | ||
206 | double newCrowdingDistance = sortedFront[i].crowdingDistance; | ||
207 | newCrowdingDistance += (sortedFront[i + 1].fitness.get(m) - sortedFront[i - 1].fitness.get(m)) | ||
208 | / (sortedFront[sortedFront.length - 1].fitness.get(m) - sortedFront[0].fitness.get(m)); | ||
209 | |||
210 | sortedFront[i].crowdingDistance = newCrowdingDistance; | ||
211 | } | ||
212 | } | ||
213 | } | ||
214 | } | ||
215 | } | ||
216 | |||
217 | } | ||