diff options
Diffstat (limited to 'Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl')
6 files changed, 1149 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 | } | ||
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BreadthFirstStrategy.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BreadthFirstStrategy.java new file mode 100644 index 00000000..6b7d9817 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BreadthFirstStrategy.java | |||
@@ -0,0 +1,220 @@ | |||
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.concurrent.BrokenBarrierException; | ||
14 | import java.util.concurrent.ConcurrentLinkedQueue; | ||
15 | import java.util.concurrent.CyclicBarrier; | ||
16 | import java.util.concurrent.atomic.AtomicBoolean; | ||
17 | |||
18 | import org.apache.log4j.Logger; | ||
19 | import org.eclipse.viatra.dse.api.strategy.interfaces.IStrategy; | ||
20 | import org.eclipse.viatra.dse.base.GlobalContext; | ||
21 | import org.eclipse.viatra.dse.base.ThreadContext; | ||
22 | import org.eclipse.viatra.dse.objectives.Fitness; | ||
23 | import org.eclipse.viatra.dse.solutionstore.SolutionStore; | ||
24 | |||
25 | /** | ||
26 | * A breadth-first search algorithm implementation, that | ||
27 | * <ul> | ||
28 | * <li>can work with multiple threads,</li> | ||
29 | * <li>indeterministic,</li> | ||
30 | * <li>saves all states (trajectories) as solutions that fulfill all the hard objectives,</li> | ||
31 | * <li>can have a depth limit,</li> | ||
32 | * <li>will backtrack when a model satisfies the hard objectives (after saving it as a solution) and will not explore | ||
33 | * beyond that state.</li> | ||
34 | * </ul> | ||
35 | * | ||
36 | * @author Andras Szabolcs Nagy | ||
37 | * | ||
38 | */ | ||
39 | public class BreadthFirstStrategy implements IStrategy { | ||
40 | |||
41 | private static final class BfsSharedObject { | ||
42 | private final ConcurrentLinkedQueue<Object[]> trajectoryQueue1 = new ConcurrentLinkedQueue<>(); | ||
43 | private final ConcurrentLinkedQueue<Object[]> trajectoryQueue2 = new ConcurrentLinkedQueue<>(); | ||
44 | |||
45 | private final AtomicBoolean pushToQueue1 = new AtomicBoolean(false); | ||
46 | private final AtomicBoolean designSpaceTraversed = new AtomicBoolean(false); | ||
47 | |||
48 | public final CyclicBarrier barrier; | ||
49 | |||
50 | public BfsSharedObject(int numberOfThreads) { | ||
51 | barrier = new CyclicBarrier(numberOfThreads, () -> { | ||
52 | boolean oldValue = pushToQueue1.get(); | ||
53 | pushToQueue1.set(!oldValue); | ||
54 | if (trajectoryQueue1.isEmpty() && trajectoryQueue2.isEmpty()) { | ||
55 | designSpaceTraversed.set(true); | ||
56 | } | ||
57 | }); | ||
58 | } | ||
59 | |||
60 | public Object[] poll() { | ||
61 | if (pushToQueue1.get()) { | ||
62 | return trajectoryQueue2.poll(); | ||
63 | } else { | ||
64 | return trajectoryQueue1.poll(); | ||
65 | } | ||
66 | } | ||
67 | |||
68 | public void push(Object[] trajectory) { | ||
69 | if (pushToQueue1.get()) { | ||
70 | trajectoryQueue1.add(trajectory); | ||
71 | } else { | ||
72 | trajectoryQueue2.add(trajectory); | ||
73 | } | ||
74 | } | ||
75 | |||
76 | public boolean isDesignSpaceTraversed() { | ||
77 | return designSpaceTraversed.get(); | ||
78 | } | ||
79 | } | ||
80 | |||
81 | private int maxDepth = 0; | ||
82 | private BfsSharedObject shared; | ||
83 | private boolean isInterrupted = false; | ||
84 | private ThreadContext context; | ||
85 | private Logger logger = Logger.getLogger(IStrategy.class); | ||
86 | private SolutionStore solutionStore; | ||
87 | private boolean isFirstThread = false; | ||
88 | |||
89 | /** | ||
90 | * Creates a new breadth-first search algorithm without depth limit. | ||
91 | */ | ||
92 | public BreadthFirstStrategy() { | ||
93 | this.maxDepth = Integer.MAX_VALUE; | ||
94 | } | ||
95 | |||
96 | /** | ||
97 | * Creates a new breadth-first search algorithm with depth limit. | ||
98 | * | ||
99 | * @param maxDepth | ||
100 | * A negative <code>maxDepth</code> means no depth limit, zero means the checking of the initial state. | ||
101 | */ | ||
102 | public BreadthFirstStrategy(int maxDepth) { | ||
103 | if (maxDepth < 0) { | ||
104 | this.maxDepth = Integer.MAX_VALUE; | ||
105 | } else { | ||
106 | this.maxDepth = maxDepth; | ||
107 | } | ||
108 | } | ||
109 | |||
110 | @Override | ||
111 | public void initStrategy(ThreadContext context) { | ||
112 | this.context = context; | ||
113 | this.solutionStore = context.getGlobalContext().getSolutionStore(); | ||
114 | |||
115 | GlobalContext globalContext = context.getGlobalContext(); | ||
116 | if (globalContext.getSharedObject() == null) { | ||
117 | isFirstThread = true; | ||
118 | shared = new BfsSharedObject(globalContext.getThreadPool().getMaximumPoolSize()); | ||
119 | globalContext.setSharedObject(shared); | ||
120 | logger.info("Breadth-first exploration strategy is inited."); | ||
121 | } else { | ||
122 | shared = (BfsSharedObject) globalContext.getSharedObject(); | ||
123 | } | ||
124 | } | ||
125 | |||
126 | @Override | ||
127 | public void explore() { | ||
128 | |||
129 | if (isFirstThread) { | ||
130 | |||
131 | boolean globalConstraintsAreSatisfied = context.checkGlobalConstraints(); | ||
132 | if (!globalConstraintsAreSatisfied) { | ||
133 | logger.info("Global contraint is not satisifed in the first state. Terminate."); | ||
134 | return; | ||
135 | } | ||
136 | |||
137 | Fitness fitness = context.calculateFitness(); | ||
138 | if (fitness.isSatisifiesHardObjectives()) { | ||
139 | context.newSolution(); | ||
140 | logger.info("First state is a solution. Terminate."); | ||
141 | return; | ||
142 | } | ||
143 | |||
144 | Object[] currentTrajectory = context.getTrajectory().toArray(new Object[0]); | ||
145 | |||
146 | shared.push(currentTrajectory); | ||
147 | |||
148 | startThreads(); | ||
149 | } else { | ||
150 | try { | ||
151 | shared.barrier.await(); | ||
152 | } catch (InterruptedException | BrokenBarrierException e) { | ||
153 | } | ||
154 | } | ||
155 | |||
156 | mainLoop: while (!isInterrupted && !shared.isDesignSpaceTraversed()) { | ||
157 | |||
158 | Object[] next = shared.poll(); | ||
159 | while (next == null) { | ||
160 | try { | ||
161 | logger.debug("Reached barrier."); | ||
162 | shared.barrier.await(); | ||
163 | } catch (InterruptedException | BrokenBarrierException e1) { | ||
164 | } | ||
165 | if (isInterrupted || shared.isDesignSpaceTraversed()) { | ||
166 | break mainLoop; | ||
167 | } | ||
168 | next = shared.poll(); | ||
169 | } | ||
170 | |||
171 | context.backtrackUntilRoot(); | ||
172 | |||
173 | context.executeTrajectory(next); | ||
174 | |||
175 | Collection<Object> activationIds = context.getCurrentActivationIds(); | ||
176 | int i = activationIds.size() - 1; | ||
177 | |||
178 | while (!isInterrupted && i >= 0) { | ||
179 | |||
180 | Iterator<Object> iterator = activationIds.iterator(); | ||
181 | int index = i--; | ||
182 | while (iterator.hasNext() && index > 0) { | ||
183 | index--; | ||
184 | iterator.next(); | ||
185 | } | ||
186 | Object activationIdToTry = iterator.next(); | ||
187 | |||
188 | context.executeAcitvationId(activationIdToTry); | ||
189 | |||
190 | if (context.isCurrentStateAlreadyTraversed()) { | ||
191 | logger.info("The new state is already visited."); | ||
192 | } else if (!context.checkGlobalConstraints()) { | ||
193 | logger.debug("Global contraint is not satisifed."); | ||
194 | } else if (context.calculateFitness().isSatisifiesHardObjectives()) { | ||
195 | solutionStore.newSolution(context); | ||
196 | logger.debug("Found a solution."); | ||
197 | } else if (context.getDepth() >= maxDepth) { | ||
198 | logger.debug("Reached max depth."); | ||
199 | } else { | ||
200 | Object[] currentTrajectory = context.getTrajectory().toArray(new Object[0]); | ||
201 | shared.push(currentTrajectory); | ||
202 | } | ||
203 | |||
204 | context.backtrack(); | ||
205 | } | ||
206 | |||
207 | } | ||
208 | } | ||
209 | |||
210 | private void startThreads() { | ||
211 | context.startAllThreads(() -> new BreadthFirstStrategy(maxDepth)); | ||
212 | } | ||
213 | |||
214 | @Override | ||
215 | public void interruptStrategy() { | ||
216 | isInterrupted = true; | ||
217 | shared.barrier.reset(); | ||
218 | } | ||
219 | |||
220 | } | ||
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 | } | ||
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/FixedPriorityStrategy.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/FixedPriorityStrategy.java new file mode 100644 index 00000000..4ccda4ce --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/FixedPriorityStrategy.java | |||
@@ -0,0 +1,208 @@ | |||
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.HashMap; | ||
13 | import java.util.List; | ||
14 | import java.util.Map; | ||
15 | import java.util.Random; | ||
16 | import java.util.concurrent.atomic.AtomicBoolean; | ||
17 | |||
18 | import org.apache.log4j.Logger; | ||
19 | import org.eclipse.viatra.dse.api.DSEException; | ||
20 | import org.eclipse.viatra.dse.api.strategy.interfaces.IStrategy; | ||
21 | import org.eclipse.viatra.dse.base.ThreadContext; | ||
22 | import org.eclipse.viatra.dse.objectives.Fitness; | ||
23 | import org.eclipse.viatra.transformation.runtime.emf.rules.batch.BatchTransformationRule; | ||
24 | |||
25 | import com.google.common.collect.Lists; | ||
26 | |||
27 | /** | ||
28 | * Works as {@link DepthFirstStrategy} but: | ||
29 | * <ul> | ||
30 | * <li>works only with single thread,</li> | ||
31 | * <li>in a given state, it only traverses the activations with locally the highest priority.</li> | ||
32 | * </ul> | ||
33 | * | ||
34 | * @author Andras Szabolcs Nagy | ||
35 | * | ||
36 | */ | ||
37 | public class FixedPriorityStrategy implements IStrategy { | ||
38 | |||
39 | private int maxDepth = Integer.MAX_VALUE; | ||
40 | private AtomicBoolean isInterrupted = new AtomicBoolean(false); | ||
41 | private ThreadContext context; | ||
42 | |||
43 | private Logger logger = Logger.getLogger(IStrategy.class); | ||
44 | private Map<BatchTransformationRule<?, ?>, Integer> priorities = new HashMap<BatchTransformationRule<?, ?>, Integer>(); | ||
45 | |||
46 | private Random random = new Random(); | ||
47 | private Map<Object, List<Object>> bestPriorityInState = new HashMap<>(); | ||
48 | |||
49 | /** | ||
50 | * Adds a depth limit to the strategy. | ||
51 | * | ||
52 | * @param depthLimit | ||
53 | * The depth limit. | ||
54 | * @return The actual instance to enable a builder pattern like usage. | ||
55 | */ | ||
56 | public FixedPriorityStrategy withDepthLimit(int maxDepth) { | ||
57 | if (maxDepth < 0) { | ||
58 | this.maxDepth = Integer.MAX_VALUE; | ||
59 | } else { | ||
60 | this.maxDepth = maxDepth; | ||
61 | } | ||
62 | return this; | ||
63 | } | ||
64 | |||
65 | /** | ||
66 | * Assigns a priority to a rule. Unassigned rule will have a priority of 0. | ||
67 | * | ||
68 | * @param rule | ||
69 | * The transformation rule. | ||
70 | * @param priority | ||
71 | * The priority of the rule. Higher is better. | ||
72 | * @return The actual instance to enable a builder pattern like usage. | ||
73 | */ | ||
74 | public FixedPriorityStrategy withRulePriority(BatchTransformationRule<?, ?> rule, int priority) { | ||
75 | priorities.put(rule, priority); | ||
76 | return this; | ||
77 | } | ||
78 | |||
79 | public Map<BatchTransformationRule<?, ?>, Integer> getPriorities() { | ||
80 | return priorities; | ||
81 | } | ||
82 | |||
83 | @Override | ||
84 | public void initStrategy(ThreadContext context) { | ||
85 | this.context = context; | ||
86 | |||
87 | logger.info("Fixed priority exploration strategy is initied."); | ||
88 | } | ||
89 | |||
90 | @Override | ||
91 | public void explore() { | ||
92 | |||
93 | mainloop: do { | ||
94 | |||
95 | boolean globalConstraintsAreSatisfied = context.checkGlobalConstraints(); | ||
96 | if (!globalConstraintsAreSatisfied) { | ||
97 | boolean isSuccessfulUndo = context.backtrack(); | ||
98 | if (!isSuccessfulUndo) { | ||
99 | logger.info("Global contraint is not satisifed and cannot backtrack."); | ||
100 | break; | ||
101 | } else { | ||
102 | logger.debug("Global contraint is not satisifed, backtrack."); | ||
103 | continue; | ||
104 | } | ||
105 | } | ||
106 | |||
107 | Fitness fitness = context.calculateFitness(); | ||
108 | if (fitness.isSatisifiesHardObjectives()) { | ||
109 | context.newSolution(); | ||
110 | boolean isSuccessfulUndo = context.backtrack(); | ||
111 | if (!isSuccessfulUndo) { | ||
112 | logger.info("Found a solution but cannot backtrack."); | ||
113 | break; | ||
114 | } else { | ||
115 | logger.debug("Found a solution, backtrack."); | ||
116 | continue; | ||
117 | } | ||
118 | } | ||
119 | |||
120 | if (context.getDepth() >= maxDepth) { | ||
121 | boolean isSuccessfulUndo = context.backtrack(); | ||
122 | if (!isSuccessfulUndo) { | ||
123 | logger.info("Reached max depth but cannot bactrack."); | ||
124 | break; | ||
125 | } else { | ||
126 | logger.debug("Reached max depth, bactrack."); | ||
127 | continue; | ||
128 | } | ||
129 | } | ||
130 | |||
131 | if (isInterrupted.get()) { | ||
132 | logger.info("Interrupted, stop exploration."); | ||
133 | break; | ||
134 | } | ||
135 | |||
136 | List<Object> transitions; | ||
137 | |||
138 | do { | ||
139 | |||
140 | transitions = bestPriorityInState.get(context.getCurrentStateId()); | ||
141 | |||
142 | if (transitions == null) { | ||
143 | Integer bestPriority = getBestPriority(context.getCurrentActivationIds()); | ||
144 | transitions = Lists.newArrayList(); | ||
145 | for (Object iTransition : context.getCurrentActivationIds()) { | ||
146 | Integer integer = priorities.get(context.getRuleByActivationId(iTransition)); | ||
147 | if (integer == null) { | ||
148 | integer = Integer.valueOf(0); | ||
149 | } | ||
150 | if (integer.equals(bestPriority)) { | ||
151 | transitions.add(iTransition); | ||
152 | } | ||
153 | } | ||
154 | bestPriorityInState.put(context.getCurrentStateId(), transitions); | ||
155 | } | ||
156 | |||
157 | if (transitions.isEmpty()) { | ||
158 | boolean isSuccessfulUndo = context.backtrack(); | ||
159 | if (!isSuccessfulUndo) { | ||
160 | logger.info("No more transitions from current state and cannot backtrack."); | ||
161 | break mainloop; | ||
162 | } else { | ||
163 | logger.debug("No more transitions from current state, backtrack."); | ||
164 | continue; | ||
165 | } | ||
166 | } | ||
167 | } while (transitions.isEmpty()); | ||
168 | |||
169 | int index = random.nextInt(transitions.size()); | ||
170 | Object transition = transitions.remove(index); | ||
171 | |||
172 | context.executeAcitvationId(transition); | ||
173 | |||
174 | boolean loopInTrajectory = context.isCurrentStateInTrajectory(); | ||
175 | if (loopInTrajectory) { | ||
176 | boolean isSuccessfulUndo = context.backtrack(); | ||
177 | if (!isSuccessfulUndo) { | ||
178 | throw new DSEException( | ||
179 | "The new state is present in the trajectoy but cannot bactkrack. Should never happen!"); | ||
180 | } else { | ||
181 | logger.info("The new state is already visited in the trajectory, backtrack."); | ||
182 | } | ||
183 | } | ||
184 | |||
185 | } while (true); | ||
186 | |||
187 | logger.info("Terminated."); | ||
188 | } | ||
189 | |||
190 | @Override | ||
191 | public void interruptStrategy() { | ||
192 | isInterrupted.set(true); | ||
193 | } | ||
194 | |||
195 | private Integer getBestPriority(Collection<? extends Object> transitions) { | ||
196 | Integer bestPriority = Integer.MIN_VALUE; | ||
197 | for (Object iTransition : transitions) { | ||
198 | Integer priority = priorities.get(context.getRuleByActivationId(iTransition)); | ||
199 | if (priority == null) { | ||
200 | priority = Integer.valueOf(0); | ||
201 | } | ||
202 | if (priority > bestPriority) { | ||
203 | bestPriority = priority; | ||
204 | } | ||
205 | } | ||
206 | return bestPriority; | ||
207 | } | ||
208 | } | ||
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/HillClimbingStrategy.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/HillClimbingStrategy.java new file mode 100644 index 00000000..0ccb0668 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/HillClimbingStrategy.java | |||
@@ -0,0 +1,142 @@ | |||
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.ArrayList; | ||
12 | import java.util.Collection; | ||
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.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.objectives.TrajectoryFitness; | ||
22 | |||
23 | public class HillClimbingStrategy implements IStrategy { | ||
24 | |||
25 | private AtomicBoolean isInterrupted = new AtomicBoolean(false); | ||
26 | private ThreadContext context; | ||
27 | |||
28 | private Logger logger = Logger.getLogger(IStrategy.class); | ||
29 | |||
30 | private Random random = new Random(); | ||
31 | private double percentOfOpenedStates; | ||
32 | private ObjectiveComparatorHelper objectiveComparatorHelper; | ||
33 | |||
34 | public HillClimbingStrategy() { | ||
35 | this(2); | ||
36 | } | ||
37 | |||
38 | public HillClimbingStrategy(double percentOfOpenedStates) { | ||
39 | this.percentOfOpenedStates = percentOfOpenedStates; | ||
40 | } | ||
41 | |||
42 | @Override | ||
43 | public void initStrategy(ThreadContext context) { | ||
44 | this.context = context; | ||
45 | objectiveComparatorHelper = context.getObjectiveComparatorHelper(); | ||
46 | logger.info("Hill climbing exploration strategy is initied."); | ||
47 | } | ||
48 | |||
49 | @Override | ||
50 | public void explore() { | ||
51 | |||
52 | boolean globalConstraintsAreSatisfied = context.checkGlobalConstraints(); | ||
53 | if (!globalConstraintsAreSatisfied) { | ||
54 | boolean isSuccessfulUndo = context.backtrack(); | ||
55 | if (!isSuccessfulUndo) { | ||
56 | logger.info("Global contraint is not satisifed and cannot backtrack."); | ||
57 | return; | ||
58 | } | ||
59 | } | ||
60 | |||
61 | mainloop: do { | ||
62 | |||
63 | Fitness previousFitness = context.calculateFitness(); | ||
64 | |||
65 | logger.debug("Current depth: " + context.getDepth() + " Fitness: " + previousFitness); | ||
66 | |||
67 | Collection<Object> transitionsFromCurrentState = context.getCurrentActivationIds(); | ||
68 | |||
69 | while (transitionsFromCurrentState.isEmpty()) { | ||
70 | logger.debug("No transitions from current state: considered as a solution."); | ||
71 | saveSolutionAndBacktrack(); | ||
72 | continue mainloop; | ||
73 | } | ||
74 | |||
75 | ArrayList<Object> transitionsToTry = new ArrayList<>(transitionsFromCurrentState.size()); | ||
76 | for (Object transition : transitionsFromCurrentState) { | ||
77 | transitionsToTry.add(transition); | ||
78 | } | ||
79 | double numberOfTransitionsToTry = transitionsToTry.size() * percentOfOpenedStates; | ||
80 | |||
81 | for (; numberOfTransitionsToTry > 0 && !transitionsToTry.isEmpty(); numberOfTransitionsToTry--) { | ||
82 | int index = random.nextInt(transitionsToTry.size()); | ||
83 | Object transition = transitionsToTry.remove(index); | ||
84 | |||
85 | context.executeAcitvationId(transition); | ||
86 | |||
87 | if (!context.checkGlobalConstraints()) { | ||
88 | logger.debug("Global contraint is not satisifed, backtrack."); | ||
89 | context.backtrack(); | ||
90 | continue; | ||
91 | } | ||
92 | if (context.isCurrentStateInTrajectory()) { | ||
93 | logger.debug("Current state is in trajectory, backtrack."); | ||
94 | context.backtrack(); | ||
95 | continue; | ||
96 | } | ||
97 | |||
98 | Fitness fitness = context.calculateFitness(); | ||
99 | objectiveComparatorHelper.addTrajectoryFitness( | ||
100 | new TrajectoryFitness(context.getTrajectoryInfo().getLastActivationId(), fitness)); | ||
101 | context.backtrack(); | ||
102 | } | ||
103 | |||
104 | if (objectiveComparatorHelper.getTrajectoryFitnesses().isEmpty()) { | ||
105 | logger.debug("No viable transitions from current state: considered as a solution."); | ||
106 | saveSolutionAndBacktrack(); | ||
107 | continue; | ||
108 | } | ||
109 | |||
110 | TrajectoryFitness randomBestFitness = objectiveComparatorHelper.getRandomBest(); | ||
111 | objectiveComparatorHelper.clearTrajectoryFitnesses(); | ||
112 | |||
113 | int compare = objectiveComparatorHelper.compare(previousFitness, randomBestFitness.fitness); | ||
114 | |||
115 | if (compare > 0) { | ||
116 | saveSolutionAndBacktrack(); | ||
117 | continue; | ||
118 | } else { | ||
119 | previousFitness = randomBestFitness.fitness; | ||
120 | Object transition = randomBestFitness.trajectory[randomBestFitness.trajectory.length - 1]; | ||
121 | context.executeAcitvationId(transition); | ||
122 | } | ||
123 | |||
124 | } while (!isInterrupted.get()); | ||
125 | |||
126 | logger.info("Terminated."); | ||
127 | } | ||
128 | |||
129 | private void saveSolutionAndBacktrack() { | ||
130 | context.calculateFitness(); | ||
131 | context.newSolution(); | ||
132 | logger.debug("Found solution: " + context.getTrajectoryInfo().toString()); | ||
133 | logger.debug("Backtrack for more solutions, if needed."); | ||
134 | context.backtrackUntilRoot(); | ||
135 | } | ||
136 | |||
137 | @Override | ||
138 | public void interruptStrategy() { | ||
139 | isInterrupted.set(true); | ||
140 | } | ||
141 | |||
142 | } | ||
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/RandomSearchStrategy.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/RandomSearchStrategy.java new file mode 100644 index 00000000..af8fb8cc --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/RandomSearchStrategy.java | |||
@@ -0,0 +1,163 @@ | |||
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 | import java.util.concurrent.atomic.AtomicInteger; | ||
16 | |||
17 | import org.apache.log4j.Logger; | ||
18 | import org.eclipse.viatra.dse.api.DSEException; | ||
19 | import org.eclipse.viatra.dse.api.strategy.interfaces.IStrategy; | ||
20 | import org.eclipse.viatra.dse.base.GlobalContext; | ||
21 | import org.eclipse.viatra.dse.base.ThreadContext; | ||
22 | import org.eclipse.viatra.dse.designspace.api.TrajectoryInfo; | ||
23 | import org.eclipse.viatra.dse.objectives.Fitness; | ||
24 | |||
25 | public class RandomSearchStrategy implements IStrategy { | ||
26 | |||
27 | private static class SharedData { | ||
28 | public final AtomicInteger triesLeft; | ||
29 | public final int minDepth; | ||
30 | public final int maxDepth; | ||
31 | |||
32 | public SharedData(int minDepth, int maxDepth, int numberOfTries) { | ||
33 | this.minDepth = minDepth; | ||
34 | this.maxDepth = maxDepth; | ||
35 | this.triesLeft = new AtomicInteger(numberOfTries); | ||
36 | } | ||
37 | } | ||
38 | |||
39 | private int maxDepth = -1; | ||
40 | private Random rnd = new Random(); | ||
41 | private SharedData shared; | ||
42 | private TrajectoryInfo trajectoryInfo; | ||
43 | int nth; | ||
44 | private ThreadContext context; | ||
45 | private AtomicBoolean isInterrupted = new AtomicBoolean(false); | ||
46 | private Logger logger = Logger.getLogger(IStrategy.class); | ||
47 | |||
48 | public RandomSearchStrategy(int minDepth, int maxDepth, int numberOfTries) { | ||
49 | shared = new SharedData(minDepth, maxDepth, numberOfTries); | ||
50 | } | ||
51 | |||
52 | private RandomSearchStrategy() { | ||
53 | } | ||
54 | |||
55 | @Override | ||
56 | public void initStrategy(ThreadContext context) { | ||
57 | this.context = context; | ||
58 | trajectoryInfo = context.getTrajectoryInfo(); | ||
59 | GlobalContext gc = context.getGlobalContext(); | ||
60 | |||
61 | Object sharedObject = gc.getSharedObject(); | ||
62 | if (sharedObject == null) { | ||
63 | gc.setSharedObject(shared); | ||
64 | logger.info("Random exploration strategy is initied."); | ||
65 | startThreads(); | ||
66 | } else { | ||
67 | shared = (SharedData) sharedObject; | ||
68 | } | ||
69 | |||
70 | maxDepth = rnd.nextInt(shared.maxDepth - shared.minDepth) + shared.minDepth; | ||
71 | |||
72 | } | ||
73 | |||
74 | @Override | ||
75 | public void explore() { | ||
76 | |||
77 | do { | ||
78 | |||
79 | boolean globalConstraintsAreSatisfied = context.checkGlobalConstraints(); | ||
80 | if (!globalConstraintsAreSatisfied) { | ||
81 | boolean isSuccessfulUndo = context.backtrack(); | ||
82 | if (!isSuccessfulUndo) { | ||
83 | logger.info("Global contraint is not satisifed and cannot backtrack."); | ||
84 | break; | ||
85 | } else { | ||
86 | logger.debug("Global contraint is not satisifed, backtrack."); | ||
87 | continue; | ||
88 | } | ||
89 | } | ||
90 | |||
91 | Fitness fitness = context.calculateFitness(); | ||
92 | if (fitness.isSatisifiesHardObjectives()) { | ||
93 | context.newSolution(); | ||
94 | boolean isSuccessfulUndo = context.backtrack(); | ||
95 | if (!isSuccessfulUndo) { | ||
96 | logger.info("Found a solution but cannot backtrack."); | ||
97 | break; | ||
98 | } else { | ||
99 | logger.debug("Found a solution, backtrack."); | ||
100 | continue; | ||
101 | } | ||
102 | } | ||
103 | |||
104 | if (trajectoryInfo.getDepth() < maxDepth) { | ||
105 | |||
106 | Collection<Object> transitions = context.getCurrentActivationIds(); | ||
107 | int index = rnd.nextInt(transitions.size()); | ||
108 | Object transition = getByIndex(transitions, index); | ||
109 | context.executeAcitvationId(transition); | ||
110 | |||
111 | } else { | ||
112 | |||
113 | nth = shared.triesLeft.getAndDecrement(); | ||
114 | logger.debug(nth + " tries left"); | ||
115 | if (nth > 0) { | ||
116 | |||
117 | context.backtrackUntilRoot(); | ||
118 | maxDepth = rnd.nextInt(shared.maxDepth - shared.minDepth) + shared.minDepth; | ||
119 | |||
120 | } else { | ||
121 | break; | ||
122 | } | ||
123 | } | ||
124 | |||
125 | boolean loopInTrajectory = context.isCurrentStateInTrajectory(); | ||
126 | if (loopInTrajectory) { | ||
127 | boolean isSuccessfulUndo = context.backtrack(); | ||
128 | if (!isSuccessfulUndo) { | ||
129 | throw new DSEException( | ||
130 | "The new state is present in the trajectoy but cannot bactkrack. Should never happen!"); | ||
131 | } else { | ||
132 | logger.info("The new state is already visited in the trajectory, backtrack."); | ||
133 | } | ||
134 | } | ||
135 | |||
136 | } while (isInterrupted.get()); | ||
137 | |||
138 | logger.info("Terminated."); | ||
139 | } | ||
140 | |||
141 | @Override | ||
142 | public void interruptStrategy() { | ||
143 | isInterrupted.set(true); | ||
144 | } | ||
145 | |||
146 | private void startThreads() { | ||
147 | context.startAllThreads(RandomSearchStrategy::new); | ||
148 | } | ||
149 | |||
150 | private static Object getByIndex(Collection<Object> availableTransitions, int index) { | ||
151 | int i = 0; | ||
152 | Iterator<Object> iterator = availableTransitions.iterator(); | ||
153 | while (iterator.hasNext()) { | ||
154 | Object transition = iterator.next(); | ||
155 | if (i == index) { | ||
156 | return transition; | ||
157 | } else { | ||
158 | ++i; | ||
159 | } | ||
160 | } | ||
161 | throw new IndexOutOfBoundsException("size: " + availableTransitions.size() + ", index: " + index); | ||
162 | } | ||
163 | } | ||