Changeset 8846

Timestamp:

10/24/12 17:16:49 (12 years ago)

Author:

abeham

Message:

#1904: Added fast evaluation option to exhaustive swap2 local improvement operator

File:

• trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPExhaustiveSwap2LocalImprovement.cs (modified) (5 diffs)

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPExhaustiveSwap2LocalImprovement.cs

@@ -81 +81 @@
     public ILookupParameter<DoubleMatrix> DistancesParameter {
       get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
+    }
+
+    public IValueLookupParameter<BoolValue> UseFastEvaluationParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["UseFastEvaluation"]; }
     }
 
@@ -100 +104 @@
       Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix."));
       Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix."));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("UseFastEvaluation", "Enabling this option will use a NxN double matrix to save the last move qualities. The moves of the first iteration will then be evaluated in O(N) while all further moves will be evaluated in O(1).", new BoolValue(true)));
     }
 
@@ -112 +117 @@
       if (!Parameters.ContainsKey("LocalIterations"))
         Parameters.Add(new LookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed."));
+      if (!Parameters.ContainsKey("UseFastEvaluation"))
+        Parameters.Add(new ValueLookupParameter<BoolValue>("UseFastEvaluation", "Enabling this option will use a NxN double matrix to save the last move qualities. The moves of the first iteration will then be evaluated in O(N) while all further moves will be evaluated in O(1).", new BoolValue(false)));
     }
     #endregion
@@ -140 +147 @@
     }
 
+    public static void ImproveFast(Permutation assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation) {
+      Swap2Move bestMove = null;
+      double evaluations = 0.0;
+      var lastQuality = new double[assignment.Length, assignment.Length];
+      for (int i = localIterations.Value; i < maxIterations; i++) {
+        double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
+        var lastMove = bestMove;
+        bestMove = null;
+        foreach (Swap2Move move in ExhaustiveSwap2MoveGenerator.Generate(assignment)) {
+          double moveQuality;
+          if (lastMove == null) {
+            moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, weights, distances);
+            evaluations += 4.0 / assignment.Length;
+          } else {
+            moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, lastQuality[move.Index1, move.Index2], weights, distances, lastMove);
+            if (move.Index1 == lastMove.Index1 || move.Index2 == lastMove.Index1 || move.Index1 == lastMove.Index2 || move.Index2 == lastMove.Index2)
+              evaluations += 4.0 / assignment.Length;
+            else evaluations += 2.0 / (assignment.Length * assignment.Length);
+          }
+          lastQuality[move.Index1, move.Index2] = moveQuality;
+          if (maximization && moveQuality > bestQuality
+            || !maximization && moveQuality < bestQuality) {
+            bestQuality = moveQuality;
+            bestMove = move;
+          }
+        }
+        if (bestMove == null) break;
+        Swap2Manipulator.Apply(assignment, bestMove.Index1, bestMove.Index2);
+        quality.Value += bestQuality;
+        localIterations.Value++;
+        if (cancellation.IsCancellationRequested) {
+          evaluatedSolutions.Value += (int)Math.Round(evaluations);
+          throw new OperationCanceledException();
+        }
+      }
+      evaluatedSolutions.Value += (int)Math.Round(evaluations);
+    }
+
     public override IOperation Apply() {
       var maxIterations = MaximumIterationsParameter.ActualValue.Value;
@@ -154 +199 @@
       }
 
-      Improve(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);
+      if (UseFastEvaluationParameter.ActualValue.Value)
+        ImproveFast(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);
+      else Improve(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);
+
       return base.Apply();
     }