Changeset 3209 for trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators

Timestamp:

03/24/10 21:15:04 (14 years ago)

Author:

abeham

Message:

Added 3-opt move and evaluators for the TSP
Added 2-opt move evaluators for TSP Geo and Euclidean
#889

Location:

trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators

Files:

• TSPMoveEvaluator.cs (modified) (2 diffs)
• TSPPathMoveEvaluator.cs (modified) (1 diff)
• ThreeOpt (added)
• ThreeOpt/TSPThreeOptEuclideanPathMoveEvaluator.cs (added)
• ThreeOpt/TSPThreeOptGeoPathMoveEvaluator.cs (added)
• ThreeOpt/TSPThreeOptPathMoveEvaluator.cs (added)
• ThreeOpt/TSPThreeOptRoundedEuclideanPathMoveEvaluator.cs (added)
• ThreeOptMoveTSPCoordinatesPathEvaluator.cs (deleted)
• ThreeOptMoveTSPRoundedEuclideanPathEvaluator.cs (deleted)
• TwoOpt (added)
• TwoOpt/TSPTwoOptEuclideanPathMoveEvaluator.cs (added)
• TwoOpt/TSPTwoOptGeoPathMoveEvaluator.cs (added)
• TwoOpt/TSPTwoOptPathMoveEvaluator.cs (added)
• TwoOpt/TSPTwoOptRoundedEuclideanPathMoveEvaluator.cs (added)
• TwoOptMoveTSPCoordinatesPathEvaluator.cs (deleted)
• TwoOptMoveTSPRoundedEuclideanPathEvaluator.cs (deleted)

trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/TSPMoveEvaluator.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using HeuristicLab.Core;
 using HeuristicLab.Data;
@@ -34 +35 @@
   [StorableClass]
   public abstract class TSPMoveEvaluator : SingleSuccessorOperator, ITSPMoveEvaluator, IMoveOperator {
+    public abstract Type EvaluatorType { get; }
+
     public ILookupParameter<DoubleValue> QualityParameter {
       get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }

trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/TSPPathMoveEvaluator.cs

@@ -54 +54 @@
       Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated (if it does not exist already) and used for evaluation, otherwise false."));
     }
+
+    public override IOperation Apply() {
+      Permutation permutation = PermutationParameter.ActualValue;
+      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
+      double relativeQualityDifference = 0;
+      if (UseDistanceMatrixParameter.ActualValue.Value) {
+        DoubleMatrix distanceMatrix = DistanceMatrixParameter.ActualValue;
+        if (distanceMatrix == null) {
+          distanceMatrix = CalculateDistanceMatrix(coordinates);
+          DistanceMatrixParameter.ActualValue = distanceMatrix;
+        }
+        relativeQualityDifference = EvaluateByDistanceMatrix(permutation, distanceMatrix);
+      } else relativeQualityDifference = EvaluateByCoordinates(permutation, coordinates);
+      DoubleValue moveQuality = MoveQualityParameter.ActualValue;
+      if (moveQuality == null) MoveQualityParameter.ActualValue = new DoubleValue(QualityParameter.ActualValue.Value + relativeQualityDifference);
+      else moveQuality.Value = QualityParameter.ActualValue.Value + relativeQualityDifference;
+      return base.Apply();
+    }
+
+    protected abstract double CalculateDistance(double x1, double y1, double x2, double y2);
+    protected abstract double EvaluateByDistanceMatrix(Permutation permutation, DoubleMatrix distanceMatrix);
+    protected abstract double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates);
+
+    private DoubleMatrix CalculateDistanceMatrix(DoubleMatrix c) {
+      DoubleMatrix distanceMatrix = new DoubleMatrix(c.Rows, c.Rows);
+      for (int i = 0; i < distanceMatrix.Rows; i++) {
+        for (int j = 0; j < distanceMatrix.Columns; j++)
+          distanceMatrix[i, j] = CalculateDistance(c[i, 0], c[i, 1], c[j, 0], c[j, 1]);
+      }
+      return distanceMatrix;
+    }
   }
 }