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/objectives/ActivationFitnessProcessor.java | 15 + .../eclipse/viatra/dse/objectives/Comparators.java | 31 ++ .../org/eclipse/viatra/dse/objectives/Fitness.java | 29 ++ .../viatra/dse/objectives/IGlobalConstraint.java | 58 ++++ .../eclipse/viatra/dse/objectives/IObjective.java | 110 +++++++ .../dse/objectives/LeveledObjectivesHelper.java | 114 ++++++++ .../dse/objectives/ObjectiveComparatorHelper.java | 217 ++++++++++++++ .../viatra/dse/objectives/TrajectoryFitness.java | 84 ++++++ .../impl/AlwaysSatisfiedDummyHardObjective.java | 52 ++++ .../viatra/dse/objectives/impl/BaseObjective.java | 150 ++++++++++ .../dse/objectives/impl/CompositeObjective.java | 137 +++++++++ .../dse/objectives/impl/ConstraintsObjective.java | 316 +++++++++++++++++++++ .../dse/objectives/impl/DepthHardObjective.java | 89 ++++++ .../impl/ModelQueriesGlobalConstraint.java | 116 ++++++++ .../viatra/dse/objectives/impl/ModelQueryType.java | 14 + .../impl/NeverSatisfiedDummyHardObjective.java | 52 ++++ .../impl/NoRuleActivationsHardObjective.java | 59 ++++ .../impl/TrajectoryCostSoftObjective.java | 148 ++++++++++ 18 files changed, 1791 insertions(+) create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/ActivationFitnessProcessor.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/Comparators.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/Fitness.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/IGlobalConstraint.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/IObjective.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/LeveledObjectivesHelper.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/ObjectiveComparatorHelper.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/TrajectoryFitness.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/AlwaysSatisfiedDummyHardObjective.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/BaseObjective.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/CompositeObjective.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/ConstraintsObjective.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/DepthHardObjective.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/ModelQueriesGlobalConstraint.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/ModelQueryType.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/NeverSatisfiedDummyHardObjective.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/NoRuleActivationsHardObjective.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/TrajectoryCostSoftObjective.java (limited to 'Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives') diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/ActivationFitnessProcessor.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/ActivationFitnessProcessor.java new file mode 100644 index 00000000..c06d2916 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/ActivationFitnessProcessor.java @@ -0,0 +1,15 @@ +/******************************************************************************* + * Copyright (c) 2010-2015, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi 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.objectives; + +import org.eclipse.viatra.query.runtime.api.IPatternMatch; + +public interface ActivationFitnessProcessor { + public double process(IPatternMatch match); +} \ No newline at end of file diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/Comparators.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/Comparators.java new file mode 100644 index 00000000..b1bd9349 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/Comparators.java @@ -0,0 +1,31 @@ +/******************************************************************************* + * Copyright (c) 2010-2015, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi 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.objectives; + +import java.util.Comparator; + +/** + * This helper class holds comparators for objective implementations. + * + * @author Andras Szabolcs Nagy + * + */ +public class Comparators { + + private Comparators() { /*Utility class constructor*/ } + + public static final Comparator HIGHER_IS_BETTER = (o1, o2) -> o1.compareTo(o2); + + public static final Comparator LOWER_IS_BETTER = (o1, o2) -> o2.compareTo(o1); + + private static final Double ZERO = Double.valueOf(0); + + public static final Comparator DIFFERENCE_TO_ZERO_IS_BETTER = (o1, o2) -> ZERO.compareTo(Math.abs(o1)-Math.abs(o2)); + +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/Fitness.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/Fitness.java new file mode 100644 index 00000000..8beef3bd --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/Fitness.java @@ -0,0 +1,29 @@ +/******************************************************************************* + * Copyright (c) 2010-2014, Miklos Foldenyi, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi 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.objectives; + +import java.util.HashMap; + +public class Fitness extends HashMap{ + + private boolean satisifiesHardObjectives; + + public boolean isSatisifiesHardObjectives() { + return satisifiesHardObjectives; + } + + public void setSatisifiesHardObjectives(boolean satisifiesHardObjectives) { + this.satisifiesHardObjectives = satisifiesHardObjectives; + } + + @Override + public String toString() { + return super.toString() + " hardObjectives=" + satisifiesHardObjectives; + } +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/IGlobalConstraint.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/IGlobalConstraint.java new file mode 100644 index 00000000..2f7f0347 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/IGlobalConstraint.java @@ -0,0 +1,58 @@ +/******************************************************************************* + * Copyright (c) 2010-2014, Miklos Foldenyi, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi 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.objectives; + +import org.eclipse.viatra.dse.base.ThreadContext; + +/** + * + * Implementation of this interface represents a global constraint of the DSE problem, which can halt an exploration + * continuing from a state which dissatisfies the global constraint. + *

+ * Certain global constraints can have inner state for the validation. In this case a new instance is necessary for + * every new thread, and the {@code createNew} method should not return the same instance more than once. + * + * @author Andras Szabolcs Nagy + * + */ +public interface IGlobalConstraint { + + /** + * Returns the name of the global constraint. + * + * @return The name of the global constraint. + */ + String getName(); + + /** + * Checks whether the current state satisfies the global constraint. + * + * @param context + * The {@link ThreadContext} which contains the necessary information. + * @return True if the state is valid and exploration can be continued from the actual state. + */ + boolean checkGlobalConstraint(ThreadContext context); + + /** + * Initializes the global constraint. It is called exactly once for every thread starts. + * + * @param context + * The {@link ThreadContext}. + */ + void init(ThreadContext context); + + /** + * Returns an instance of the {@link IGlobalConstraint}. If it returns the same instance, all the methods has to be + * thread save as they are called concurrently. + * + * @return An instance of the global constraint. + */ + IGlobalConstraint createNew(); + +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/IObjective.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/IObjective.java new file mode 100644 index 00000000..849dd4e8 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/IObjective.java @@ -0,0 +1,110 @@ +/******************************************************************************* + * Copyright (c) 2010-2014, Miklos Foldenyi, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi 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.objectives; + +import java.util.Comparator; + +import org.eclipse.viatra.dse.base.ThreadContext; + +/** + * + * Implementation of this interface represents a single objective of the DSE problem, which can assess a solution + * (trajectory) in a single number. It has a name and a comparator which orders two solution based on the calculated + * value. + *

+ * Objectives can be either hard or soft objectives. Hard objectives can be satisfied or unsatisfied. If all of the hard + * objectives are satisfied on a single solution, then it is considered to be a valid (or goal) solution. + *

+ * Certain objectives can have inner state for calculating the fitness value. In this case a new instance is necessary + * for every new thread, and the {@code createNew} method should not return the same instance more than once. + * + * @author Andras Szabolcs Nagy + * + */ +public interface IObjective { + + /** + * Returns the name of the objective. + * + * @return The name of the objective. + */ + String getName(); + + /** + * Sets the {@link Comparator} which is used to compare fitness (doubles). It determines whether the objective is to + * minimize or maximize (or minimize or maximize a delta from a given number). + * + * @param comparator The comparator. + */ + void setComparator(Comparator comparator); + + /** + * Returns a {@link Comparator} which is used to compare fitness (doubles). It determines whether the objective is + * to minimize or maximize (or minimize or maximize a delta from a given number). + * + * @return The comparator. + */ + Comparator getComparator(); + + /** + * Calculates the value of the objective on a given solution (trajectory). + * + * @param context + * The {@link ThreadContext} + * @return The objective value in double. + */ + Double getFitness(ThreadContext context); + + /** + * Initializes the objective. It is called exactly once for every thread starts. + * + * @param context + * The {@link ThreadContext}. + */ + void init(ThreadContext context); + + /** + * Returns an instance of the {@link IObjective}. If it returns the same instance, all the methods has to be thread + * save as they are called concurrently. + * + * @return An instance of the objective. + */ + IObjective createNew(); + + /** + * Returns true if the objective is a hard objective. In such a case the method + * {@link IObjective#satisifiesHardObjective(Double)} is called. + * + * @return True if the objective is a hard objective. + * @see IObjective#satisifiesHardObjective(Double) + * @see IObjective + */ + boolean isHardObjective(); + + /** + * Determines if the given fitness value satisfies the hard objective. + * + * @param fitness + * The fitness value of a solution. + * @return True if it satisfies the hard objective or it is a soft constraint. + * @see IObjective + */ + boolean satisifiesHardObjective(Double fitness); + + /** + * Set the level of the objective. + */ + void setLevel(int level); + + /** + * Gets the level of the objective. + */ + int getLevel(); + +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/LeveledObjectivesHelper.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/LeveledObjectivesHelper.java new file mode 100644 index 00000000..2d81629b --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/LeveledObjectivesHelper.java @@ -0,0 +1,114 @@ +/******************************************************************************* + * Copyright (c) 2010-2016, 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.objectives; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Comparator; +import java.util.List; + +public class LeveledObjectivesHelper { + + private List objectives = new ArrayList(); + private IObjective[][] leveledObjectives; + + public LeveledObjectivesHelper(List objectives) { + this.objectives = objectives; + } + + public IObjective[][] initLeveledObjectives() { + if (objectives.isEmpty()) { + leveledObjectives = new IObjective[0][0]; + return leveledObjectives; + } + + int level = objectives.get(0).getLevel(); + boolean oneLevelOnly = true; + for (IObjective objective : objectives) { + if (objective.getLevel() != level) { + oneLevelOnly = false; + break; + } + } + + if (oneLevelOnly) { + leveledObjectives = new IObjective[1][objectives.size()]; + for (int i = 0; i < objectives.size(); i++) { + leveledObjectives[0][i] = objectives.get(i); + } + return leveledObjectives; + } + + IObjective[] objectivesArray = getSortedByLevelObjectives(objectives); + + int numberOfLevels = getNumberOfObjectiveLevels(objectivesArray); + + leveledObjectives = new IObjective[numberOfLevels][]; + + fillLeveledObjectives(objectivesArray); + + return leveledObjectives; + } + + private void fillLeveledObjectives(IObjective[] objectivesArray) { + int actLevel = objectivesArray[0].getLevel(); + int levelIndex = 0; + int lastIndex = 0; + int corrigationForLastLevel = 0; + boolean oneObjectiveAtLastLevel = false; + for (int i = 0; i < objectivesArray.length; i++) { + if (i == objectivesArray.length - 1) { + corrigationForLastLevel = 1; + if (objectivesArray[i - 1].getLevel() != objectivesArray[i].getLevel()) { + oneObjectiveAtLastLevel = true; + corrigationForLastLevel = 0; + } + } + if (objectivesArray[i].getLevel() != actLevel || corrigationForLastLevel == 1 || oneObjectiveAtLastLevel) { + leveledObjectives[levelIndex] = new IObjective[i - lastIndex + corrigationForLastLevel]; + for (int j = lastIndex; j < i + corrigationForLastLevel; j++) { + leveledObjectives[levelIndex][j - lastIndex] = objectivesArray[j]; + } + if (oneObjectiveAtLastLevel) { + leveledObjectives[levelIndex + 1] = new IObjective[1]; + leveledObjectives[levelIndex + 1][0] = objectivesArray[i]; + } + actLevel = objectivesArray[i].getLevel(); + levelIndex++; + lastIndex = i; + } + } + } + + private int getNumberOfObjectiveLevels(IObjective[] objectivesArray) { + + int actLevel = objectivesArray[0].getLevel(); + int numberOfLevels = 1; + + for (int i = 1; i < objectivesArray.length; i++) { + if (objectivesArray[i].getLevel() != actLevel) { + numberOfLevels++; + actLevel = objectivesArray[i].getLevel(); + } + } + + return numberOfLevels; + } + + private IObjective[] getSortedByLevelObjectives(List objectives) { + IObjective[] objectivesArray = objectives.toArray(new IObjective[objectives.size()]); + Arrays.sort(objectivesArray, Comparator.comparingInt(IObjective::getLevel)); + return objectivesArray; + } + + public IObjective[][] getLeveledObjectives() { + return leveledObjectives; + } + +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/ObjectiveComparatorHelper.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/ObjectiveComparatorHelper.java new file mode 100644 index 00000000..39139bb0 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/ObjectiveComparatorHelper.java @@ -0,0 +1,217 @@ +/******************************************************************************* + * Copyright (c) 2010-2015, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi 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.objectives; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Random; + +import org.eclipse.viatra.query.runtime.matchers.util.Preconditions; + +/** + * This class is responsible to compare and sort fitness values. {@link TrajectoryFitness} instances can be added to an + * instance of this class, that it can sort them. + * + * @author András Szabolcs Nagy + */ +public class ObjectiveComparatorHelper { + + private IObjective[][] leveledObjectives; + private List trajectoryFitnesses = new ArrayList(); + private Random random = new Random(); + private boolean computeCrowdingDistance = false; + + public ObjectiveComparatorHelper(IObjective[][] leveledObjectives) { + this.leveledObjectives = leveledObjectives; + } + + public void setComputeCrowdingDistance(boolean computeCrowdingDistance) { + this.computeCrowdingDistance = computeCrowdingDistance; + } + + /** + * Compares two fitnesses based on hierarchical dominance. Returns -1 if the second parameter {@code o2} is a better + * solution ({@code o2} dominates {@code o1}), 1 if the first parameter {@code o1} is better ({@code o1} dominates + * {@code o2}) and returns 0 if they are non-dominating each other. + */ + public int compare(Fitness o1, Fitness o2) { + + levelsLoop: for (int i = 0; i < leveledObjectives.length; i++) { + + boolean o1HasBetterFitness = false; + boolean o2HasBetterFitness = false; + + for (IObjective objective : leveledObjectives[i]) { + String objectiveName = objective.getName(); + int sgn = objective.getComparator().compare(o1.get(objectiveName), o2.get(objectiveName)); + + if (sgn < 0) { + o2HasBetterFitness = true; + } + if (sgn > 0) { + o1HasBetterFitness = true; + } + if (o1HasBetterFitness && o2HasBetterFitness) { + continue levelsLoop; + } + } + if (o2HasBetterFitness && !o1HasBetterFitness) { + return -1; + } else if (!o2HasBetterFitness && o1HasBetterFitness) { + return 1; + } + } + + return 0; + + } + + /** + * Adds a {@link TrajectoryFitness} to an inner list to compare later. + * + * @param trajectoryFitness + */ + public void addTrajectoryFitness(TrajectoryFitness trajectoryFitness) { + trajectoryFitnesses.add(trajectoryFitness); + } + + /** + * Clears the inner {@link TrajectoryFitness} list. + */ + public void clearTrajectoryFitnesses() { + trajectoryFitnesses.clear(); + } + + /** + * Returns the inner {@link TrajectoryFitness} list. + */ + public List getTrajectoryFitnesses() { + return trajectoryFitnesses; + } + + /** + * Returns a random {@link TrajectoryFitness} from the pareto front. + */ + public TrajectoryFitness getRandomBest() { + List paretoFront = getParetoFront(); + int randomIndex = random.nextInt(paretoFront.size()); + return paretoFront.get(randomIndex); + } + + /** + * Returns the pareto front of the previously added {@link TrajectoryFitness}. + */ + public List getParetoFront() { + return getFronts().get(0); + } + + /** + * Returns the previously added {@link TrajectoryFitness} instances in fronts. + */ + public List> getFronts() { + Preconditions.checkArgument(!trajectoryFitnesses.isEmpty(), "No trajectory fitnesses were added."); + List> fronts = new ArrayList>(); + + Map> dominatedInstances = new HashMap>(); + Map dominatingInstances = new HashMap(); + + // calculate dominations + for (TrajectoryFitness TrajectoryFitnessP : trajectoryFitnesses) { + dominatedInstances.put(TrajectoryFitnessP, new ArrayList()); + dominatingInstances.put(TrajectoryFitnessP, 0); + + for (TrajectoryFitness TrajectoryFitnessQ : trajectoryFitnesses) { + int dominates = compare(TrajectoryFitnessP.fitness, TrajectoryFitnessQ.fitness); + if (dominates > 0) { + dominatedInstances.get(TrajectoryFitnessP).add(TrajectoryFitnessQ); + } else if (dominates < 0) { + dominatingInstances.put(TrajectoryFitnessP, dominatingInstances.get(TrajectoryFitnessP) + 1); + } + } + + if (dominatingInstances.get(TrajectoryFitnessP) == 0) { + // p belongs to the first front + TrajectoryFitnessP.rank = 1; + if (fronts.isEmpty()) { + ArrayList firstDominationFront = new ArrayList(); + firstDominationFront.add(TrajectoryFitnessP); + fronts.add(firstDominationFront); + } else { + List firstDominationFront = fronts.get(0); + firstDominationFront.add(TrajectoryFitnessP); + } + } + } + + // create fronts + int i = 1; + while (fronts.size() == i) { + ArrayList nextDominationFront = new ArrayList(); + for (TrajectoryFitness TrajectoryFitnessP : fronts.get(i - 1)) { + for (TrajectoryFitness TrajectoryFitnessQ : dominatedInstances.get(TrajectoryFitnessP)) { + dominatingInstances.put(TrajectoryFitnessQ, dominatingInstances.get(TrajectoryFitnessQ) - 1); + if (dominatingInstances.get(TrajectoryFitnessQ) == 0) { + TrajectoryFitnessQ.rank = i + 1; + nextDominationFront.add(TrajectoryFitnessQ); + } + } + } + i++; + if (!nextDominationFront.isEmpty()) { + if (computeCrowdingDistance) { + crowdingDistanceAssignment(nextDominationFront, leveledObjectives); + } + fronts.add(nextDominationFront); + } + } + + return fronts; + } + + /** + * Executes the crowding distance assignment for the specified front. + * + * @param front + */ + public static void crowdingDistanceAssignment(List front, IObjective[][] leveledObjectives) { + + for (TrajectoryFitness InstanceData : front) { + // initialize crowding distance + InstanceData.crowdingDistance = 0; + } + + for (final IObjective[] objectives : leveledObjectives) { + for (final IObjective objective : objectives) { + + final String m = objective.getName(); + TrajectoryFitness[] sortedFront = front.toArray(new TrajectoryFitness[0]); + // sort using m-th objective value + Arrays.sort(sortedFront, (o1, o2) -> objective.getComparator().compare(o1.fitness.get(m), o2.fitness.get(m))); + // so that boundary points are always selected + sortedFront[0].crowdingDistance = Double.POSITIVE_INFINITY; + sortedFront[sortedFront.length - 1].crowdingDistance = Double.POSITIVE_INFINITY; + // If minimal and maximal fitness value for this objective are + // equal, then do not change crowding distance + if (sortedFront[0].fitness.get(m) != sortedFront[sortedFront.length - 1].fitness.get(m)) { + for (int i = 1; i < sortedFront.length - 1; i++) { + double newCrowdingDistance = sortedFront[i].crowdingDistance; + newCrowdingDistance += (sortedFront[i + 1].fitness.get(m) - sortedFront[i - 1].fitness.get(m)) + / (sortedFront[sortedFront.length - 1].fitness.get(m) - sortedFront[0].fitness.get(m)); + + sortedFront[i].crowdingDistance = newCrowdingDistance; + } + } + } + } + } + +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/TrajectoryFitness.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/TrajectoryFitness.java new file mode 100644 index 00000000..f783afac --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/TrajectoryFitness.java @@ -0,0 +1,84 @@ +/******************************************************************************* + * Copyright (c) 2010-2015, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi 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.objectives; + +import java.util.Arrays; +import java.util.List; + +import org.eclipse.viatra.dse.designspace.api.TrajectoryInfo; + +/** + * This class represents a trajectory and its fitness. + * @author Andras Szabolcs Nagy + * + */ +public class TrajectoryFitness { + + public Object[] trajectory; + public Fitness fitness; + + public int rank; + public double crowdingDistance; + + private int hash; + + public int survive; + + /** + * Creates a {@link TrajectoryFitness} with the full trajectory. + * @param trajectory The trajectory. + * @param fitness The fitness. + */ + public TrajectoryFitness(Object[] trajectory, Fitness fitness) { + this.fitness = fitness; + this.trajectory = trajectory; + } + + /** + * Creates a {@link TrajectoryFitness} with the full trajectory. + * @param trajectoryInfo The trajectory. + * @param fitness The fitness. + */ + public TrajectoryFitness(TrajectoryInfo trajectoryInfo, Fitness fitness) { + this.fitness = fitness; + List fullTraj = trajectoryInfo.getTrajectory(); + trajectory = fullTraj.toArray(new Object[fullTraj.size()]); + } + + /** + * Creates a {@link TrajectoryFitness} with the given activation id} + * @param transition The transition. + * @param fitness The fitness. + */ + public TrajectoryFitness(Object transition, Fitness fitness) { + this.fitness = fitness; + trajectory = new Object[] {transition}; + } + + @Override + public boolean equals(Object obj) { + if (obj instanceof TrajectoryFitness) { + return Arrays.equals(trajectory, ((TrajectoryFitness) obj).trajectory); + } + return false; + } + + @Override + public int hashCode() { + if (hash == 0 && trajectory.length > 0) { + hash = Arrays.hashCode(trajectory); + } + return hash; + } + + @Override + public String toString() { + return Arrays.toString(trajectory) + fitness.toString(); + } +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/AlwaysSatisfiedDummyHardObjective.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/AlwaysSatisfiedDummyHardObjective.java new file mode 100644 index 00000000..9898a3b5 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/AlwaysSatisfiedDummyHardObjective.java @@ -0,0 +1,52 @@ +/******************************************************************************* + * Copyright (c) 2010-2016, Andras Szabolcs Nagy, Zoltan Ujhelyi 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.objectives.impl; + +import org.eclipse.viatra.dse.base.ThreadContext; +import org.eclipse.viatra.dse.objectives.IObjective; + +/** + * This hard objective is fulfilled in any circumstances. Use it if all states should be regarded as a valid solution. + * + * @author Andras Szabolcs Nagy + * + */ +public class AlwaysSatisfiedDummyHardObjective extends BaseObjective { + + private static final String DEFAULT_NAME = "AlwaysSatisfiedDummyHardObjective"; + + public AlwaysSatisfiedDummyHardObjective() { + super(DEFAULT_NAME); + } + + public AlwaysSatisfiedDummyHardObjective(String name) { + super(name); + } + + @Override + public Double getFitness(ThreadContext context) { + return 0d; + } + + @Override + public boolean isHardObjective() { + return true; + } + + @Override + public boolean satisifiesHardObjective(Double fitness) { + return true; + } + + @Override + public IObjective createNew() { + return this; + } + +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/BaseObjective.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/BaseObjective.java new file mode 100644 index 00000000..0a1de875 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/BaseObjective.java @@ -0,0 +1,150 @@ +/******************************************************************************* + * Copyright (c) 2010-2015, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi 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.objectives.impl; + +import java.util.Comparator; +import java.util.Objects; + +import org.eclipse.viatra.dse.base.ThreadContext; +import org.eclipse.viatra.dse.objectives.Comparators; +import org.eclipse.viatra.dse.objectives.IObjective; + +/** + * This abstract class implements the basic functionality of an objective ({@link IObjective} namely its name, + * comparator, level and fitness hard constraint. + * + * @author Andras Szabolcs Nagy + * + */ +public abstract class BaseObjective implements IObjective { + + protected final String name; + protected Comparator comparator = Comparators.HIGHER_IS_BETTER; + protected int level = 0; + + protected double fitnessConstraint; + protected boolean isThereFitnessConstraint = false; + protected Comparator fitnessConstraintComparator; + + public BaseObjective(String name) { + Objects.requireNonNull(name, "Name of the objective cannot be null."); + this.name = name; + } + + @Override + public String getName() { + return name; + } + + @Override + public void setComparator(Comparator comparator) { + this.comparator = comparator; + } + + @Override + public Comparator getComparator() { + return comparator; + } + + @Override + public void setLevel(int level) { + this.level = level; + } + + @Override + public int getLevel() { + return level; + } + + public BaseObjective withLevel(int level) { + setLevel(level); + return this; + } + + public BaseObjective withComparator(Comparator comparator) { + setComparator(comparator); + return this; + } + + /** + * Adds a hard constraint on the fitness value. For example, the fitness value must be better than 10 to accept the + * current state as a solution. + * + * @param fitnessConstraint + * Solutions should be better than this value. + * @param fitnessConstraintComparator + * {@link Comparator} to determine if the current state is better than the given value. + * @return The actual instance to enable builder pattern like usage. + */ + public BaseObjective withHardConstraintOnFitness(double fitnessConstraint, + Comparator fitnessConstraintComparator) { + this.fitnessConstraint = fitnessConstraint; + this.fitnessConstraintComparator = fitnessConstraintComparator; + this.isThereFitnessConstraint = true; + return this; + } + + /** + * Adds a hard constraint on the fitness value. For example, the fitness value must be better than 10 to accept the + * current state as a solution. The provided comparator will be used. + * + * @param fitnessConstraint + * Solutions should be better than this value. + * @return The actual instance to enable builder pattern like usage. + */ + public BaseObjective withHardConstraintOnFitness(double fitnessConstraint) { + return withHardConstraintOnFitness(fitnessConstraint, null); + } + + @Override + public void init(ThreadContext context) { + if (fitnessConstraintComparator == null) { + fitnessConstraintComparator = comparator; + } + } + + @Override + public boolean isHardObjective() { + return isThereFitnessConstraint; + } + + @Override + public boolean satisifiesHardObjective(Double fitness) { + if (isThereFitnessConstraint) { + int compare = fitnessConstraintComparator.compare(fitness, fitnessConstraint); + if (compare < 0) { + return false; + } + } + return true; + } + + @Override + public int hashCode() { + return name.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof BaseObjective) { + BaseObjective baseObjective = (BaseObjective) obj; + return name.equals(baseObjective.getName()); + } + return false; + } + + @Override + public String toString() { + return name; + } + +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/CompositeObjective.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/CompositeObjective.java new file mode 100644 index 00000000..cc48d22e --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/CompositeObjective.java @@ -0,0 +1,137 @@ +/******************************************************************************* + * Copyright (c) 2010-2014, Miklos Foldenyi, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi 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.objectives.impl; + +import java.util.ArrayList; +import java.util.List; +import java.util.Objects; + +import org.eclipse.viatra.dse.base.ThreadContext; +import org.eclipse.viatra.dse.objectives.IObjective; +import org.eclipse.viatra.query.runtime.matchers.util.Preconditions; + +/** + * This objective collects a list of other objectives. It returns the weighted sum of the objectives. + * + * @author Andras Szabolcs Nagy + * + */ +public class CompositeObjective extends BaseObjective { + + public static final String DEFAULT_NAME = "CompositeObjective"; + protected List objectives; + protected List weights; + protected boolean hardObjective; + + public CompositeObjective(String name, List objectives, List weights) { + super(name); + Objects.requireNonNull(objectives, "The list of objectives cannot be null."); + Objects.requireNonNull(weights, "The list of weights cannot be null."); + Preconditions.checkState(objectives.size() == weights.size(), "The size of the objectives and weights must match."); + this.objectives = objectives; + this.weights = weights; + } + + public CompositeObjective(List objectives, List weights) { + this(DEFAULT_NAME, objectives, weights); + } + + public CompositeObjective(String name) { + this(name, new ArrayList(), new ArrayList()); + } + + public CompositeObjective() { + this(DEFAULT_NAME, new ArrayList(), new ArrayList()); + } + + /** + * Adds a new objective. + * + * @param objective + * @return The actual instance to enable builder pattern like usage. + */ + public CompositeObjective withObjective(IObjective objective) { + objectives.add(objective); + weights.add(1d); + return this; + } + + /** + * Adds a new objective. + * + * @param objective + * @return The actual instance to enable builder pattern like usage. + */ + public CompositeObjective withObjective(IObjective objective, double weight) { + objectives.add(objective); + weights.add(weight); + return this; + } + + @Override + public Double getFitness(ThreadContext context) { + + double result = 0; + + for (int i = 0; i < objectives.size(); i++) { + IObjective objective = objectives.get(i); + Double weight = weights.get(i); + result += objective.getFitness(context) * weight; + } + return result; + } + + @Override + public void init(ThreadContext context) { + super.init(context); + hardObjective = false; + for (IObjective objective : objectives) { + objective.init(context); + if (objective.isHardObjective()) { + hardObjective = true; + } + } + } + + @Override + public IObjective createNew() { + + List newObjectives = new ArrayList(); + + for (IObjective objective : objectives) { + newObjectives.add(objective.createNew()); + } + + CompositeObjective objective = new CompositeObjective(name, newObjectives, weights); + if (isThereFitnessConstraint) { + objective.withHardConstraintOnFitness(fitnessConstraint, fitnessConstraintComparator); + } + + return objective.withComparator(comparator).withLevel(level); + } + + @Override + public boolean isHardObjective() { + return hardObjective; + } + + @Override + public boolean satisifiesHardObjective(Double fitness) { + + boolean hardObjectiveSatisfied = true; + + for (IObjective objective : objectives) { + hardObjectiveSatisfied = objective.satisifiesHardObjective(fitness) ? hardObjectiveSatisfied : false; + } + + hardObjectiveSatisfied = super.satisifiesHardObjective(fitness) ? hardObjectiveSatisfied : false; + + return hardObjectiveSatisfied; + } +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/ConstraintsObjective.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/ConstraintsObjective.java new file mode 100644 index 00000000..77d416f5 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/ConstraintsObjective.java @@ -0,0 +1,316 @@ +/******************************************************************************* + * Copyright (c) 2010-2016, Andras Szabolcs Nagy, Zoltan Ujhelyi 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.objectives.impl; + +import java.util.ArrayList; +import java.util.List; +import java.util.Objects; + +import org.eclipse.viatra.dse.api.DSEException; +import org.eclipse.viatra.dse.base.ThreadContext; +import org.eclipse.viatra.dse.objectives.IObjective; +import org.eclipse.viatra.query.runtime.api.IPatternMatch; +import org.eclipse.viatra.query.runtime.api.IQuerySpecification; +import org.eclipse.viatra.query.runtime.api.ViatraQueryEngine; +import org.eclipse.viatra.query.runtime.api.ViatraQueryMatcher; +import org.eclipse.viatra.query.runtime.exception.ViatraQueryException; + +/** + * This objective serves as soft and as hard objective at the same time by defining two lists of VIATRA Query + * specifications. + * + * As a soft objective, it collects a list of VIATRA Query specifications, which have predefined weights. Then the + * fitness value of an arbitrary solution is calculated in the following way: + *

+ * fitness = sum( pattern[i].countMatches() * weight[i] ) + *

+ * As a hard objective it collects a separate list of VIATRA Query specifications. If every one of them has a match the + * hard constraint is considered to be fulfilled. + * + * @author Andras Szabolcs Nagy + * @see IObjective + * + */ +public class ConstraintsObjective extends BaseObjective { + + public static final String DEFAULT_NAME = "ConstraintsObjective"; + + public static class QueryConstraint { + public final String name; + public final IQuerySpecification> query; + public final Double weight; + public final ModelQueryType type; + + public QueryConstraint(String name, + IQuerySpecification> query, Double weight, + ModelQueryType type) { + this.name = name; + this.query = query; + this.weight = weight; + this.type = type; + } + + public QueryConstraint(String name, + IQuerySpecification> query, Double weight) { + this(name, query, weight, ModelQueryType.MUST_HAVE_MATCH); + } + + public QueryConstraint(String name, + IQuerySpecification> query, ModelQueryType type) { + this(name, query, 0d, type); + } + } + + protected List softConstraints; + protected List hardConstraints; + + protected List> softMatchers; + protected List> hardMatchers; + protected List softMatches; + protected List hardMatches; + + public ConstraintsObjective(String name, List softConstraints, + List hardConstraints) { + super(name); + Objects.requireNonNull(softConstraints, "The list of soft constraints cannot be null."); + Objects.requireNonNull(hardConstraints, "The list of hard constraints cannot be null."); + + this.softConstraints = softConstraints; + this.hardConstraints = hardConstraints; + } + + public ConstraintsObjective(String name, List hardConstraints) { + this(name, new ArrayList(), hardConstraints); + } + + public ConstraintsObjective(List hardConstraints) { + this(DEFAULT_NAME, new ArrayList(), hardConstraints); + } + + public ConstraintsObjective(String name) { + this(name, new ArrayList(), new ArrayList()); + } + + public ConstraintsObjective() { + this(DEFAULT_NAME, new ArrayList(), new ArrayList()); + } + + /** + * Adds a new soft constraint. + * + * @param name + * A name for the soft constraint. + * @param softConstraint + * A VIATRA Query pattern specification. + * @param weight + * The weight of the pattern. + * @return The actual instance to enable builder pattern like usage. + */ + public ConstraintsObjective withSoftConstraint(String name, + IQuerySpecification> softConstraint, double weight) { + softConstraints.add(new QueryConstraint(name, softConstraint, weight)); + return this; + } + + /** + * Adds a new soft constraint with the name of the query specification's fully qualified name. + * + * @param softConstraint + * A VIATRA Query pattern specification. + * @param weight + * The weight of the pattern. + * @return The actual instance to enable builder pattern like usage. + */ + public ConstraintsObjective withSoftConstraint( + IQuerySpecification> softConstraint, double weight) { + return withSoftConstraint(softConstraint.getFullyQualifiedName(), softConstraint, weight); + } + + /** + * Adds a new hard constraint. + * + * @param name + * A name for the hard constraint. + * @param softConstraint + * A VIATRA Query pattern specification. + * @param type + * {@link ModelQueryType}, which determines whether the constraint should have at least one match or none + * at all. + * @return The actual instance to enable builder pattern like usage. + */ + public ConstraintsObjective withHardConstraint(String name, + IQuerySpecification> hardConstraint, + ModelQueryType type) { + hardConstraints.add(new QueryConstraint(name, hardConstraint, type)); + return this; + } + + /** + * Adds a new hard constraint with the default {@link ModelQueryType#MUST_HAVE_MATCH}. + * + * @param name + * A name for the hard constraint. + * @param softConstraint + * A VIATRA Query pattern specification. + * @return The actual instance to enable builder pattern like usage. + */ + public ConstraintsObjective withHardConstraint(String name, + IQuerySpecification> hardConstraint) { + hardConstraints.add(new QueryConstraint(name, hardConstraint, ModelQueryType.MUST_HAVE_MATCH)); + return this; + } + + /** + * Adds a new hard constraint with the name of the query specification's fully qualified name and the default + * {@link ModelQueryType#MUST_HAVE_MATCH}. + * + * @param softConstraint + * A VIATRA Query pattern specification. + * @return The actual instance to enable builder pattern like usage. + */ + public ConstraintsObjective withHardConstraint( + IQuerySpecification> hardConstraint) { + return withHardConstraint(hardConstraint.getFullyQualifiedName(), hardConstraint, + ModelQueryType.MUST_HAVE_MATCH); + } + + /** + * Adds a new hard constraint with the name of the query specification's fully qualified name. + * + * @param softConstraint + * A VIATRA Query pattern specification. + * @param type + * {@link ModelQueryType}, which determines whether the constraint should have at least one match or none + * at all. + * @return The actual instance to enable builder pattern like usage. + */ + public ConstraintsObjective withHardConstraint( + IQuerySpecification> hardConstraint, + ModelQueryType type) { + return withHardConstraint(hardConstraint.getFullyQualifiedName(), hardConstraint, type); + } + + @Override + public Double getFitness(ThreadContext context) { + + if (softConstraints.isEmpty()) { + return 0d; + } + + double result = 0; + + for (int i = 0; i < softConstraints.size(); i++) { + int countMatches = softMatchers.get(i).countMatches(); + result += countMatches * softConstraints.get(i).weight; + softMatches.set(i, Integer.valueOf(countMatches)); + } + + return result; + } + + @Override + public void init(ThreadContext context) { + + super.init(context); + + softMatches = new ArrayList(softConstraints.size()); + softMatchers = new ArrayList>(softConstraints.size()); + hardMatches = new ArrayList(hardConstraints.size()); + hardMatchers = new ArrayList>(hardConstraints.size()); + for (int i = 0; i < softConstraints.size(); i++) { + softMatches.add(0); + } + for (int i = 0; i < hardConstraints.size(); i++) { + hardMatches.add(0); + } + + try { + ViatraQueryEngine queryEngine = context.getQueryEngine(); + + for (QueryConstraint qc : softConstraints) { + softMatchers.add(qc.query.getMatcher(queryEngine)); + } + + for (QueryConstraint qc : hardConstraints) { + hardMatchers.add(qc.query.getMatcher(queryEngine)); + } + + } catch (ViatraQueryException e) { + throw new DSEException("Couldn't initialize the VIATRA Query matcher, see inner exception", e); + } + } + + @Override + public IObjective createNew() { + new ArrayList(softConstraints.size()); + ConstraintsObjective result = new ConstraintsObjective(name, softConstraints, hardConstraints); + if (isThereFitnessConstraint) { + result.withHardConstraintOnFitness(fitnessConstraint, fitnessConstraintComparator); + } + return result.withComparator(comparator).withLevel(level); + } + + @Override + public boolean isHardObjective() { + return !hardConstraints.isEmpty() || super.isHardObjective(); + } + + @Override + public boolean satisifiesHardObjective(Double fitness) { + + boolean result = true; + + for (int i = 0; i < hardConstraints.size(); i++) { + ModelQueryType type = hardConstraints.get(i).type; + int countMatches = hardMatchers.get(i).countMatches(); + hardMatches.set(i, Integer.valueOf(countMatches)); + if ((type.equals(ModelQueryType.MUST_HAVE_MATCH) && countMatches <= 0) + || (type.equals(ModelQueryType.NO_MATCH) && countMatches > 0)) { + result = false; + } + } + + result = super.satisifiesHardObjective(fitness) ? result : false; + + return result; + } + + public List getSoftConstraints() { + return softConstraints; + } + + public List getHardConstraints() { + return hardConstraints; + } + + public String getSoftName(int index) { + return softConstraints.get(index).name; + } + + public String getHardName(int index) { + return hardConstraints.get(index).name; + } + + public List getSoftMatches() { + return softMatches; + } + + public List getHardMatches() { + return hardMatches; + } + + public List getSoftNames() { + List softNames = new ArrayList<>(softConstraints.size()); + for (QueryConstraint qc : softConstraints) { + softNames.add(qc.name); + } + return softNames; + } + +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/DepthHardObjective.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/DepthHardObjective.java new file mode 100644 index 00000000..b21da397 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/DepthHardObjective.java @@ -0,0 +1,89 @@ +/******************************************************************************* + * Copyright (c) 2010-2016, Andras Szabolcs Nagy, Zoltan Ujhelyi 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.objectives.impl; + +import org.eclipse.viatra.dse.base.ThreadContext; +import org.eclipse.viatra.dse.objectives.IObjective; + +/** + * This hard objective is fulfilled if the trajectory is in the specified interval (inclusive). + * + * @author Andras Szabolcs Nagy + * + */ +public class DepthHardObjective extends BaseObjective { + + private static final String DEFAULT_NAME = "DepthHardObjective"; + protected int minDepth; + protected int maxDepth; + private ThreadContext context; + + public DepthHardObjective() { + this(DEFAULT_NAME, 0, Integer.MAX_VALUE); + } + + public DepthHardObjective(String name) { + this(name, 0, Integer.MAX_VALUE); + } + + public DepthHardObjective(int minDepth) { + this(DEFAULT_NAME, minDepth, Integer.MAX_VALUE); + } + + public DepthHardObjective(String name, int minDepth) { + this(name, minDepth, Integer.MAX_VALUE); + } + + public DepthHardObjective(int minDepth, int maxDepth) { + this(DEFAULT_NAME, minDepth, maxDepth); + } + + public DepthHardObjective(String name, int minDepth, int maxDepth) { + super(name); + this.minDepth = minDepth; + this.maxDepth = maxDepth; + } + + public DepthHardObjective withMinDepth(int minDepth) { + this.minDepth = minDepth; + return this; + } + + public DepthHardObjective withMaxDepth(int maxDepth) { + this.maxDepth = maxDepth; + return this; + } + + @Override + public void init(ThreadContext context) { + super.init(context); + this.context = context; + } + + @Override + public Double getFitness(ThreadContext context) { + return 0d; + } + + @Override + public boolean isHardObjective() { + return true; + } + + @Override + public boolean satisifiesHardObjective(Double fitness) { + return minDepth <= context.getDepth() && context.getDepth() <= maxDepth; + } + + @Override + public IObjective createNew() { + return new DepthHardObjective(name, minDepth, maxDepth); + } + +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/ModelQueriesGlobalConstraint.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/ModelQueriesGlobalConstraint.java new file mode 100644 index 00000000..7616b4a2 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/ModelQueriesGlobalConstraint.java @@ -0,0 +1,116 @@ +/******************************************************************************* + * Copyright (c) 2010-2014, Miklos Foldenyi, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi 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.objectives.impl; + +import java.util.ArrayList; +import java.util.List; +import java.util.Objects; + +import org.eclipse.viatra.dse.api.DSEException; +import org.eclipse.viatra.dse.base.ThreadContext; +import org.eclipse.viatra.dse.objectives.IGlobalConstraint; +import org.eclipse.viatra.query.runtime.api.IPatternMatch; +import org.eclipse.viatra.query.runtime.api.IQuerySpecification; +import org.eclipse.viatra.query.runtime.api.ViatraQueryEngine; +import org.eclipse.viatra.query.runtime.api.ViatraQueryMatcher; +import org.eclipse.viatra.query.runtime.exception.ViatraQueryException; + +/** + * This global constraint collects a list of VIATRA Query pattern and checks if any of them has a match on along a trajectory. + * If any of the patterns has a match then it is unsatisfied and the exploration should backtrack. + * + * @author Andras Szabolcs Nagy + * + */ +public class ModelQueriesGlobalConstraint implements IGlobalConstraint { + + public static final String GLOBAL_CONSTRAINT = "GlobalConstraint"; + protected String name; + protected List>> constraints; + protected List> matchers = new ArrayList>(); + protected ModelQueryType type = ModelQueryType.NO_MATCH; + + public ModelQueriesGlobalConstraint(String name, + List>> constraints) { + Objects.requireNonNull(name, "Name of the global constraint cannot be null."); + Objects.requireNonNull(constraints, "The list of constraints cannot be null."); + + this.name = name; + this.constraints = constraints; + } + + public ModelQueriesGlobalConstraint( + List>> constraints) { + this(GLOBAL_CONSTRAINT, constraints); + } + + public ModelQueriesGlobalConstraint(String name) { + this(name, new ArrayList>>()); + } + + public ModelQueriesGlobalConstraint() { + this(GLOBAL_CONSTRAINT, + new ArrayList>>()); + } + + /** + * Adds a new VIATRA Query pattern. + * + * @param constraint + * A VIATRA Query pattern. + * @return The actual instance to enable builder pattern like usage. + */ + public ModelQueriesGlobalConstraint withConstraint( + IQuerySpecification> constraint) { + constraints.add(constraint); + return this; + } + + public ModelQueriesGlobalConstraint withType(ModelQueryType type) { + this.type = type; + return this; + } + + @Override + public String getName() { + return name; + } + + @Override + public boolean checkGlobalConstraint(ThreadContext context) { + for (ViatraQueryMatcher matcher : matchers) { + if ((type.equals(ModelQueryType.NO_MATCH) && matcher.countMatches() > 0) + || (type.equals(ModelQueryType.MUST_HAVE_MATCH) && matcher.countMatches() == 0)) { + return false; + } + } + return true; + } + + @Override + public void init(ThreadContext context) { + try { + ViatraQueryEngine queryEngine = context.getQueryEngine(); + + for (IQuerySpecification> querySpecification : constraints) { + ViatraQueryMatcher matcher = querySpecification.getMatcher(queryEngine); + matchers.add(matcher); + } + + } catch (ViatraQueryException e) { + throw new DSEException("Couldn't get the VIATRA Query matcher, see inner exception", e); + } + } + + @Override + public IGlobalConstraint createNew() { + return new ModelQueriesGlobalConstraint(name, constraints); + } + +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/ModelQueryType.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/ModelQueryType.java new file mode 100644 index 00000000..76390352 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/ModelQueryType.java @@ -0,0 +1,14 @@ +/******************************************************************************* + * Copyright (c) 2010-2015, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi 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.objectives.impl; + +public enum ModelQueryType { + MUST_HAVE_MATCH, + NO_MATCH +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/NeverSatisfiedDummyHardObjective.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/NeverSatisfiedDummyHardObjective.java new file mode 100644 index 00000000..27cf139c --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/NeverSatisfiedDummyHardObjective.java @@ -0,0 +1,52 @@ +/******************************************************************************* + * 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.objectives.impl; + +import org.eclipse.viatra.dse.base.ThreadContext; +import org.eclipse.viatra.dse.objectives.IObjective; + +/** + * This hard objective is never fulfilled. Use it if all states should be regarded as an invalid solution. + * + * @author Andras Szabolcs Nagy + * + */ +public class NeverSatisfiedDummyHardObjective extends BaseObjective { + + private static final String DEFAULT_NAME = "NeverSatisfiedDummyHardObjective"; + + public NeverSatisfiedDummyHardObjective() { + super(DEFAULT_NAME); + } + + public NeverSatisfiedDummyHardObjective(String name) { + super(name); + } + + @Override + public Double getFitness(ThreadContext context) { + return 0d; + } + + @Override + public boolean isHardObjective() { + return true; + } + + @Override + public boolean satisifiesHardObjective(Double fitness) { + return false; + } + + @Override + public IObjective createNew() { + return this; + } + +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/NoRuleActivationsHardObjective.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/NoRuleActivationsHardObjective.java new file mode 100644 index 00000000..756d94ec --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/NoRuleActivationsHardObjective.java @@ -0,0 +1,59 @@ +/******************************************************************************* + * Copyright (c) 2010-2015, 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.objectives.impl; + +import org.eclipse.viatra.dse.base.ThreadContext; +import org.eclipse.viatra.dse.objectives.IObjective; + +/** + * This hard objective is satisfied if there are no rule activations from the current state (returning 1 in this case). + * + * @author Andras Szabolcs Nagy + * + */ +public class NoRuleActivationsHardObjective extends BaseObjective { + + protected static final String DEFAULT_NAME = "NoMoreActivationHardObjective"; + private ThreadContext context; + + public NoRuleActivationsHardObjective(String name) { + super(name); + } + + public NoRuleActivationsHardObjective() { + this(DEFAULT_NAME); + } + + @Override + public Double getFitness(ThreadContext context) { + return 0d; + } + + @Override + public void init(ThreadContext context) { + super.init(context); + this.context = context; + } + + @Override + public IObjective createNew() { + return new NoRuleActivationsHardObjective(name); + } + + @Override + public boolean isHardObjective() { + return true; + } + + @Override + public boolean satisifiesHardObjective(Double fitness) { + return context.getConflictSet().getNextActivations().isEmpty(); + } + +} diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/TrajectoryCostSoftObjective.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/TrajectoryCostSoftObjective.java new file mode 100644 index 00000000..25ff45ae --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/objectives/impl/TrajectoryCostSoftObjective.java @@ -0,0 +1,148 @@ +/******************************************************************************* + * Copyright (c) 2010-2014, Miklos Foldenyi, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi 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.objectives.impl; + +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Objects; + +import org.eclipse.viatra.dse.base.DesignSpaceManager; +import org.eclipse.viatra.dse.base.ThreadContext; +import org.eclipse.viatra.dse.designspace.api.TrajectoryInfo; +import org.eclipse.viatra.dse.objectives.ActivationFitnessProcessor; +import org.eclipse.viatra.dse.objectives.Comparators; +import org.eclipse.viatra.dse.objectives.IObjective; +import org.eclipse.viatra.query.runtime.matchers.util.Preconditions; +import org.eclipse.viatra.transformation.runtime.emf.rules.batch.BatchTransformationRule; + +/** + * This soft objective calculates a fitness value based on the length of the trajectory. Costs to the rules can be + * assigned. + * + * @author Andras Szabolcs Nagy + * + */ +public class TrajectoryCostSoftObjective extends BaseObjective { + + public static final String DEFAULT_NAME = "TrajectoryCostObjective"; + protected Map, Double> fixCosts; + protected Map, ActivationFitnessProcessor> activationCostProcessors; + protected double trajectoryLengthWeight = 0.0; + protected boolean calculateTrajectoryLengthWeight; + + public TrajectoryCostSoftObjective(String name) { + super(name); + comparator = Comparators.LOWER_IS_BETTER; + } + + public TrajectoryCostSoftObjective() { + this(DEFAULT_NAME); + } + + /** + * Sets the cost of a rule. + * + * @param rule + * @param cost + * @return The actual instance to enable builder pattern like usage. + */ + public TrajectoryCostSoftObjective withRuleCost(BatchTransformationRule rule, double cost) { + Objects.requireNonNull(rule); + if (fixCosts == null) { + fixCosts = new HashMap, Double>(); + } + Preconditions.checkArgument(!fixCosts.containsKey(rule)); + fixCosts.put(rule, cost); + return this; + } + + /** + * Sets an activation processor for a rule. + * + * @param rule + * @param activationCostProcessor + * @return The actual instance to enable builder pattern like usage. + */ + public TrajectoryCostSoftObjective withActivationCost(BatchTransformationRule rule, + ActivationFitnessProcessor activationCostProcessor) { + Objects.requireNonNull(rule); + Objects.requireNonNull(activationCostProcessor); + if (activationCostProcessors == null) { + activationCostProcessors = new HashMap, ActivationFitnessProcessor>(); + } + Preconditions.checkArgument(!activationCostProcessors.containsKey(rule)); + activationCostProcessors.put(rule, activationCostProcessor); + return this; + } + + /** + * The length of the trajectory multiplied with given parameter will be added to the fitness value. + * + * @param trajectoryLengthWeight + * The weight of a transformation rule application. + * @return The actual instance to enable builder pattern like usage. + */ + public TrajectoryCostSoftObjective withTrajectoryLengthWeight(double trajectoryLengthWeight) { + this.trajectoryLengthWeight = trajectoryLengthWeight; + this.calculateTrajectoryLengthWeight = true; + return this; + } + + @Override + public Double getFitness(ThreadContext context) { + + DesignSpaceManager dsm = context.getDesignSpaceManager(); + TrajectoryInfo trajectoryInfo = dsm.getTrajectoryInfo(); + List trajectory = trajectoryInfo.getTrajectory(); + List> rules = trajectoryInfo.getRules(); + + double result = 0; + + for (int i = 0; i < trajectory.size(); i++) { + BatchTransformationRule rule = rules.get(i); + + Double cost = fixCosts.get(rule); + if (cost != null) { + result += cost; + } + + Map costs = trajectoryInfo.getMeasuredCosts().get(i); + if (costs != null) { + cost = costs.get(name); + if (cost != null) { + result += cost; + } + } + } + + if (calculateTrajectoryLengthWeight) { + result += trajectory.size() * trajectoryLengthWeight; + } + + return result; + } + + @Override + public void init(ThreadContext context) { + super.init(context); + DesignSpaceManager dsm = context.getDesignSpaceManager(); + if (activationCostProcessors != null) { + for (Entry, ActivationFitnessProcessor> entry : activationCostProcessors.entrySet()) { + dsm.registerActivationCostProcessor(name, entry.getKey(), entry.getValue()); + } + } + } + + @Override + public IObjective createNew() { + return this; + } +} -- cgit v1.2.3-70-g09d2