Changeset 14454 for branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators

Timestamp:

12/05/16 16:06:18 (8 years ago)

Author:

abeham

Message:

#2701:

• Worked on MemPR algorithm for permutations
• Refactored TSP

Location:

branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators

Files:

• TSPMoveEvaluator.cs (modified) (1 diff)
• TSPPathMoveEvaluator.cs (modified) (3 diffs)
• ThreeOpt/TSPTranslocationMoveDistanceMatrixEvaluator.cs (deleted)
• ThreeOpt/TSPTranslocationMoveEuclideanPathEvaluator.cs (deleted)
• ThreeOpt/TSPTranslocationMoveGeoPathEvaluator.cs (deleted)
• ThreeOpt/TSPTranslocationMovePathEvaluator.cs (modified) (3 diffs)
• ThreeOpt/TSPTranslocationMoveRoundedEuclideanPathEvaluator.cs (deleted)
• TwoOpt/TSPInversionMoveDistanceMatrixEvaluator.cs (deleted)
• TwoOpt/TSPInversionMoveEuclideanPathEvaluator.cs (deleted)
• TwoOpt/TSPInversionMoveGeoPathEvaluator.cs (deleted)
• TwoOpt/TSPInversionMovePathEvaluator.cs (modified) (4 diffs)
• TwoOpt/TSPInversionMoveRoundedEuclideanPathEvaluator.cs (deleted)

branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/TSPMoveEvaluator.cs

@@ -36 +36 @@
   [StorableClass]
   public abstract class TSPMoveEvaluator : SingleSuccessorOperator, ITSPMoveEvaluator, IMoveOperator {
-
-    public abstract Type EvaluatorType { get; }
+    
     public override bool CanChangeName {
       get { return false; }

branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/TSPPathMoveEvaluator.cs

@@ -47 +47 @@
       get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
     }
+    public ILookupParameter<EnumValue<TSPDistanceFunction>> DistanceFunctionParameter {
+      get { return (ILookupParameter<EnumValue<TSPDistanceFunction>>)Parameters["DistanceFunction"]; }
+    }
 
     [StorableConstructor]
@@ -57 +60 @@
       Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
       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."));
-    }
-
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      // BackwardsCompatibility3.3
-      #region Backwards compatible code (remove with 3.4)
-      LookupParameter<DoubleMatrix> oldDistanceMatrixParameter = Parameters["DistanceMatrix"] as LookupParameter<DoubleMatrix>;
-      if (oldDistanceMatrixParameter != null) {
-        Parameters.Remove(oldDistanceMatrixParameter);
-        Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
-        DistanceMatrixParameter.ActualName = oldDistanceMatrixParameter.ActualName;
-      }
-      #endregion
+      Parameters.Add(new LookupParameter<EnumValue<TSPDistanceFunction>>("DistanceFunction", "The distance function to use when the distance matrix is not being used."));
     }
 
     public override IOperation Apply() {
-      Permutation permutation = PermutationParameter.ActualValue;
-      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
+      var permutation = PermutationParameter.ActualValue;
+      var coordinates = CoordinatesParameter.ActualValue;
+      var distanceFunction = DistanceFunctionParameter.ActualValue.Value;
       double relativeQualityDifference = 0;
       if (UseDistanceMatrixParameter.ActualValue.Value) {
         DistanceMatrix distanceMatrix = DistanceMatrixParameter.ActualValue;
         if (distanceMatrix == null) {
-          if (coordinates == null) throw new InvalidOperationException("Neither a distance matrix nor coordinates were given.");
-          distanceMatrix = CalculateDistanceMatrix(coordinates);
-          DistanceMatrixParameter.ActualValue = distanceMatrix;
+          throw new InvalidOperationException("Distance matrix is not given.");
         }
         relativeQualityDifference = EvaluateByDistanceMatrix(permutation, distanceMatrix);
       } else {
         if (coordinates == null) throw new InvalidOperationException("No coordinates were given.");
-        relativeQualityDifference = EvaluateByCoordinates(permutation, coordinates);
+        relativeQualityDifference = EvaluateByCoordinates(permutation, coordinates, distanceFunction);
       }
       DoubleValue moveQuality = MoveQualityParameter.ActualValue;
@@ -93 +83 @@
       return base.Apply();
     }
-
-    protected abstract double CalculateDistance(double x1, double y1, double x2, double y2);
     protected abstract double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix);
-    protected abstract double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates);
-
-    private DistanceMatrix CalculateDistanceMatrix(DoubleMatrix c) {
-      DistanceMatrix distanceMatrix = new DistanceMatrix(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)distanceMatrix.AsReadOnly();
-    }
+    protected abstract double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, TSPDistanceFunction distanceFunction);
   }
 }

branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/ThreeOpt/TSPTranslocationMovePathEvaluator.cs

@@ -46 +46 @@
     }
 
-    public static double EvaluateByCoordinates(Permutation permutation, TranslocationMove move, DoubleMatrix coordinates, TSPTranslocationMovePathEvaluator evaluator) {
+    public static double EvaluateByCoordinates(Permutation permutation, TranslocationMove move, DoubleMatrix coordinates, TSPDistanceFunction distanceFunction) {
       if (move.Index1 == move.Index3
         || move.Index2 == permutation.Length - 1 && move.Index3 == 0
@@ -65 +65 @@
       double moveQuality = 0;
       // remove three edges
-      moveQuality -= evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
+      moveQuality -= TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge1source, 0], coordinates[edge1source, 1],
         coordinates[edge1target, 0], coordinates[edge1target, 1]);
-      moveQuality -= evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
+      moveQuality -= TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge2source, 0], coordinates[edge2source, 1],
         coordinates[edge2target, 0], coordinates[edge2target, 1]);
-      moveQuality -= evaluator.CalculateDistance(coordinates[edge3source, 0], coordinates[edge3source, 1],
+      moveQuality -= TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge3source, 0], coordinates[edge3source, 1],
         coordinates[edge3target, 0], coordinates[edge3target, 1]);
       // add three edges
-      moveQuality += evaluator.CalculateDistance(coordinates[edge3source, 0], coordinates[edge3source, 1],
+      moveQuality += TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge3source, 0], coordinates[edge3source, 1],
         coordinates[edge1target, 0], coordinates[edge1target, 1]);
-      moveQuality += evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
+      moveQuality += TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge2source, 0], coordinates[edge2source, 1],
         coordinates[edge3target, 0], coordinates[edge3target, 1]);
-      moveQuality += evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
+      moveQuality += TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge1source, 0], coordinates[edge1source, 1],
         coordinates[edge2target, 0], coordinates[edge2target, 1]);
       return moveQuality;
@@ -110 +110 @@
     }
 
-    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {
-      return EvaluateByCoordinates(permutation, TranslocationMoveParameter.ActualValue, coordinates, this);
+    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, TSPDistanceFunction distanceFunction) {
+      return EvaluateByCoordinates(permutation, TranslocationMoveParameter.ActualValue, coordinates, distanceFunction);
     }
 

branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/TwoOpt/TSPInversionMovePathEvaluator.cs

@@ -33 +33 @@
   [Item("TSPInversionMovePathEvaluator", "Evaluates an inversion move (2-opt) by summing up the length of all added edges and subtracting the length of all deleted edges.")]
   [StorableClass]
-  public abstract class TSPInversionMovePathEvaluator : TSPPathMoveEvaluator, IPermutationInversionMoveOperator {
+  public class TSPInversionMovePathEvaluator : TSPPathMoveEvaluator, IPermutationInversionMoveOperator {
     public ILookupParameter<InversionMove> InversionMoveParameter {
       get { return (ILookupParameter<InversionMove>)Parameters["InversionMove"]; }
@@ -46 +46 @@
     }
 
-    public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, TSPInversionMovePathEvaluator evaluator) {
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new TSPInversionMovePathEvaluator(this, cloner);
+    }
+
+    public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, TSPDistanceFunction distanceFunction) {
       int edge1source = permutation.GetCircular(move.Index1 - 1);
       int edge1target = permutation[move.Index1];
@@ -54 +58 @@
       double moveQuality = 0;
       // remove two edges
-      moveQuality -= evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
+      moveQuality -= TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge1source, 0], coordinates[edge1source, 1],
             coordinates[edge1target, 0], coordinates[edge1target, 1]);
-      moveQuality -= evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
+      moveQuality -= TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge2source, 0], coordinates[edge2source, 1],
         coordinates[edge2target, 0], coordinates[edge2target, 1]);
       // add two edges
-      moveQuality += evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
+      moveQuality += TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge1source, 0], coordinates[edge1source, 1],
         coordinates[edge2source, 0], coordinates[edge2source, 1]);
-      moveQuality += evaluator.CalculateDistance(coordinates[edge1target, 0], coordinates[edge1target, 1],
+      moveQuality += TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge1target, 0], coordinates[edge1target, 1],
         coordinates[edge2target, 0], coordinates[edge2target, 1]);
       return moveQuality;
@@ -82 +86 @@
     }
 
-    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {
-      return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, this);
+    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, TSPDistanceFunction distanceFunction) {
+      return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, distanceFunction);
     }