Changeset 12261

Timestamp:

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

Author:

apolidur

Message:

#2221: Fixing MoveEvaluators after running unit tests

Location:

branches/PTSP

Files:

• HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs (modified) (3 diffs)
• HeuristicLab.Problems.PTSP/3.3/HeuristicLab.Problems.PTSP-3.3.csproj (modified) (1 diff)
• HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPExhaustiveInsertionLocalImprovement.cs (modified) (1 diff)
• HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/OneShift/PTSPEstimatedInsertionEvaluator.cs (modified) (4 diffs)
• HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/TwoOpt/PTSPEstimatedInversionMovePathEvaluator.cs (modified) (2 diffs)
• HeuristicLab.Problems.PTSP/3.3/PTSP.cs (modified) (3 diffs)
• PTSP.sln (modified) (2 diffs)

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs

@@ -10 +10 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Data;
+using HeuristicLab.Random;
 using System;
 using System.Linq;
-using HeuristicLab.Problems.PTSP.MoveEvaluators.OneShift;
 
 namespace HeuristicLab.Problems.PTSP {
@@ -36 +36 @@
       Permutation p = individual.Permutation();
       // Estimation-based evaluation
-      Random r = new Random();
+      MersenneTwister r = new MersenneTwister();
       double estimatedSum = 0;
       for (int i = 0; i < realizations.Count; i++) {
-        int singleRealization = -1;
+        int singleRealization = -1, firstNode = -1;
         for (int j = 0; j < realizations[i].Count; j++) {
-          if (realizations[i][j].Value == 1) {
+          if (realizations[i][p[j]].Value == 1) {
             if (singleRealization != -1) {
               estimatedSum += DistanceMatrix[singleRealization, p[j]];
+            } else {
+              firstNode = p[j];
             }
             singleRealization = p[j];
           }
         }
+        if (singleRealization != -1) {
+          estimatedSum += DistanceMatrix[singleRealization, firstNode];
+        }
       }
       return estimatedSum / SampleSize.Value;
+    }
+
+    public double[] EvaluateWithParams(DistanceMatrix distances, DoubleArray probabilities, ItemList<ItemList<IntValue>> realizations, Permutation individual ) {
+      // Estimation-based evaluation
+      MersenneTwister r = new MersenneTwister();
+      double estimatedSum = 0;
+      double[] partialSums = new double[realizations.Count];
+      for (int i = 0; i < realizations.Count; i++) {
+        partialSums[i] = 0;
+        int singleRealization = -1, firstNode = -1;
+        for (int j = 0; j < realizations[i].Count; j++) {
+          if (realizations[i][individual[j]].Value == 1) {
+            if (singleRealization != -1) {
+              partialSums[i] += distances[singleRealization, individual[j]];
+            } else {
+              firstNode = individual[j];
+            }
+            singleRealization = individual[j];
+          }
+        }
+        if (singleRealization != -1) {
+          partialSums[i] += distances[singleRealization, firstNode];
+        }
+        estimatedSum += partialSums[i];
+      }
+      double mean = estimatedSum / realizations.Count;
+      double variance = 0;
+      for (int i = 0; i < realizations.Count; i++) {
+        variance += Math.Pow((partialSums[i] - mean), 2);
+      }
+      variance = variance / realizations.Count;
+      return new double[] {mean,variance};
     }
 
@@ -61 +98 @@
     }
 
+    private int Ttest(int ProblemSize) {
+      MersenneTwister random = new MersenneTwister();
+      Permutation p1 = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
+      Permutation p2 = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
+      ItemList<ItemList<IntValue>> realizations = new ItemList<ItemList<IntValue>>();
+      int index = -1;
+      while (true) {
+        for (int i = index+1; i < index+5; i++) {
+          realizations.Add(new ItemList<IntValue>());
+          for (int j = 0; j < ProblemSize; j++) {
+            if (ProbabilityMatrix[j] > random.NextDouble()) {
+              realizations.ElementAt(i).Add(new IntValue(1));
+            } else {
+              realizations.ElementAt(i).Add(new IntValue(0));
+            }
+          }
+        }
+        index += 4;
+        double[] eval1 = EvaluateWithParams(DistanceMatrix, ProbabilityMatrix, realizations, p1);
+        double[] eval2 = EvaluateWithParams(DistanceMatrix, ProbabilityMatrix, realizations, p2);
+        double sx1x2 = Math.Sqrt((eval1[1]+eval2[1])/2);
+        int degrees = 2 * realizations.Count - 2;
+        double t = (eval1[0]-eval2[0])/(sx1x2*Math.Sqrt(2.0/(double)realizations.Count));
+      }
+    }
+
     public override void Load(TSPData data) {
       base.Load(data);
       // For now uses sample size of 20 but should use Student's t-test
-      SampleSize = new IntValue(20);
+      //Ttest(data.Dimension);
+      SampleSize = new IntValue(25);
+      MersenneTwister r = new MersenneTwister();
+      int countOnes = 0;
       realizations = new ItemList<ItemList<IntValue>>(SampleSize.Value);
-      Random r = new Random();
       for (int i = 0; i < SampleSize.Value; i++) {
-        realizations.Add(new ItemList<IntValue>());
-        for (int j = 0; j < data.Dimension; j++) {
-          if (ProbabilityMatrix[j] > r.NextDouble()) {
-            realizations.ElementAt(i).Add(new IntValue(1));
-          } else {
-            realizations.ElementAt(i).Add(new IntValue(0));
+        ItemList<IntValue> newRealization = new ItemList<IntValue>();
+        while (countOnes < 4) { //only generate realizations with at least 4 cities visited
+          countOnes = 0;
+          newRealization.Clear();
+          for (int j = 0; j < data.Dimension; j++) {
+            if (ProbabilityMatrix[j] > r.NextDouble()) {
+              newRealization.Add(new IntValue(1));
+              countOnes++;
+            } else {
+              newRealization.Add(new IntValue(0));
+            }
           }
         }
-        
+        countOnes = 0;
+        realizations.Add(newRealization);
       }
 

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/HeuristicLab.Problems.PTSP-3.3.csproj

@@ -98 +98 @@
       <Private>False</Private>
     </Reference>
+    <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
+    </Reference>
     <Reference Include="System" />
     <Reference Include="System.Core" />

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPExhaustiveInsertionLocalImprovement.cs

@@ -30 +30 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using System.Threading;
-using HeuristicLab.Problems.PTSP.MoveEvaluators.OneShift;
 
 namespace HeuristicLab.Problems.PTSP {

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;
     }
 

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/PTSP.cs

@@ -34 +34 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Data;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Problems.PTSP {
@@ -133 +134 @@
       Description = data.Description;
 
+      // Get Probabilities of cities using random with seed from hash function on the Name of the instance
+      double[] tempMatrix = new double[data.Dimension];
+      MersenneTwister r = new MersenneTwister((uint)data.Name.GetHashCode());
+      for (int i = 0; i < data.Dimension; i++) {
+        tempMatrix[i] = r.NextDouble();
+      }
+      ProbabilityMatrix = new DoubleArray(tempMatrix);
+
+      if (data.BestKnownTour != null) {
+        BestKnownSolution = new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour);
+      }
+      
       bool clearCoordinates = false, clearDistanceMatrix = false;
       if (data.Coordinates != null && data.Coordinates.GetLength(0) > 0)
@@ -143 +156 @@
 
       DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
-      // Get Probabilities of cities using random with seed from hash function on the Name of the instance
-      ProbabilityMatrix = new DoubleArray(data.Dimension);
-      Random r = new Random(data.Name.GetHashCode());
-      for (int i = 0; i < data.Dimension; i++) {
-        ProbabilityMatrix[i] = r.NextDouble();
-      }
+      
       Encoding.Length = data.Dimension;
 

branches/PTSP/PTSP.sln

@@ -7 +7 @@
 EndProject
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.PTSP.Views-3.3", "HeuristicLab.Problems.PTSP.Views\3.3\HeuristicLab.Problems.PTSP.Views-3.3.csproj", "{90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}"
+EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.PTSP.Tests-3.3", "HeuristicLab.Problems.PTSP.Tests-3.3\HeuristicLab.Problems.PTSP.Tests-3.3.csproj", "{CBEC171A-F7EC-460D-94E2-D58625811D99}"
 EndProject
 Global
@@ -22 +24 @@
     {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Release|Any CPU.ActiveCfg = Release|Any CPU
     {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Release|Any CPU.Build.0 = Release|Any CPU
+    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Debug|Any CPU.Build.0 = Debug|Any CPU
+    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Release|Any CPU.ActiveCfg = Release|Any CPU
+    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Release|Any CPU.Build.0 = Release|Any CPU
   EndGlobalSection
   GlobalSection(SolutionProperties) = preSolution