diff options
author | 2023-08-08 23:43:25 +0200 | |
---|---|---|
committer | 2023-08-08 23:43:25 +0200 | |
commit | 5c5dd4b36fda50e5635fe6a3255b48bb13cfe0ef (patch) | |
tree | 55d8b6c89de6625e0b9177e494ebf8f78b2b17c2 /subprojects/store-dse/src/main | |
parent | Merge pull request #36 from OszkarSemerath/datastructure (diff) | |
parent | Add return value to fireRandomActivation (diff) | |
download | refinery-5c5dd4b36fda50e5635fe6a3255b48bb13cfe0ef.tar.gz refinery-5c5dd4b36fda50e5635fe6a3255b48bb13cfe0ef.tar.zst refinery-5c5dd4b36fda50e5635fe6a3255b48bb13cfe0ef.zip |
Merge pull request #37 from nagilooh/design-space-exploration
Design-space exploration improvements
Diffstat (limited to 'subprojects/store-dse/src/main')
13 files changed, 296 insertions, 211 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 8963a496..5aed5298 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 | |||
@@ -38,7 +38,9 @@ public interface DesignSpaceExplorationAdapter extends ModelAdapter { | |||
38 | 38 | ||
39 | public boolean backtrack(); | 39 | public boolean backtrack(); |
40 | 40 | ||
41 | public Fitness calculateFitness(); | 41 | public boolean backtrack(String reason); |
42 | |||
43 | public Fitness getFitness(); | ||
42 | 44 | ||
43 | public void newSolution(); | 45 | public void newSolution(); |
44 | 46 | ||
@@ -48,9 +50,7 @@ public interface DesignSpaceExplorationAdapter extends ModelAdapter { | |||
48 | 50 | ||
49 | public boolean fireActivation(Activation activation); | 51 | public boolean fireActivation(Activation activation); |
50 | 52 | ||
51 | public void fireRandomActivation(); | 53 | public boolean fireRandomActivation(); |
52 | |||
53 | public boolean isCurrentInTrajectory(); | ||
54 | 54 | ||
55 | public List<Version> getTrajectory(); | 55 | public List<Version> getTrajectory(); |
56 | 56 | ||
@@ -63,4 +63,6 @@ public interface DesignSpaceExplorationAdapter extends ModelAdapter { | |||
63 | public void setRandom(Random random); | 63 | public void setRandom(Random random); |
64 | 64 | ||
65 | public void setRandom(long seed); | 65 | public void setRandom(long seed); |
66 | |||
67 | public List<Version> getSolutions(); | ||
66 | } | 68 | } |
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationStoreAdapter.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationStoreAdapter.java index 186bfebb..0252748d 100644 --- a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationStoreAdapter.java +++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationStoreAdapter.java | |||
@@ -6,6 +6,24 @@ | |||
6 | package tools.refinery.store.dse; | 6 | package tools.refinery.store.dse; |
7 | 7 | ||
8 | import tools.refinery.store.adapter.ModelStoreAdapter; | 8 | import tools.refinery.store.adapter.ModelStoreAdapter; |
9 | import tools.refinery.store.dse.internal.TransformationRule; | ||
10 | import tools.refinery.store.dse.objectives.Objective; | ||
11 | import tools.refinery.store.model.Model; | ||
12 | import tools.refinery.store.query.dnf.RelationalQuery; | ||
13 | |||
14 | import java.util.List; | ||
15 | import java.util.Set; | ||
9 | 16 | ||
10 | public interface DesignSpaceExplorationStoreAdapter extends ModelStoreAdapter { | 17 | public interface DesignSpaceExplorationStoreAdapter extends ModelStoreAdapter { |
18 | |||
19 | @Override | ||
20 | DesignSpaceExplorationAdapter createModelAdapter(Model model); | ||
21 | |||
22 | Set<TransformationRule> getTransformationSpecifications(); | ||
23 | |||
24 | Set<RelationalQuery> getGlobalConstraints(); | ||
25 | |||
26 | List<Objective> getObjectives(); | ||
27 | |||
28 | Strategy getStrategy(); | ||
11 | } | 29 | } |
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/Strategy.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/Strategy.java index e240f478..c60a4410 100644 --- a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/Strategy.java +++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/Strategy.java | |||
@@ -7,7 +7,7 @@ package tools.refinery.store.dse; | |||
7 | 7 | ||
8 | public interface Strategy { | 8 | public interface Strategy { |
9 | 9 | ||
10 | public void initStrategy(DesignSpaceExplorationAdapter designSpaceExplorationAdapter); | 10 | void initialize(DesignSpaceExplorationAdapter designSpaceExplorationAdapter); |
11 | 11 | ||
12 | public void explore(); | 12 | void explore(); |
13 | } | 13 | } |
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 b32e9696..220f0b2d 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 | |||
@@ -33,27 +33,24 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
33 | private final Model model; | 33 | private final Model model; |
34 | private final ModelQueryAdapter queryEngine; | 34 | private final ModelQueryAdapter queryEngine; |
35 | private final DesignSpaceExplorationStoreAdapterImpl storeAdapter; | 35 | private final DesignSpaceExplorationStoreAdapterImpl storeAdapter; |
36 | private final LinkedHashSet<TransformationRule> transformationRules; | 36 | private final Set<TransformationRule> transformationRules; |
37 | private final LinkedHashSet<RelationalQuery> globalConstraints; | 37 | private final Set<RelationalQuery> globalConstraints; |
38 | private final List<Objective> objectives; | 38 | private final List<Objective> objectives; |
39 | private final LinkedHashSet<ResultSet<Boolean>> globalConstraintResultSets = new LinkedHashSet<>(); | 39 | private final LinkedHashSet<ResultSet<Boolean>> globalConstraintResultSets = new LinkedHashSet<>(); |
40 | private final Interpretation<Integer> sizeInterpretation; | 40 | private final Interpretation<Integer> sizeInterpretation; |
41 | private final Strategy strategy; | 41 | private final Strategy strategy; |
42 | 42 | ||
43 | private ObjectiveComparatorHelper objectiveComparatorHelper; | 43 | private ObjectiveComparatorHelper objectiveComparatorHelper; |
44 | private List<Version> trajectory = new LinkedList<>(); | 44 | private List<Version> trajectory = new ArrayList<>(); |
45 | private Fitness lastFitness; | 45 | private Map<Version, Version> parents = new HashMap<>(); |
46 | private final LinkedHashSet<Version> solutions = new LinkedHashSet<>(); | 46 | private final List<Version> solutions = new ArrayList<>(); |
47 | private Map<Version, LinkedHashSet<Activation>> statesAndUntraversedActivations; | 47 | private Map<Version, List<Activation>> statesAndTraversedActivations; |
48 | private Map<Version, LinkedHashSet<Activation>> statesAndTraversedActivations; | ||
49 | private Random random = new Random(); | 48 | private Random random = new Random(); |
50 | private boolean isNewState = false; | 49 | private boolean isNewState = false; |
51 | private final boolean isVisualizationEnabled; | 50 | private final boolean isVisualizationEnabled; |
52 | private final ModelVisualizerAdapter modelVisualizerAdapter; | 51 | private final ModelVisualizerAdapter modelVisualizerAdapter; |
53 | 52 | ||
54 | public List<Version> getTrajectory() { | 53 | private final Map<Version, Fitness> fitnessCache = new HashMap<>(); |
55 | return new LinkedList<>(trajectory); | ||
56 | } | ||
57 | 54 | ||
58 | public DesignSpaceExplorationAdapterImpl(Model model, DesignSpaceExplorationStoreAdapterImpl storeAdapter) { | 55 | public DesignSpaceExplorationAdapterImpl(Model model, DesignSpaceExplorationStoreAdapterImpl storeAdapter) { |
59 | this.model = model; | 56 | this.model = model; |
@@ -72,14 +69,18 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
72 | } | 69 | } |
73 | 70 | ||
74 | objectives = storeAdapter.getObjectives(); | 71 | objectives = storeAdapter.getObjectives(); |
75 | statesAndUntraversedActivations = new HashMap<>(); | ||
76 | statesAndTraversedActivations = new HashMap<>(); | 72 | statesAndTraversedActivations = new HashMap<>(); |
77 | strategy = storeAdapter.getStrategy(); | 73 | strategy = storeAdapter.getStrategy(); |
74 | strategy.initialize(this); | ||
78 | modelVisualizerAdapter = model.tryGetAdapter(ModelVisualizerAdapter.class).orElse(null); | 75 | modelVisualizerAdapter = model.tryGetAdapter(ModelVisualizerAdapter.class).orElse(null); |
79 | isVisualizationEnabled = modelVisualizerAdapter != null; | 76 | isVisualizationEnabled = modelVisualizerAdapter != null; |
80 | 77 | ||
81 | } | 78 | } |
82 | 79 | ||
80 | public List<Version> getTrajectory() { | ||
81 | return new ArrayList<>(trajectory); | ||
82 | } | ||
83 | |||
83 | @Override | 84 | @Override |
84 | public Model getModel() { | 85 | public Model getModel() { |
85 | return model; | 86 | return model; |
@@ -91,13 +92,13 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
91 | } | 92 | } |
92 | 93 | ||
93 | @Override | 94 | @Override |
94 | public LinkedHashSet<Version> explore() { | 95 | public List<Version> explore() { |
95 | var state = model.commit(); | 96 | var state = model.commit(); |
96 | trajectory.add(state); | 97 | trajectory.add(state); |
97 | statesAndUntraversedActivations.put(state, getAllActivations()); | ||
98 | statesAndTraversedActivations.put(state, new LinkedHashSet<>()); | ||
99 | strategy.initStrategy(this); | ||
100 | strategy.explore(); | 98 | strategy.explore(); |
99 | if (isVisualizationEnabled) { | ||
100 | modelVisualizerAdapter.visualize(); | ||
101 | } | ||
101 | return solutions; | 102 | return solutions; |
102 | } | 103 | } |
103 | 104 | ||
@@ -137,14 +138,22 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
137 | 138 | ||
138 | @Override | 139 | @Override |
139 | public boolean backtrack() { | 140 | public boolean backtrack() { |
141 | return backtrack(""); | ||
142 | } | ||
143 | @Override | ||
144 | public boolean backtrack(String reason) { | ||
140 | if (trajectory.size() < 2) { | 145 | if (trajectory.size() < 2) { |
141 | return false; | 146 | return false; |
142 | } | 147 | } |
148 | var currentState = model.getState(); | ||
149 | if (!parents.containsKey(currentState)) { | ||
150 | return false; | ||
151 | } | ||
143 | if (isVisualizationEnabled) { | 152 | if (isVisualizationEnabled) { |
144 | modelVisualizerAdapter.addTransition(trajectory.get(trajectory.size() - 1), | 153 | modelVisualizerAdapter.addTransition(trajectory.get(trajectory.size() - 1), |
145 | trajectory.get(trajectory.size() - 2), "backtrack"); | 154 | trajectory.get(trajectory.size() - 2), "backtrack(" + reason + ")"); |
146 | } | 155 | } |
147 | model.restore(trajectory.get(trajectory.size() - 2)); | 156 | model.restore(parents.get(model.getState())); |
148 | trajectory.remove(trajectory.size() - 1); | 157 | trajectory.remove(trajectory.size() - 1); |
149 | return true; | 158 | return true; |
150 | } | 159 | } |
@@ -156,7 +165,7 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
156 | // modelVisualizerAdapter.addTransition(this.trajectory.get(trajectory.size() - 1), | 165 | // modelVisualizerAdapter.addTransition(this.trajectory.get(trajectory.size() - 1), |
157 | // trajectory.get(trajectory.size() - 1), "restore"); | 166 | // trajectory.get(trajectory.size() - 1), "restore"); |
158 | // } | 167 | // } |
159 | this.trajectory = trajectory; | 168 | this.trajectory = new ArrayList<>(trajectory); |
160 | 169 | ||
161 | } | 170 | } |
162 | 171 | ||
@@ -171,7 +180,16 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
171 | } | 180 | } |
172 | 181 | ||
173 | @Override | 182 | @Override |
174 | public Fitness calculateFitness() { | 183 | public List<Version> getSolutions() { |
184 | return solutions; | ||
185 | } | ||
186 | |||
187 | @Override | ||
188 | public Fitness getFitness() { | ||
189 | return fitnessCache.computeIfAbsent(model.getState(), s -> calculateFitness()); | ||
190 | } | ||
191 | |||
192 | private Fitness calculateFitness() { | ||
175 | Fitness result = new Fitness(); | 193 | Fitness result = new Fitness(); |
176 | boolean satisfiesHardObjectives = true; | 194 | boolean satisfiesHardObjectives = true; |
177 | for (Objective objective : objectives) { | 195 | for (Objective objective : objectives) { |
@@ -183,8 +201,6 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
183 | } | 201 | } |
184 | result.setSatisfiesHardObjectives(satisfiesHardObjectives); | 202 | result.setSatisfiesHardObjectives(satisfiesHardObjectives); |
185 | 203 | ||
186 | lastFitness = result; | ||
187 | |||
188 | return result; | 204 | return result; |
189 | } | 205 | } |
190 | 206 | ||
@@ -203,15 +219,19 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
203 | } | 219 | } |
204 | 220 | ||
205 | public LinkedHashSet<Activation> getUntraversedActivations() { | 221 | public LinkedHashSet<Activation> getUntraversedActivations() { |
206 | // return statesAndUntraversedActivations.get(model.getState()); | 222 | var traversedActivations = statesAndTraversedActivations.get(model.getState()); |
207 | LinkedHashSet<Activation> untraversedActivations = new LinkedHashSet<>(); | 223 | if (traversedActivations == null) { |
208 | for (Activation activation : getAllActivations()) { | 224 | return new LinkedHashSet<>(getAllActivations()); |
209 | if (!statesAndTraversedActivations.get(model.getState()).contains(activation)) { | 225 | } |
210 | untraversedActivations.add(activation); | 226 | else { |
227 | LinkedHashSet<Activation> untraversedActivations = new LinkedHashSet<>(); | ||
228 | for (Activation activation : getAllActivations()) { | ||
229 | if (!traversedActivations.contains(activation)) { | ||
230 | untraversedActivations.add(activation); | ||
231 | } | ||
211 | } | 232 | } |
233 | return untraversedActivations; | ||
212 | } | 234 | } |
213 | |||
214 | return untraversedActivations; | ||
215 | } | 235 | } |
216 | 236 | ||
217 | @Override | 237 | @Override |
@@ -220,37 +240,29 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
220 | return false; | 240 | return false; |
221 | } | 241 | } |
222 | var previousState = model.getState(); | 242 | var previousState = model.getState(); |
223 | if (!statesAndUntraversedActivations.get(previousState).contains(activation)) { | ||
224 | // TODO: throw exception? | ||
225 | return false; | ||
226 | } | ||
227 | if (!activation.fire()) { | 243 | if (!activation.fire()) { |
228 | return false; | 244 | return false; |
229 | } | 245 | } |
230 | statesAndUntraversedActivations.get(previousState).remove(activation); | 246 | statesAndTraversedActivations.computeIfAbsent(previousState, s -> new ArrayList<>()).add(activation); |
231 | statesAndTraversedActivations.get(previousState).add(activation); | ||
232 | var newState = model.commit(); | 247 | var newState = model.commit(); |
233 | trajectory.add(newState); | 248 | trajectory.add(newState); |
234 | isNewState = !statesAndUntraversedActivations.containsKey(newState); | 249 | parents.put(newState, previousState); |
235 | statesAndUntraversedActivations.put(newState, getAllActivations()); | 250 | isNewState = !statesAndTraversedActivations.containsKey(newState); |
236 | statesAndTraversedActivations.put(newState, new LinkedHashSet<>()); | ||
237 | if (isVisualizationEnabled) { | 251 | if (isVisualizationEnabled) { |
238 | if (isNewState) { | 252 | if (isNewState) { |
239 | modelVisualizerAdapter.addState(newState); | 253 | modelVisualizerAdapter.addState(newState, getFitness().values()); |
240 | } | 254 | } |
241 | modelVisualizerAdapter.addTransition(trajectory.get(trajectory.size() - 2), | 255 | modelVisualizerAdapter.addTransition(previousState, newState, activation.transformationRule().getName(), |
242 | trajectory.get(trajectory.size() - 1), activation.transformationRule().getName(), | ||
243 | activation.activation()); | 256 | activation.activation()); |
244 | } | 257 | } |
245 | return true; | 258 | return true; |
246 | } | 259 | } |
247 | 260 | ||
248 | @Override | 261 | @Override |
249 | public void fireRandomActivation() { | 262 | public boolean fireRandomActivation() { |
250 | var activations = getUntraversedActivations(); | 263 | var activations = getUntraversedActivations(); |
251 | if (activations.isEmpty()) { | 264 | if (activations.isEmpty()) { |
252 | // TODO: throw exception | 265 | return false; |
253 | return; | ||
254 | } | 266 | } |
255 | int index = random.nextInt(activations.size()); | 267 | int index = random.nextInt(activations.size()); |
256 | var iterator = activations.iterator(); | 268 | var iterator = activations.iterator(); |
@@ -258,31 +270,21 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
258 | iterator.next(); | 270 | iterator.next(); |
259 | } | 271 | } |
260 | var activationId = iterator.next(); | 272 | var activationId = iterator.next(); |
261 | fireActivation(activationId); | 273 | return fireActivation(activationId); |
262 | } | 274 | } |
263 | 275 | ||
264 | @Override | 276 | public List<Activation> getAllActivations() { |
265 | public boolean isCurrentInTrajectory() { | 277 | List<Activation> result = new LinkedList<>(); |
266 | return trajectory.contains(model.getState()); | ||
267 | } | ||
268 | |||
269 | public LinkedHashSet<Activation> getAllActivations() { | ||
270 | LinkedHashSet<Activation> result = new LinkedHashSet<>(); | ||
271 | for (var rule : transformationRules) { | 278 | for (var rule : transformationRules) { |
272 | result.addAll(rule.getAllActivations()); | 279 | result.addAll(rule.getAllActivationsAsList()); |
273 | } | 280 | } |
274 | return result; | 281 | return result; |
275 | } | 282 | } |
276 | 283 | ||
277 | public boolean isCurrentStateAlreadyTraversed() { | 284 | public boolean isCurrentStateAlreadyTraversed() { |
278 | // TODO: check isomorphism? | ||
279 | return !isNewState; | 285 | return !isNewState; |
280 | } | 286 | } |
281 | 287 | ||
282 | public Fitness getLastFitness() { | ||
283 | return lastFitness; | ||
284 | } | ||
285 | |||
286 | public ObjectiveComparatorHelper getObjectiveComparatorHelper() { | 288 | public ObjectiveComparatorHelper getObjectiveComparatorHelper() { |
287 | if (objectiveComparatorHelper == null) { | 289 | if (objectiveComparatorHelper == null) { |
288 | objectiveComparatorHelper = new ObjectiveComparatorHelper(objectives); | 290 | objectiveComparatorHelper = new ObjectiveComparatorHelper(objectives); |
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationStoreAdapterImpl.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationStoreAdapterImpl.java index 09925ae7..fea39886 100644 --- a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationStoreAdapterImpl.java +++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationStoreAdapterImpl.java | |||
@@ -5,27 +5,26 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.dse.internal; | 6 | package tools.refinery.store.dse.internal; |
7 | 7 | ||
8 | import tools.refinery.store.adapter.ModelAdapter; | ||
9 | import tools.refinery.store.model.Model; | ||
10 | import tools.refinery.store.model.ModelStore; | ||
11 | import tools.refinery.store.query.dnf.RelationalQuery; | ||
12 | import tools.refinery.store.dse.DesignSpaceExplorationStoreAdapter; | 8 | import tools.refinery.store.dse.DesignSpaceExplorationStoreAdapter; |
13 | import tools.refinery.store.dse.Strategy; | 9 | import tools.refinery.store.dse.Strategy; |
14 | import tools.refinery.store.dse.objectives.Objective; | 10 | import tools.refinery.store.dse.objectives.Objective; |
11 | import tools.refinery.store.model.Model; | ||
12 | import tools.refinery.store.model.ModelStore; | ||
13 | import tools.refinery.store.query.dnf.RelationalQuery; | ||
15 | 14 | ||
16 | import java.util.LinkedHashSet; | ||
17 | import java.util.List; | 15 | import java.util.List; |
16 | import java.util.Set; | ||
18 | 17 | ||
19 | public class DesignSpaceExplorationStoreAdapterImpl implements DesignSpaceExplorationStoreAdapter { | 18 | public class DesignSpaceExplorationStoreAdapterImpl implements DesignSpaceExplorationStoreAdapter { |
20 | private final ModelStore store; | 19 | private final ModelStore store; |
21 | private final LinkedHashSet<TransformationRule> transformationSpecifications; | 20 | private final Set<TransformationRule> transformationSpecifications; |
22 | private final LinkedHashSet<RelationalQuery> globalConstraints; | 21 | private final Set<RelationalQuery> globalConstraints; |
23 | private final List<Objective> objectives; | 22 | private final List<Objective> objectives; |
24 | private final Strategy strategy; | 23 | private final Strategy strategy; |
25 | 24 | ||
26 | public DesignSpaceExplorationStoreAdapterImpl(ModelStore store, | 25 | public DesignSpaceExplorationStoreAdapterImpl(ModelStore store, |
27 | LinkedHashSet<TransformationRule> transformationSpecifications, | 26 | Set<TransformationRule> transformationSpecifications, |
28 | LinkedHashSet<RelationalQuery> globalConstraints, | 27 | Set<RelationalQuery> globalConstraints, |
29 | List<Objective> objectives, Strategy strategy) { | 28 | List<Objective> objectives, Strategy strategy) { |
30 | this.store = store; | 29 | this.store = store; |
31 | this.transformationSpecifications = transformationSpecifications; | 30 | this.transformationSpecifications = transformationSpecifications; |
@@ -40,22 +39,26 @@ public class DesignSpaceExplorationStoreAdapterImpl implements DesignSpaceExplor | |||
40 | } | 39 | } |
41 | 40 | ||
42 | @Override | 41 | @Override |
43 | public ModelAdapter createModelAdapter(Model model) { | 42 | public DesignSpaceExplorationAdapterImpl createModelAdapter(Model model) { |
44 | return new DesignSpaceExplorationAdapterImpl(model, this); | 43 | return new DesignSpaceExplorationAdapterImpl(model, this); |
45 | } | 44 | } |
46 | 45 | ||
47 | public LinkedHashSet<TransformationRule> getTransformationSpecifications() { | 46 | @Override |
47 | public Set<TransformationRule> getTransformationSpecifications() { | ||
48 | return transformationSpecifications; | 48 | return transformationSpecifications; |
49 | } | 49 | } |
50 | 50 | ||
51 | public LinkedHashSet<RelationalQuery> getGlobalConstraints() { | 51 | @Override |
52 | public Set<RelationalQuery> getGlobalConstraints() { | ||
52 | return globalConstraints; | 53 | return globalConstraints; |
53 | } | 54 | } |
54 | 55 | ||
56 | @Override | ||
55 | public List<Objective> getObjectives() { | 57 | public List<Objective> getObjectives() { |
56 | return objectives; | 58 | return objectives; |
57 | } | 59 | } |
58 | 60 | ||
61 | @Override | ||
59 | public Strategy getStrategy() { | 62 | public Strategy getStrategy() { |
60 | return strategy; | 63 | return strategy; |
61 | } | 64 | } |
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/TransformationRule.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/TransformationRule.java index 015d4815..8123c0d6 100644 --- a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/TransformationRule.java +++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/TransformationRule.java | |||
@@ -14,8 +14,7 @@ import tools.refinery.store.query.resultset.OrderedResultSet; | |||
14 | import tools.refinery.store.query.resultset.ResultSet; | 14 | import tools.refinery.store.query.resultset.ResultSet; |
15 | import tools.refinery.store.tuple.Tuple; | 15 | import tools.refinery.store.tuple.Tuple; |
16 | 16 | ||
17 | import java.util.LinkedHashSet; | 17 | import java.util.*; |
18 | import java.util.Random; | ||
19 | 18 | ||
20 | public class TransformationRule { | 19 | public class TransformationRule { |
21 | 20 | ||
@@ -66,11 +65,11 @@ public class TransformationRule { | |||
66 | return precondition; | 65 | return precondition; |
67 | } | 66 | } |
68 | 67 | ||
69 | public ResultSet<Boolean> getAllActivationsAsSets() { | 68 | public ResultSet<Boolean> getAllActivationsAsResultSet() { |
70 | return activations; | 69 | return activations; |
71 | } | 70 | } |
72 | 71 | ||
73 | public LinkedHashSet<Activation> getAllActivations() { | 72 | public Set<Activation> getAllActivations() { |
74 | var result = new LinkedHashSet<Activation>(); | 73 | var result = new LinkedHashSet<Activation>(); |
75 | var cursor = activations.getAll(); | 74 | var cursor = activations.getAll(); |
76 | while (cursor.move()) { | 75 | while (cursor.move()) { |
@@ -79,6 +78,15 @@ public class TransformationRule { | |||
79 | return result; | 78 | return result; |
80 | } | 79 | } |
81 | 80 | ||
81 | public List<Activation> getAllActivationsAsList() { | ||
82 | var result = new ArrayList<Activation>(); | ||
83 | var cursor = activations.getAll(); | ||
84 | while (cursor.move()) { | ||
85 | result.add(new Activation(this, cursor.getKey())); | ||
86 | } | ||
87 | return result; | ||
88 | } | ||
89 | |||
82 | public Activation getRandomActivation() { | 90 | public Activation getRandomActivation() { |
83 | return new Activation(this, activations.getKey(random.nextInt(activations.size()))); | 91 | return new Activation(this, activations.getKey(random.nextInt(activations.size()))); |
84 | } | 92 | } |
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/AlwaysSatisfiedRandomHardObjective.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/AlwaysSatisfiedRandomHardObjective.java new file mode 100644 index 00000000..327d5e2f --- /dev/null +++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/AlwaysSatisfiedRandomHardObjective.java | |||
@@ -0,0 +1,56 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2016, Andras Szabolcs Nagy, Zoltan Ujhelyi and Daniel Varro | ||
3 | * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/> | ||
4 | * This program and the accompanying materials are made available under the | ||
5 | * terms of the Eclipse Public License v. 2.0 which is available at | ||
6 | * http://www.eclipse.org/legal/epl-v20.html. | ||
7 | * | ||
8 | * SPDX-License-Identifier: EPL-2.0 | ||
9 | *******************************************************************************/ | ||
10 | package tools.refinery.store.dse.objectives; | ||
11 | |||
12 | import tools.refinery.store.dse.DesignSpaceExplorationAdapter; | ||
13 | |||
14 | import java.util.Random; | ||
15 | |||
16 | /** | ||
17 | * This hard objective is fulfilled in any circumstances. Use it if all states should be regarded as a valid solution. | ||
18 | * | ||
19 | * @author Andras Szabolcs Nagy | ||
20 | * | ||
21 | */ | ||
22 | public class AlwaysSatisfiedRandomHardObjective extends BaseObjective { | ||
23 | |||
24 | private static final String DEFAULT_NAME = "AlwaysSatisfiedDummyHardObjective"; | ||
25 | private static final Random random = new Random(0); | ||
26 | |||
27 | public AlwaysSatisfiedRandomHardObjective() { | ||
28 | super(DEFAULT_NAME); | ||
29 | } | ||
30 | |||
31 | public AlwaysSatisfiedRandomHardObjective(String name) { | ||
32 | super(name); | ||
33 | } | ||
34 | |||
35 | @Override | ||
36 | public Double getFitness(DesignSpaceExplorationAdapter context) { | ||
37 | // return 0d; | ||
38 | return random.nextDouble(); | ||
39 | } | ||
40 | |||
41 | @Override | ||
42 | public boolean isHardObjective() { | ||
43 | return true; | ||
44 | } | ||
45 | |||
46 | @Override | ||
47 | public boolean satisfiesHardObjective(Double fitness) { | ||
48 | return true; | ||
49 | } | ||
50 | |||
51 | @Override | ||
52 | public Objective createNew() { | ||
53 | return this; | ||
54 | } | ||
55 | |||
56 | } | ||
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..b1dc4442 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,20 @@ 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 | if (!super.equals(other)) return false; | ||
36 | return satisfiesHardObjectives == ((Fitness) other).satisfiesHardObjectives; | ||
37 | } | ||
38 | |||
39 | @Override | ||
40 | public int hashCode() { | ||
41 | int h = super.hashCode(); | ||
42 | h = h * 31 + (satisfiesHardObjectives ? 1 : 0); | ||
43 | return h; | ||
44 | } | ||
45 | |||
30 | } | 46 | } |
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 8648864c..92d878ce 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 | |||
@@ -16,49 +16,52 @@ import tools.refinery.store.dse.internal.Activation; | |||
16 | import tools.refinery.store.dse.objectives.Fitness; | 16 | import tools.refinery.store.dse.objectives.Fitness; |
17 | import tools.refinery.store.dse.objectives.ObjectiveComparatorHelper; | 17 | import tools.refinery.store.dse.objectives.ObjectiveComparatorHelper; |
18 | 18 | ||
19 | import java.util.Collection; | 19 | import java.util.*; |
20 | import java.util.Iterator; | ||
21 | import java.util.List; | ||
22 | import java.util.PriorityQueue; | ||
23 | 20 | ||
24 | public class BestFirstStrategy implements Strategy { | 21 | public class BestFirstStrategy implements Strategy { |
25 | 22 | ||
26 | private DesignSpaceExplorationAdapter dseAdapter; | 23 | private DesignSpaceExplorationAdapter dseAdapter; |
27 | 24 | ||
28 | private int maxDepth; | 25 | private int maxDepth = Integer.MAX_VALUE; |
26 | private int maxSolutions = Integer.MAX_VALUE; | ||
29 | private boolean backTrackIfSolution = true; | 27 | private boolean backTrackIfSolution = true; |
30 | private boolean onlyBetterFirst = false; | 28 | private boolean onlyBetterFirst = false; |
31 | 29 | ||
32 | private PriorityQueue<TrajectoryWithFitness> trajectoriesToExplore; | 30 | private PriorityQueue<TrajectoryWithFitness> trajectoriesToExplore; |
33 | 31 | ||
34 | private static class TrajectoryWithFitness { | 32 | private record TrajectoryWithFitness(List<Version> trajectory, Fitness fitness) { |
35 | 33 | @Override | |
36 | public List<Version> trajectory; | 34 | public String toString() { |
37 | public Fitness fitness; | 35 | return trajectory.toString() + fitness.toString(); |
36 | } | ||
38 | 37 | ||
39 | public TrajectoryWithFitness(List<Version> trajectory, Fitness fitness) { | 38 | @Override |
40 | super(); | 39 | public int hashCode() { |
41 | this.trajectory = trajectory; | 40 | return trajectory.get(trajectory.size() - 1).hashCode(); |
42 | this.fitness = fitness; | ||
43 | } | 41 | } |
44 | 42 | ||
45 | @Override | 43 | @Override |
46 | public String toString() { | 44 | public boolean equals(Object obj) { |
47 | return trajectory.toString() + fitness.toString(); | 45 | if (obj instanceof TrajectoryWithFitness other) { |
46 | return Objects.equals(trajectory.get(trajectory.size() - 1), other.trajectory.get(other.trajectory.size() - 1)); | ||
47 | // return trajectory.equals(((TrajectoryWithFitness) obj).trajectory); | ||
48 | } | ||
49 | return false; | ||
48 | } | 50 | } |
49 | |||
50 | } | 51 | } |
51 | 52 | ||
52 | public BestFirstStrategy() { | 53 | public BestFirstStrategy withDepthLimit(int maxDepth) { |
53 | this(-1); | 54 | if (maxDepth >= 0) { |
55 | this.maxDepth = maxDepth; | ||
56 | } | ||
57 | return this; | ||
54 | } | 58 | } |
55 | 59 | ||
56 | public BestFirstStrategy(int maxDepth) { | 60 | public BestFirstStrategy withSolutionLimit(int maxSolutions) { |
57 | if (maxDepth < 0) { | 61 | if (maxSolutions >= 0) { |
58 | this.maxDepth = Integer.MAX_VALUE; | 62 | this.maxSolutions = maxSolutions; |
59 | } else { | ||
60 | this.maxDepth = maxDepth; | ||
61 | } | 63 | } |
64 | return this; | ||
62 | } | 65 | } |
63 | 66 | ||
64 | public BestFirstStrategy continueIfHardObjectivesFulfilled() { | 67 | public BestFirstStrategy continueIfHardObjectivesFulfilled() { |
@@ -72,28 +75,31 @@ public class BestFirstStrategy implements Strategy { | |||
72 | } | 75 | } |
73 | 76 | ||
74 | @Override | 77 | @Override |
75 | public void initStrategy(DesignSpaceExplorationAdapter designSpaceExplorationAdapter) { | 78 | public void initialize(DesignSpaceExplorationAdapter designSpaceExplorationAdapter) { |
76 | this.dseAdapter = designSpaceExplorationAdapter; | 79 | this.dseAdapter = designSpaceExplorationAdapter; |
77 | final ObjectiveComparatorHelper objectiveComparatorHelper = dseAdapter.getObjectiveComparatorHelper(); | 80 | final ObjectiveComparatorHelper objectiveComparatorHelper = dseAdapter.getObjectiveComparatorHelper(); |
78 | 81 | ||
79 | trajectoriesToExplore = new PriorityQueue<TrajectoryWithFitness>(11, | 82 | trajectoriesToExplore = new PriorityQueue<>(11, |
80 | (o1, o2) -> objectiveComparatorHelper.compare(o2.fitness, o1.fitness)); | 83 | (o1, o2) -> objectiveComparatorHelper.compare(o2.fitness, o1.fitness)); |
81 | } | 84 | } |
82 | 85 | ||
83 | @Override | 86 | @Override |
84 | public void explore() { | 87 | public void explore() { |
88 | if (maxSolutions == 0) { | ||
89 | return; | ||
90 | } | ||
85 | final ObjectiveComparatorHelper objectiveComparatorHelper = dseAdapter.getObjectiveComparatorHelper(); | 91 | final ObjectiveComparatorHelper objectiveComparatorHelper = dseAdapter.getObjectiveComparatorHelper(); |
86 | 92 | ||
87 | boolean globalConstraintsAreSatisfied = dseAdapter.checkGlobalConstraints(); | 93 | boolean globalConstraintsAreSatisfied = dseAdapter.checkGlobalConstraints(); |
88 | if (!globalConstraintsAreSatisfied) { | 94 | if (!globalConstraintsAreSatisfied) { |
89 | // "Global constraint is not satisfied in the first state. Terminate."); | 95 | // Global constraint is not satisfied in the first state. Terminate. |
90 | return; | 96 | return; |
91 | } | 97 | } |
92 | 98 | ||
93 | final Fitness firstFitness = dseAdapter.calculateFitness(); | 99 | final Fitness firstFitness = dseAdapter.getFitness(); |
94 | if (firstFitness.isSatisfiesHardObjectives()) { | 100 | if (firstFitness.isSatisfiesHardObjectives()) { |
95 | dseAdapter.newSolution(); | 101 | dseAdapter.newSolution(); |
96 | // "First state is a solution. Terminate."); | 102 | // First state is a solution. Terminate. |
97 | if (backTrackIfSolution) { | 103 | if (backTrackIfSolution) { |
98 | return; | 104 | return; |
99 | } | 105 | } |
@@ -103,21 +109,20 @@ public class BestFirstStrategy implements Strategy { | |||
103 | return; | 109 | return; |
104 | } | 110 | } |
105 | 111 | ||
106 | final List<Version> firstTrajectory = dseAdapter.getTrajectory(); | 112 | |
107 | TrajectoryWithFitness currentTrajectoryWithFitness = new TrajectoryWithFitness(firstTrajectory, firstFitness); | 113 | var firstTrajectoryWithFitness = new TrajectoryWithFitness(dseAdapter.getTrajectory(), firstFitness); |
108 | trajectoriesToExplore.add(currentTrajectoryWithFitness); | 114 | trajectoriesToExplore.add(firstTrajectoryWithFitness); |
115 | TrajectoryWithFitness currentTrajectoryWithFitness = null; | ||
109 | 116 | ||
110 | mainLoop: while (true) { | 117 | mainLoop: while (true) { |
111 | 118 | ||
112 | if (currentTrajectoryWithFitness == null) { | 119 | if (currentTrajectoryWithFitness == null) { |
113 | if (trajectoriesToExplore.isEmpty()) { | 120 | if (trajectoriesToExplore.isEmpty()) { |
114 | // "State space is fully traversed."); | 121 | // State space is fully traversed. |
115 | return; | 122 | return; |
116 | } else { | 123 | } else { |
117 | currentTrajectoryWithFitness = trajectoriesToExplore.element(); | 124 | currentTrajectoryWithFitness = trajectoriesToExplore.element(); |
118 | // if (logger.isDebugEnabled()) { | 125 | // New trajectory is chosen: " + currentTrajectoryWithFitness |
119 | // "New trajectory is chosen: " + currentTrajectoryWithFitness); | ||
120 | // } | ||
121 | dseAdapter.restoreTrajectory(currentTrajectoryWithFitness.trajectory); | 126 | dseAdapter.restoreTrajectory(currentTrajectoryWithFitness.trajectory); |
122 | } | 127 | } |
123 | } | 128 | } |
@@ -130,32 +135,34 @@ public class BestFirstStrategy implements Strategy { | |||
130 | while (iterator.hasNext()) { | 135 | while (iterator.hasNext()) { |
131 | final Activation nextActivation = iterator.next(); | 136 | final Activation nextActivation = iterator.next(); |
132 | if (!iterator.hasNext()) { | 137 | if (!iterator.hasNext()) { |
133 | // "Last untraversed activation of the state."); | 138 | // Last untraversed activation of the state. |
134 | trajectoriesToExplore.remove(currentTrajectoryWithFitness); | 139 | trajectoriesToExplore.remove(currentTrajectoryWithFitness); |
135 | } | 140 | } |
136 | 141 | ||
137 | // if (logger.isDebugEnabled()) { | 142 | // Executing new activation |
138 | // "Executing new activation: " + nextActivation); | ||
139 | // } | ||
140 | dseAdapter.fireActivation(nextActivation); | 143 | dseAdapter.fireActivation(nextActivation); |
141 | if (dseAdapter.isCurrentStateAlreadyTraversed()) { | 144 | if (dseAdapter.isCurrentStateAlreadyTraversed()) { |
142 | // "The new state is already visited."); | 145 | // The new state is already visited. |
143 | dseAdapter.backtrack(); | 146 | dseAdapter.backtrack(); |
144 | } else if (!dseAdapter.checkGlobalConstraints()) { | 147 | } else if (!dseAdapter.checkGlobalConstraints()) { |
145 | // "Global constraint is not satisfied."); | 148 | // Global constraint is not satisfied. |
146 | dseAdapter.backtrack(); | 149 | dseAdapter.backtrack(); |
147 | } else { | 150 | } else { |
148 | final Fitness nextFitness = dseAdapter.calculateFitness(); | 151 | final Fitness nextFitness = dseAdapter.getFitness(); |
149 | if (nextFitness.isSatisfiesHardObjectives()) { | 152 | if (nextFitness.isSatisfiesHardObjectives()) { |
150 | dseAdapter.newSolution(); | 153 | dseAdapter.newSolution(); |
151 | // "Found a solution."); | 154 | var solutions = dseAdapter.getSolutions().size(); |
155 | if (solutions >= maxSolutions) { | ||
156 | return; | ||
157 | } | ||
158 | // Found a solution. | ||
152 | if (backTrackIfSolution) { | 159 | if (backTrackIfSolution) { |
153 | dseAdapter.backtrack(); | 160 | dseAdapter.backtrack(); |
154 | continue; | 161 | continue; |
155 | } | 162 | } |
156 | } | 163 | } |
157 | if (dseAdapter.getDepth() >= maxDepth) { | 164 | if (dseAdapter.getDepth() >= maxDepth) { |
158 | // "Reached max depth."); | 165 | // Reached max depth. |
159 | dseAdapter.backtrack(); | 166 | dseAdapter.backtrack(); |
160 | continue; | 167 | continue; |
161 | } | 168 | } |
@@ -167,33 +174,30 @@ public class BestFirstStrategy implements Strategy { | |||
167 | int compare = objectiveComparatorHelper.compare(currentTrajectoryWithFitness.fitness, | 174 | int compare = objectiveComparatorHelper.compare(currentTrajectoryWithFitness.fitness, |
168 | nextTrajectoryWithFitness.fitness); | 175 | nextTrajectoryWithFitness.fitness); |
169 | if (compare < 0) { | 176 | if (compare < 0) { |
170 | // "Better fitness, moving on: " + nextFitness); | 177 | // Better fitness, moving on |
171 | currentTrajectoryWithFitness = nextTrajectoryWithFitness; | 178 | currentTrajectoryWithFitness = nextTrajectoryWithFitness; |
172 | continue mainLoop; | 179 | continue mainLoop; |
173 | } else if (compare == 0) { | 180 | } else if (compare == 0) { |
174 | if (onlyBetterFirst) { | 181 | if (onlyBetterFirst) { |
175 | // "Equally good fitness, backtrack: " + nextFitness); | 182 | // Equally good fitness, backtrack |
176 | dseAdapter.backtrack(); | 183 | dseAdapter.backtrack(); |
177 | continue; | ||
178 | } else { | 184 | } else { |
179 | // "Equally good fitness, moving on: " + nextFitness); | 185 | // Equally good fitness, moving on |
180 | currentTrajectoryWithFitness = nextTrajectoryWithFitness; | 186 | currentTrajectoryWithFitness = nextTrajectoryWithFitness; |
181 | continue mainLoop; | 187 | continue mainLoop; |
182 | } | 188 | } |
183 | } else { | 189 | } else { |
184 | // "Worse fitness."); | 190 | //"Worse fitness |
185 | currentTrajectoryWithFitness = null; | 191 | currentTrajectoryWithFitness = null; |
186 | continue mainLoop; | 192 | continue mainLoop; |
187 | } | 193 | } |
188 | } | 194 | } |
189 | } | 195 | } |
190 | 196 | ||
191 | // "State is fully traversed."); | 197 | // State is fully traversed. |
192 | trajectoriesToExplore.remove(currentTrajectoryWithFitness); | ||
193 | currentTrajectoryWithFitness = null; | 198 | currentTrajectoryWithFitness = null; |
194 | 199 | ||
195 | } | 200 | } |
196 | // "Interrupted."); | 201 | // Interrupted. |
197 | |||
198 | } | 202 | } |
199 | } | 203 | } |
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 1405789b..0a0caa7e 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 | |||
@@ -1,117 +1,92 @@ | |||
1 | /******************************************************************************* | 1 | /* |
2 | * Copyright (c) 2010-2016, Andras Szabolcs Nagy, Zoltan Ujhelyi and Daniel Varro | 2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> |
3 | * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/> | ||
4 | * This program and the accompanying materials are made available under the | ||
5 | * terms of the Eclipse Public License v. 2.0 which is available at | ||
6 | * http://www.eclipse.org/legal/epl-v20.html. | ||
7 | * | 3 | * |
8 | * SPDX-License-Identifier: EPL-2.0 | 4 | * SPDX-License-Identifier: EPL-2.0 |
9 | *******************************************************************************/ | 5 | */ |
10 | package tools.refinery.store.dse.strategy; | 6 | package tools.refinery.store.dse.strategy; |
11 | 7 | ||
12 | import tools.refinery.store.dse.DesignSpaceExplorationAdapter; | 8 | import tools.refinery.store.dse.DesignSpaceExplorationAdapter; |
13 | import tools.refinery.store.dse.Strategy; | 9 | import tools.refinery.store.dse.Strategy; |
14 | import tools.refinery.store.dse.internal.Activation; | ||
15 | import tools.refinery.store.dse.objectives.Fitness; | 10 | import tools.refinery.store.dse.objectives.Fitness; |
16 | 11 | ||
17 | import java.util.Collection; | ||
18 | |||
19 | public class DepthFirstStrategy implements Strategy { | 12 | public class DepthFirstStrategy implements Strategy { |
20 | 13 | ||
21 | private DesignSpaceExplorationAdapter dseAdapter; | 14 | private DesignSpaceExplorationAdapter dseAdapter; |
22 | 15 | ||
23 | private int maxDepth; | 16 | private int maxDepth = Integer.MAX_VALUE; |
24 | private boolean backTrackIfSolution = true; | 17 | private int maxSolutions = Integer.MAX_VALUE; |
18 | private boolean backtrackFromSolution = true; | ||
25 | 19 | ||
26 | public DepthFirstStrategy() { | 20 | public DepthFirstStrategy withDepthLimit(int maxDepth) { |
27 | this(-1); | 21 | if (maxDepth >= 0) { |
22 | this.maxDepth = maxDepth; | ||
23 | } | ||
24 | return this; | ||
28 | } | 25 | } |
29 | 26 | ||
30 | public DepthFirstStrategy(int maxDepth) { | 27 | public DepthFirstStrategy withSolutionLimit(int maxSolutions) { |
31 | if (maxDepth < 0) { | 28 | if (maxSolutions >= 0) { |
32 | this.maxDepth = Integer.MAX_VALUE; | 29 | this.maxSolutions = maxSolutions; |
33 | } else { | ||
34 | this.maxDepth = maxDepth; | ||
35 | } | 30 | } |
31 | return this; | ||
36 | } | 32 | } |
37 | 33 | ||
38 | public DepthFirstStrategy continueIfHardObjectivesFulfilled() { | 34 | public DepthFirstStrategy continueIfHardObjectivesFulfilled() { |
39 | backTrackIfSolution = false; | 35 | backtrackFromSolution = false; |
40 | return this; | 36 | return this; |
41 | } | 37 | } |
42 | 38 | ||
43 | @Override | 39 | @Override |
44 | public void initStrategy(DesignSpaceExplorationAdapter designSpaceExplorationAdapter) { | 40 | public void initialize(DesignSpaceExplorationAdapter designSpaceExplorationAdapter) { |
45 | this.dseAdapter = designSpaceExplorationAdapter; | 41 | this.dseAdapter = designSpaceExplorationAdapter; |
46 | } | 42 | } |
47 | 43 | ||
48 | @Override | 44 | @Override |
49 | public void explore() { | 45 | public void explore() { |
50 | mainloop: while (true) { | 46 | if (maxSolutions == 0) { |
51 | var globalConstraintsAreSatisfied = dseAdapter.checkGlobalConstraints(); | 47 | return; |
52 | if (!globalConstraintsAreSatisfied) { | 48 | } |
53 | var isSuccessfulUndo = dseAdapter.backtrack(); | 49 | while (dseAdapter.getSolutions().size() < maxSolutions) { |
54 | if (!isSuccessfulUndo) { | 50 | if (!checkAndHandleGlobalConstraints()) { |
55 | // "Global constraint is not satisfied and cannot backtrack." | 51 | return; |
56 | break; | ||
57 | } | ||
58 | else { | ||
59 | // "Global constraint is not satisfied, backtrack." | ||
60 | continue; | ||
61 | } | ||
62 | } | 52 | } |
63 | 53 | ||
64 | Fitness fitness = dseAdapter.calculateFitness(); | 54 | Fitness fitness = dseAdapter.getFitness(); |
65 | if (fitness.isSatisfiesHardObjectives()) { | 55 | if (fitness.isSatisfiesHardObjectives()) { |
66 | dseAdapter.newSolution(); | 56 | dseAdapter.newSolution(); |
67 | if (backTrackIfSolution) { | 57 | if (backtrackFromSolution && !dseAdapter.backtrack()) { |
68 | var isSuccessfulUndo = dseAdapter.backtrack(); | 58 | return; |
69 | if (!isSuccessfulUndo) { | ||
70 | // "Found a solution but cannot backtrack." | ||
71 | break; | ||
72 | } else { | ||
73 | // "Found a solution, backtrack." | ||
74 | continue; | ||
75 | } | ||
76 | } | 59 | } |
77 | } | 60 | } |
78 | 61 | ||
79 | var depth = dseAdapter.getDepth(); | 62 | if (!checkAndHandleDepth()) { |
80 | if (dseAdapter.getDepth() >= maxDepth) { | 63 | return; |
81 | var isSuccessfulUndo = dseAdapter.backtrack(); | ||
82 | if (!isSuccessfulUndo) { | ||
83 | // "Reached max depth but cannot backtrack." | ||
84 | break; | ||
85 | } | ||
86 | } | 64 | } |
87 | 65 | ||
88 | Collection<Activation> activations; | 66 | if (!backtrackToLastUntraversed()) { |
89 | do { | 67 | return; |
90 | activations = dseAdapter.getUntraversedActivations(); | 68 | } |
91 | if (activations.isEmpty()) { | 69 | |
92 | if (!dseAdapter.backtrack()) { | 70 | if (!dseAdapter.fireRandomActivation()) { |
93 | // "No more transitions from current state and cannot backtrack." | 71 | return; |
94 | break mainloop; | 72 | } |
95 | } | 73 | } |
96 | else { | 74 | } |
97 | // "No more transitions from current state, backtrack." | 75 | |
98 | continue; | 76 | private boolean checkAndHandleGlobalConstraints() { |
99 | } | 77 | return dseAdapter.checkGlobalConstraints() || dseAdapter.backtrack(); |
100 | } | 78 | } |
101 | } while (activations.isEmpty()); | 79 | |
102 | 80 | private boolean checkAndHandleDepth() { | |
103 | dseAdapter.fireRandomActivation(); | 81 | return dseAdapter.getDepth() < maxDepth || dseAdapter.backtrack(); |
104 | // if (dseAdapter.isCurrentInTrajectory()) { | 82 | } |
105 | // if (!dseAdapter.backtrack()) { | 83 | |
106 | //// TODO: throw exception | 84 | private boolean backtrackToLastUntraversed() { |
107 | //// "The new state is present in the trajectory but cannot backtrack. Should never happen!" | 85 | while (dseAdapter.getUntraversedActivations().isEmpty()) { |
108 | // break; | 86 | if (!dseAdapter.backtrack()) { |
109 | // } | 87 | return false; |
110 | // else { | 88 | } |
111 | //// "The new state is already visited in the trajectory, backtrack." | ||
112 | // continue; | ||
113 | // } | ||
114 | // } | ||
115 | } | 89 | } |
90 | return true; | ||
116 | } | 91 | } |
117 | } | 92 | } |