Changeset 5598 for branches/QAP

Timestamp:

03/02/11 22:33:30 (13 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

Files:

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

branches/QAP/HeuristicLab.Problems.QuadraticAssignment.Views/3.3/QAPAssignmentView.Designer.cs

@@ -33 +33 @@
       this.assignmentGroupBox = new System.Windows.Forms.GroupBox();
       this.assignmentViewHost = new HeuristicLab.MainForm.WindowsForms.ViewHost();
+      this.weightsRadioButton = new System.Windows.Forms.RadioButton();
+      this.distancesRadioButton = new System.Windows.Forms.RadioButton();
       ((System.ComponentModel.ISupportInitialize)(this.splitContainer)).BeginInit();
       this.splitContainer.Panel1.SuspendLayout();
@@ -108 +110 @@
       // visualizationTabPage
       // 
+      this.visualizationTabPage.Controls.Add(this.distancesRadioButton);
+      this.visualizationTabPage.Controls.Add(this.weightsRadioButton);
       this.visualizationTabPage.Controls.Add(this.pictureBox);
       this.visualizationTabPage.Location = new System.Drawing.Point(4, 22);
@@ -124 +128 @@
       this.pictureBox.BackColor = System.Drawing.Color.White;
       this.pictureBox.BorderStyle = System.Windows.Forms.BorderStyle.FixedSingle;
-      this.pictureBox.Location = new System.Drawing.Point(6, 6);
+      this.pictureBox.Location = new System.Drawing.Point(84, 6);
       this.pictureBox.Name = "pictureBox";
-      this.pictureBox.Size = new System.Drawing.Size(516, 269);
+      this.pictureBox.Size = new System.Drawing.Size(438, 269);
       this.pictureBox.TabIndex = 0;
       this.pictureBox.TabStop = false;
@@ -170 +174 @@
       this.assignmentViewHost.ViewsLabelVisible = true;
       this.assignmentViewHost.ViewType = null;
+      // 
+      // weightsRadioButton
+      // 
+      this.weightsRadioButton.AutoSize = true;
+      this.weightsRadioButton.Location = new System.Drawing.Point(6, 29);
+      this.weightsRadioButton.Name = "weightsRadioButton";
+      this.weightsRadioButton.Size = new System.Drawing.Size(64, 17);
+      this.weightsRadioButton.TabIndex = 1;
+      this.weightsRadioButton.Text = "Weights";
+      this.weightsRadioButton.UseVisualStyleBackColor = true;
+      this.weightsRadioButton.CheckedChanged += new System.EventHandler(this.radioButton_CheckedChanged);
+      // 
+      // distancesRadioButton
+      // 
+      this.distancesRadioButton.AutoSize = true;
+      this.distancesRadioButton.Checked = true;
+      this.distancesRadioButton.Location = new System.Drawing.Point(6, 6);
+      this.distancesRadioButton.Name = "distancesRadioButton";
+      this.distancesRadioButton.Size = new System.Drawing.Size(72, 17);
+      this.distancesRadioButton.TabIndex = 2;
+      this.distancesRadioButton.TabStop = true;
+      this.distancesRadioButton.Text = "Distances";
+      this.distancesRadioButton.UseVisualStyleBackColor = true;
+      this.distancesRadioButton.CheckedChanged += new System.EventHandler(this.radioButton_CheckedChanged);
       // 
       // QAPAssignmentView
@@ -185 +213 @@
       this.tabControl.ResumeLayout(false);
       this.visualizationTabPage.ResumeLayout(false);
+      this.visualizationTabPage.PerformLayout();
       ((System.ComponentModel.ISupportInitialize)(this.pictureBox)).EndInit();
       this.valueTabPage.ResumeLayout(false);
@@ -203 +232 @@
     private System.Windows.Forms.GroupBox assignmentGroupBox;
     private MainForm.WindowsForms.ViewHost assignmentViewHost;
+    private System.Windows.Forms.RadioButton distancesRadioButton;
+    private System.Windows.Forms.RadioButton weightsRadioButton;
   }
 }

branches/QAP/HeuristicLab.Problems.QuadraticAssignment.Views/3.3/QAPAssignmentView.cs

@@ -37 +37 @@
   [Content(typeof(QAPAssignment), true)]
   public sealed partial class QAPAssignmentView : ItemView {
+    private Bitmap bitmap;
+
     public new QAPAssignment Content {
       get { return (QAPAssignment)base.Content; }
@@ -82 +84 @@
         if (Content == null) {
           pictureBox.Image = null;
+          if (bitmap != null) bitmap.Dispose();
+          bitmap = null;
         } else {
-          bool drawDistances = false;
+          Bitmap newBitmap = new Bitmap(pictureBox.Width, pictureBox.Height);
+          bool drawDistances = distancesRadioButton.Checked;
           DoubleMatrix coordinates = Content.Coordinates;
           DoubleMatrix distances = Content.Distances;
+
           if ((coordinates == null || coordinates.Rows == 0)
-            && (distances == null || distances.Rows == 0)) return;
-          else if ((coordinates == null || coordinates.Rows == 0)
-            && Content.ViewCoordinates == null) {
-            coordinates = new DoubleMatrix(distances.Rows, 2);
-            int columns = (int)Math.Ceiling(Math.Sqrt(coordinates.Rows));
-            int x = 0, y = 0;
-            for (int i = 0; i < coordinates.Rows; i++) {
-              coordinates[i, 0] = 10 * x;
-              coordinates[i, 1] = 10 * y;
-              if (++x > columns) {
-                y++;
-                x = 0;
-              }
-            }
-            Content.ViewCoordinates = coordinates;
-            drawDistances = true;
-          } else if ((coordinates == null || coordinates.Rows == 0)
-            && Content.ViewCoordinates != null) {
-            coordinates = Content.ViewCoordinates;
-            drawDistances = true;
-          }
-
-          DoubleMatrix weights = Content.Weights;
-          Permutation permutation = Content.Assignment;
-          Bitmap bitmap = new Bitmap(pictureBox.Width, pictureBox.Height);
-
-          if ((coordinates != null) && (coordinates.Rows > 0) && (coordinates.Columns == 2)) {
+            && (distances == null || distances.Rows == 0)) {
+            using (Graphics g = Graphics.FromImage(newBitmap)) {
+              string str = "No coordinates and no distance matrix specified.";
+              SizeF strSize = g.MeasureString(str, Font);
+              g.DrawString(str, Font, Brushes.Black, (float)(newBitmap.Width - strSize.Width) / 2.0f, (float)(newBitmap.Height - strSize.Height) / 2.0f);
+            }
+          } else {
+            if ((coordinates == null || coordinates.Rows == 0)
+              && Content.ViewCoordinates == null) {
+              coordinates = new DoubleMatrix(distances.Rows, 2);
+              double rad = (2 * Math.PI) / coordinates.Rows;
+              for (int i = 0; i < coordinates.Rows; i++) {
+                coordinates[i, 0] = 10 * Math.Cos(rad * i);
+                coordinates[i, 1] = 10 * Math.Sin(rad * i);
+              }
+              Content.ViewCoordinates = coordinates;
+            } else if ((coordinates == null || coordinates.Rows == 0)
+              && Content.ViewCoordinates != null) {
+              coordinates = Content.ViewCoordinates;
+            }
+
+            DoubleMatrix weights = Content.Weights;
+            Permutation assignment = Content.Assignment;
+
             double xMin = double.MaxValue, yMin = double.MaxValue, xMax = double.MinValue, yMax = double.MinValue;
+            double maxWeight = double.MinValue, maxDistance = double.MinValue;
             for (int i = 0; i < coordinates.Rows; i++) {
               if (xMin > coordinates[i, 0]) xMin = coordinates[i, 0];
@@ -120 +124 @@
               if (xMax < coordinates[i, 0]) xMax = coordinates[i, 0];
               if (yMax < coordinates[i, 1]) yMax = coordinates[i, 1];
+
+              for (int j = i + 1; j < coordinates.Rows; j++) {
+                if (weights[i, j] + weights[j, i] > maxWeight)
+                  maxWeight = weights[i, j] + weights[j, i];
+
+                if (distances[i, j] > maxDistance)
+                  maxDistance = distances[i, j];
+                else if (distances[j, i] > maxDistance)
+                  maxDistance = distances[j, i];
+              }
             }
 
@@ -129 +143 @@
             for (int i = 0; i < coordinates.Rows; i++)
               points[i] = new Point(border + ((int)((coordinates[i, 0] - xMin) * xStep)),
-                                    bitmap.Height - (border + ((int)((coordinates[i, 1] - yMin) * yStep))));
-
-            using (Graphics graphics = Graphics.FromImage(bitmap)) {
-              if ((permutation != null) && (permutation.Length == coordinates.Rows) && (permutation.Validate())) {
-                for (int i = 0; i < permutation.Length; i++) {
-                  for (int j = 0; j < permutation.Length; j++) {
-                    if (i != j && weights[i, j] > 0) {
-                      graphics.DrawLine(Pens.Black, points[permutation[i]], points[permutation[j]]);
-                      float midX = ((points[permutation[i]].X + points[permutation[j]].X) / 2.0f) + 5;
-                      float midY = ((points[permutation[i]].Y + points[permutation[j]].Y) / 2.0f) - 5;
-                      graphics.DrawString(weights[i, j].ToString(CultureInfo.InvariantCulture.NumberFormat), Font, Brushes.Black, midX, midY);
+                                    newBitmap.Height - (border + ((int)((coordinates[i, 1] - yMin) * yStep))));
+
+            Random rand = new Random();
+            using (Graphics graphics = Graphics.FromImage(newBitmap)) {
+              graphics.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;
+              graphics.TextRenderingHint = System.Drawing.Text.TextRenderingHint.AntiAlias;
+              if ((assignment != null) && (assignment.Length == coordinates.Rows) && (assignment.Validate())) {
+                for (int i = 0; i < assignment.Length - 1; i++) {
+                  for (int j = i + 1; j < assignment.Length; j++) {
+                    Point start = points[assignment[i]], end = points[assignment[j]];
+                    string caption = String.Empty;
+                    double d = Math.Max(distances[i, j], distances[j, i]);
+                    if (drawDistances) {
+                      float width = (float)Math.Ceiling(5.0 * d / maxDistance);
+                      graphics.DrawLine(new Pen(Color.IndianRed, width), start, end);
+                      if (distances[i, j] != distances[j, i])
+                        caption = distances[i, j].ToString(CultureInfo.InvariantCulture.NumberFormat)
+                          + " / " + distances[j, i].ToString(CultureInfo.InvariantCulture.NumberFormat);
+                      else
+                        caption = distances[i, j].ToString(CultureInfo.InvariantCulture.NumberFormat);
+                    } else {
+                      double w = weights[i, j] + weights[j, i];
+                      if (w > 0) {
+                        float width = (float)Math.Ceiling(5.0 * w / maxWeight);
+                        graphics.DrawLine(new Pen(Color.MediumBlue, width), start, end);
+                        caption = w.ToString(CultureInfo.InvariantCulture.NumberFormat);
+                      }
+                      if (!String.IsNullOrEmpty(caption)) {
+                        double r = rand.NextDouble();
+                        while (r < 0.2 || r > 0.8) r = rand.NextDouble();
+                        float x = (float)(start.X + (end.X - start.X) * r + 5);
+                        float y = (float)(start.Y + (end.Y - start.Y) * r + 5);
+                        graphics.DrawString(caption, Font, Brushes.Black, x, y);
+                      }
                     }
                   }
                 }
               }
-              for (int i = 0; i < points.Length; i++)
-                graphics.FillRectangle(Brushes.Red, points[i].X - 2, points[i].Y - 2, 6, 6);
+              for (int i = 0; i < points.Length; i++) {
+                Point p = new Point(points[assignment[i]].X - 3, points[assignment[i]].Y - 3);
+                graphics.FillRectangle(Brushes.Black, p.X, p.Y, 8, 8);
+                graphics.DrawString(i.ToString(), Font, Brushes.Black, p.X, p.Y + 10);
+              }
             }
           }
-          pictureBox.Image = bitmap;
+          pictureBox.Image = newBitmap;
+          if (bitmap != null) bitmap.Dispose();
+          bitmap = newBitmap;
         }
       }
@@ -163 +205 @@
             GenerateImage();
             break;
-          case "Permutation":
+          case "Assignment":
             GenerateImage();
             assignmentViewHost.Content = Content.Assignment;
@@ -178 +220 @@
       GenerateImage();
     }
+
+    private void radioButton_CheckedChanged(object sender, EventArgs e) {
+      GenerateImage();
+    }
   }
 }

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;
+      }
     }
   }