diff options
Diffstat (limited to 'Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BestFirstStrategy.java')
-rw-r--r-- | Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BestFirstStrategy.java | 228 |
1 files changed, 228 insertions, 0 deletions
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BestFirstStrategy.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BestFirstStrategy.java new file mode 100644 index 00000000..fe5604a1 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BestFirstStrategy.java | |||
@@ -0,0 +1,228 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2017, Andras Szabolcs Nagy 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.api.strategy.impl; | ||
10 | |||
11 | import java.util.Arrays; | ||
12 | import java.util.Collection; | ||
13 | import java.util.Iterator; | ||
14 | import java.util.PriorityQueue; | ||
15 | |||
16 | import org.apache.log4j.Logger; | ||
17 | import org.eclipse.viatra.dse.api.strategy.interfaces.IStrategy; | ||
18 | import org.eclipse.viatra.dse.base.ThreadContext; | ||
19 | import org.eclipse.viatra.dse.objectives.Fitness; | ||
20 | import org.eclipse.viatra.dse.objectives.ObjectiveComparatorHelper; | ||
21 | import org.eclipse.viatra.dse.solutionstore.SolutionStore; | ||
22 | |||
23 | /** | ||
24 | * This exploration strategy eventually explorers the whole design space but goes in the most promising directions | ||
25 | * first, based on the {@link Fitness}. | ||
26 | * | ||
27 | * There are a few parameter to tune such as | ||
28 | * <ul> | ||
29 | * <li>maximum depth</li> | ||
30 | * <li>continue the exploration from a state that satisfies the hard objectives (the default that it will | ||
31 | * backtrack),</li> | ||
32 | * <li>whether to continue the exploration from the newly explored state if it is at least equally good than the | ||
33 | * previous one or only if it is better (default is "at least equally good").</li> | ||
34 | * </ul> | ||
35 | * | ||
36 | * @author Andras Szabolcs Nagy | ||
37 | * | ||
38 | */ | ||
39 | public class BestFirstStrategy implements IStrategy { | ||
40 | |||
41 | private ThreadContext context; | ||
42 | private SolutionStore solutionStore; | ||
43 | |||
44 | private int maxDepth; | ||
45 | private boolean isInterrupted = false; | ||
46 | private boolean backTrackIfSolution = true; | ||
47 | private boolean onlyBetterFirst = false; | ||
48 | |||
49 | private PriorityQueue<TrajectoryWithFitness> trajectoiresToExplore; | ||
50 | private Logger logger = Logger.getLogger(IStrategy.class); | ||
51 | |||
52 | private static class TrajectoryWithFitness { | ||
53 | |||
54 | public Object[] trajectory; | ||
55 | public Fitness fitness; | ||
56 | |||
57 | public TrajectoryWithFitness(Object[] trajectory, Fitness fitness) { | ||
58 | super(); | ||
59 | this.trajectory = trajectory; | ||
60 | this.fitness = fitness; | ||
61 | } | ||
62 | |||
63 | @Override | ||
64 | public String toString() { | ||
65 | return Arrays.toString(trajectory) + fitness.toString(); | ||
66 | } | ||
67 | |||
68 | } | ||
69 | |||
70 | /** | ||
71 | * Creates a new best-first search algorithm without depth limit. | ||
72 | */ | ||
73 | public BestFirstStrategy() { | ||
74 | this(-1); | ||
75 | } | ||
76 | |||
77 | /** | ||
78 | * Creates a new best-first search algorithm with depth limit. | ||
79 | * | ||
80 | * @param maxDepth | ||
81 | * A negative <code>maxDepth</code> means no depth limit, zero means the checking of the initial state. | ||
82 | */ | ||
83 | public BestFirstStrategy(int maxDepth) { | ||
84 | if (maxDepth < 0) { | ||
85 | this.maxDepth = Integer.MAX_VALUE; | ||
86 | } else { | ||
87 | this.maxDepth = maxDepth; | ||
88 | } | ||
89 | } | ||
90 | |||
91 | public BestFirstStrategy continueIfHardObjectivesFulfilled() { | ||
92 | backTrackIfSolution = false; | ||
93 | return this; | ||
94 | } | ||
95 | |||
96 | public BestFirstStrategy goOnOnlyIfFitnessIsBetter() { | ||
97 | onlyBetterFirst = true; | ||
98 | return this; | ||
99 | } | ||
100 | |||
101 | @Override | ||
102 | public void initStrategy(ThreadContext context) { | ||
103 | this.context = context; | ||
104 | this.solutionStore = context.getGlobalContext().getSolutionStore(); | ||
105 | final ObjectiveComparatorHelper objectiveComparatorHelper = context.getObjectiveComparatorHelper(); | ||
106 | |||
107 | trajectoiresToExplore = new PriorityQueue<TrajectoryWithFitness>(11, | ||
108 | (o1, o2) -> objectiveComparatorHelper.compare(o2.fitness, o1.fitness)); | ||
109 | } | ||
110 | |||
111 | @Override | ||
112 | public void explore() { | ||
113 | final ObjectiveComparatorHelper objectiveComparatorHelper = context.getObjectiveComparatorHelper(); | ||
114 | |||
115 | boolean globalConstraintsAreSatisfied = context.checkGlobalConstraints(); | ||
116 | if (!globalConstraintsAreSatisfied) { | ||
117 | logger.info("Global contraint is not satisifed in the first state. Terminate."); | ||
118 | return; | ||
119 | } | ||
120 | |||
121 | final Fitness firstFittness = context.calculateFitness(); | ||
122 | if (firstFittness.isSatisifiesHardObjectives()) { | ||
123 | context.newSolution(); | ||
124 | logger.info("First state is a solution. Terminate."); | ||
125 | return; | ||
126 | } | ||
127 | |||
128 | if (maxDepth == 0) { | ||
129 | return; | ||
130 | } | ||
131 | |||
132 | final Object[] firstTrajectory = context.getTrajectory().toArray(new Object[0]); | ||
133 | TrajectoryWithFitness currentTrajectoryWithFittness = new TrajectoryWithFitness(firstTrajectory, firstFittness); | ||
134 | trajectoiresToExplore.add(currentTrajectoryWithFittness); | ||
135 | |||
136 | mainLoop: while (!isInterrupted) { | ||
137 | |||
138 | if (currentTrajectoryWithFittness == null) { | ||
139 | if (trajectoiresToExplore.isEmpty()) { | ||
140 | logger.debug("State space is fully traversed."); | ||
141 | return; | ||
142 | } else { | ||
143 | currentTrajectoryWithFittness = trajectoiresToExplore.element(); | ||
144 | if (logger.isDebugEnabled()) { | ||
145 | logger.debug("New trajectory is chosen: " + currentTrajectoryWithFittness); | ||
146 | } | ||
147 | context.getDesignSpaceManager().executeTrajectoryWithMinimalBacktrackWithoutStateCoding(currentTrajectoryWithFittness.trajectory); | ||
148 | } | ||
149 | } | ||
150 | |||
151 | Collection<Object> activationIds = context.getUntraversedActivationIds(); | ||
152 | Iterator<Object> iterator = activationIds.iterator(); | ||
153 | |||
154 | while (!isInterrupted && iterator.hasNext()) { | ||
155 | final Object nextActivation = iterator.next(); | ||
156 | if (!iterator.hasNext()) { | ||
157 | logger.debug("Last untraversed activation of the state."); | ||
158 | trajectoiresToExplore.remove(currentTrajectoryWithFittness); | ||
159 | } | ||
160 | |||
161 | if (logger.isDebugEnabled()) { | ||
162 | logger.debug("Executing new activation: " + nextActivation); | ||
163 | } | ||
164 | context.executeAcitvationId(nextActivation); | ||
165 | if (context.isCurrentStateAlreadyTraversed()) { | ||
166 | logger.info("The new state is already visited."); | ||
167 | context.backtrack(); | ||
168 | } else if (!context.checkGlobalConstraints()) { | ||
169 | logger.debug("Global contraint is not satisifed."); | ||
170 | context.backtrack(); | ||
171 | } else { | ||
172 | final Fitness nextFitness = context.calculateFitness(); | ||
173 | if (nextFitness.isSatisifiesHardObjectives()) { | ||
174 | solutionStore.newSolution(context); | ||
175 | logger.debug("Found a solution."); | ||
176 | if (backTrackIfSolution) { | ||
177 | context.backtrack(); | ||
178 | continue; | ||
179 | } | ||
180 | } | ||
181 | if (context.getDepth() >= maxDepth) { | ||
182 | logger.debug("Reached max depth."); | ||
183 | context.backtrack(); | ||
184 | continue; | ||
185 | } | ||
186 | |||
187 | TrajectoryWithFitness nextTrajectoryWithFittness = new TrajectoryWithFitness( | ||
188 | context.getTrajectory().toArray(), nextFitness); | ||
189 | trajectoiresToExplore.add(nextTrajectoryWithFittness); | ||
190 | |||
191 | int compare = objectiveComparatorHelper.compare(currentTrajectoryWithFittness.fitness, | ||
192 | nextTrajectoryWithFittness.fitness); | ||
193 | if (compare < 0) { | ||
194 | logger.debug("Better fitness, moving on: " + nextFitness); | ||
195 | currentTrajectoryWithFittness = nextTrajectoryWithFittness; | ||
196 | continue mainLoop; | ||
197 | } else if (compare == 0) { | ||
198 | if (onlyBetterFirst) { | ||
199 | logger.debug("Equally good fitness, backtrack: " + nextFitness); | ||
200 | context.backtrack(); | ||
201 | continue; | ||
202 | } else { | ||
203 | logger.debug("Equally good fitness, moving on: " + nextFitness); | ||
204 | currentTrajectoryWithFittness = nextTrajectoryWithFittness; | ||
205 | continue mainLoop; | ||
206 | } | ||
207 | } else { | ||
208 | logger.debug("Worse fitness."); | ||
209 | currentTrajectoryWithFittness = null; | ||
210 | continue mainLoop; | ||
211 | } | ||
212 | } | ||
213 | } | ||
214 | |||
215 | logger.debug("State is fully traversed."); | ||
216 | trajectoiresToExplore.remove(currentTrajectoryWithFittness); | ||
217 | currentTrajectoryWithFittness = null; | ||
218 | |||
219 | } | ||
220 | logger.info("Interrupted."); | ||
221 | } | ||
222 | |||
223 | @Override | ||
224 | public void interruptStrategy() { | ||
225 | isInterrupted = true; | ||
226 | } | ||
227 | |||
228 | } | ||