Changeset 13412 for branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoOpt

Timestamp:

11/28/15 23:38:51 (9 years ago)

Author:

abeham

Message:

#2221:

• Completely refactored PTSP branch
  • Added two sets of problem instances based on TSPLIB: homogeneous and heterogeneous
  • Implemented missing EvaluateByCoordinates for 1-shift moves
  • Made it clear that move evaluators are for estimated PTSP only
  • Changed parameter realization from a rather strange list of list of ints to a list of bool arrays
  • Reusing code of the 2-opt and 1-shift move evaluators in 2.5 move evaluator
  • Introducing distance calculators to properly handle the case when no distance matrix is given (previous code only worked with distance matrix and without only with euclidean distance in some settings)
  • Fixed several smaller code issues: protected, static, method parameters, copy & paste, interfaces, naming, parameters, serialization hooks, license headers, doc comments, data types

Location:

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoOpt

Files:

• . (added)
• PTSPEstimatedInversionMoveEvaluator.cs (copied) (copied from branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/TwoOpt/PTSPEstimatedInversionEvaluator.cs) (6 diffs)

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoOpt/PTSPEstimatedInversionMoveEvaluator.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -26 +27 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using System;
 
 namespace HeuristicLab.Problems.PTSP {
-  /// <summary>
-  /// An operator to evaluate inversion moves (2-opt).
-  /// </summary>
-  [Item("PTSPInversionMovePathEvaluator", "Evaluates an inversion move (2-opt) by summing up the length of all added edges and subtracting the length of all deleted edges.")]
+  [Item("PTSPEstimatedInversionMoveEvaluator", "Evaluates an inversion move (2-opt) over several realizations of tours by summing up the length of all added edges and subtracting the length of all deleted edges.")]
   [StorableClass]
-  public class PTSPEstimatedInversionEvaluator : PTSPMoveEvaluator, IPermutationInversionMoveOperator {
-    public override Type EvaluatorType {
-      get { return typeof(PTSPEstimatedInversionEvaluator); }
-    }
+  public class PTSPEstimatedInversionMoveEvaluator : EstimatedPTSPMoveEvaluator, IPermutationInversionMoveOperator {
+
     public ILookupParameter<InversionMove> InversionMoveParameter {
       get { return (ILookupParameter<InversionMove>)Parameters["InversionMove"]; }
     }
 
-    
-
     [StorableConstructor]
-    protected PTSPEstimatedInversionEvaluator(bool deserializing) : base(deserializing) { }
-    protected PTSPEstimatedInversionEvaluator(PTSPEstimatedInversionEvaluator original, Cloner cloner) : base(original, cloner) { }
-    public PTSPEstimatedInversionEvaluator()
+    protected PTSPEstimatedInversionMoveEvaluator(bool deserializing) : base(deserializing) { }
+    protected PTSPEstimatedInversionMoveEvaluator(PTSPEstimatedInversionMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
+    public PTSPEstimatedInversionMoveEvaluator()
       : base() {
       Parameters.Add(new LookupParameter<InversionMove>("InversionMove", "The move to evaluate."));
@@ -53 +46 @@
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new PTSPEstimatedInversionEvaluator(this, cloner);
+      return new PTSPEstimatedInversionMoveEvaluator(this, cloner);
     }
 
-    public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, PTSPEstimatedInversionEvaluator evaluator) {
-      int edge1source = permutation.GetCircular(move.Index1 - 1);
-      int edge1target = permutation[move.Index1];
-      int edge2source = permutation[move.Index2];
-      int edge2target = permutation.GetCircular(move.Index2 + 1);
-      if (move.Index2 - move.Index1 >= permutation.Length - 2) return 0;
+    public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, DistanceCalculator distanceCalculator, ItemList<BoolArray> realizations) {
       double moveQuality = 0;
-      // remove two edges
-      moveQuality -= evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
-            coordinates[edge1target, 0], coordinates[edge1target, 1]);
-      moveQuality -= evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
-        coordinates[edge2target, 0], coordinates[edge2target, 1]);
-      // add two edges
-      moveQuality += evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
-        coordinates[edge2source, 0], coordinates[edge2source, 1]);
-      moveQuality += evaluator.CalculateDistance(coordinates[edge1target, 0], coordinates[edge1target, 1],
-        coordinates[edge2target, 0], coordinates[edge2target, 1]);
-      return moveQuality;
-    }
-
-    public static double EvaluateByDistanceMatrix(Permutation permutation, InversionMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) {
-      double moveQuality = 0;
-      int[] edges = new int[4];
-      int[] indices = new int[4];
+      var edges = new int[4];
+      var indices = new int[4];
       edges[0] = permutation.GetCircular(move.Index1 - 1);
-      indices[0] = move.Index1-1;
+      indices[0] = move.Index1 - 1;
       if (indices[0] == -1) indices[0] = permutation.Length - 1;
       edges[1] = permutation[move.Index1];
@@ -88 +61 @@
       indices[2] = move.Index2;
       edges[3] = permutation.GetCircular(move.Index2 + 1);
-      indices[3] = move.Index2+1; 
+      indices[3] = move.Index2 + 1;
       if (indices[3] == permutation.Length + 1) indices[3] = 0;
-      int[] aPosteriori = new int[4];
-      foreach (ItemList<IntValue> realization in realizations) {
-        for (int i = 0; i < edges.Length; i++) {
-          if (realization[edges[i]].Value == 1) {
+      var aPosteriori = new int[4];
+      foreach (var realization in realizations) {
+        for (var i = 0; i < edges.Length; i++) {
+          if (realization[edges[i]]) {
             aPosteriori[i] = edges[i];
           } else {
-            int j=1;
-            if (i%2==0) {
+            var j = 1;
+            if (i % 2 == 0) {
               // find nearest predecessor in realization if source edge
-              while(realization[permutation.GetCircular(indices[i]-j)].Value==0) {
+              while (!realization[permutation.GetCircular(indices[i] - j)]) {
                 j++;
               }
@@ -105 +78 @@
             } else {
               // find nearest successor in realization if target edge
-              while(realization[permutation.GetCircular(indices[i]+j)].Value==0) {
+              while (!realization[permutation.GetCircular(indices[i] + j)]) {
+                j++;
+              }
+              aPosteriori[i] = permutation.GetCircular(indices[i] + j);
+            }
+          }
+        }
+        // compute cost difference between the two a posteriori solutions
+        if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3])) {
+          moveQuality = moveQuality
+            + distanceCalculator.Calculate(0, 2, coordinates)
+            + distanceCalculator.Calculate(1, 3, coordinates)
+            - distanceCalculator.Calculate(0, 1, coordinates)
+            - distanceCalculator.Calculate(2, 3, coordinates);
+        }
+        Array.Clear(aPosteriori, 0, aPosteriori.Length);
+      }
+      // return average of cost differences
+      return moveQuality / realizations.Count;
+    }
+
+    public static double EvaluateByDistanceMatrix(Permutation permutation, InversionMove move, DistanceMatrix distanceMatrix, ItemList<BoolArray> realizations) {
+      double moveQuality = 0;
+      var edges = new int[4];
+      var indices = new int[4];
+      edges[0] = permutation.GetCircular(move.Index1 - 1);
+      indices[0] = move.Index1 - 1;
+      if (indices[0] == -1) indices[0] = permutation.Length - 1;
+      edges[1] = permutation[move.Index1];
+      indices[1] = move.Index1;
+      edges[2] = permutation[move.Index2];
+      indices[2] = move.Index2;
+      edges[3] = permutation.GetCircular(move.Index2 + 1);
+      indices[3] = move.Index2 + 1;
+      if (indices[3] == permutation.Length + 1) indices[3] = 0;
+      var aPosteriori = new int[4];
+      foreach (var realization in realizations) {
+        for (var i = 0; i < edges.Length; i++) {
+          if (realization[edges[i]]) {
+            aPosteriori[i] = edges[i];
+          } else {
+            var j = 1;
+            if (i % 2 == 0) {
+              // find nearest predecessor in realization if source edge
+              while (!realization[permutation.GetCircular(indices[i] - j)]) {
+                j++;
+              }
+              aPosteriori[i] = permutation.GetCircular(indices[i] - j);
+            } else {
+              // find nearest successor in realization if target edge
+              while (!realization[permutation.GetCircular(indices[i] + j)]) {
                 j++;
               }
@@ -122 +145 @@
     }
 
-    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {
-      return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, this);
+    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator) {
+      return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, distanceCalculator, RealizationsParameter.ActualValue);
     }
 
     protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
-      return EvaluateByDistanceMatrix(permutation, InversionMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.Value);
-    }
-
-    protected override double CalculateDistance(double x1, double y1, double x2, double y2) {
-      return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
+      return EvaluateByDistanceMatrix(permutation, InversionMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.ActualValue);
     }
   }