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