Changeset 6586 for branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment

Timestamp:

07/22/11 12:03:36 (13 years ago)

Author:

abeham

Message:

#1541

• Updated code to reflect what Eric Taillard's code does at ​http://mistic.heig-vd.ch/taillard/codes.dir/tabou_qap.cpp which is however not quite what is described in the paper.
• Updated the swap2 move evaluator to perform move evaluations in O(1) for several cases by memorizing the move quality of the previous iteration
• Added a unit test to test the new faster evaluation
• Changed the robust taboo search to use this faster evaluation
• Renamed some operators (dropping the QAP pre- and postfix)

Location:

branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment/3.3

Files:

• Evaluators/QAPSwap2MoveEvaluator.cs (modified) (2 diffs)
• Tests/QAPMoveEvaluatorTest.cs (modified) (1 diff)

branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment/3.3/Evaluators/QAPSwap2MoveEvaluator.cs

@@ -49 +49 @@
     }
 
+    /// <summary>
+    /// Calculates the quality of the move <paramref name="move"/> by evaluating the changes.
+    /// The runtime complexity of this method is O(N) with N being the size of the permutation.
+    /// </summary>
+    /// <param name="assignment">The current permutation.</param>
+    /// <param name="move">The move that is to be evaluated if it was applied to the current permutation.</param>
+    /// <param name="weights">The weights matrix.</param>
+    /// <param name="distances">The distances matrix.</param>
+    /// <returns>The relative change in quality if <paramref name="move"/> was applied to <paramref name="assignment"/>.</returns>
     public static double Apply(Permutation assignment, Swap2Move move, DoubleMatrix weights, DoubleMatrix distances) {
       if (move.Index1 == move.Index2) return 0;
@@ -73 +82 @@
     }
 
+    /// <summary>
+    /// Is able to compute the move qualities faster O(1) in some cases if it knows the quality of
+    /// performing the move <paramref name="move"/> previously. In other cases it performs a
+    /// standard move quality calculation with runtime complexity O(N).
+    /// </summary>
+    /// <remarks>
+    /// The number of cases that the calculation can be performed faster grows with N^2
+    /// while the number of cases which require a larger recalculation grows linearly with N.
+    /// Larger problem instances thus benefit from this faster method to a larger degree.
+    /// </remarks>
+    /// <param name="assignment">The current permutation.</param>
+    /// <param name="move">The current move that is to be evaluated.</param>
+    /// <param name="previousQuality">The quality of that move as evaluated for the previous permutation.</param>
+    /// <param name="weights">The weigths matrix.</param>
+    /// <param name="distances">The distances matrix.</param>
+    /// <param name="lastMove">The move that was applied to transform the permutation from the previous to the current one.</param>
+    /// <returns>The relative change in quality if <paramref name="move"/> was applied to <paramref name="assignment"/>.</returns>
+    public static double Apply(Permutation assignment, Swap2Move move, double previousQuality,
+      DoubleMatrix weights, DoubleMatrix distances, Swap2Move lastMove) {
+      bool overlapsLastMove = move.Index1 == lastMove.Index1
+                           || move.Index2 == lastMove.Index1
+                           || move.Index1 == lastMove.Index2
+                           || move.Index2 == lastMove.Index2;
+
+      if (!overlapsLastMove) {
+        int r = lastMove.Index1, u = move.Index1, s = lastMove.Index2, v = move.Index2;
+        int pR = assignment[lastMove.Index1], pU = assignment[move.Index1], pS = assignment[lastMove.Index2], pV = assignment[move.Index2];
+
+        return previousQuality
+          + (weights[r, u] - weights[r, v] + weights[s, v] - weights[s, u])
+            * (distances[pS, pU] - distances[pS, pV] + distances[pR, pV] - distances[pR, pU])
+          + (weights[u, r] - weights[v, r] + weights[v, s] - weights[u, s])
+            * (distances[pU, pS] - distances[pV, pS] + distances[pV, pR] - distances[pU, pR]);
+      } else {
+        return Apply(assignment, move, weights, distances);
+      }
+    }
+
     public override IOperation Apply() {
       Swap2Move move = Swap2MoveParameter.ActualValue;

branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment/3.3/Tests/QAPMoveEvaluatorTest.cs

@@ -60 +60 @@
       for (int i = 0; i < ProblemSize - 1; i++) {
         for (int j = i + 1; j < ProblemSize; j++) {
-          symmetricDistances[i, j] = random.Next(ProblemSize);
+          symmetricDistances[i, j] = random.Next(ProblemSize * 100);
           symmetricDistances[j, i] = symmetricDistances[i, j];
-          symmetricWeights[i, j] = random.Next(ProblemSize);
+          symmetricWeights[i, j] = random.Next(ProblemSize * 100);
           symmetricWeights[j, i] = symmetricWeights[i, j];
-          asymmetricDistances[i, j] = random.Next(ProblemSize);
-          asymmetricDistances[j, i] = random.Next(ProblemSize);
-          asymmetricWeights[i, j] = random.Next(ProblemSize);
-          asymmetricWeights[j, i] = random.Next(ProblemSize);
-          nonZeroDiagonalDistances[i, j] = random.Next(ProblemSize);
-          nonZeroDiagonalDistances[j, i] = random.Next(ProblemSize);
-          nonZeroDiagonalWeights[i, j] = random.Next(ProblemSize);
-          nonZeroDiagonalWeights[j, i] = random.Next(ProblemSize);
+          asymmetricDistances[i, j] = random.Next(ProblemSize * 100);
+          asymmetricDistances[j, i] = random.Next(ProblemSize * 100);
+          asymmetricWeights[i, j] = random.Next(ProblemSize * 100);
+          asymmetricWeights[j, i] = random.Next(ProblemSize * 100);
+          nonZeroDiagonalDistances[i, j] = random.Next(ProblemSize * 100);
+          nonZeroDiagonalDistances[j, i] = random.Next(ProblemSize * 100);
+          nonZeroDiagonalWeights[i, j] = random.Next(ProblemSize * 100);
+          nonZeroDiagonalWeights[j, i] = random.Next(ProblemSize * 100);
         }
-        nonZeroDiagonalDistances[i, i] = random.Next(ProblemSize);
-        nonZeroDiagonalWeights[i, i] = random.Next(ProblemSize);
+        nonZeroDiagonalDistances[i, i] = random.Next(ProblemSize * 100);
+        nonZeroDiagonalWeights[i, i] = random.Next(ProblemSize * 100);
       }
       int index = random.Next(ProblemSize);
       if (nonZeroDiagonalDistances[index, index] == 0)
-        nonZeroDiagonalDistances[index, index] = random.Next(1, ProblemSize);
+        nonZeroDiagonalDistances[index, index] = random.Next(1, ProblemSize * 100);
       index = random.Next(ProblemSize);
       if (nonZeroDiagonalWeights[index, index] == 0)
-        nonZeroDiagonalWeights[index, index] = random.Next(1, ProblemSize);
+        nonZeroDiagonalWeights[index, index] = random.Next(1, ProblemSize * 100);
       assignment = new Permutation(PermutationTypes.Absolute, ProblemSize, random);
+    }
+
+    [TestMethod]
+    public void Swap2MoveEvaluatorFastEvaluationTest() {
+
+      for (int i = 0; i < 500; i++) {
+        Swap2Move lastMove = new Swap2Move(random.Next(ProblemSize), random.Next(ProblemSize));
+        Permutation prevAssignment = (Permutation)assignment.Clone();
+        Swap2Manipulator.Apply(assignment, lastMove.Index1, lastMove.Index2);
+        Permutation nextAssignment = (Permutation)assignment.Clone();
+        Swap2Move currentMove = new Swap2Move(random.Next(ProblemSize), random.Next(ProblemSize));
+        Swap2Manipulator.Apply(nextAssignment, currentMove.Index1, currentMove.Index2);
+
+        double moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, symmetricWeights, symmetricDistances);
+        double moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
+                moveBefore, symmetricWeights, symmetricDistances, lastMove);
+        double before = QAPEvaluator.Apply(assignment, symmetricWeights, symmetricDistances);
+        double after = QAPEvaluator.Apply(nextAssignment, symmetricWeights, symmetricDistances);
+
+        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on symmetric matrices: " + Environment.NewLine
+          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
+
+        moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, asymmetricWeights, asymmetricDistances);
+        moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
+                moveBefore, asymmetricWeights, asymmetricDistances, lastMove);
+        before = QAPEvaluator.Apply(assignment, asymmetricWeights, asymmetricDistances);
+        after = QAPEvaluator.Apply(nextAssignment, asymmetricWeights, asymmetricDistances);
+
+        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on asymmetric matrices: " + Environment.NewLine
+          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
+
+        moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
+        moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
+                moveBefore, nonZeroDiagonalWeights, nonZeroDiagonalDistances, lastMove);
+        before = QAPEvaluator.Apply(assignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
+        after = QAPEvaluator.Apply(nextAssignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
+
+        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on non-zero diagonal matrices: " + Environment.NewLine
+          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
+      }
     }