diff options
Diffstat (limited to 'Solvers')
3 files changed, 520 insertions, 19 deletions
diff --git a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/ViatraReasoner.xtend b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/ViatraReasoner.xtend index 92aefb56..ad276bb4 100644 --- a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/ViatraReasoner.xtend +++ b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/ViatraReasoner.xtend | |||
@@ -33,6 +33,7 @@ import org.eclipse.viatra.dse.api.DesignSpaceExplorer | |||
33 | import org.eclipse.viatra.dse.api.DesignSpaceExplorer.DseLoggingLevel | 33 | import org.eclipse.viatra.dse.api.DesignSpaceExplorer.DseLoggingLevel |
34 | import org.eclipse.viatra.dse.solutionstore.SolutionStore | 34 | import org.eclipse.viatra.dse.solutionstore.SolutionStore |
35 | import org.eclipse.viatra.dse.statecode.IStateCoderFactory | 35 | import org.eclipse.viatra.dse.statecode.IStateCoderFactory |
36 | import hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner.dse.HillClimbingOnRealisticMetricStrategyForModelGeneration | ||
36 | 37 | ||
37 | class ViatraReasoner extends LogicReasoner{ | 38 | class ViatraReasoner extends LogicReasoner{ |
38 | val PartialInterpretationInitialiser initialiser = new PartialInterpretationInitialiser() | 39 | val PartialInterpretationInitialiser initialiser = new PartialInterpretationInitialiser() |
@@ -112,7 +113,7 @@ class ViatraReasoner extends LogicReasoner{ | |||
112 | dse.addTransformationRule(rule) | 113 | dse.addTransformationRule(rule) |
113 | } | 114 | } |
114 | 115 | ||
115 | val strategy = new BestFirstStrategyForModelGeneration(workspace,viatraConfig,method) | 116 | val strategy = new HillClimbingOnRealisticMetricStrategyForModelGeneration(workspace,viatraConfig,method) |
116 | viatraConfig.progressMonitor.workedForwardTransformation | 117 | viatraConfig.progressMonitor.workedForwardTransformation |
117 | 118 | ||
118 | val transformationTime = System.nanoTime - transformationStartTime | 119 | val transformationTime = System.nanoTime - transformationStartTime |
@@ -133,7 +134,7 @@ class ViatraReasoner extends LogicReasoner{ | |||
133 | //find trajectory to each solution | 134 | //find trajectory to each solution |
134 | if(viatraConfig.documentationLevel == DocumentationLevel.NONE){ | 135 | if(viatraConfig.documentationLevel == DocumentationLevel.NONE){ |
135 | PartialInterpretationMetric.initPaths(); | 136 | PartialInterpretationMetric.initPaths(); |
136 | PartialInterpretationMetric.outputTrajectories(emptySolutionCopy, dse.solutions.toList()); | 137 | //PartialInterpretationMetric.outputTrajectories(emptySolutionCopy, dse.solutions.toList()); |
137 | } | 138 | } |
138 | 139 | ||
139 | //additionalMatches = strategy.solutionStoreWithCopy.additionalMatches | 140 | //additionalMatches = strategy.solutionStoreWithCopy.additionalMatches |
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 index 81b551fb..71178f3d 100644 --- 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 | |||
@@ -191,24 +191,9 @@ public class BestFirstStrategyForModelGeneration implements IStrategy { | |||
191 | // continue mainLoop; | 191 | // continue mainLoop; |
192 | // } | 192 | // } |
193 | 193 | ||
194 | List<Object> activationIds = selectActivation(); | ||
195 | PartialInterpretation model = (PartialInterpretation) context.getModel(); | ||
196 | System.out.println(model.getNewElements().size() ); | ||
197 | PartialInterpretationMetric.initPaths(); | ||
198 | if(model.getNewElements().size() >= 10) { | ||
199 | Map<Object, Double> valueMap = new HashMap<Object, Double>(); | ||
200 | System.out.println(PartialInterpretationMetric.calculateMetricDistance(model).getMPCDistance()); | ||
201 | for(Object id : activationIds) { | ||
202 | context.executeAcitvationId(id); | ||
203 | model = (PartialInterpretation) context.getModel(); | ||
204 | MetricDistanceGroup g = PartialInterpretationMetric.calculateMetricDistance(model); | ||
205 | valueMap.put(id, g.getMPCDistance()); | ||
206 | context.backtrack(); | ||
207 | } | ||
208 | Collections.sort(activationIds, Comparator.comparing(li -> valueMap.get(li))); | ||
209 | } | ||
210 | 194 | ||
211 | 195 | ||
196 | List<Object> activationIds = selectActivation(); | ||
212 | Iterator<Object> iterator = activationIds.iterator(); | 197 | Iterator<Object> iterator = activationIds.iterator(); |
213 | 198 | ||
214 | while (!isInterrupted && !configuration.progressMonitor.isCancelled() && iterator.hasNext()) { | 199 | while (!isInterrupted && !configuration.progressMonitor.isCancelled() && iterator.hasNext()) { |
@@ -219,7 +204,6 @@ public class BestFirstStrategyForModelGeneration implements IStrategy { | |||
219 | // } | 204 | // } |
220 | logger.debug("Executing new activation: " + nextActivation); | 205 | logger.debug("Executing new activation: " + nextActivation); |
221 | context.executeAcitvationId(nextActivation); | 206 | context.executeAcitvationId(nextActivation); |
222 | |||
223 | visualiseCurrentState(); | 207 | visualiseCurrentState(); |
224 | // for(ViatraQueryMatcher<? extends IPatternMatch> matcher : matchers) { | 208 | // for(ViatraQueryMatcher<? extends IPatternMatch> matcher : matchers) { |
225 | // System.out.println(matcher.getPatternName()); | 209 | // System.out.println(matcher.getPatternName()); |
diff --git a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/HillClimbingOnRealisticMetricStrategyForModelGeneration.java b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/HillClimbingOnRealisticMetricStrategyForModelGeneration.java new file mode 100644 index 00000000..148cb243 --- /dev/null +++ b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/HillClimbingOnRealisticMetricStrategyForModelGeneration.java | |||
@@ -0,0 +1,516 @@ | |||
1 | package hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner.dse; | ||
2 | |||
3 | import java.util.ArrayList; | ||
4 | import java.util.Arrays; | ||
5 | import java.util.Collection; | ||
6 | import java.util.Collections; | ||
7 | import java.util.Comparator; | ||
8 | import java.util.HashMap; | ||
9 | import java.util.Iterator; | ||
10 | import java.util.LinkedList; | ||
11 | import java.util.List; | ||
12 | import java.util.Map; | ||
13 | import java.util.PriorityQueue; | ||
14 | import java.util.Random; | ||
15 | |||
16 | import org.apache.log4j.Logger; | ||
17 | import org.eclipse.emf.ecore.util.EcoreUtil; | ||
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 | import org.eclipse.viatra.dse.objectives.ObjectiveComparatorHelper; | ||
22 | import org.eclipse.viatra.dse.solutionstore.SolutionStore; | ||
23 | import org.eclipse.viatra.query.runtime.api.IPatternMatch; | ||
24 | import org.eclipse.viatra.query.runtime.api.ViatraQueryEngine; | ||
25 | import org.eclipse.viatra.query.runtime.api.ViatraQueryMatcher; | ||
26 | |||
27 | import ca.mcgill.ecse.dslreasoner.realistic.metrics.calculator.app.MetricDistanceGroup; | ||
28 | import ca.mcgill.ecse.dslreasoner.realistic.metrics.calculator.app.PartialInterpretationMetric; | ||
29 | import hu.bme.mit.inf.dslreasoner.logic.model.builder.DocumentationLevel; | ||
30 | import hu.bme.mit.inf.dslreasoner.logic.model.builder.LogicReasoner; | ||
31 | import hu.bme.mit.inf.dslreasoner.logic.model.logicproblem.LogicProblem; | ||
32 | import hu.bme.mit.inf.dslreasoner.logic.model.logicresult.InconsistencyResult; | ||
33 | import hu.bme.mit.inf.dslreasoner.logic.model.logicresult.LogicResult; | ||
34 | import hu.bme.mit.inf.dslreasoner.logic.model.logicresult.ModelResult; | ||
35 | import hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra.ModelGenerationMethod; | ||
36 | import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretation2logic.PartialInterpretation2Logic; | ||
37 | import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.partialinterpretation.PartialInterpretation; | ||
38 | import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.visualisation.PartialInterpretationVisualisation; | ||
39 | import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.visualisation.PartialInterpretationVisualiser; | ||
40 | import hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner.ViatraReasonerConfiguration; | ||
41 | import hu.bme.mit.inf.dslreasoner.workspace.ReasonerWorkspace; | ||
42 | |||
43 | public class HillClimbingOnRealisticMetricStrategyForModelGeneration implements IStrategy { | ||
44 | // Services and Configuration | ||
45 | private ThreadContext context; | ||
46 | private ReasonerWorkspace workspace; | ||
47 | private ViatraReasonerConfiguration configuration; | ||
48 | private ModelGenerationMethod method; | ||
49 | private PartialInterpretation2Logic partialInterpretation2Logic = new PartialInterpretation2Logic(); | ||
50 | private Comparator<TrajectoryWithFitness> comparator; | ||
51 | private Logger logger = Logger.getLogger(IStrategy.class); | ||
52 | |||
53 | // Running | ||
54 | private PriorityQueue<TrajectoryWithFitness> trajectoiresToExplore; | ||
55 | private SolutionStore solutionStore; | ||
56 | private SolutionStoreWithCopy solutionStoreWithCopy; | ||
57 | private SolutionStoreWithDiversityDescriptor solutionStoreWithDiversityDescriptor; | ||
58 | private volatile boolean isInterrupted = false; | ||
59 | private ModelResult modelResultByInternalSolver = null; | ||
60 | private Random random = new Random(); | ||
61 | private Collection<ViatraQueryMatcher<? extends IPatternMatch>> mustMatchers; | ||
62 | private Collection<ViatraQueryMatcher<? extends IPatternMatch>> mayMatchers; | ||
63 | private Map<Object, List<Object>> stateAndActivations; | ||
64 | private Map<TrajectoryWithFitness, Double> trajectoryFit; | ||
65 | |||
66 | // Statistics | ||
67 | private int numberOfStatecoderFail = 0; | ||
68 | private int numberOfPrintedModel = 0; | ||
69 | private int numberOfSolverCalls = 0; | ||
70 | |||
71 | public HillClimbingOnRealisticMetricStrategyForModelGeneration( | ||
72 | ReasonerWorkspace workspace, | ||
73 | ViatraReasonerConfiguration configuration, | ||
74 | ModelGenerationMethod method) | ||
75 | { | ||
76 | this.workspace = workspace; | ||
77 | this.configuration = configuration; | ||
78 | this.method = method; | ||
79 | } | ||
80 | |||
81 | public SolutionStoreWithCopy getSolutionStoreWithCopy() { | ||
82 | return solutionStoreWithCopy; | ||
83 | } | ||
84 | public SolutionStoreWithDiversityDescriptor getSolutionStoreWithDiversityDescriptor() { | ||
85 | return solutionStoreWithDiversityDescriptor; | ||
86 | } | ||
87 | public int getNumberOfStatecoderFail() { | ||
88 | return numberOfStatecoderFail; | ||
89 | } | ||
90 | |||
91 | @Override | ||
92 | public void initStrategy(ThreadContext context) { | ||
93 | this.context = context; | ||
94 | this.solutionStore = context.getGlobalContext().getSolutionStore(); | ||
95 | |||
96 | ViatraQueryEngine engine = context.getQueryEngine(); | ||
97 | // // TODO: visualisation | ||
98 | mustMatchers = new LinkedList<ViatraQueryMatcher<? extends IPatternMatch>>(); | ||
99 | mayMatchers = new LinkedList<ViatraQueryMatcher<? extends IPatternMatch>>(); | ||
100 | |||
101 | this.method.getInvalidWF().forEach(a ->{ | ||
102 | ViatraQueryMatcher<? extends IPatternMatch> matcher = a.getMatcher(engine); | ||
103 | mustMatchers.add(matcher); | ||
104 | }); | ||
105 | |||
106 | this.method.getUnfinishedWF().forEach(a ->{ | ||
107 | ViatraQueryMatcher<? extends IPatternMatch> matcher = a.getMatcher(engine); | ||
108 | mayMatchers.add(matcher); | ||
109 | }); | ||
110 | |||
111 | |||
112 | this.solutionStoreWithCopy = new SolutionStoreWithCopy(); | ||
113 | this.solutionStoreWithDiversityDescriptor = new SolutionStoreWithDiversityDescriptor(configuration.diversityRequirement); | ||
114 | |||
115 | final ObjectiveComparatorHelper objectiveComparatorHelper = context.getObjectiveComparatorHelper(); | ||
116 | trajectoryFit = new HashMap<TrajectoryWithFitness, Double>(); | ||
117 | |||
118 | this.comparator = new Comparator<TrajectoryWithFitness>() { | ||
119 | @Override | ||
120 | public int compare(TrajectoryWithFitness o1, TrajectoryWithFitness o2) { | ||
121 | return Double.compare(trajectoryFit.get(o1), trajectoryFit.get(o2)); | ||
122 | } | ||
123 | }; | ||
124 | |||
125 | trajectoiresToExplore = new PriorityQueue<TrajectoryWithFitness>(11, comparator); | ||
126 | stateAndActivations = new HashMap<Object, List<Object>>(); | ||
127 | } | ||
128 | |||
129 | @Override | ||
130 | public void explore() { | ||
131 | if (!context.checkGlobalConstraints()) { | ||
132 | logger.info("Global contraint is not satisifed in the first state. Terminate."); | ||
133 | return; | ||
134 | } | ||
135 | if (configuration.searchSpaceConstraints.maxDepth == 0) { | ||
136 | logger.info("Maximal depth is reached in the initial solution. Terminate."); | ||
137 | return; | ||
138 | } | ||
139 | |||
140 | final Fitness firstFittness = context.calculateFitness(); | ||
141 | //checkForSolution(firstFittness); | ||
142 | |||
143 | final ObjectiveComparatorHelper objectiveComparatorHelper = context.getObjectiveComparatorHelper(); | ||
144 | final Object[] firstTrajectory = context.getTrajectory().toArray(new Object[0]); | ||
145 | TrajectoryWithFitness currentTrajectoryWithFittness = new TrajectoryWithFitness(firstTrajectory, firstFittness); | ||
146 | trajectoryFit.put(currentTrajectoryWithFittness, Double.MAX_VALUE); | ||
147 | trajectoiresToExplore.add(currentTrajectoryWithFittness); | ||
148 | |||
149 | //if(configuration) | ||
150 | visualiseCurrentState(); | ||
151 | |||
152 | PartialInterpretationMetric.initPaths(); | ||
153 | //create matcher | ||
154 | int count = 0; | ||
155 | mainLoop: while (!isInterrupted && !configuration.progressMonitor.isCancelled()) { | ||
156 | |||
157 | if (currentTrajectoryWithFittness == null) { | ||
158 | if (trajectoiresToExplore.isEmpty()) { | ||
159 | logger.debug("State space is fully traversed."); | ||
160 | return; | ||
161 | } else { | ||
162 | currentTrajectoryWithFittness = selectState(); | ||
163 | if (logger.isDebugEnabled()) { | ||
164 | logger.debug("Current trajectory: " + Arrays.toString(context.getTrajectory().toArray())); | ||
165 | logger.debug("New trajectory is chosen: " + currentTrajectoryWithFittness); | ||
166 | } | ||
167 | context.getDesignSpaceManager().executeTrajectoryWithMinimalBacktrackWithoutStateCoding(currentTrajectoryWithFittness.trajectory); | ||
168 | } | ||
169 | } | ||
170 | |||
171 | List<Object> activationIds = selectActivation(); | ||
172 | PartialInterpretation model = (PartialInterpretation) context.getModel(); | ||
173 | System.out.println(model.getNewElements().size()); | ||
174 | System.out.println("# violations: " + getNumberOfViolations(mayMatchers)); | ||
175 | |||
176 | Map<Object, Double> valueMap = new HashMap<Object,Double>(); | ||
177 | |||
178 | //init epsilon and draw | ||
179 | double epsilon = 0; | ||
180 | double draw = 1; | ||
181 | MetricDistanceGroup heuristics = PartialInterpretationMetric.calculateMetricDistanceKS(model); | ||
182 | |||
183 | if(!stateAndActivations.containsKey(model)) { | ||
184 | stateAndActivations.put(model, new ArrayList<Object>()); | ||
185 | } | ||
186 | |||
187 | //Output intermediate model | ||
188 | if(model.getNewElements().size() >= 10) { | ||
189 | epsilon = 1.0/count; | ||
190 | draw = Math.random(); | ||
191 | count++; | ||
192 | // cut off the trajectory for bad graph | ||
193 | double distance = heuristics.getMPCDistance(); | ||
194 | System.out.println("KS"); | ||
195 | System.out.println("NA distance: " + heuristics.getNADistance()); | ||
196 | System.out.println("MPC distance: " + heuristics.getMPCDistance()); | ||
197 | System.out.println("Out degree distance:" + heuristics.getOutDegreeDistance()); | ||
198 | |||
199 | MetricDistanceGroup lsHeuristic = PartialInterpretationMetric.calculateMetricDistance(model); | ||
200 | System.out.println("LS"); | ||
201 | System.out.println("NA distance: " + lsHeuristic.getNADistance()); | ||
202 | System.out.println("MPC distance: " + lsHeuristic.getMPCDistance()); | ||
203 | System.out.println("Out degree distance:" + lsHeuristic.getOutDegreeDistance()); | ||
204 | |||
205 | if(distance <= 0.23880597014925373 + 0.00001 && distance >= 0.23880597014925373 - 0.00001) { | ||
206 | context.backtrack(); | ||
207 | final Fitness nextFitness = context.calculateFitness(); | ||
208 | currentTrajectoryWithFittness = new TrajectoryWithFitness(context.getTrajectory().toArray(), nextFitness); | ||
209 | continue; | ||
210 | } | ||
211 | |||
212 | //check for next value when doing greedy move | ||
213 | valueMap = sortWithWeight(activationIds, currentTrajectoryWithFittness.trajectory.length+1); | ||
214 | // if(activationIds.isEmpty() || (model.getNewElements().size() >= 20 && valueMap.get(activationIds.get(0)) > currentValue && epsilon < draw)) { | ||
215 | // context.backtrack(); | ||
216 | // final Fitness nextFitness = context.calculateFitness(); | ||
217 | // currentTrajectoryWithFittness = new TrajectoryWithFitness(context.getTrajectory().toArray(), nextFitness); | ||
218 | // continue; | ||
219 | // } | ||
220 | } | ||
221 | while (!isInterrupted && !configuration.progressMonitor.isCancelled() && activationIds.size() > 0) { | ||
222 | final Object nextActivation = drawWithEpsilonProbabilty(activationIds, valueMap, epsilon, draw); | ||
223 | // if (!iterator.hasNext()) { | ||
224 | // logger.debug("Last untraversed activation of the state."); | ||
225 | // trajectoiresToExplore.remove(currentTrajectoryWithFittness); | ||
226 | // } | ||
227 | stateAndActivations.get(context.getModel()).add(nextActivation); | ||
228 | logger.debug("Executing new activation: " + nextActivation); | ||
229 | context.executeAcitvationId(nextActivation); | ||
230 | visualiseCurrentState(); | ||
231 | |||
232 | //calculate the metrics for each state | ||
233 | // logCurrentStateMetric(); | ||
234 | |||
235 | boolean consistencyCheckResult = checkConsistency(currentTrajectoryWithFittness); | ||
236 | if(consistencyCheckResult == true) { continue mainLoop; } | ||
237 | |||
238 | /* if (context.isCurrentStateAlreadyTraversed()) { | ||
239 | // logger.info("The new state is already visited."); | ||
240 | // context.backtrack(); | ||
241 | // } else if (!context.checkGlobalConstraints()) { | ||
242 | logger.debug("Global contraint is not satisifed."); | ||
243 | context.backtrack(); | ||
244 | } else*/// { | ||
245 | if(getNumberOfViolations(mustMatchers) > 8) { | ||
246 | context.backtrack(); | ||
247 | }else if(model.getNewElements().size() > 90 && heuristics.getNADistance() + heuristics.getMPCDistance() + heuristics.getOutDegreeDistance() > 0.18) { | ||
248 | context.backtrack(); | ||
249 | }else if(model.getNewElements().size() > 70 && heuristics.getNADistance() + heuristics.getMPCDistance() + heuristics.getOutDegreeDistance() > 0.36) { | ||
250 | context.backtrack(); | ||
251 | } else if(model.getNewElements().size() > 50 && heuristics.getNADistance() + heuristics.getMPCDistance() + heuristics.getOutDegreeDistance() > 0.72) { | ||
252 | context.backtrack(); | ||
253 | } else { | ||
254 | final Fitness nextFitness = context.calculateFitness(); | ||
255 | |||
256 | // the only hard objectives are the size | ||
257 | |||
258 | if(model.getNewElements().size() >= configuration.typeScopes.maxNewElements + 2) { | ||
259 | System.out.println("Solution Found!!"); | ||
260 | System.out.println("# violations: " + (getNumberOfViolations(mustMatchers) + getNumberOfViolations(mayMatchers))); | ||
261 | nextFitness.setSatisifiesHardObjectives(true); | ||
262 | } | ||
263 | |||
264 | checkForSolution(nextFitness); | ||
265 | |||
266 | |||
267 | |||
268 | if (context.getDepth() > configuration.searchSpaceConstraints.maxDepth) { | ||
269 | logger.debug("Reached max depth."); | ||
270 | context.backtrack(); | ||
271 | continue; | ||
272 | } | ||
273 | |||
274 | TrajectoryWithFitness nextTrajectoryWithFittness = new TrajectoryWithFitness( | ||
275 | context.getTrajectory().toArray(), nextFitness); | ||
276 | trajectoryFit.put(nextTrajectoryWithFittness, calculateCurrentStateValue(nextTrajectoryWithFittness.trajectory.length)); | ||
277 | trajectoiresToExplore.add(nextTrajectoryWithFittness); | ||
278 | |||
279 | int compare = objectiveComparatorHelper.compare(currentTrajectoryWithFittness.fitness, | ||
280 | nextTrajectoryWithFittness.fitness); | ||
281 | if (compare < 0) { | ||
282 | logger.debug("Better fitness, moving on: " + nextFitness); | ||
283 | currentTrajectoryWithFittness = nextTrajectoryWithFittness; | ||
284 | continue mainLoop; | ||
285 | } else if (compare == 0) { | ||
286 | logger.debug("Equally good fitness, moving on: " + nextFitness); | ||
287 | currentTrajectoryWithFittness = nextTrajectoryWithFittness; | ||
288 | continue mainLoop; | ||
289 | } else { | ||
290 | logger.debug("Worse fitness."); | ||
291 | currentTrajectoryWithFittness = nextTrajectoryWithFittness; | ||
292 | continue mainLoop; | ||
293 | } | ||
294 | } | ||
295 | } | ||
296 | logger.debug("State is fully traversed."); | ||
297 | trajectoiresToExplore.remove(currentTrajectoryWithFittness); | ||
298 | currentTrajectoryWithFittness = null; | ||
299 | context.backtrack(); | ||
300 | } | ||
301 | PartialInterpretation model = (PartialInterpretation) context.getModel(); | ||
302 | PartialInterpretationMetric.calculateMetric(model, "debug/metric/output", context.getCurrentStateId().toString(), count); | ||
303 | count++; | ||
304 | logger.info("Interrupted."); | ||
305 | } | ||
306 | |||
307 | /** | ||
308 | * | ||
309 | * @param activationIds | ||
310 | * @return: activation to value map | ||
311 | */ | ||
312 | private Map<Object, Double> sortWithWeight(List<Object> activationIds, int factor){ | ||
313 | Map<Object, Double> valueMap = new HashMap<Object, Double>(); | ||
314 | // do hill climbing | ||
315 | for(Object id : activationIds) { | ||
316 | context.executeAcitvationId(id); | ||
317 | |||
318 | valueMap.put(id, calculateCurrentStateValue(factor)); | ||
319 | context.backtrack(); | ||
320 | } | ||
321 | |||
322 | Collections.sort(activationIds, Comparator.comparing(li -> valueMap.get(li))); | ||
323 | return valueMap; | ||
324 | } | ||
325 | |||
326 | private double calculateCurrentStateValue(int factor) { | ||
327 | PartialInterpretation model = (PartialInterpretation) context.getModel(); | ||
328 | MetricDistanceGroup g = PartialInterpretationMetric.calculateMetricDistanceKS(model); | ||
329 | |||
330 | int violations = getNumberOfViolations(mayMatchers); | ||
331 | double consistenceWeights = 1.0/(1+violations); | ||
332 | |||
333 | return(2.5 / Math.log(factor) * (g.getNADistance() + g.getMPCDistance() + g.getOutDegreeDistance()) + 1-consistenceWeights); | ||
334 | } | ||
335 | |||
336 | private int getNumberOfViolations(Collection<ViatraQueryMatcher<? extends IPatternMatch>> matchers) { | ||
337 | int violations = matchers.stream().mapToInt(m -> m.countMatches()).sum(); | ||
338 | |||
339 | return violations; | ||
340 | } | ||
341 | |||
342 | // Modified epsilon greedy choose for action based on value function | ||
343 | // with probability epsilon, choose the state with probability based on the weight | ||
344 | // with probability 1 - epsilon, choose the best state | ||
345 | // epsilon should decay w.r.t. time | ||
346 | private Object drawWithEpsilonProbabilty(List<Object> activationIds, Map<Object, Double> valueMap, double epsilon, double currentDraw) { | ||
347 | if(activationIds.size() <= 0) { | ||
348 | return null; | ||
349 | } | ||
350 | |||
351 | // if epsilon is smaller than current draw, return greedy choice | ||
352 | if(epsilon < currentDraw) { | ||
353 | return activationIds.remove(0); | ||
354 | }else { | ||
355 | //else return draw with probability of the weights | ||
356 | //find the sum of all 1-weights: the smaller the better | ||
357 | double sum = valueMap.values().stream().mapToDouble(d->1).sum(); | ||
358 | double rand = Math.random() * sum; | ||
359 | double iterator = 0.0; | ||
360 | Object idToReturn = null; | ||
361 | |||
362 | // draw an item with probability | ||
363 | for(Object o : valueMap.keySet()) { | ||
364 | iterator += (1); | ||
365 | if(rand < iterator) { | ||
366 | idToReturn = o; | ||
367 | break; | ||
368 | } | ||
369 | } | ||
370 | |||
371 | //delete the item from the list | ||
372 | activationIds.remove(idToReturn); | ||
373 | valueMap.remove(idToReturn); | ||
374 | return idToReturn; | ||
375 | } | ||
376 | } | ||
377 | |||
378 | private List<Object> selectActivation() { | ||
379 | List<Object> activationIds; | ||
380 | try { | ||
381 | activationIds = new ArrayList<Object>(context.getCurrentActivationIds()); | ||
382 | if(stateAndActivations.containsKey(context.getModel())) { | ||
383 | activationIds.removeAll(stateAndActivations.get(context.getModel())); | ||
384 | } | ||
385 | Collections.shuffle(activationIds); | ||
386 | } catch (NullPointerException e) { | ||
387 | numberOfStatecoderFail++; | ||
388 | activationIds = Collections.emptyList(); | ||
389 | } | ||
390 | return activationIds; | ||
391 | } | ||
392 | |||
393 | private void checkForSolution(final Fitness fittness) { | ||
394 | if (fittness.isSatisifiesHardObjectives()) { | ||
395 | if (solutionStoreWithDiversityDescriptor.isDifferent(context)) { | ||
396 | solutionStoreWithCopy.newSolution(context); | ||
397 | solutionStoreWithDiversityDescriptor.newSolution(context); | ||
398 | solutionStore.newSolution(context); | ||
399 | configuration.progressMonitor.workedModelFound(configuration.solutionScope.numberOfRequiredSolution); | ||
400 | |||
401 | logger.debug("Found a solution."); | ||
402 | } | ||
403 | } | ||
404 | } | ||
405 | |||
406 | @Override | ||
407 | public void interruptStrategy() { | ||
408 | isInterrupted = true; | ||
409 | } | ||
410 | |||
411 | |||
412 | private TrajectoryWithFitness selectState() { | ||
413 | int randomNumber = random.nextInt(configuration.randomBacktrackChance); | ||
414 | if (randomNumber == 0) { | ||
415 | int elements = trajectoiresToExplore.size(); | ||
416 | int randomElementIndex = random.nextInt(elements); | ||
417 | logger.debug("Randomly backtract to the " + randomElementIndex + " best solution..."); | ||
418 | Iterator<TrajectoryWithFitness> iterator = trajectoiresToExplore.iterator(); | ||
419 | while (randomElementIndex != 0) { | ||
420 | iterator.next(); | ||
421 | randomElementIndex--; | ||
422 | } | ||
423 | TrajectoryWithFitness res = iterator.next(); | ||
424 | if (res == null) { | ||
425 | return trajectoiresToExplore.element(); | ||
426 | } else { | ||
427 | return res; | ||
428 | } | ||
429 | } else { | ||
430 | return trajectoiresToExplore.element(); | ||
431 | } | ||
432 | } | ||
433 | |||
434 | // private void logCurrentStateMetric() { | ||
435 | // if(this.configuration.documentationLevel != DocumentationLevel.NONE || workspace == null) { | ||
436 | // return; | ||
437 | // } | ||
438 | // | ||
439 | // PartialInterpretation interpretation = (PartialInterpretation)context.getModel(); //pattern.get("interpretation"); | ||
440 | // PartialInterpretationMetric.calculateMetric(interpretation, "debug/metric/" + context.getModel().hashCode(), context.getCurrentStateId().toString()); | ||
441 | // } | ||
442 | |||
443 | public void visualiseCurrentState() { | ||
444 | PartialInterpretationVisualiser partialInterpretatioVisualiser = configuration.debugCongiguration.partialInterpretatioVisualiser; | ||
445 | if(partialInterpretatioVisualiser != null && this.configuration.documentationLevel == DocumentationLevel.FULL && workspace != null) { | ||
446 | PartialInterpretation p = (PartialInterpretation) (context.getModel()); | ||
447 | int id = ++numberOfPrintedModel; | ||
448 | if (id % configuration.debugCongiguration.partalInterpretationVisualisationFrequency == 0) { | ||
449 | PartialInterpretationVisualisation visualisation = partialInterpretatioVisualiser.visualiseConcretization(p); | ||
450 | visualisation.writeToFile(workspace, String.format("state%09d.png", id)); | ||
451 | } | ||
452 | } | ||
453 | } | ||
454 | |||
455 | protected boolean checkConsistency(TrajectoryWithFitness t) { | ||
456 | LogicReasoner internalIncosnsitencyDetector = configuration.internalConsistencyCheckerConfiguration.internalIncosnsitencyDetector; | ||
457 | if (internalIncosnsitencyDetector!= null) { | ||
458 | int id = ++numberOfSolverCalls; | ||
459 | if (id % configuration.internalConsistencyCheckerConfiguration.incternalConsistencyCheckingFrequency == 0) { | ||
460 | try { | ||
461 | PartialInterpretation interpretation = (PartialInterpretation) (context.getModel()); | ||
462 | PartialInterpretation copied = EcoreUtil.copy(interpretation); | ||
463 | this.partialInterpretation2Logic.transformPartialIntepretation2Logic(copied.getProblem(), copied); | ||
464 | LogicProblem newProblem = copied.getProblem(); | ||
465 | |||
466 | this.configuration.typeScopes.maxNewElements = interpretation.getMaxNewElements(); | ||
467 | this.configuration.typeScopes.minNewElements = interpretation.getMinNewElements(); | ||
468 | LogicResult result = internalIncosnsitencyDetector.solve(newProblem, configuration, workspace); | ||
469 | if (result instanceof InconsistencyResult) { | ||
470 | logger.debug("Solver found an Inconsistency!"); | ||
471 | removeSubtreeFromQueue(t); | ||
472 | return true; | ||
473 | } else if (result instanceof ModelResult) { | ||
474 | logger.debug("Solver found a model!"); | ||
475 | solutionStore.newSolution(context); | ||
476 | |||
477 | this.modelResultByInternalSolver = (ModelResult) result; | ||
478 | return true; | ||
479 | } else { | ||
480 | logger.debug("Failed consistency check."); | ||
481 | return false; | ||
482 | } | ||
483 | } catch (Exception e) { | ||
484 | logger.debug("Problem with internal consistency checking: "+e.getMessage()); | ||
485 | e.printStackTrace(); | ||
486 | return false; | ||
487 | } | ||
488 | } | ||
489 | |||
490 | } | ||
491 | return false; | ||
492 | } | ||
493 | |||
494 | protected void removeSubtreeFromQueue(TrajectoryWithFitness t) { | ||
495 | PriorityQueue<TrajectoryWithFitness> previous = this.trajectoiresToExplore; | ||
496 | this.trajectoiresToExplore = new PriorityQueue<>(this.comparator); | ||
497 | for (TrajectoryWithFitness trajectoryWithFitness : previous) { | ||
498 | if (!containsAsSubstring(trajectoryWithFitness.trajectory, t.trajectory)) { | ||
499 | this.trajectoiresToExplore.add(trajectoryWithFitness); | ||
500 | } else { | ||
501 | logger.debug("State has been excluded due to inherent inconsistency"); | ||
502 | } | ||
503 | } | ||
504 | } | ||
505 | |||
506 | private boolean containsAsSubstring(Object[] full, Object[] substring) { | ||
507 | if (substring.length > full.length) { | ||
508 | return false; | ||
509 | } else if (substring.length == full.length) { | ||
510 | return Arrays.equals(full, substring); | ||
511 | } else { | ||
512 | Object[] part = Arrays.copyOfRange(full, 0, substring.length); | ||
513 | return Arrays.equals(part, substring); | ||
514 | } | ||
515 | } | ||
516 | } | ||