Changeset 12261 for branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators

Timestamp:

03/26/15 16:14:52 (9 years ago)

Author:

apolidur

Message:

#2221: Fixing MoveEvaluators after running unit tests

Location:

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators

Files:

• OneShift/PTSPEstimatedInsertionEvaluator.cs (modified) (4 diffs)
• TwoOpt/PTSPEstimatedInversionMovePathEvaluator.cs (modified) (2 diffs)

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/OneShift/PTSPEstimatedInsertionEvaluator.cs

@@ -1 @@
-using HeuristicLab.Common;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Data;
@@ -7 +28 @@
 using System;
 
-namespace HeuristicLab.Problems.PTSP.MoveEvaluators.OneShift {
-  class PTSPEstimatedInsertionEvaluator : PTSPPathMoveEvaluator, IPermutationTranslocationMoveOperator {
+namespace HeuristicLab.Problems.PTSP {
+  [Item("PTSPEstimatedInsertionEvaluator", "Evaluates an insertion move (1-shift)")]
+  [StorableClass]
+  public class PTSPEstimatedInsertionEvaluator : PTSPPathMoveEvaluator, IPermutationTranslocationMoveOperator {
 
     public override Type EvaluatorType {
-      get { return typeof(PTSPEstimatedInversionMovePathEvaluator); }
+      get { return typeof(PTSPEstimatedInsertionEvaluator); }
     }
     public ILookupParameter<TranslocationMove> TranslocationMoveParameter {
@@ -54 +77 @@
 
     public static double EvaluateByDistanceMatrix(Permutation permutation, TranslocationMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) {
-      //permutation = new Permutation(PermutationTypes.Absolute, new int[]{0,1,2,3,4,5,6,7}); TODO remove test
-      //move = new TranslocationMove(0, 0, 4); TODO remove test
+      Permutation afterMove = new Permutation(PermutationTypes.RelativeUndirected,permutation);
+      TranslocationManipulator.Apply(afterMove, move.Index1, move.Index1, move.Index3);
       double moveQuality = 0;
       int[] edges = new int[12];
       int[] indices = new int[12];
       edges[0] = permutation.GetCircular(move.Index1 - 1);
-      edges[6] = edges[0];
-      indices[0] = move.Index1-1;
-      if (indices[0] == -1) indices[0] = permutation.Length - 1;
-      indices[6] = indices[0];
+      indices[0] = decreaseCircularIndex(permutation.Length, move.Index1);
       edges[1] = permutation[move.Index1];
       indices[1] = move.Index1;
-      edges[2] = edges[1];
-      indices[2] = indices[1];
-      edges[9] = edges[1];
-      indices[9] = indices[1];
-      edges[10] = edges[1];
-      indices[10] = indices[1];
+      edges[2] = permutation[move.Index1];
+      indices[2] = move.Index1;
       edges[3] = permutation.GetCircular(move.Index1 + 1);
-      edges[7] = edges[3];
-      indices[3] = move.Index1+1;
-      if (indices[3] == permutation.Length + 1) indices[3] = 0;
-      indices[7] = indices[3];
-      edges[4] = permutation[move.Index3];
-      indices[4] = move.Index3;
-      edges[8] = edges[4];
-      indices[8] = indices[4];
-      edges[5] = permutation.GetCircular(move.Index3 + 1);
-      edges[11] = edges[5];
-      indices[5] = move.Index3+1;
-      if (indices[5] == permutation.Length + 1) indices[5] = 0;
-      indices[11] = indices[5];
+      indices[3] = increaseCircularIndex(permutation.Length, move.Index1);
+
+      edges[6] = afterMove.GetCircular(move.Index3 - 1);
+      indices[6] = decreaseCircularIndex(afterMove.Length, move.Index3);
+      edges[7] = afterMove[move.Index3];
+      indices[7] = move.Index3;
+      edges[8] = afterMove[move.Index3];
+      indices[8] = move.Index3;
+      edges[9] = afterMove.GetCircular(move.Index3 + 1);
+      indices[9] = increaseCircularIndex(afterMove.Length, move.Index3);
+
+      if (move.Index3 > move.Index1) {
+        edges[4] = permutation[move.Index3];
+        indices[4] = move.Index3;
+        edges[5] = permutation.GetCircular(move.Index3 + 1);
+        indices[5] = indices[9];
+        edges[10] = afterMove.GetCircular(move.Index1 - 1);
+        indices[10] = indices[0];
+        edges[11] = afterMove[move.Index1];
+        indices[11] = move.Index1;
+      } else {
+        edges[4] = permutation.GetCircular(move.Index3 - 1);
+        indices[4] = indices[6];
+        edges[5] = permutation[move.Index3];
+        indices[5] = move.Index3;
+        edges[10] = afterMove[move.Index1];
+        indices[10] = move.Index1;
+        edges[11] = afterMove.GetCircular(move.Index1 + 1);
+        indices[11] = indices[3];
+      }
       int[] aPosteriori = new int[12];
+      Permutation tempPermutation;
       foreach (ItemList<IntValue> realization in realizations) {
-        //int[] realization2 = new int[] { 1, 0, 1, 1, 0, 0, 1, 1 }; TODO remove test
         for (int i = 0; i < edges.Length; i++) {
+          if (i < 6) {
+            tempPermutation = permutation;
+          } else {
+            tempPermutation = afterMove;
+          }
           if (realization[edges[i]].Value == 1) {
             aPosteriori[i] = edges[i];
@@ -96 +134 @@
             if (i%2==0) {
               // find nearest predecessor in realization if source edge
-              while(realization[permutation.GetCircular(indices[i]-j)].Value == 0) {
-                j--;
+              while (realization[tempPermutation.GetCircular(indices[i] - j)].Value == 0) {
+                j++;
               }
-              aPosteriori[i] = permutation.GetCircular(indices[i] - j);
+              aPosteriori[i] = tempPermutation.GetCircular(indices[i] - j);
             } else {
               // find nearest successor in realization if target edge
-              while(realization[permutation.GetCircular(indices[i]+j)].Value == 0) {
+              while (realization[tempPermutation.GetCircular(indices[i] + j)].Value == 0) {
                 j++;
               }
-              aPosteriori[i] = permutation.GetCircular(indices[i] + j);
+              aPosteriori[i] = tempPermutation.GetCircular(indices[i] + j);
             }
           }
         }
-        // compute cost difference between the two a posteriori solutions
-        moveQuality += distanceMatrix[aPosteriori[6], aPosteriori[7]] + distanceMatrix[aPosteriori[8], aPosteriori[9]] + distanceMatrix[aPosteriori[10], aPosteriori[11]];
-        moveQuality -= distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]] - distanceMatrix[aPosteriori[4], aPosteriori[5]];
+        if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3]) &&
+          !(aPosteriori[0] == aPosteriori[4] && aPosteriori[1] == aPosteriori[5]) &&
+          !(aPosteriori[2] == aPosteriori[4] && aPosteriori[3] == aPosteriori[5])) {
+          // compute cost difference between the two a posteriori solutions
+          moveQuality = moveQuality + distanceMatrix[aPosteriori[6], aPosteriori[7]] + distanceMatrix[aPosteriori[8], aPosteriori[9]] + distanceMatrix[aPosteriori[10], aPosteriori[11]];
+          moveQuality = moveQuality - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]] - distanceMatrix[aPosteriori[4], aPosteriori[5]];
+        }
+        Array.Clear(aPosteriori, 0, aPosteriori.Length);
       }
       // return average of cost differences
-      return moveQuality / realizations.Capacity;
+      return Math.Abs(moveQuality) / realizations.Capacity;
+    }
+
+    private static int decreaseCircularIndex(int length, int index) {
+      int result = index - 1;
+      if (result == -1) {
+        result = length - 1;
+      }
+      return result;
+    }
+
+    private static int increaseCircularIndex(int length, int index) {
+      int result = index + 1;
+      if (result == length + 1) {
+        result = 0;
+      }
+      return result;
     }
 

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/TwoOpt/PTSPEstimatedInversionMovePathEvaluator.cs

@@ -100 +100 @@
               // find nearest predecessor in realization if source edge
               while(realization[permutation.GetCircular(indices[i]-j)].Value==0) {
-                j--;
+                j++;
               }
               aPosteriori[i] = permutation.GetCircular(indices[i] - j);
@@ -113 +113 @@
         }
         // compute cost difference between the two a posteriori solutions
-        moveQuality += distanceMatrix[aPosteriori[0], aPosteriori[2]] + distanceMatrix[aPosteriori[1], aPosteriori[3]];
-        moveQuality -= distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]];
+        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.Capacity;
+      return Math.Abs(moveQuality) / realizations.Capacity;
     }