Changeset 13470 for branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoOpt/PTSPEstimatedInversionMoveEvaluator.cs

Timestamp:

12/15/15 16:38:08 (8 years ago)

Author:

abeham

Message:

#2221:

• implemented review comments
  • hid rng as private class, implemented djb2 hash function (hash function implementation may also change)
  • added missing probabilities
  • base class for instance providers
  • prebuild event events
  • build platforms
  • unit test will be removed on trunk integration
  • corrected assembly file version
  • distance calculator parameter was not hidden, can be changed by user, updates distance matrix
  • fixed performance problems (ouch!) also for estimated ptsp (inlined GetDistance method)
• added moves (full evaluation) for analytical tsp
• added local improvement operators for analytical ptsp
• added recalculation of distance matrix when parameters change
• still lots of other changes

File:

• branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoOpt/PTSPEstimatedInversionMoveEvaluator.cs (modified) (5 diffs)

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

@@ -29 +29 @@
 
 namespace HeuristicLab.Problems.PTSP {
-  [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.")]
+  [Item("PTSP Estimated Inversion Move Evaluator", "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 PTSPEstimatedInversionMoveEvaluator : EstimatedPTSPMoveEvaluator, IPermutationInversionMoveOperator {
@@ -49 +49 @@
     }
 
-    public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, DistanceCalculator distanceCalculator, ItemList<BoolArray> realizations) {
+    public static double EvaluateMove(Permutation tour, InversionMove move, Func<int, int, double> distance, ItemList<BoolArray> realizations) {
       double moveQuality = 0;
       var edges = new int[4];
       var indices = new int[4];
-      edges[0] = permutation.GetCircular(move.Index1 - 1);
+      edges[0] = tour.GetCircular(move.Index1 - 1);
       indices[0] = move.Index1 - 1;
-      if (indices[0] == -1) indices[0] = permutation.Length - 1;
-      edges[1] = permutation[move.Index1];
+      if (indices[0] == -1) indices[0] = tour.Length - 1;
+      edges[1] = tour[move.Index1];
       indices[1] = move.Index1;
-      edges[2] = permutation[move.Index2];
+      edges[2] = tour[move.Index2];
       indices[2] = move.Index2;
-      edges[3] = permutation.GetCircular(move.Index2 + 1);
+      edges[3] = tour.GetCircular(move.Index2 + 1);
       indices[3] = move.Index2 + 1;
-      if (indices[3] == permutation.Length + 1) indices[3] = 0;
+      if (indices[3] == tour.Length + 1) indices[3] = 0;
       var aPosteriori = new int[4];
       foreach (var realization in realizations) {
@@ -72 +72 @@
             if (i % 2 == 0) {
               // find nearest predecessor in realization if source edge
-              while (!realization[permutation.GetCircular(indices[i] - j)]) {
+              while (!realization[tour.GetCircular(indices[i] - j)]) {
                 j++;
               }
-              aPosteriori[i] = permutation.GetCircular(indices[i] - j);
+              aPosteriori[i] = tour.GetCircular(indices[i] - j);
             } else {
               // find nearest successor in realization if target edge
-              while (!realization[permutation.GetCircular(indices[i] + j)]) {
+              while (!realization[tour.GetCircular(indices[i] + j)]) {
                 j++;
               }
-              aPosteriori[i] = permutation.GetCircular(indices[i] + j);
+              aPosteriori[i] = tour.GetCircular(indices[i] + j);
             }
           }
@@ -87 +87 @@
         // 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);
+          moveQuality = moveQuality + distance(aPosteriori[0], aPosteriori[2]) + distance(aPosteriori[1], aPosteriori[3])
+            - distance(aPosteriori[0], aPosteriori[1]) - distance(aPosteriori[2], aPosteriori[3]);
         }
         Array.Clear(aPosteriori, 0, aPosteriori.Length);
@@ -99 +96 @@
     }
 
-    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++;
-              }
-              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 + distanceMatrix[aPosteriori[0], aPosteriori[2]] + distanceMatrix[aPosteriori[1], aPosteriori[3]] - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]];
-        }
-        Array.Clear(aPosteriori, 0, aPosteriori.Length);
-      }
-      // return average of cost differences
-      return moveQuality / realizations.Count;
-    }
-
-    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.ActualValue);
+    protected override double EvaluateMove(Permutation tour, Func<int, int, double> distance, ItemList<BoolArray> realizations) {
+      return EvaluateMove(tour, InversionMoveParameter.ActualValue, distance, realizations);
     }
   }