diff options
author | 2023-07-25 21:48:55 +0200 | |
---|---|---|
committer | 2023-07-26 00:11:53 +0200 | |
commit | 4f307849e09477cfaa600b50837e999208d05ad6 (patch) | |
tree | 25e815d3d18506e5de1b62c0a3e131a7a5cbbee3 | |
parent | Add Design space exploration and DFS strategy (diff) | |
download | refinery-4f307849e09477cfaa600b50837e999208d05ad6.tar.gz refinery-4f307849e09477cfaa600b50837e999208d05ad6.tar.zst refinery-4f307849e09477cfaa600b50837e999208d05ad6.zip |
Add best first strategy
2 files changed, 260 insertions, 0 deletions
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/dse/objectives/TrajectoryFitness.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/dse/objectives/TrajectoryFitness.java new file mode 100644 index 00000000..b9ff7067 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/dse/objectives/TrajectoryFitness.java | |||
@@ -0,0 +1,71 @@ | |||
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 tools.refinery.store.query.dse.objectives; | ||
10 | |||
11 | import java.util.Arrays; | ||
12 | |||
13 | |||
14 | /** | ||
15 | * This class represents a trajectory and its fitness. | ||
16 | * @author Andras Szabolcs Nagy | ||
17 | * | ||
18 | */ | ||
19 | public class TrajectoryFitness { | ||
20 | |||
21 | public Object[] trajectory; | ||
22 | public Fitness fitness; | ||
23 | |||
24 | public int rank; | ||
25 | public double crowdingDistance; | ||
26 | |||
27 | private int hash; | ||
28 | |||
29 | public int survive; | ||
30 | |||
31 | /** | ||
32 | * Creates a {@link TrajectoryFitness} with the full trajectory. | ||
33 | * @param trajectory The trajectory. | ||
34 | * @param fitness The fitness. | ||
35 | */ | ||
36 | public TrajectoryFitness(Object[] trajectory, Fitness fitness) { | ||
37 | this.fitness = fitness; | ||
38 | this.trajectory = trajectory; | ||
39 | } | ||
40 | |||
41 | /** | ||
42 | * Creates a {@link TrajectoryFitness} with the given activation id} | ||
43 | * @param transition The transition. | ||
44 | * @param fitness The fitness. | ||
45 | */ | ||
46 | public TrajectoryFitness(Object transition, Fitness fitness) { | ||
47 | this.fitness = fitness; | ||
48 | trajectory = new Object[] {transition}; | ||
49 | } | ||
50 | |||
51 | @Override | ||
52 | public boolean equals(Object obj) { | ||
53 | if (obj instanceof TrajectoryFitness) { | ||
54 | return Arrays.equals(trajectory, ((TrajectoryFitness) obj).trajectory); | ||
55 | } | ||
56 | return false; | ||
57 | } | ||
58 | |||
59 | @Override | ||
60 | public int hashCode() { | ||
61 | if (hash == 0 && trajectory.length > 0) { | ||
62 | hash = Arrays.hashCode(trajectory); | ||
63 | } | ||
64 | return hash; | ||
65 | } | ||
66 | |||
67 | @Override | ||
68 | public String toString() { | ||
69 | return Arrays.toString(trajectory) + fitness.toString(); | ||
70 | } | ||
71 | } | ||
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/dse/strategy/BestFirstStrategy.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/dse/strategy/BestFirstStrategy.java new file mode 100644 index 00000000..62adb72f --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/dse/strategy/BestFirstStrategy.java | |||
@@ -0,0 +1,189 @@ | |||
1 | package tools.refinery.store.query.dse.strategy; | ||
2 | |||
3 | import tools.refinery.store.query.dse.DesignSpaceExplorationAdapter; | ||
4 | import tools.refinery.store.query.dse.Strategy; | ||
5 | import tools.refinery.store.query.dse.internal.Activation; | ||
6 | import tools.refinery.store.query.dse.objectives.Fitness; | ||
7 | import tools.refinery.store.query.dse.objectives.ObjectiveComparatorHelper; | ||
8 | |||
9 | import java.util.Collection; | ||
10 | import java.util.Iterator; | ||
11 | import java.util.List; | ||
12 | import java.util.PriorityQueue; | ||
13 | |||
14 | public class BestFirstStrategy implements Strategy { | ||
15 | |||
16 | private DesignSpaceExplorationAdapter dseAdapter; | ||
17 | |||
18 | private int maxDepth; | ||
19 | private boolean backTrackIfSolution = true; | ||
20 | private boolean onlyBetterFirst = false; | ||
21 | |||
22 | private PriorityQueue<TrajectoryWithFitness> trajectoriesToExplore; | ||
23 | |||
24 | private static class TrajectoryWithFitness { | ||
25 | |||
26 | public List<Long> trajectory; | ||
27 | public Fitness fitness; | ||
28 | |||
29 | public TrajectoryWithFitness(List<Long> trajectory, Fitness fitness) { | ||
30 | super(); | ||
31 | this.trajectory = trajectory; | ||
32 | this.fitness = fitness; | ||
33 | } | ||
34 | |||
35 | @Override | ||
36 | public String toString() { | ||
37 | return trajectory.toString() + fitness.toString(); | ||
38 | } | ||
39 | |||
40 | } | ||
41 | |||
42 | public BestFirstStrategy() { | ||
43 | this(-1); | ||
44 | } | ||
45 | |||
46 | public BestFirstStrategy(int maxDepth) { | ||
47 | if (maxDepth < 0) { | ||
48 | this.maxDepth = Integer.MAX_VALUE; | ||
49 | } else { | ||
50 | this.maxDepth = maxDepth; | ||
51 | } | ||
52 | } | ||
53 | |||
54 | public BestFirstStrategy continueIfHardObjectivesFulfilled() { | ||
55 | backTrackIfSolution = false; | ||
56 | return this; | ||
57 | } | ||
58 | |||
59 | public BestFirstStrategy goOnOnlyIfFitnessIsBetter() { | ||
60 | onlyBetterFirst = true; | ||
61 | return this; | ||
62 | } | ||
63 | |||
64 | @Override | ||
65 | public void initStrategy(DesignSpaceExplorationAdapter designSpaceExplorationAdapter) { | ||
66 | this.dseAdapter = designSpaceExplorationAdapter; | ||
67 | final ObjectiveComparatorHelper objectiveComparatorHelper = dseAdapter.getObjectiveComparatorHelper(); | ||
68 | |||
69 | trajectoriesToExplore = new PriorityQueue<TrajectoryWithFitness>(11, | ||
70 | (o1, o2) -> objectiveComparatorHelper.compare(o2.fitness, o1.fitness)); | ||
71 | } | ||
72 | |||
73 | @Override | ||
74 | public void explore() { | ||
75 | final ObjectiveComparatorHelper objectiveComparatorHelper = dseAdapter.getObjectiveComparatorHelper(); | ||
76 | |||
77 | boolean globalConstraintsAreSatisfied = dseAdapter.checkGlobalConstraints(); | ||
78 | if (!globalConstraintsAreSatisfied) { | ||
79 | // "Global constraint is not satisfied in the first state. Terminate."); | ||
80 | return; | ||
81 | } | ||
82 | |||
83 | final Fitness firstFitness = dseAdapter.calculateFitness(); | ||
84 | if (firstFitness.isSatisfiesHardObjectives()) { | ||
85 | dseAdapter.newSolution(); | ||
86 | // "First state is a solution. Terminate."); | ||
87 | if (backTrackIfSolution) { | ||
88 | return; | ||
89 | } | ||
90 | } | ||
91 | |||
92 | if (maxDepth == 0) { | ||
93 | return; | ||
94 | } | ||
95 | |||
96 | final List<Long> firstTrajectory = dseAdapter.getTrajectory(); | ||
97 | TrajectoryWithFitness currentTrajectoryWithFitness = new TrajectoryWithFitness(firstTrajectory, firstFitness); | ||
98 | trajectoriesToExplore.add(currentTrajectoryWithFitness); | ||
99 | |||
100 | mainLoop: while (true) { | ||
101 | |||
102 | if (currentTrajectoryWithFitness == null) { | ||
103 | if (trajectoriesToExplore.isEmpty()) { | ||
104 | // "State space is fully traversed."); | ||
105 | return; | ||
106 | } else { | ||
107 | currentTrajectoryWithFitness = trajectoriesToExplore.element(); | ||
108 | // if (logger.isDebugEnabled()) { | ||
109 | // "New trajectory is chosen: " + currentTrajectoryWithFitness); | ||
110 | // } | ||
111 | dseAdapter.restoreTrajectory(currentTrajectoryWithFitness.trajectory); | ||
112 | } | ||
113 | } | ||
114 | |||
115 | Collection<Activation> activations = dseAdapter.getUntraversedActivations(); | ||
116 | Iterator<Activation> iterator = activations.iterator(); | ||
117 | |||
118 | |||
119 | |||
120 | while (iterator.hasNext()) { | ||
121 | final Activation nextActivation = iterator.next(); | ||
122 | if (!iterator.hasNext()) { | ||
123 | // "Last untraversed activation of the state."); | ||
124 | trajectoriesToExplore.remove(currentTrajectoryWithFitness); | ||
125 | } | ||
126 | |||
127 | // if (logger.isDebugEnabled()) { | ||
128 | // "Executing new activation: " + nextActivation); | ||
129 | // } | ||
130 | dseAdapter.fireActivation(nextActivation); | ||
131 | if (dseAdapter.isCurrentStateAlreadyTraversed()) { | ||
132 | // "The new state is already visited."); | ||
133 | dseAdapter.backtrack(); | ||
134 | } else if (!dseAdapter.checkGlobalConstraints()) { | ||
135 | // "Global constraint is not satisfied."); | ||
136 | dseAdapter.backtrack(); | ||
137 | } else { | ||
138 | final Fitness nextFitness = dseAdapter.calculateFitness(); | ||
139 | if (nextFitness.isSatisfiesHardObjectives()) { | ||
140 | dseAdapter.newSolution(); | ||
141 | // "Found a solution."); | ||
142 | if (backTrackIfSolution) { | ||
143 | dseAdapter.backtrack(); | ||
144 | continue; | ||
145 | } | ||
146 | } | ||
147 | if (dseAdapter.getDepth() >= maxDepth) { | ||
148 | // "Reached max depth."); | ||
149 | dseAdapter.backtrack(); | ||
150 | continue; | ||
151 | } | ||
152 | |||
153 | TrajectoryWithFitness nextTrajectoryWithFitness = new TrajectoryWithFitness( | ||
154 | dseAdapter.getTrajectory(), nextFitness); | ||
155 | trajectoriesToExplore.add(nextTrajectoryWithFitness); | ||
156 | |||
157 | int compare = objectiveComparatorHelper.compare(currentTrajectoryWithFitness.fitness, | ||
158 | nextTrajectoryWithFitness.fitness); | ||
159 | if (compare < 0) { | ||
160 | // "Better fitness, moving on: " + nextFitness); | ||
161 | currentTrajectoryWithFitness = nextTrajectoryWithFitness; | ||
162 | continue mainLoop; | ||
163 | } else if (compare == 0) { | ||
164 | if (onlyBetterFirst) { | ||
165 | // "Equally good fitness, backtrack: " + nextFitness); | ||
166 | dseAdapter.backtrack(); | ||
167 | continue; | ||
168 | } else { | ||
169 | // "Equally good fitness, moving on: " + nextFitness); | ||
170 | currentTrajectoryWithFitness = nextTrajectoryWithFitness; | ||
171 | continue mainLoop; | ||
172 | } | ||
173 | } else { | ||
174 | // "Worse fitness."); | ||
175 | currentTrajectoryWithFitness = null; | ||
176 | continue mainLoop; | ||
177 | } | ||
178 | } | ||
179 | } | ||
180 | |||
181 | // "State is fully traversed."); | ||
182 | trajectoriesToExplore.remove(currentTrajectoryWithFitness); | ||
183 | currentTrajectoryWithFitness = null; | ||
184 | |||
185 | } | ||
186 | // "Interrupted."); | ||
187 | |||
188 | } | ||
189 | } | ||