Changeset 8910

Timestamp:

11/14/12 11:19:36 (11 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

Files:

• HeuristicLab.Problems.Instances.QAPLIB/3.3/Data/microarray.sln.zip (modified) (previous)
• HeuristicLab.Problems.Instances.QAPLIB/3.3/Data/taillard.sln.zip (modified) (previous)
• HeuristicLab.Problems.Instances.QAPLIB/3.3/QAPLIBInstanceProvider.cs (modified) (2 diffs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/BoundsCalculators/GilmoreLawlerBoundCalculator.cs (modified) (3 diffs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs (modified) (2 diffs)

trunk/sources/HeuristicLab.Problems.Instances.QAPLIB/3.3/QAPLIBInstanceProvider.cs

@@ -32 +32 @@
     #region Reversed instances
     // These instances specified their best known solution in the wrong order
-    private static HashSet<string> reversedSolutions = new HashSet<string>(new string[] {
-      "bur26a",
-      "bur26b",
-      "bur26c",
-      "bur26d",
-      "bur26e",
-      "bur26f",
-      "bur26g",
-      "bur26h",
-      "chr12a",
-      "chr12b",
-      "chr12c",
-      "chr15a",
-      "chr15b",
-      "chr15c",
-      "chr18a",
-      "chr18b",
-      "chr20a",
-      "chr20b",
-      "chr20c",
-      "chr22a",
-      "chr22b",
-      "chr25a",
-      "esc16a",
-      "esc16b",
-      "esc16c",
-      "esc16d",
-      "esc16e",
-      "esc16g",
-      "esc16h",
-      "esc16i",
-      "esc16j",
-      "esc32a",
-      "esc32b",
-      "esc32c",
-      "esc32d",
-      "esc32e",
-      "esc32f",
-      "esc32g",
-      "esc32h",
-      "had12",
-      "had14",
-      "had16",
-      "had18",
-      "had20",
-      "kra32",
-      "lipa20a",
-      "lipa30a",
-      "lipa40a",
-      "lipa50a",
-      "lipa60a",
-      "lipa70a",
-      "lipa80a",
-      "lipa90a",
-      "nug12",
-      "nug14",
-      "nug15",
-      "nug16a",
-      "nug16b",
-      "nug17",
-      "nug18",
-      "nug20",
-      "nug21",
-      "nug22",
-      "nug24",
-      "nug25",
-      "nug27",
-      "nug28",
-      "rou12",
-      "rou15",
-      "rou20",
-      "scr12",
-      "scr15",
-      "scr20",
-      "sko100a",
-      "sko100b",
-      "sko100c",
-      "sko100d",
-      "sko100e",
-      "sko100f",
-      "sko49",
-      "sko81",
-      "sko90",
-      "ste36a",
-      "ste36b",
-      "tai100a",
-      "tai100b",
-      "tai12a",
-      "tai12b",
-      "tai150b",
-      "tai15a",
-      "tai15b",
-      "tai17a",
-      "tai20a",
-      "tai20b",
-      "tai256c",
-      "tai25a",
-      "tai25b",
-      "tai30a",
-      "tai30b",
-      "tai35a",
-      "tai35b",
-      "tai40a",
-      "tai40b",
-      "tai50a",
-      "tai50b",
-      "tai60a",
-      "tai60b",
-      "tai64c",
-      "tai80a",
-      "tai80b",
-      "wil100"
-    });
+    protected virtual HashSet<string> ReversedSolutions {
+      get {
+            return new HashSet<string>(new string[] {
+              "bur26a",
+              "bur26b",
+              "bur26c",
+              "bur26d",
+              "bur26e",
+              "bur26f",
+              "bur26g",
+              "bur26h",
+              "chr12a",
+              "chr12b",
+              "chr12c",
+              "chr15a",
+              "chr15b",
+              "chr15c",
+              "chr18a",
+              "chr18b",
+              "chr20a",
+              "chr20b",
+              "chr20c",
+              "chr22a",
+              "chr22b",
+              "chr25a",
+              "esc16a",
+              "esc16b",
+              "esc16c",
+              "esc16d",
+              "esc16e",
+              "esc16g",
+              "esc16h",
+              "esc16i",
+              "esc16j",
+              "esc32a",
+              "esc32b",
+              "esc32c",
+              "esc32d",
+              "esc32e",
+              "esc32f",
+              "esc32g",
+              "esc32h",
+              "had12",
+              "had14",
+              "had16",
+              "had18",
+              "had20",
+              "kra32",
+              "lipa20a",
+              "lipa30a",
+              "lipa40a",
+              "lipa50a",
+              "lipa60a",
+              "lipa70a",
+              "lipa80a",
+              "lipa90a",
+              "nug12",
+              "nug14",
+              "nug15",
+              "nug16a",
+              "nug16b",
+              "nug17",
+              "nug18",
+              "nug20",
+              "nug21",
+              "nug22",
+              "nug24",
+              "nug25",
+              "nug27",
+              "nug28",
+              "rou12",
+              "rou15",
+              "rou20",
+              "scr12",
+              "scr15",
+              "scr20",
+              "sko100a",
+              "sko100b",
+              "sko100c",
+              "sko100d",
+              "sko100e",
+              "sko100f",
+              "sko49",
+              "sko81",
+              "sko90",
+              "ste36a",
+              "ste36b",
+              "tai100a",
+              "tai100b",
+              "tai12a",
+              "tai12b",
+              "tai150b",
+              "tai15a",
+              "tai15b",
+              "tai17a",
+              "tai20a",
+              "tai20b",
+              "tai256c",
+              "tai25a",
+              "tai25b",
+              "tai30a",
+              "tai30b",
+              "tai35a",
+              "tai35b",
+              "tai40a",
+              "tai40b",
+              "tai50a",
+              "tai50b",
+              "tai60a",
+              "tai60b",
+              "tai64c",
+              "tai80a",
+              "tai80b",
+              "wil100"
+        });
+      }
+    }
     #endregion
 
@@ -211 +215 @@
 
                 int[] assignment = slnParser.Assignment;
-                if (assignment != null && reversedSolutions.Contains(instance.Name)) {
+                if (assignment != null && ReversedSolutions.Contains(instance.Name)) {
                   assignment = (int[])slnParser.Assignment.Clone();
                   for (int i = 0; i < assignment.Length; i++)

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