diff options
Diffstat (limited to 'Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/DepthFirstStrategy.java')
-rw-r--r-- | Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/DepthFirstStrategy.java | 188 |
1 files changed, 188 insertions, 0 deletions
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/DepthFirstStrategy.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/DepthFirstStrategy.java new file mode 100644 index 00000000..22a4a683 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/DepthFirstStrategy.java | |||
@@ -0,0 +1,188 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2016, Andras Szabolcs Nagy, 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 org.eclipse.viatra.dse.api.strategy.impl; | ||
10 | |||
11 | import java.util.Collection; | ||
12 | import java.util.Iterator; | ||
13 | import java.util.Random; | ||
14 | import java.util.concurrent.atomic.AtomicBoolean; | ||
15 | |||
16 | import org.apache.log4j.Logger; | ||
17 | import org.eclipse.viatra.dse.api.DSEException; | ||
18 | import org.eclipse.viatra.dse.api.strategy.interfaces.IStrategy; | ||
19 | import org.eclipse.viatra.dse.base.ThreadContext; | ||
20 | import org.eclipse.viatra.dse.objectives.Fitness; | ||
21 | |||
22 | /** | ||
23 | * A depth-first search algorithm implementation, that | ||
24 | * <ul> | ||
25 | * <li>can work with multiple threads,</li> | ||
26 | * <li>randomly traverses the search space,</li> | ||
27 | * <li>saves all states (trajectories) as solutions that fulfill all the hard objectives,</li> | ||
28 | * <li>can have a depth limit,</li> | ||
29 | * <li>will backtrack when a model satisfies the hard objectives (after saving it as a solution), which can be modified | ||
30 | * by calling {@link #continueIfHardObjectivesFulfilled()}</li> | ||
31 | * </ul> | ||
32 | * | ||
33 | * @author Andras Szabolcs Nagy | ||
34 | * | ||
35 | */ | ||
36 | public class DepthFirstStrategy implements IStrategy { | ||
37 | |||
38 | private int maxDepth; | ||
39 | private AtomicBoolean isInterrupted = new AtomicBoolean(false); | ||
40 | private ThreadContext context; | ||
41 | |||
42 | private Logger logger = Logger.getLogger(IStrategy.class); | ||
43 | |||
44 | private Random random = new Random(); | ||
45 | private boolean backTrackIfSolution = true; | ||
46 | |||
47 | /** | ||
48 | * Creates a new depth-first search algorithm without depth limit. | ||
49 | */ | ||
50 | public DepthFirstStrategy() { | ||
51 | this.maxDepth = Integer.MAX_VALUE; | ||
52 | } | ||
53 | |||
54 | /** | ||
55 | * Creates a new depth-first search algorithm with depth limit. | ||
56 | * | ||
57 | * @param maxDepth | ||
58 | * A negative <code>maxDepth</code> means no depth limit, zero means the checking of the initial state. | ||
59 | */ | ||
60 | public DepthFirstStrategy(int maxDepth) { | ||
61 | if (maxDepth < 0) { | ||
62 | this.maxDepth = Integer.MAX_VALUE; | ||
63 | } else { | ||
64 | this.maxDepth = maxDepth; | ||
65 | } | ||
66 | } | ||
67 | |||
68 | /** | ||
69 | * If called, the algorithm will not backtrack after the hard objectives are fulfilled, instead it goes deeper in | ||
70 | * the search space. | ||
71 | */ | ||
72 | public DepthFirstStrategy continueIfHardObjectivesFulfilled() { | ||
73 | backTrackIfSolution = false; | ||
74 | return this; | ||
75 | } | ||
76 | |||
77 | @Override | ||
78 | public void initStrategy(ThreadContext context) { | ||
79 | this.context = context; | ||
80 | |||
81 | if (context.getSharedObject() == null) { | ||
82 | context.setSharedObject(new Object()); | ||
83 | logger.info("Depth-first exploration strategy is initied."); | ||
84 | startThreads(); | ||
85 | } | ||
86 | |||
87 | } | ||
88 | |||
89 | private void startThreads() { | ||
90 | context.startAllThreads(() -> new DepthFirstStrategy(maxDepth)); | ||
91 | } | ||
92 | |||
93 | @Override | ||
94 | public void explore() { | ||
95 | |||
96 | mainloop: do { | ||
97 | |||
98 | boolean globalConstraintsAreSatisfied = context.checkGlobalConstraints(); | ||
99 | if (!globalConstraintsAreSatisfied) { | ||
100 | boolean isSuccessfulUndo = context.backtrack(); | ||
101 | if (!isSuccessfulUndo) { | ||
102 | logger.info("Global contraint is not satisifed and cannot backtrack."); | ||
103 | break; | ||
104 | } else { | ||
105 | logger.debug("Global contraint is not satisifed, backtrack."); | ||
106 | continue; | ||
107 | } | ||
108 | } | ||
109 | |||
110 | Fitness fitness = context.calculateFitness(); | ||
111 | if (fitness.isSatisifiesHardObjectives()) { | ||
112 | context.newSolution(); | ||
113 | if (backTrackIfSolution) { | ||
114 | boolean isSuccessfulUndo = context.backtrack(); | ||
115 | if (!isSuccessfulUndo) { | ||
116 | logger.info("Found a solution but cannot backtrack."); | ||
117 | break; | ||
118 | } else { | ||
119 | logger.debug("Found a solution, backtrack."); | ||
120 | continue; | ||
121 | } | ||
122 | } | ||
123 | } | ||
124 | |||
125 | if (context.getDepth() >= maxDepth) { | ||
126 | boolean isSuccessfulUndo = context.backtrack(); | ||
127 | if (!isSuccessfulUndo) { | ||
128 | logger.info("Reached max depth but cannot bactrack."); | ||
129 | break; | ||
130 | } else { | ||
131 | logger.debug("Reached max depth, bactrack."); | ||
132 | continue; | ||
133 | } | ||
134 | } | ||
135 | |||
136 | if (isInterrupted.get()) { | ||
137 | logger.info("Interrupted, stop exploration."); | ||
138 | break; | ||
139 | } | ||
140 | |||
141 | Object activationId = null; | ||
142 | Collection<Object> activationIds; | ||
143 | |||
144 | do { | ||
145 | activationIds = context.getUntraversedActivationIds(); | ||
146 | if (activationIds.isEmpty()) { | ||
147 | boolean isSuccessfulUndo = context.backtrack(); | ||
148 | if (!isSuccessfulUndo) { | ||
149 | logger.info("No more transitions from current state and cannot backtrack."); | ||
150 | break mainloop; | ||
151 | } else { | ||
152 | logger.debug("No more transitions from current state, backtrack."); | ||
153 | continue; | ||
154 | } | ||
155 | } | ||
156 | } while (activationIds.isEmpty()); | ||
157 | |||
158 | int index = random.nextInt(activationIds.size()); | ||
159 | |||
160 | Iterator<Object> iterator = activationIds.iterator(); | ||
161 | while (index-- > 0) { | ||
162 | iterator.next(); | ||
163 | } | ||
164 | activationId = iterator.next(); | ||
165 | |||
166 | context.executeAcitvationId(activationId); | ||
167 | |||
168 | boolean loopInTrajectory = context.isCurrentStateInTrajectory(); | ||
169 | if (loopInTrajectory) { | ||
170 | boolean isSuccessfulUndo = context.backtrack(); | ||
171 | if (!isSuccessfulUndo) { | ||
172 | throw new DSEException("The new state is present in the trajectoy but cannot bactkrack. Should never happen!"); | ||
173 | } else { | ||
174 | logger.info("The new state is already visited in the trajectory, backtrack."); | ||
175 | } | ||
176 | } | ||
177 | |||
178 | } while (true); | ||
179 | |||
180 | logger.info("Terminated."); | ||
181 | } | ||
182 | |||
183 | @Override | ||
184 | public void interruptStrategy() { | ||
185 | isInterrupted.set(true); | ||
186 | } | ||
187 | |||
188 | } | ||