From e11bce7ad3e803e80883499fec0ad6e4540ffe43 Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Tue, 30 Jun 2020 18:03:48 +0200 Subject: Add modified VIATRA-DSE version --- .../dse/api/strategy/impl/BestFirstStrategy.java | 228 +++++++++++++++++++++ 1 file changed, 228 insertions(+) create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BestFirstStrategy.java (limited to 'Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BestFirstStrategy.java') 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 @@ +/******************************************************************************* + * Copyright (c) 2010-2017, Andras Szabolcs Nagy and Daniel Varro + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v. 2.0 which is available at + * http://www.eclipse.org/legal/epl-v20.html. + * + * SPDX-License-Identifier: EPL-2.0 + *******************************************************************************/ +package org.eclipse.viatra.dse.api.strategy.impl; + +import java.util.Arrays; +import java.util.Collection; +import java.util.Iterator; +import java.util.PriorityQueue; + +import org.apache.log4j.Logger; +import org.eclipse.viatra.dse.api.strategy.interfaces.IStrategy; +import org.eclipse.viatra.dse.base.ThreadContext; +import org.eclipse.viatra.dse.objectives.Fitness; +import org.eclipse.viatra.dse.objectives.ObjectiveComparatorHelper; +import org.eclipse.viatra.dse.solutionstore.SolutionStore; + +/** + * This exploration strategy eventually explorers the whole design space but goes in the most promising directions + * first, based on the {@link Fitness}. + * + * There are a few parameter to tune such as + * + * + * @author Andras Szabolcs Nagy + * + */ +public class BestFirstStrategy implements IStrategy { + + private ThreadContext context; + private SolutionStore solutionStore; + + private int maxDepth; + private boolean isInterrupted = false; + private boolean backTrackIfSolution = true; + private boolean onlyBetterFirst = false; + + private PriorityQueue trajectoiresToExplore; + private Logger logger = Logger.getLogger(IStrategy.class); + + private static class TrajectoryWithFitness { + + public Object[] trajectory; + public Fitness fitness; + + public TrajectoryWithFitness(Object[] trajectory, Fitness fitness) { + super(); + this.trajectory = trajectory; + this.fitness = fitness; + } + + @Override + public String toString() { + return Arrays.toString(trajectory) + fitness.toString(); + } + + } + + /** + * Creates a new best-first search algorithm without depth limit. + */ + public BestFirstStrategy() { + this(-1); + } + + /** + * Creates a new best-first search algorithm with depth limit. + * + * @param maxDepth + * A negative maxDepth means no depth limit, zero means the checking of the initial state. + */ + public BestFirstStrategy(int maxDepth) { + if (maxDepth < 0) { + this.maxDepth = Integer.MAX_VALUE; + } else { + this.maxDepth = maxDepth; + } + } + + public BestFirstStrategy continueIfHardObjectivesFulfilled() { + backTrackIfSolution = false; + return this; + } + + public BestFirstStrategy goOnOnlyIfFitnessIsBetter() { + onlyBetterFirst = true; + return this; + } + + @Override + public void initStrategy(ThreadContext context) { + this.context = context; + this.solutionStore = context.getGlobalContext().getSolutionStore(); + final ObjectiveComparatorHelper objectiveComparatorHelper = context.getObjectiveComparatorHelper(); + + trajectoiresToExplore = new PriorityQueue(11, + (o1, o2) -> objectiveComparatorHelper.compare(o2.fitness, o1.fitness)); + } + + @Override + public void explore() { + final ObjectiveComparatorHelper objectiveComparatorHelper = context.getObjectiveComparatorHelper(); + + boolean globalConstraintsAreSatisfied = context.checkGlobalConstraints(); + if (!globalConstraintsAreSatisfied) { + logger.info("Global contraint is not satisifed in the first state. Terminate."); + return; + } + + final Fitness firstFittness = context.calculateFitness(); + if (firstFittness.isSatisifiesHardObjectives()) { + context.newSolution(); + logger.info("First state is a solution. Terminate."); + return; + } + + if (maxDepth == 0) { + return; + } + + final Object[] firstTrajectory = context.getTrajectory().toArray(new Object[0]); + TrajectoryWithFitness currentTrajectoryWithFittness = new TrajectoryWithFitness(firstTrajectory, firstFittness); + trajectoiresToExplore.add(currentTrajectoryWithFittness); + + mainLoop: while (!isInterrupted) { + + if (currentTrajectoryWithFittness == null) { + if (trajectoiresToExplore.isEmpty()) { + logger.debug("State space is fully traversed."); + return; + } else { + currentTrajectoryWithFittness = trajectoiresToExplore.element(); + if (logger.isDebugEnabled()) { + logger.debug("New trajectory is chosen: " + currentTrajectoryWithFittness); + } + context.getDesignSpaceManager().executeTrajectoryWithMinimalBacktrackWithoutStateCoding(currentTrajectoryWithFittness.trajectory); + } + } + + Collection activationIds = context.getUntraversedActivationIds(); + Iterator iterator = activationIds.iterator(); + + while (!isInterrupted && iterator.hasNext()) { + final Object nextActivation = iterator.next(); + if (!iterator.hasNext()) { + logger.debug("Last untraversed activation of the state."); + trajectoiresToExplore.remove(currentTrajectoryWithFittness); + } + + if (logger.isDebugEnabled()) { + logger.debug("Executing new activation: " + nextActivation); + } + context.executeAcitvationId(nextActivation); + if (context.isCurrentStateAlreadyTraversed()) { + logger.info("The new state is already visited."); + context.backtrack(); + } else if (!context.checkGlobalConstraints()) { + logger.debug("Global contraint is not satisifed."); + context.backtrack(); + } else { + final Fitness nextFitness = context.calculateFitness(); + if (nextFitness.isSatisifiesHardObjectives()) { + solutionStore.newSolution(context); + logger.debug("Found a solution."); + if (backTrackIfSolution) { + context.backtrack(); + continue; + } + } + if (context.getDepth() >= maxDepth) { + logger.debug("Reached max depth."); + context.backtrack(); + continue; + } + + TrajectoryWithFitness nextTrajectoryWithFittness = new TrajectoryWithFitness( + context.getTrajectory().toArray(), nextFitness); + trajectoiresToExplore.add(nextTrajectoryWithFittness); + + int compare = objectiveComparatorHelper.compare(currentTrajectoryWithFittness.fitness, + nextTrajectoryWithFittness.fitness); + if (compare < 0) { + logger.debug("Better fitness, moving on: " + nextFitness); + currentTrajectoryWithFittness = nextTrajectoryWithFittness; + continue mainLoop; + } else if (compare == 0) { + if (onlyBetterFirst) { + logger.debug("Equally good fitness, backtrack: " + nextFitness); + context.backtrack(); + continue; + } else { + logger.debug("Equally good fitness, moving on: " + nextFitness); + currentTrajectoryWithFittness = nextTrajectoryWithFittness; + continue mainLoop; + } + } else { + logger.debug("Worse fitness."); + currentTrajectoryWithFittness = null; + continue mainLoop; + } + } + } + + logger.debug("State is fully traversed."); + trajectoiresToExplore.remove(currentTrajectoryWithFittness); + currentTrajectoryWithFittness = null; + + } + logger.info("Interrupted."); + } + + @Override + public void interruptStrategy() { + isInterrupted = true; + } + +} -- cgit v1.2.3-54-g00ecf