diff options
Diffstat (limited to 'Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/BestFirstStrategyForModelGeneration.java')
-rw-r--r-- | Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/BestFirstStrategyForModelGeneration.java | 372 |
1 files changed, 372 insertions, 0 deletions
diff --git a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/BestFirstStrategyForModelGeneration.java b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/BestFirstStrategyForModelGeneration.java new file mode 100644 index 00000000..5a6fee2c --- /dev/null +++ b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/BestFirstStrategyForModelGeneration.java | |||
@@ -0,0 +1,372 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2017, Andras Szabolcs Nagy and Daniel Varro | ||
3 | * All rights reserved. This program and the accompanying materials | ||
4 | * are made available under the terms of the Eclipse Public License v1.0 | ||
5 | * which accompanies this distribution, and is available at | ||
6 | * http://www.eclipse.org/legal/epl-v10.html | ||
7 | * Contributors: | ||
8 | * Andras Szabolcs Nagy - initial API and implementation | ||
9 | *******************************************************************************/ | ||
10 | package hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner.dse; | ||
11 | |||
12 | import java.util.ArrayList; | ||
13 | import java.util.Arrays; | ||
14 | import java.util.Collections; | ||
15 | import java.util.Comparator; | ||
16 | import java.util.Iterator; | ||
17 | import java.util.List; | ||
18 | import java.util.PriorityQueue; | ||
19 | import java.util.Random; | ||
20 | |||
21 | import org.apache.log4j.Logger; | ||
22 | import org.eclipse.viatra.dse.api.strategy.interfaces.IStrategy; | ||
23 | import org.eclipse.viatra.dse.base.ThreadContext; | ||
24 | import org.eclipse.viatra.dse.objectives.Fitness; | ||
25 | import org.eclipse.viatra.dse.objectives.ObjectiveComparatorHelper; | ||
26 | import org.eclipse.viatra.dse.solutionstore.SolutionStore; | ||
27 | |||
28 | import hu.bme.mit.inf.dslreasoner.logic.model.builder.LogicReasoner; | ||
29 | import hu.bme.mit.inf.dslreasoner.logic.model.builder.LogicSolverConfiguration; | ||
30 | import hu.bme.mit.inf.dslreasoner.logic.model.logicresult.ModelResult; | ||
31 | import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretation2logic.PartialInterpretation2Logic; | ||
32 | import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.partialinterpretation.PartialInterpretation; | ||
33 | import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.visualisation.PartialInterpretation2Gml; | ||
34 | import hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner.DiversityDescriptor; | ||
35 | import hu.bme.mit.inf.dslreasoner.workspace.ReasonerWorkspace; | ||
36 | |||
37 | /** | ||
38 | * This exploration strategy eventually explorers the whole design space but goes in the most promising directions | ||
39 | * first, based on the {@link Fitness}. | ||
40 | * | ||
41 | * There are a few parameter to tune such as | ||
42 | * <ul> | ||
43 | * <li>maximum depth</li> | ||
44 | * <li>continue the exploration from a state that satisfies the hard objectives (the default that it will | ||
45 | * backtrack),</li> | ||
46 | * <li>whether to continue the exploration from the newly explored state if it is at least equally good than the | ||
47 | * previous one or only if it is better (default is "at least equally good").</li> | ||
48 | * </ul> | ||
49 | * | ||
50 | * @author Andras Szabolcs Nagy | ||
51 | * | ||
52 | */ | ||
53 | public class BestFirstStrategyForModelGeneration implements IStrategy { | ||
54 | |||
55 | private ThreadContext context; | ||
56 | private SolutionStore solutionStore; | ||
57 | private SolutionStoreWithCopy solutionStoreWithCopy; | ||
58 | private SolutionStoreWithDiversityDescriptor solutionStoreWithDiversityDescriptor; | ||
59 | private int numberOfStatecoderFail=0; | ||
60 | |||
61 | private int maxDepth = Integer.MAX_VALUE; | ||
62 | private boolean isInterrupted = false; | ||
63 | //private boolean backTrackIfSolution = true; | ||
64 | private boolean onlyBetterFirst = false; | ||
65 | |||
66 | private PriorityQueue<TrajectoryWithFitness> trajectoiresToExplore; | ||
67 | private Logger logger = Logger.getLogger(IStrategy.class); | ||
68 | |||
69 | private static class TrajectoryWithFitness { | ||
70 | |||
71 | public Object[] trajectory; | ||
72 | public Fitness fitness; | ||
73 | |||
74 | public TrajectoryWithFitness(Object[] trajectory, Fitness fitness) { | ||
75 | super(); | ||
76 | this.trajectory = trajectory; | ||
77 | this.fitness = fitness; | ||
78 | } | ||
79 | |||
80 | @Override | ||
81 | public String toString() { | ||
82 | return Arrays.toString(trajectory) + fitness.toString(); | ||
83 | } | ||
84 | |||
85 | } | ||
86 | |||
87 | public BestFirstStrategyForModelGeneration(ReasonerWorkspace workspace, LogicReasoner reasoner, LogicSolverConfiguration configuration, DiversityDescriptor descriptor) { | ||
88 | this.maxDepth = Integer.MAX_VALUE; | ||
89 | this.workspace = workspace; | ||
90 | this.reasoner = reasoner; | ||
91 | this.configuration = configuration; | ||
92 | this.solutionStoreWithDiversityDescriptor = new SolutionStoreWithDiversityDescriptor(descriptor); | ||
93 | } | ||
94 | |||
95 | @Override | ||
96 | public void initStrategy(ThreadContext context) { | ||
97 | this.context = context; | ||
98 | this.solutionStore = context.getGlobalContext().getSolutionStore(); | ||
99 | this.solutionStoreWithCopy = new SolutionStoreWithCopy(); | ||
100 | |||
101 | |||
102 | final ObjectiveComparatorHelper objectiveComparatorHelper = context.getObjectiveComparatorHelper(); | ||
103 | |||
104 | Comparator<TrajectoryWithFitness> comparator = new Comparator<BestFirstStrategyForModelGeneration.TrajectoryWithFitness>() { | ||
105 | |||
106 | @Override | ||
107 | public int compare(TrajectoryWithFitness o1, TrajectoryWithFitness o2) { | ||
108 | return objectiveComparatorHelper.compare(o2.fitness, o1.fitness); | ||
109 | } | ||
110 | }; | ||
111 | |||
112 | trajectoiresToExplore = new PriorityQueue<TrajectoryWithFitness>(11, comparator); | ||
113 | |||
114 | } | ||
115 | |||
116 | public SolutionStoreWithCopy getSolutionStoreWithCopy() { | ||
117 | return solutionStoreWithCopy; | ||
118 | } | ||
119 | |||
120 | public SolutionStoreWithDiversityDescriptor getSolutionStoreWithDiversityDescriptor() { | ||
121 | return solutionStoreWithDiversityDescriptor; | ||
122 | } | ||
123 | |||
124 | public int getNumberOfStatecoderFaiL() { | ||
125 | return numberOfStatecoderFail; | ||
126 | } | ||
127 | |||
128 | @Override | ||
129 | public void explore() { | ||
130 | final ObjectiveComparatorHelper objectiveComparatorHelper = context.getObjectiveComparatorHelper(); | ||
131 | |||
132 | boolean globalConstraintsAreSatisfied = context.checkGlobalConstraints(); | ||
133 | if (!globalConstraintsAreSatisfied) { | ||
134 | logger.info("Global contraint is not satisifed in the first state. Terminate."); | ||
135 | return; | ||
136 | } | ||
137 | |||
138 | final Fitness firstFittness = context.calculateFitness(); | ||
139 | if (firstFittness.isSatisifiesHardObjectives()) { | ||
140 | context.newSolution(); | ||
141 | logger.info("First state is a solution. Terminate."); | ||
142 | return; | ||
143 | } | ||
144 | |||
145 | if (maxDepth == 0) { | ||
146 | return; | ||
147 | } | ||
148 | |||
149 | final Object[] firstTrajectory = context.getTrajectory().toArray(new Object[0]); | ||
150 | TrajectoryWithFitness currentTrajectoryWithFittness = new TrajectoryWithFitness(firstTrajectory, firstFittness); | ||
151 | trajectoiresToExplore.add(currentTrajectoryWithFittness); | ||
152 | |||
153 | mainLoop: while (!isInterrupted) { | ||
154 | |||
155 | if (currentTrajectoryWithFittness == null) { | ||
156 | if (trajectoiresToExplore.isEmpty()) { | ||
157 | logger.debug("State space is fully traversed."); | ||
158 | return; | ||
159 | } else { | ||
160 | currentTrajectoryWithFittness = selectRandomState();// trajectoiresToExplore.element(); | ||
161 | if (logger.isDebugEnabled()) { | ||
162 | logger.debug("Current trajectory: " + Arrays.toString(context.getTrajectory().toArray())); | ||
163 | logger.debug("New trajectory is chosen: " + currentTrajectoryWithFittness); | ||
164 | } | ||
165 | // context.backtrackUntilRoot(); | ||
166 | // context.executeTrajectoryWithoutStateCoding(currentTrajectoryWithFittness.trajectory); | ||
167 | context.getDesignSpaceManager().executeTrajectoryWithMinimalBacktrackWithoutStateCoding(currentTrajectoryWithFittness.trajectory); | ||
168 | } | ||
169 | |||
170 | } | ||
171 | |||
172 | List<Object> activationIds; | ||
173 | try { | ||
174 | activationIds = new ArrayList<Object>(context.getUntraversedActivationIds()); | ||
175 | Collections.shuffle(activationIds); | ||
176 | } catch (NullPointerException e) { | ||
177 | numberOfStatecoderFail++; | ||
178 | activationIds = Collections.emptyList(); | ||
179 | } | ||
180 | |||
181 | Iterator<Object> iterator = activationIds.iterator(); | ||
182 | |||
183 | // writeCurrentState(); | ||
184 | // boolean consistencyCheckResult = checkConsistency(currentTrajectoryWithFittness); | ||
185 | // if(consistencyCheckResult == true) { | ||
186 | // continue mainLoop; | ||
187 | // } | ||
188 | |||
189 | while (!isInterrupted && iterator.hasNext()) { | ||
190 | final Object nextActivation = iterator.next(); | ||
191 | if (!iterator.hasNext()) { | ||
192 | logger.debug("Last untraversed activation of the state."); | ||
193 | trajectoiresToExplore.remove(currentTrajectoryWithFittness); | ||
194 | } | ||
195 | |||
196 | if (logger.isDebugEnabled()) { | ||
197 | logger.debug("Executing new activation: " + nextActivation); | ||
198 | } | ||
199 | context.executeAcitvationId(nextActivation); | ||
200 | |||
201 | // writeCurrentState(); | ||
202 | |||
203 | if (context.isCurrentStateAlreadyTraversed()) { | ||
204 | logger.info("The new state is already visited."); | ||
205 | context.backtrack(); | ||
206 | } else if (!context.checkGlobalConstraints()) { | ||
207 | logger.debug("Global contraint is not satisifed."); | ||
208 | context.backtrack(); | ||
209 | } else { | ||
210 | final Fitness nextFitness = context.calculateFitness(); | ||
211 | if (nextFitness.isSatisifiesHardObjectives()) { | ||
212 | if(solutionStoreWithDiversityDescriptor.isDifferent(context)) { | ||
213 | solutionStoreWithCopy.newSolution(context); | ||
214 | solutionStoreWithDiversityDescriptor.newSolution(context); | ||
215 | solutionStore.newSolution(context); | ||
216 | logger.debug("Found a solution."); | ||
217 | } | ||
218 | } | ||
219 | if (context.getDepth() > maxDepth) { | ||
220 | logger.debug("Reached max depth."); | ||
221 | context.backtrack(); | ||
222 | continue; | ||
223 | } | ||
224 | |||
225 | TrajectoryWithFitness nextTrajectoryWithFittness = new TrajectoryWithFitness( | ||
226 | context.getTrajectory().toArray(), nextFitness); | ||
227 | trajectoiresToExplore.add(nextTrajectoryWithFittness); | ||
228 | |||
229 | int compare = objectiveComparatorHelper.compare(currentTrajectoryWithFittness.fitness, | ||
230 | nextTrajectoryWithFittness.fitness); | ||
231 | if (compare < 0) { | ||
232 | logger.debug("Better fitness, moving on: " + nextFitness); | ||
233 | currentTrajectoryWithFittness = nextTrajectoryWithFittness; | ||
234 | continue mainLoop; | ||
235 | } else if (compare == 0) { | ||
236 | if (onlyBetterFirst) { | ||
237 | logger.debug("Equally good fitness, backtrack: " + nextFitness); | ||
238 | context.backtrack(); | ||
239 | continue; | ||
240 | } else { | ||
241 | logger.debug("Equally good fitness, moving on: " + nextFitness); | ||
242 | currentTrajectoryWithFittness = nextTrajectoryWithFittness; | ||
243 | continue mainLoop; | ||
244 | } | ||
245 | } else { | ||
246 | logger.debug("Worse fitness."); | ||
247 | // context.backtrack(); | ||
248 | currentTrajectoryWithFittness = null; | ||
249 | continue mainLoop; | ||
250 | } | ||
251 | } | ||
252 | } | ||
253 | |||
254 | logger.debug("State is fully traversed."); | ||
255 | trajectoiresToExplore.remove(currentTrajectoryWithFittness); | ||
256 | currentTrajectoryWithFittness = null; | ||
257 | |||
258 | } | ||
259 | logger.info("Interrupted."); | ||
260 | } | ||
261 | |||
262 | @Override | ||
263 | public void interruptStrategy() { | ||
264 | isInterrupted = true; | ||
265 | } | ||
266 | |||
267 | Random random = new Random(); | ||
268 | private TrajectoryWithFitness selectRandomState() { | ||
269 | int randomNumber = random.nextInt(100); | ||
270 | if(randomNumber < 5) { | ||
271 | int elements = trajectoiresToExplore.size(); | ||
272 | int randomElementIndex = random.nextInt(elements); | ||
273 | logger.debug("Randomly backtract to the " + randomElementIndex + " best solution..."); | ||
274 | Iterator<TrajectoryWithFitness> iterator = trajectoiresToExplore.iterator(); | ||
275 | while(randomElementIndex!=0) { | ||
276 | iterator.next(); | ||
277 | randomElementIndex--; | ||
278 | } | ||
279 | TrajectoryWithFitness res = iterator.next(); | ||
280 | if(res == null) { | ||
281 | return trajectoiresToExplore.element(); | ||
282 | } else { | ||
283 | return res; | ||
284 | } | ||
285 | } else { | ||
286 | return trajectoiresToExplore.element(); | ||
287 | } | ||
288 | } | ||
289 | |||
290 | private PartialInterpretation2Logic partialInterpretation2Logic = new PartialInterpretation2Logic(); | ||
291 | private LogicReasoner reasoner; | ||
292 | private PartialInterpretation2Gml partialInterpretation2Gml = new PartialInterpretation2Gml(); | ||
293 | private ReasonerWorkspace workspace; | ||
294 | private LogicSolverConfiguration configuration; | ||
295 | int numberOfPrintedModel = 0; | ||
296 | public ModelResult modelResultByTheSolver = null; | ||
297 | public void writeCurrentState() { | ||
298 | PartialInterpretation p = (PartialInterpretation)(context.getModel()); | ||
299 | int id= ++numberOfPrintedModel; | ||
300 | if(id%100 == 1) { | ||
301 | String text = this.partialInterpretation2Gml.transform(p); | ||
302 | this.workspace.writeText(id+".gml", text); | ||
303 | this.workspace.writeModel(p, id+".partialinterpretation"); | ||
304 | logger.debug("State "+id+" is saved."); | ||
305 | } | ||
306 | } | ||
307 | |||
308 | // int numberOfSolverCalls = 0; | ||
309 | // | ||
310 | // protected boolean checkConsistency(TrajectoryWithFitness t) { | ||
311 | // if (reasoner != null) { | ||
312 | // int id = ++numberOfSolverCalls; | ||
313 | // if (id % 100 == 1) { | ||
314 | // try { | ||
315 | // PartialInterpretation interpretation = (PartialInterpretation) (context.getModel()); | ||
316 | // PartialInterpretation copied = EcoreUtil.copy(interpretation); | ||
317 | // this.partialInterpretation2Logic.transformPartialIntepretation2Logic(copied.getProblem(), copied); | ||
318 | // LogicProblem newProblem = copied.getProblem(); | ||
319 | // | ||
320 | // this.configuration.typeScopes.maxNewElements = interpretation.getMaxNewElements(); | ||
321 | // this.configuration.typeScopes.minNewElements = interpretation.getMinNewElements(); | ||
322 | // LogicResult result = reasoner.solve(newProblem, configuration, workspace); | ||
323 | // if (result instanceof InconsistencyResult) { | ||
324 | // logger.debug("Solver found an Inconsistency!"); | ||
325 | // removeSubtreeFromQueue(t); | ||
326 | // return true; | ||
327 | // } else if (result instanceof ModelResult) { | ||
328 | // logger.debug("Solver found a model!"); | ||
329 | // solutionStore.newSolution(context); | ||
330 | |||
331 | // modelResultByTheSolver = (ModelResult) result; | ||
332 | // return true; | ||
333 | // } else { | ||
334 | // logger.debug("Failed consistency check."); | ||
335 | // return false; | ||
336 | // } | ||
337 | // } catch (Exception e) { | ||
338 | // // TODO Auto-generated catch block | ||
339 | // e.printStackTrace(); | ||
340 | // return false; | ||
341 | // } | ||
342 | // } | ||
343 | // | ||
344 | // } | ||
345 | // return false; | ||
346 | // } | ||
347 | // | ||
348 | // protected void removeSubtreeFromQueue(TrajectoryWithFitness t) { | ||
349 | // PriorityQueue<TrajectoryWithFitness> previous = this.trajectoiresToExplore; | ||
350 | // this.trajectoiresToExplore = new PriorityQueue<>(this.comparator); | ||
351 | // for (TrajectoryWithFitness trajectoryWithFitness : previous) { | ||
352 | // if(! containsAsSubstring(trajectoryWithFitness.trajectory,t.trajectory)) { | ||
353 | // this.trajectoiresToExplore.add(trajectoryWithFitness); | ||
354 | // } else { | ||
355 | // logger.debug("State has been excluded due to inherent inconsistency"); | ||
356 | // } | ||
357 | // } | ||
358 | // } | ||
359 | // | ||
360 | // private boolean containsAsSubstring(Object[] full, Object[] substring) { | ||
361 | // if(substring.length > full.length) { | ||
362 | // return false; | ||
363 | // } else if(substring.length == full.length) { | ||
364 | // return Arrays.equals(full, substring); | ||
365 | // } else { | ||
366 | // Object[] part = Arrays.copyOfRange(full, 0, substring.length); | ||
367 | // return Arrays.equals(part, substring); | ||
368 | // } | ||
369 | // } | ||
370 | // | ||
371 | |||
372 | } | ||