diff options
author | 2023-08-07 12:59:35 +0200 | |
---|---|---|
committer | 2023-08-07 15:12:37 +0200 | |
commit | a20fd33c647d8511762f84436dbd8d1632b57fe8 (patch) | |
tree | f28113c37476cca869a3283cd57d81de605b06e7 /subprojects/store-dse/src/main | |
parent | Update exploration strategies (diff) | |
download | refinery-a20fd33c647d8511762f84436dbd8d1632b57fe8.tar.gz refinery-a20fd33c647d8511762f84436dbd8d1632b57fe8.tar.zst refinery-a20fd33c647d8511762f84436dbd8d1632b57fe8.zip |
Clean up design space exploration
Diffstat (limited to 'subprojects/store-dse/src/main')
8 files changed, 49 insertions, 68 deletions
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationAdapter.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationAdapter.java index c4aa97c2..c45f088a 100644 --- a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationAdapter.java +++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationAdapter.java | |||
@@ -52,8 +52,6 @@ public interface DesignSpaceExplorationAdapter extends ModelAdapter { | |||
52 | 52 | ||
53 | public void fireRandomActivation(); | 53 | public void fireRandomActivation(); |
54 | 54 | ||
55 | public boolean isCurrentInTrajectory(); | ||
56 | |||
57 | public List<Version> getTrajectory(); | 55 | public List<Version> getTrajectory(); |
58 | 56 | ||
59 | public boolean isCurrentStateAlreadyTraversed(); | 57 | public boolean isCurrentStateAlreadyTraversed(); |
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationAdapterImpl.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationAdapterImpl.java index 4e5cc467..1329480c 100644 --- a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationAdapterImpl.java +++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationAdapterImpl.java | |||
@@ -43,7 +43,6 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
43 | private ObjectiveComparatorHelper objectiveComparatorHelper; | 43 | private ObjectiveComparatorHelper objectiveComparatorHelper; |
44 | private List<Version> trajectory = new ArrayList<>(); | 44 | private List<Version> trajectory = new ArrayList<>(); |
45 | private Map<Version, Version> parents = new HashMap<>(); | 45 | private Map<Version, Version> parents = new HashMap<>(); |
46 | private Fitness lastFitness; | ||
47 | private final List<Version> solutions = new ArrayList<>(); | 46 | private final List<Version> solutions = new ArrayList<>(); |
48 | private Map<Version, List<Activation>> statesAndTraversedActivations; | 47 | private Map<Version, List<Activation>> statesAndTraversedActivations; |
49 | private Random random = new Random(); | 48 | private Random random = new Random(); |
@@ -184,9 +183,7 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
184 | 183 | ||
185 | @Override | 184 | @Override |
186 | public Fitness getFitness() { | 185 | public Fitness getFitness() { |
187 | var result = fitnessCache.computeIfAbsent(model.getState(), s -> calculateFitness()); | 186 | return fitnessCache.computeIfAbsent(model.getState(), s -> calculateFitness()); |
188 | lastFitness = result; | ||
189 | return result; | ||
190 | } | 187 | } |
191 | 188 | ||
192 | private Fitness calculateFitness() { | 189 | private Fitness calculateFitness() { |
@@ -201,8 +198,6 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
201 | } | 198 | } |
202 | result.setSatisfiesHardObjectives(satisfiesHardObjectives); | 199 | result.setSatisfiesHardObjectives(satisfiesHardObjectives); |
203 | 200 | ||
204 | lastFitness = result; | ||
205 | |||
206 | return result; | 201 | return result; |
207 | } | 202 | } |
208 | 203 | ||
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/BaseObjective.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/BaseObjective.java index 7df33efe..b76598fb 100644 --- a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/BaseObjective.java +++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/BaseObjective.java | |||
@@ -30,7 +30,7 @@ public abstract class BaseObjective implements Objective { | |||
30 | protected boolean isThereFitnessConstraint = false; | 30 | protected boolean isThereFitnessConstraint = false; |
31 | protected Comparator<Double> fitnessConstraintComparator; | 31 | protected Comparator<Double> fitnessConstraintComparator; |
32 | 32 | ||
33 | public BaseObjective(String name) { | 33 | protected BaseObjective(String name) { |
34 | Objects.requireNonNull(name, "Name of the objective cannot be null."); | 34 | Objects.requireNonNull(name, "Name of the objective cannot be null."); |
35 | this.name = name; | 35 | this.name = name; |
36 | } | 36 | } |
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Comparators.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Comparators.java index 476504b0..181397b3 100644 --- a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Comparators.java +++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Comparators.java | |||
@@ -15,7 +15,7 @@ public class Comparators { | |||
15 | 15 | ||
16 | private Comparators() { /*Utility class constructor*/ } | 16 | private Comparators() { /*Utility class constructor*/ } |
17 | 17 | ||
18 | public static final Comparator<Double> HIGHER_IS_BETTER = (o1, o2) -> o1.compareTo(o2); | 18 | public static final Comparator<Double> HIGHER_IS_BETTER = Double::compareTo; |
19 | 19 | ||
20 | public static final Comparator<Double> LOWER_IS_BETTER = (o1, o2) -> o2.compareTo(o1); | 20 | public static final Comparator<Double> LOWER_IS_BETTER = (o1, o2) -> o2.compareTo(o1); |
21 | 21 | ||
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Fitness.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Fitness.java index 92709d3e..0bf956d2 100644 --- a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Fitness.java +++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Fitness.java | |||
@@ -27,4 +27,19 @@ public class Fitness extends HashMap<String, Double> { | |||
27 | public String toString() { | 27 | public String toString() { |
28 | return super.toString() + " hardObjectives=" + satisfiesHardObjectives; | 28 | return super.toString() + " hardObjectives=" + satisfiesHardObjectives; |
29 | } | 29 | } |
30 | |||
31 | @Override | ||
32 | public boolean equals(Object other) { | ||
33 | if (other == null) return false; | ||
34 | if (getClass() != other.getClass()) return false; | ||
35 | return satisfiesHardObjectives == ((Fitness) other).satisfiesHardObjectives; | ||
36 | } | ||
37 | |||
38 | @Override | ||
39 | public int hashCode() { | ||
40 | int h = super.hashCode(); | ||
41 | h = h * 31 + (satisfiesHardObjectives ? 1 : 0); | ||
42 | return h; | ||
43 | } | ||
44 | |||
30 | } | 45 | } |
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/ObjectiveComparatorHelper.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/ObjectiveComparatorHelper.java index 1d676562..eb03eeaf 100644 --- a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/ObjectiveComparatorHelper.java +++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/ObjectiveComparatorHelper.java | |||
@@ -49,6 +49,7 @@ public class ObjectiveComparatorHelper { | |||
49 | } | 49 | } |
50 | } | 50 | } |
51 | if (o2HasBetterFitness) { | 51 | if (o2HasBetterFitness) { |
52 | return -1; | ||
52 | } else if (o1HasBetterFitness) { | 53 | } else if (o1HasBetterFitness) { |
53 | return 1; | 54 | return 1; |
54 | } | 55 | } |
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/BestFirstStrategy.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/BestFirstStrategy.java index 57f86401..98af5695 100644 --- a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/BestFirstStrategy.java +++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/BestFirstStrategy.java | |||
@@ -25,29 +25,18 @@ public class BestFirstStrategy implements Strategy { | |||
25 | 25 | ||
26 | private DesignSpaceExplorationAdapter dseAdapter; | 26 | private DesignSpaceExplorationAdapter dseAdapter; |
27 | 27 | ||
28 | private int maxDepth; | 28 | private final int maxDepth; |
29 | private int maxSolutions; | 29 | private final int maxSolutions; |
30 | private boolean backTrackIfSolution = true; | 30 | private boolean backTrackIfSolution = true; |
31 | private boolean onlyBetterFirst = false; | 31 | private boolean onlyBetterFirst = false; |
32 | 32 | ||
33 | private PriorityQueue<TrajectoryWithFitness> trajectoriesToExplore; | 33 | private PriorityQueue<TrajectoryWithFitness> trajectoriesToExplore; |
34 | 34 | ||
35 | private static class TrajectoryWithFitness { | 35 | private record TrajectoryWithFitness(List<Version> trajectory, Fitness fitness) { |
36 | |||
37 | public List<Version> trajectory; | ||
38 | public Fitness fitness; | ||
39 | |||
40 | public TrajectoryWithFitness(List<Version> trajectory, Fitness fitness) { | ||
41 | super(); | ||
42 | this.trajectory = trajectory; | ||
43 | this.fitness = fitness; | ||
44 | } | ||
45 | |||
46 | @Override | 36 | @Override |
47 | public String toString() { | 37 | public String toString() { |
48 | return trajectory.toString() + fitness.toString(); | 38 | return trajectory.toString() + fitness.toString(); |
49 | } | 39 | } |
50 | |||
51 | } | 40 | } |
52 | 41 | ||
53 | public BestFirstStrategy() { | 42 | public BestFirstStrategy() { |
@@ -99,14 +88,14 @@ public class BestFirstStrategy implements Strategy { | |||
99 | 88 | ||
100 | boolean globalConstraintsAreSatisfied = dseAdapter.checkGlobalConstraints(); | 89 | boolean globalConstraintsAreSatisfied = dseAdapter.checkGlobalConstraints(); |
101 | if (!globalConstraintsAreSatisfied) { | 90 | if (!globalConstraintsAreSatisfied) { |
102 | // "Global constraint is not satisfied in the first state. Terminate."); | 91 | // Global constraint is not satisfied in the first state. Terminate. |
103 | return; | 92 | return; |
104 | } | 93 | } |
105 | 94 | ||
106 | final Fitness firstFitness = dseAdapter.getFitness(); | 95 | final Fitness firstFitness = dseAdapter.getFitness(); |
107 | if (firstFitness.isSatisfiesHardObjectives()) { | 96 | if (firstFitness.isSatisfiesHardObjectives()) { |
108 | dseAdapter.newSolution(); | 97 | dseAdapter.newSolution(); |
109 | // "First state is a solution. Terminate."); | 98 | // First state is a solution. Terminate. |
110 | if (backTrackIfSolution) { | 99 | if (backTrackIfSolution) { |
111 | return; | 100 | return; |
112 | } | 101 | } |
@@ -116,12 +105,6 @@ public class BestFirstStrategy implements Strategy { | |||
116 | return; | 105 | return; |
117 | } | 106 | } |
118 | 107 | ||
119 | // final List<Version> firstTrajectory = dseAdapter.getTrajectory(); | ||
120 | |||
121 | // TrajectoryWithFitness currentTrajectoryWithFitness = new TrajectoryWithFitness(dseAdapter.getTrajectory(), | ||
122 | // firstFitness); | ||
123 | // trajectoriesToExplore.add(currentTrajectoryWithFitness); | ||
124 | |||
125 | 108 | ||
126 | var firstTrajectoryWithFitness = new TrajectoryWithFitness(dseAdapter.getTrajectory(), firstFitness); | 109 | var firstTrajectoryWithFitness = new TrajectoryWithFitness(dseAdapter.getTrajectory(), firstFitness); |
127 | trajectoriesToExplore.add(firstTrajectoryWithFitness); | 110 | trajectoriesToExplore.add(firstTrajectoryWithFitness); |
@@ -131,13 +114,11 @@ public class BestFirstStrategy implements Strategy { | |||
131 | 114 | ||
132 | if (currentTrajectoryWithFitness == null) { | 115 | if (currentTrajectoryWithFitness == null) { |
133 | if (trajectoriesToExplore.isEmpty()) { | 116 | if (trajectoriesToExplore.isEmpty()) { |
134 | // "State space is fully traversed."); | 117 | // State space is fully traversed. |
135 | return; | 118 | return; |
136 | } else { | 119 | } else { |
137 | currentTrajectoryWithFitness = trajectoriesToExplore.element(); | 120 | currentTrajectoryWithFitness = trajectoriesToExplore.element(); |
138 | // if (logger.isDebugEnabled()) { | 121 | // New trajectory is chosen: " + currentTrajectoryWithFitness |
139 | // "New trajectory is chosen: " + currentTrajectoryWithFitness); | ||
140 | // } | ||
141 | dseAdapter.restoreTrajectory(currentTrajectoryWithFitness.trajectory); | 122 | dseAdapter.restoreTrajectory(currentTrajectoryWithFitness.trajectory); |
142 | } | 123 | } |
143 | } | 124 | } |
@@ -150,19 +131,17 @@ public class BestFirstStrategy implements Strategy { | |||
150 | while (iterator.hasNext()) { | 131 | while (iterator.hasNext()) { |
151 | final Activation nextActivation = iterator.next(); | 132 | final Activation nextActivation = iterator.next(); |
152 | if (!iterator.hasNext()) { | 133 | if (!iterator.hasNext()) { |
153 | // "Last untraversed activation of the state."); | 134 | // Last untraversed activation of the state. |
154 | trajectoriesToExplore.remove(currentTrajectoryWithFitness); | 135 | trajectoriesToExplore.remove(currentTrajectoryWithFitness); |
155 | } | 136 | } |
156 | 137 | ||
157 | // if (logger.isDebugEnabled()) { | 138 | // Executing new activation |
158 | // "Executing new activation: " + nextActivation); | ||
159 | // } | ||
160 | dseAdapter.fireActivation(nextActivation); | 139 | dseAdapter.fireActivation(nextActivation); |
161 | if (dseAdapter.isCurrentStateAlreadyTraversed()) { | 140 | if (dseAdapter.isCurrentStateAlreadyTraversed()) { |
162 | // "The new state is already visited."); | 141 | // The new state is already visited. |
163 | dseAdapter.backtrack(); | 142 | dseAdapter.backtrack(); |
164 | } else if (!dseAdapter.checkGlobalConstraints()) { | 143 | } else if (!dseAdapter.checkGlobalConstraints()) { |
165 | // "Global constraint is not satisfied."); | 144 | // Global constraint is not satisfied. |
166 | dseAdapter.backtrack(); | 145 | dseAdapter.backtrack(); |
167 | } else { | 146 | } else { |
168 | final Fitness nextFitness = dseAdapter.getFitness(); | 147 | final Fitness nextFitness = dseAdapter.getFitness(); |
@@ -172,14 +151,14 @@ public class BestFirstStrategy implements Strategy { | |||
172 | if (solutions >= maxSolutions) { | 151 | if (solutions >= maxSolutions) { |
173 | return; | 152 | return; |
174 | } | 153 | } |
175 | // "Found a solution."); | 154 | // Found a solution. |
176 | if (backTrackIfSolution) { | 155 | if (backTrackIfSolution) { |
177 | dseAdapter.backtrack(); | 156 | dseAdapter.backtrack(); |
178 | continue; | 157 | continue; |
179 | } | 158 | } |
180 | } | 159 | } |
181 | if (dseAdapter.getDepth() >= maxDepth) { | 160 | if (dseAdapter.getDepth() >= maxDepth) { |
182 | // "Reached max depth."); | 161 | // Reached max depth. |
183 | dseAdapter.backtrack(); | 162 | dseAdapter.backtrack(); |
184 | continue; | 163 | continue; |
185 | } | 164 | } |
@@ -191,33 +170,31 @@ public class BestFirstStrategy implements Strategy { | |||
191 | int compare = objectiveComparatorHelper.compare(currentTrajectoryWithFitness.fitness, | 170 | int compare = objectiveComparatorHelper.compare(currentTrajectoryWithFitness.fitness, |
192 | nextTrajectoryWithFitness.fitness); | 171 | nextTrajectoryWithFitness.fitness); |
193 | if (compare < 0) { | 172 | if (compare < 0) { |
194 | // "Better fitness, moving on: " + nextFitness); | 173 | // Better fitness, moving on |
195 | currentTrajectoryWithFitness = nextTrajectoryWithFitness; | 174 | currentTrajectoryWithFitness = nextTrajectoryWithFitness; |
196 | continue mainLoop; | 175 | continue mainLoop; |
197 | } else if (compare == 0) { | 176 | } else if (compare == 0) { |
198 | if (onlyBetterFirst) { | 177 | if (onlyBetterFirst) { |
199 | // "Equally good fitness, backtrack: " + nextFitness); | 178 | // Equally good fitness, backtrack |
200 | dseAdapter.backtrack(); | 179 | dseAdapter.backtrack(); |
201 | continue; | ||
202 | } else { | 180 | } else { |
203 | // "Equally good fitness, moving on: " + nextFitness); | 181 | // Equally good fitness, moving on |
204 | currentTrajectoryWithFitness = nextTrajectoryWithFitness; | 182 | currentTrajectoryWithFitness = nextTrajectoryWithFitness; |
205 | continue mainLoop; | 183 | continue mainLoop; |
206 | } | 184 | } |
207 | } else { | 185 | } else { |
208 | // "Worse fitness."); | 186 | //"Worse fitness |
209 | currentTrajectoryWithFitness = null; | 187 | currentTrajectoryWithFitness = null; |
210 | continue mainLoop; | 188 | continue mainLoop; |
211 | } | 189 | } |
212 | } | 190 | } |
213 | } | 191 | } |
214 | 192 | ||
215 | // "State is fully traversed."); | 193 | // State is fully traversed. |
216 | trajectoriesToExplore.remove(currentTrajectoryWithFitness); | 194 | trajectoriesToExplore.remove(currentTrajectoryWithFitness); |
217 | currentTrajectoryWithFitness = null; | 195 | currentTrajectoryWithFitness = null; |
218 | 196 | ||
219 | } | 197 | } |
220 | // "Interrupted."); | 198 | // Interrupted. |
221 | |||
222 | } | 199 | } |
223 | } | 200 | } |
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/DepthFirstStrategy.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/DepthFirstStrategy.java index f4a0747a..15529371 100644 --- a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/DepthFirstStrategy.java +++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/DepthFirstStrategy.java | |||
@@ -65,11 +65,11 @@ public class DepthFirstStrategy implements Strategy { | |||
65 | if (!globalConstraintsAreSatisfied) { | 65 | if (!globalConstraintsAreSatisfied) { |
66 | var isSuccessfulUndo = dseAdapter.backtrack(); | 66 | var isSuccessfulUndo = dseAdapter.backtrack(); |
67 | if (!isSuccessfulUndo) { | 67 | if (!isSuccessfulUndo) { |
68 | // "Global constraint is not satisfied and cannot backtrack." | 68 | // Global constraint is not satisfied and cannot backtrack. |
69 | break; | 69 | break; |
70 | } | 70 | } |
71 | else { | 71 | else { |
72 | // "Global constraint is not satisfied, backtrack." | 72 | // Global constraint is not satisfied, backtrack. |
73 | continue; | 73 | continue; |
74 | } | 74 | } |
75 | } | 75 | } |
@@ -84,10 +84,10 @@ public class DepthFirstStrategy implements Strategy { | |||
84 | if (backTrackIfSolution) { | 84 | if (backTrackIfSolution) { |
85 | var isSuccessfulUndo = dseAdapter.backtrack(); | 85 | var isSuccessfulUndo = dseAdapter.backtrack(); |
86 | if (!isSuccessfulUndo) { | 86 | if (!isSuccessfulUndo) { |
87 | // "Found a solution but cannot backtrack." | 87 | // Found a solution but cannot backtrack. |
88 | break; | 88 | break; |
89 | } else { | 89 | } else { |
90 | // "Found a solution, backtrack." | 90 | // Found a solution, backtrack. |
91 | continue; | 91 | continue; |
92 | } | 92 | } |
93 | } | 93 | } |
@@ -96,7 +96,7 @@ public class DepthFirstStrategy implements Strategy { | |||
96 | if (dseAdapter.getDepth() >= maxDepth) { | 96 | if (dseAdapter.getDepth() >= maxDepth) { |
97 | var isSuccessfulUndo = dseAdapter.backtrack(); | 97 | var isSuccessfulUndo = dseAdapter.backtrack(); |
98 | if (!isSuccessfulUndo) { | 98 | if (!isSuccessfulUndo) { |
99 | // "Reached max depth but cannot backtrack." | 99 | // Reached max depth but cannot backtrack. |
100 | break; | 100 | break; |
101 | } | 101 | } |
102 | } | 102 | } |
@@ -104,16 +104,11 @@ public class DepthFirstStrategy implements Strategy { | |||
104 | Collection<Activation> activations; | 104 | Collection<Activation> activations; |
105 | do { | 105 | do { |
106 | activations = dseAdapter.getUntraversedActivations(); | 106 | activations = dseAdapter.getUntraversedActivations(); |
107 | if (activations.isEmpty()) { | 107 | if (activations.isEmpty() && !dseAdapter.backtrack()) { |
108 | if (!dseAdapter.backtrack()) { | 108 | // No more transitions from current state and cannot backtrack. |
109 | // "No more transitions from current state and cannot backtrack." | 109 | break mainloop; |
110 | break mainloop; | ||
111 | } | ||
112 | else { | ||
113 | // "No more transitions from current state, backtrack." | ||
114 | continue; | ||
115 | } | ||
116 | } | 110 | } |
111 | // No more transitions from current state, backtrack. | ||
117 | } while (activations.isEmpty()); | 112 | } while (activations.isEmpty()); |
118 | 113 | ||
119 | dseAdapter.fireRandomActivation(); | 114 | dseAdapter.fireRandomActivation(); |