aboutsummaryrefslogtreecommitdiffstats
path: root/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/BestFirstStrategyForModelGeneration.java
diff options
context:
space:
mode:
authorLibravatar OszkarSemerath <oszka@152.66.252.189>2017-06-10 19:05:05 +0200
committerLibravatar OszkarSemerath <oszka@152.66.252.189>2017-06-10 19:05:05 +0200
commit60f01f46ba232ed6416054f0a6115cb2a9b70b4e (patch)
tree5edf8aeb07abc51f3fec63bbd15c926e1de09552 /Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/BestFirstStrategyForModelGeneration.java
parentInitial commit, migrating from SVN (diff)
downloadVIATRA-Generator-60f01f46ba232ed6416054f0a6115cb2a9b70b4e.tar.gz
VIATRA-Generator-60f01f46ba232ed6416054f0a6115cb2a9b70b4e.tar.zst
VIATRA-Generator-60f01f46ba232ed6416054f0a6115cb2a9b70b4e.zip
Migrating Additional projects
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.java372
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 *******************************************************************************/
10package hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner.dse;
11
12import java.util.ArrayList;
13import java.util.Arrays;
14import java.util.Collections;
15import java.util.Comparator;
16import java.util.Iterator;
17import java.util.List;
18import java.util.PriorityQueue;
19import java.util.Random;
20
21import org.apache.log4j.Logger;
22import org.eclipse.viatra.dse.api.strategy.interfaces.IStrategy;
23import org.eclipse.viatra.dse.base.ThreadContext;
24import org.eclipse.viatra.dse.objectives.Fitness;
25import org.eclipse.viatra.dse.objectives.ObjectiveComparatorHelper;
26import org.eclipse.viatra.dse.solutionstore.SolutionStore;
27
28import hu.bme.mit.inf.dslreasoner.logic.model.builder.LogicReasoner;
29import hu.bme.mit.inf.dslreasoner.logic.model.builder.LogicSolverConfiguration;
30import hu.bme.mit.inf.dslreasoner.logic.model.logicresult.ModelResult;
31import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretation2logic.PartialInterpretation2Logic;
32import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.partialinterpretation.PartialInterpretation;
33import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.visualisation.PartialInterpretation2Gml;
34import hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner.DiversityDescriptor;
35import 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 */
53public 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}
generated by cgit v1.2.3-54-g00ecf (git 2.45.2) at 2024-06-26 15:16:19 +0000