diff options
Diffstat (limited to 'Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/RandomSearchStrategy.java')
-rw-r--r-- | Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/RandomSearchStrategy.java | 163 |
1 files changed, 163 insertions, 0 deletions
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 | } | ||