Add best first strategy

2 files changed, 260 insertions, 0 deletions

diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/dse/objectives/TrajectoryFitness.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/dse/objectives/TrajectoryFitness.java
new file mode 100644
index 00000000..b9ff7067
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/dse/objectives/TrajectoryFitness.java
@@ -0,0 +1,71 @@
+/*******************************************************************************

+ * 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 tools.refinery.store.query.dse.objectives;

+

+import java.util.Arrays;

+

+

+/**

+ * 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 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/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/dse/strategy/BestFirstStrategy.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/dse/strategy/BestFirstStrategy.java
new file mode 100644
index 00000000..62adb72f
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/dse/strategy/BestFirstStrategy.java
@@ -0,0 +1,189 @@
+package tools.refinery.store.query.dse.strategy;
+
+import tools.refinery.store.query.dse.DesignSpaceExplorationAdapter;
+import tools.refinery.store.query.dse.Strategy;
+import tools.refinery.store.query.dse.internal.Activation;
+import tools.refinery.store.query.dse.objectives.Fitness;
+import tools.refinery.store.query.dse.objectives.ObjectiveComparatorHelper;
+
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+import java.util.PriorityQueue;
+
+public class BestFirstStrategy implements Strategy {
+
+        private DesignSpaceExplorationAdapter dseAdapter;
+
+        private int maxDepth;
+        private boolean backTrackIfSolution = true;
+        private boolean onlyBetterFirst = false;
+
+        private PriorityQueue<TrajectoryWithFitness> trajectoriesToExplore;
+
+        private static class TrajectoryWithFitness {
+
+                public List<Long> trajectory;
+                public Fitness fitness;
+
+                public TrajectoryWithFitness(List<Long> trajectory, Fitness fitness) {
+                        super();
+                        this.trajectory = trajectory;
+                        this.fitness = fitness;
+                }
+
+                @Override
+                public String toString() {
+                        return trajectory.toString() + fitness.toString();
+                }
+
+        }
+
+        public BestFirstStrategy() {
+                this(-1);
+        }
+
+        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(DesignSpaceExplorationAdapter designSpaceExplorationAdapter) {
+                this.dseAdapter = designSpaceExplorationAdapter;
+                final ObjectiveComparatorHelper objectiveComparatorHelper = dseAdapter.getObjectiveComparatorHelper();
+
+                trajectoriesToExplore = new PriorityQueue<TrajectoryWithFitness>(11,
+                                (o1, o2) -> objectiveComparatorHelper.compare(o2.fitness, o1.fitness));
+        }
+
+        @Override
+        public void explore() {
+                final ObjectiveComparatorHelper objectiveComparatorHelper = dseAdapter.getObjectiveComparatorHelper();
+
+                boolean globalConstraintsAreSatisfied = dseAdapter.checkGlobalConstraints();
+                if (!globalConstraintsAreSatisfied) {
+                        // "Global constraint is not satisfied in the first state. Terminate.");
+                        return;
+                }
+
+                final Fitness firstFitness = dseAdapter.calculateFitness();
+                if (firstFitness.isSatisfiesHardObjectives()) {
+                        dseAdapter.newSolution();
+                        // "First state is a solution. Terminate.");
+                        if (backTrackIfSolution) {
+                                return;
+                        }
+                }
+
+                if (maxDepth == 0) {
+                        return;
+                }
+
+                final List<Long> firstTrajectory = dseAdapter.getTrajectory();
+                TrajectoryWithFitness currentTrajectoryWithFitness = new TrajectoryWithFitness(firstTrajectory, firstFitness);
+                trajectoriesToExplore.add(currentTrajectoryWithFitness);
+
+                mainLoop: while (true) {
+
+                        if (currentTrajectoryWithFitness == null) {
+                                if (trajectoriesToExplore.isEmpty()) {
+                                        // "State space is fully traversed.");
+                                        return;
+                                } else {
+                                        currentTrajectoryWithFitness = trajectoriesToExplore.element();
+//                                      if (logger.isDebugEnabled()) {
+//                                               "New trajectory is chosen: " + currentTrajectoryWithFitness);
+//                                      }
+                                        dseAdapter.restoreTrajectory(currentTrajectoryWithFitness.trajectory);
+                                }
+                        }
+
+                        Collection<Activation> activations = dseAdapter.getUntraversedActivations();
+                        Iterator<Activation> iterator = activations.iterator();
+
+
+
+                        while (iterator.hasNext()) {
+                                final Activation nextActivation = iterator.next();
+                                if (!iterator.hasNext()) {
+                                        // "Last untraversed activation of the state.");
+                                        trajectoriesToExplore.remove(currentTrajectoryWithFitness);
+                                }
+
+//                              if (logger.isDebugEnabled()) {
+//                                       "Executing new activation: " + nextActivation);
+//                              }
+                                dseAdapter.fireActivation(nextActivation);
+                                if (dseAdapter.isCurrentStateAlreadyTraversed()) {
+                                        // "The new state is already visited.");
+                                        dseAdapter.backtrack();
+                                } else if (!dseAdapter.checkGlobalConstraints()) {
+                                        // "Global constraint is not satisfied.");
+                                        dseAdapter.backtrack();
+                                } else {
+                                        final Fitness nextFitness = dseAdapter.calculateFitness();
+                                        if (nextFitness.isSatisfiesHardObjectives()) {
+                                                dseAdapter.newSolution();
+                                                // "Found a solution.");
+                                                if (backTrackIfSolution) {
+                                                        dseAdapter.backtrack();
+                                                        continue;
+                                                }
+                                        }
+                                        if (dseAdapter.getDepth() >= maxDepth) {
+                                                // "Reached max depth.");
+                                                dseAdapter.backtrack();
+                                                continue;
+                                        }
+
+                                        TrajectoryWithFitness nextTrajectoryWithFitness = new TrajectoryWithFitness(
+                                                        dseAdapter.getTrajectory(), nextFitness);
+                                        trajectoriesToExplore.add(nextTrajectoryWithFitness);
+
+                                        int compare = objectiveComparatorHelper.compare(currentTrajectoryWithFitness.fitness,
+                                                        nextTrajectoryWithFitness.fitness);
+                                        if (compare < 0) {
+                                                // "Better fitness, moving on: " + nextFitness);
+                                                currentTrajectoryWithFitness = nextTrajectoryWithFitness;
+                                                continue mainLoop;
+                                        } else if (compare == 0) {
+                                                if (onlyBetterFirst) {
+                                                        // "Equally good fitness, backtrack: " + nextFitness);
+                                                        dseAdapter.backtrack();
+                                                        continue;
+                                                } else {
+                                                        // "Equally good fitness, moving on: " + nextFitness);
+                                                        currentTrajectoryWithFitness = nextTrajectoryWithFitness;
+                                                        continue mainLoop;
+                                                }
+                                        } else {
+                                                // "Worse fitness.");
+                                                currentTrajectoryWithFitness = null;
+                                                continue mainLoop;
+                                        }
+                                }
+                        }
+
+                        // "State is fully traversed.");
+                        trajectoriesToExplore.remove(currentTrajectoryWithFitness);
+                        currentTrajectoryWithFitness = null;
+
+                }
+                // "Interrupted.");
+
+        }
+}