Changeset 5598 for branches/QAP/HeuristicLab.Problems.QuadraticAssignment

Timestamp:

03/02/11 22:33:30 (14 years ago)

Author:

abeham

Message:

#1330

• Updated solution view
• Made distance matrix a mandatory parameter (solution instances are small anyway)
• Added and set best known solution if available for a QAPLIB instance

Location:

branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3

Files:

• Evaluators/QAPEvaluator.cs (modified) (5 diffs)
• HeuristicLab.Problems.QuadraticAssignment-3.3.csproj (modified) (1 diff)
• Interfaces/IQAPEvaluator.cs (modified) (1 diff)
• Parsers/QAPLIBSolutionParser.cs (added)
• QuadraticAssignmentProblem.cs (modified) (9 diffs)

branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/Evaluators/QAPEvaluator.cs

@@ -20 +20 @@
 #endregion
 
-using System;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -35 +34 @@
     public ILookupParameter<Permutation> PermutationParameter {
       get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
-    }
-    public ILookupParameter<BoolValue> UseDistanceMatrixParameter {
-      get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
     }
     public ILookupParameter<DoubleMatrix> DistanceMatrixParameter {
@@ -57 +53 @@
     public QAPEvaluator() {
       Parameters.Add(new LookupParameter<Permutation>("Permutation", "The permutation that represents the current solution."));
-      Parameters.Add(new ValueLookupParameter<BoolValue>("UseDistanceMatrix", "True if the distance matrix should be used, false if the distances should be caluclated by taking the euclidean distance between the coordinates."));
       Parameters.Add(new LookupParameter<DoubleMatrix>("DistanceMatrix", "The distance matrix that contains the distances between the locations."));
       Parameters.Add(new LookupParameter<DoubleMatrix>("Coordinates", "The coordinates in case the distance matrix should not be used."));
@@ -68 +63 @@
     }
 
-    public static double Apply(Permutation assignment, DoubleMatrix weights, Func<int, int, double> distance) {
+    public static double Apply(Permutation assignment, DoubleMatrix weights, DoubleMatrix distances) {
       double quality = 0;
       for (int i = 0; i < assignment.Length; i++) {
         for (int j = 0; j < assignment.Length; j++) {
-          quality += weights[i, j] * distance(assignment[i], assignment[j]);
+          quality += weights[i, j] * distances[assignment[i], assignment[j]];
         }
       }
@@ -80 +75 @@
     public override IOperation Apply() {
       Permutation assignment = PermutationParameter.ActualValue;
-      bool useDistanceMatrix = UseDistanceMatrixParameter.ActualValue.Value;
       DoubleMatrix weights = WeightsParameter.ActualValue;
-      double quality;
+      DoubleMatrix distanceMatrix = DistanceMatrixParameter.ActualValue;
 
-      if (useDistanceMatrix) {
-        DoubleMatrix distanceMatrix = DistanceMatrixParameter.ActualValue;
-        quality = Apply(assignment, weights, (x, y) => distanceMatrix[x, y]);
-      } else {
-        DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
-        quality = Apply(assignment, weights, (x, y) => Distance(coordinates, x, y));
-      }
-
+      double quality = Apply(assignment, weights, distanceMatrix);
       QualityParameter.ActualValue = new DoubleValue(quality);
 
       return base.Apply();
     }
-
-    private double Distance(DoubleMatrix coordinates, int row1, int row2) {
-      double dx = coordinates[row1, 0] - coordinates[row2, 0];
-      double dy = coordinates[row1, 1] - coordinates[row2, 1];
-      return Math.Sqrt(dx * dx + dy * dy);
-    }
   }
 }

branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/HeuristicLab.Problems.QuadraticAssignment-3.3.csproj

@@ -144 +144 @@
     <Compile Include="Evaluators\QAPEvaluator.cs" />
     <Compile Include="Interfaces\IQAPEvaluator.cs" />
+    <Compile Include="Parsers\QAPLIBSolutionParser.cs" />
     <Compile Include="Parsers\QAPLIBParser.cs" />
     <Compile Include="QAPAssignment.cs" />

branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/Interfaces/IQAPEvaluator.cs

@@ -28 +28 @@
   public interface IQAPEvaluator : ISingleObjectiveEvaluator {
     ILookupParameter<Permutation> PermutationParameter { get; }
-    ILookupParameter<BoolValue> UseDistanceMatrixParameter { get; }
     ILookupParameter<DoubleMatrix> DistanceMatrixParameter { get; }
     ILookupParameter<DoubleMatrix> CoordinatesParameter { get; }

branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs

@@ -59 +59 @@
       get { return (ValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
     }
-    public ValueParameter<BoolValue> UseDistanceMatrixParameter {
-      get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
-    }
-
     #endregion
 
@@ -81 +77 @@
       get { return DistanceMatrixParameter.Value; }
       set { DistanceMatrixParameter.Value = value; }
-    }
-    public BoolValue UseDistanceMatrix {
-      get { return UseDistanceMatrixParameter.Value; }
-      set { UseDistanceMatrixParameter.Value = value; }
     }
 
@@ -112 +104 @@
       : base() {
       Parameters.Add(new ValueParameter<Permutation>("BestKnownSolution", "The best known solution which is updated whenever a new better solution is found or may be the optimal solution if it is known beforehand.", null));
-      Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The coordinates of the locations."));
+      Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The coordinates of the locations. If this is changed the distance matrix is calculated automatically using the euclidean distance."));
       Parameters.Add(new ValueParameter<DoubleMatrix>("Weights", "The strength of the connection between the facilities.", new DoubleMatrix(5, 5)));
       Parameters.Add(new ValueParameter<DoubleMatrix>("DistanceMatrix", "The distance matrix which can either be specified directly without the coordinates, or can be calculated automatically from the coordinates.", new DoubleMatrix(5, 5)));
-      Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "Defaults to true, set to false only when the number of facilities is very high and a distance matrix would become too large (>1000 facilities).", new BoolValue(true)));
 
       Maximization = new BoolValue(false);
@@ -196 +187 @@
       ParameterizeOperators();
     }
+    private void CoordinatesParameter_ValueChanged(object sender, EventArgs e) {
+      Coordinates.Reset += new EventHandler(Coordinates_Reset);
+      Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
+      UpdateDistanceMatrix();
+    }
+    private void Coordinates_ItemChanged(object sender, EventArgs<int, int> e) {
+      UpdateDistanceMatrix();
+    }
+    private void Coordinates_Reset(object sender, EventArgs e) {
+      UpdateDistanceMatrix();
+    }
     #endregion
 
@@ -205 +207 @@
 
     private void AttachEventHandlers() {
+      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
+      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
       WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
       Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
-      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
-      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
+      CoordinatesParameter.ValueChanged += new EventHandler(CoordinatesParameter_ValueChanged);
+      Coordinates.Reset += new EventHandler(Coordinates_Reset);
+      Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
     }
 
@@ -226 +231 @@
       if (Evaluator != null) {
         Evaluator.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
-        Evaluator.UseDistanceMatrixParameter.ActualName = UseDistanceMatrixParameter.Name;
         Evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
         Evaluator.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
@@ -265 +269 @@
       }
     }
+
+    private void UpdateDistanceMatrix() {
+      if (Coordinates != null && Coordinates.Columns == 2 && Coordinates.Rows > 1) {
+        DistanceMatrix = new DoubleMatrix(Coordinates.Rows, Coordinates.Rows);
+        for (int i = 0; i < Coordinates.Rows - 1; i++) {
+          for (int j = i + 1; j < Coordinates.Rows; j++) {
+            double dx = Coordinates[i, 0] - Coordinates[j, 0];
+            double dy = Coordinates[i, 1] - Coordinates[j, 1];
+            DistanceMatrix[i, j] = Math.Sqrt(dx * dx + dy * dy);
+            DistanceMatrix[j, i] = DistanceMatrix[i, j];
+          }
+        }
+      }
+    }
     #endregion
 
@@ -273 +291 @@
       DistanceMatrix = new DoubleMatrix(parser.Distances);
       Weights = new DoubleMatrix(parser.Weights);
-      UseDistanceMatrix.Value = true;
       Name = "Quadratic Assignment Problem (imported from " + Path.GetFileNameWithoutExtension(filename) + ")";
       Description = "Imported problem data using QAPLIBParser " + Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(AssemblyFileVersionAttribute), true).Cast<AssemblyFileVersionAttribute>().FirstOrDefault().Version + ".";
+      BestKnownQuality = null;
+      BestKnownSolution = null;
       OnReset();
     }
@@ -287 +306 @@
         DistanceMatrix = new DoubleMatrix(parser.Distances);
         Weights = new DoubleMatrix(parser.Weights);
-        UseDistanceMatrix.Value = true;
         Name = "Quadratic Assignment Problem (loaded instance " + instance + ")";
         Description = "Loaded embedded problem data of instance " + instance + ".";
         OnReset();
       }
+      bool solutionExists = Assembly.GetExecutingAssembly()
+          .GetManifestResourceNames()
+          .Where(x => x.EndsWith(instance + ".sln"))
+          .Any();
+      if (solutionExists) {
+        using (Stream solStream = Assembly.GetExecutingAssembly()
+          .GetManifestResourceStream(InstancePrefix + instance + ".sln")) {
+          QAPLIBSolutionParser solParser = new QAPLIBSolutionParser();
+          solParser.Parse(solStream);
+          BestKnownQuality = new DoubleValue(solParser.Qualiy);
+          BestKnownSolution = new Permutation(PermutationTypes.Absolute, solParser.Assignment);
+        }
+      } else {
+        BestKnownQuality = null;
+        BestKnownSolution = null;
+      }
     }
   }