Changeset 8910 for trunk/sources/HeuristicLab.Problems.QuadraticAssignment

Timestamp:

11/14/12 11:19:36 (12 years ago)

Author:

abeham

Message:

#1841:

• Corrected best known solutions in new taillard and microarray instances
• Improved computation of an average fitness in the QAP

Location:

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3

Files:

• BoundsCalculators/GilmoreLawlerBoundCalculator.cs (modified) (3 diffs)
• QuadraticAssignmentProblem.cs (modified) (2 diffs)

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/BoundsCalculators/GilmoreLawlerBoundCalculator.cs

@@ -22 +22 @@
 using System;
 using HeuristicLab.Data;
+using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Problems.LinearAssignment;
 
@@ -27 +28 @@
   public static class GilmoreLawlerBoundCalculator {
     public static double CalculateLowerBound(DoubleMatrix weights, DoubleMatrix distances) {
+      Permutation tmp;
+      return CalculateLowerBound(weights, distances, out tmp);
+    }
+
+    public static double CalculateLowerBound(DoubleMatrix weights, DoubleMatrix distances, out Permutation solution) {
       int N = weights.Rows;
       DoubleMatrix sortedWeights = SortEachRowExceptDiagonal(weights), sortedDistances = SortEachRowExceptDiagonal(distances);
@@ -40 +46 @@
 
       double result;
-      LinearAssignmentProblemSolver.Solve(costs, out result);
+      solution = new Permutation(PermutationTypes.Absolute, LinearAssignmentProblemSolver.Solve(costs, out result));
       return result;
     }

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs

@@ -177 +177 @@
       if (!Parameters.ContainsKey("AverageQuality")) {
         Parameters.Add(new OptionalValueParameter<DoubleValue>("AverageQuality", "The expected quality of a random solution."));
-        AverageQuality = new DoubleValue(Weights.Average() * Distances.Average() * Weights.Rows * Weights.Rows);
+        AverageQuality = new DoubleValue(ComputeAverageQuality());
       }
       #endregion
@@ -401 +401 @@
 
     private void UpdateParameterValues() {
-      LowerBound = new DoubleValue(GilmoreLawlerBoundCalculator.CalculateLowerBound(Weights, Distances));
-      AverageQuality = new DoubleValue(Weights.Average() * Distances.Average() * Weights.Rows * Weights.Rows);
+      Permutation lbSolution;
+      // calculate the optimum of a LAP relaxation and use it as lower bound of our QAP
+      LowerBound = new DoubleValue(GilmoreLawlerBoundCalculator.CalculateLowerBound(Weights, Distances, out lbSolution));
+      // evalute the LAP optimal solution as if it was a QAP solution
+      var lbSolutionQuality = QAPEvaluator.Apply(lbSolution, Weights, Distances);
+      // in case both qualities are the same it means that the LAP optimum is also a QAP optimum
+      if (LowerBound.Value.IsAlmost(lbSolutionQuality)) {
+        BestKnownSolution = lbSolution;
+        BestKnownQuality = new DoubleValue(LowerBound.Value);
+      }
+      AverageQuality = new DoubleValue(ComputeAverageQuality());
+    }
+
+    private double ComputeAverageQuality() {
+      double rt = 0, rd = 0, wt = 0, wd = 0;
+      int n = Weights.Rows;
+      for (int i = 0; i < n; i++)
+        for (int j = 0; j < n; j++) {
+          if (i == j) {
+            rd += Distances[i, i];
+            wd += Weights[i, i];
+          } else {
+            rt += Distances[i, j];
+            wt += Weights[i, j];
+          }
+        }
+
+      return rt * wt / (n * (n - 1)) + rd * wd / n;
     }
     #endregion