Changeset 3066

Timestamp:

03/16/10 16:04:54 (15 years ago)

Author:

swagner

Message:

Implemented first version of distance matrix-based evaluation for the TSP (#912)

Location:

trunk/sources/HeuristicLab.Problems.TSP/3.3

Files:

• Evaluators/TSPCoordinatesPathEvaluator.cs (modified) (2 diffs)
• Evaluators/TSPDistanceMatrixPathEvaluator.cs (deleted)
• HeuristicLab.Problems.TSP-3.3.csproj (modified) (1 diff)
• Interfaces/ITSPCoordinatesPathEvaluator.cs (modified) (1 diff)
• Interfaces/ITSPDistanceMatrixPathEvaluator.cs (deleted)
• TSP.cs (modified) (7 diffs)

trunk/sources/HeuristicLab.Problems.TSP/3.3/Evaluators/TSPCoordinatesPathEvaluator.cs

@@ -39 +39 @@
       get { return (ILookupParameter<DoubleMatrix>)Parameters["Coordinates"]; }
     }
+    public ILookupParameter<DoubleMatrix> DistanceMatrixParameter {
+      get { return (ILookupParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
+    }
+    public ILookupParameter<BoolValue> UseDistanceMatrixParameter {
+      get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
+    }
 
     protected TSPCoordinatesPathEvaluator()
@@ -44 +50 @@
       Parameters.Add(new LookupParameter<Permutation>("Permutation", "The TSP solution given in path representation which should be evaluated."));
       Parameters.Add(new LookupParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
+      Parameters.Add(new LookupParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
+      Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false."));
     }
 
     public sealed override IOperation Apply() {
-      Permutation p = PermutationParameter.ActualValue;
-      DoubleMatrix c = CoordinatesParameter.ActualValue;
+      if (UseDistanceMatrixParameter.ActualValue.Value) {
+        Permutation p = PermutationParameter.ActualValue;
+        DoubleMatrix dm = DistanceMatrixParameter.ActualValue;
 
-      double length = 0;
-      for (int i = 0; i < p.Length - 1; i++)
-        length += CalculateDistance(c[p[i], 0], c[p[i], 1], c[p[i + 1], 0], c[p[i + 1], 1]);
-      length += CalculateDistance(c[p[p.Length - 1], 0], c[p[p.Length - 1], 1], c[p[0], 0], c[p[0], 1]);
-      QualityParameter.ActualValue = new DoubleValue(length);
+        if (dm == null) {  // calculate distance matrix
+          DoubleMatrix c = CoordinatesParameter.ActualValue;
 
+          dm = new DoubleMatrix(c.Rows, c.Rows);
+          for (int i = 0; i < dm.Rows; i++) {
+            for (int j = 0; j < dm.Columns; j++)
+              dm[i, j] = CalculateDistance(c[i, 0], c[i, 1], c[j, 0], c[j, 1]);
+          }
+          DistanceMatrixParameter.ActualValue = dm;
+        }
+
+        double length = 0;
+        for (int i = 0; i < p.Length - 1; i++)
+          length += dm[p[i], p[i + 1]];
+        length += dm[p[p.Length - 1], p[0]];
+        QualityParameter.ActualValue = new DoubleValue(length);
+      } else {
+        Permutation p = PermutationParameter.ActualValue;
+        DoubleMatrix c = CoordinatesParameter.ActualValue;
+
+        double length = 0;
+        for (int i = 0; i < p.Length - 1; i++)
+          length += CalculateDistance(c[p[i], 0], c[p[i], 1], c[p[i + 1], 0], c[p[i + 1], 1]);
+        length += CalculateDistance(c[p[p.Length - 1], 0], c[p[p.Length - 1], 1], c[p[0], 0], c[p[0], 1]);
+        QualityParameter.ActualValue = new DoubleValue(length);
+      }
       return base.Apply();
     }

trunk/sources/HeuristicLab.Problems.TSP/3.3/HeuristicLab.Problems.TSP-3.3.csproj

@@ -85 +85 @@
   <ItemGroup>
     <Compile Include="Evaluators\TSPCoordinatesPathEvaluator.cs" />
-    <Compile Include="Evaluators\TSPDistanceMatrixPathEvaluator.cs" />
     <Compile Include="Evaluators\TSPEvaluator.cs" />
     <Compile Include="Evaluators\TSPRoundedEuclideanPathEvaluator.cs" />
     <Compile Include="Interfaces\ITSPCoordinatesPathEvaluator.cs" />
-    <Compile Include="Interfaces\ITSPDistanceMatrixPathEvaluator.cs" />
     <Compile Include="Interfaces\ITSPEvaluator.cs" />
     <Compile Include="Interfaces\ITSPPathEvaluator.cs" />

trunk/sources/HeuristicLab.Problems.TSP/3.3/Interfaces/ITSPCoordinatesPathEvaluator.cs

@@ -29 +29 @@
   public interface ITSPCoordinatesPathEvaluator : ITSPPathEvaluator {
     ILookupParameter<DoubleMatrix> CoordinatesParameter { get; }
+    ILookupParameter<DoubleMatrix> DistanceMatrixParameter { get; }
+    ILookupParameter<BoolValue> UseDistanceMatrixParameter { get; }
   }
 }

trunk/sources/HeuristicLab.Problems.TSP/3.3/TSP.cs

@@ -52 +52 @@
       get { return (ValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
     }
+    public OptionalValueParameter<DoubleMatrix> DistanceMatrixParameter {
+      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
+    }
+    public ValueParameter<BoolValue> UseDistanceMatrixParameter {
+      get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
+    }
     public ValueParameter<IPermutationCreator> SolutionCreatorParameter {
       get { return (ValueParameter<IPermutationCreator>)Parameters["SolutionCreator"]; }
@@ -74 +80 @@
       set { CoordinatesParameter.Value = value; }
     }
+    public DoubleMatrix DistanceMatrix {
+      get { return DistanceMatrixParameter.Value; }
+      set { DistanceMatrixParameter.Value = value; }
+    }
+    public BoolValue UseDistanceMatrix {
+      get { return UseDistanceMatrixParameter.Value; }
+      set { UseDistanceMatrixParameter.Value = value; }
+    }
     public IPermutationCreator SolutionCreator {
       get { return SolutionCreatorParameter.Value; }
@@ -108 +122 @@
       Parameters.Add(new ValueParameter<BoolValue>("Maximization", "Set to false as the Traveling Salesman Problem is a minimization problem.", new BoolValue(false)));
       Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities.", new DoubleMatrix(0, 0)));
+      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
+      Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false.", new BoolValue(true)));
       Parameters.Add(new ValueParameter<IPermutationCreator>("SolutionCreator", "The operator which should be used to create new TSP solutions.", creator));
       Parameters.Add(new ValueParameter<ITSPEvaluator>("Evaluator", "The operator which should be used to evaluate TSP solutions.", evaluator));
@@ -155 +171 @@
       Coordinates.Reset += new EventHandler(Coordinates_Reset);
       ParameterizeSolutionCreator();
+      ClearDistanceMatrix();
     }
     private void Coordinates_ItemChanged(object sender, EventArgs<int, int> e) {
+      ClearDistanceMatrix();
     }
     private void Coordinates_Reset(object sender, EventArgs e) {
       ParameterizeSolutionCreator();
+      ClearDistanceMatrix();
     }
     private void SolutionCreatorParameter_ValueChanged(object sender, EventArgs e) {
@@ -174 +193 @@
     private void EvaluatorParameter_ValueChanged(object sender, EventArgs e) {
       ParameterizeEvaluator();
+      ClearDistanceMatrix();
       OnEvaluatorChanged();
     }
@@ -195 +215 @@
       if (Evaluator is ITSPPathEvaluator)
         ((ITSPPathEvaluator)Evaluator).PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
-      if (Evaluator is ITSPCoordinatesPathEvaluator)
-        ((ITSPCoordinatesPathEvaluator)Evaluator).CoordinatesParameter.ActualName = CoordinatesParameter.Name;
+      if (Evaluator is ITSPCoordinatesPathEvaluator) {
+        ITSPCoordinatesPathEvaluator evaluator = (ITSPCoordinatesPathEvaluator)Evaluator;
+        evaluator.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
+        evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
+        evaluator.UseDistanceMatrixParameter.ActualName = UseDistanceMatrixParameter.Name;
+      }
     }
     private void InitializeOperators() {
@@ -214 +238 @@
       }
     }
+    private void ClearDistanceMatrix() {
+      DistanceMatrixParameter.Value = null;
+    }
     #endregion
   }