Changeset 13412 for branches/PTSP/HeuristicLab.Problems.PTSP.Tests-3.3/PTSPMoveEvaluatorTest.cs

Timestamp:

11/28/15 23:38:51 (8 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

File:

• branches/PTSP/HeuristicLab.Problems.PTSP.Tests-3.3/PTSPMoveEvaluatorTest.cs (modified) (8 diffs)

branches/PTSP/HeuristicLab.Problems.PTSP.Tests-3.3/PTSPMoveEvaluatorTest.cs

@@ -1 @@
-using System;
+#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 System;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -6 +27 @@
 using HeuristicLab.Random;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
-using System.Diagnostics;
 
-namespace HeuristicLab.Problems.PTSP.Tests_3._3 {
+namespace HeuristicLab.Problems.PTSP.Tests {
   /// <summary>
   ///This is a test class for PTSP move evaluators
@@ -15 +35 @@
   public class PTSPMoveEvaluatorTest {
     private const int ProblemSize = 10;
+    private const int RealizationsSize = 100;
     private static DoubleMatrix coordinates;
     private static DistanceMatrix distances;
     private static Permutation tour;
     private static MersenneTwister random;
-    private static ItemList<ItemList<IntValue>> realizations;
-    private static DoubleArray ProbabilityMatrix;
+    private static ItemList<BoolArray> realizations;
+    private static DoubleArray probabilities;
 
     [ClassInitialize]
@@ -27 +48 @@
       coordinates = new DoubleMatrix(ProblemSize, 2);
       distances = new DistanceMatrix(ProblemSize, ProblemSize);
-      for (int i = 0; i < ProblemSize; i++) {
+      for (var i = 0; i < ProblemSize; i++) {
         coordinates[i, 0] = random.Next(ProblemSize * 10);
         coordinates[i, 1] = random.Next(ProblemSize * 10);
       }
-      for (int i = 0; i < ProblemSize - 1; i++) {
-        for (int j = i + 1; j < ProblemSize; j++) {
+      for (var i = 0; i < ProblemSize - 1; i++) {
+        for (var j = i + 1; j < ProblemSize; j++) {
           distances[i, j] = Math.Round(Math.Sqrt(Math.Pow(coordinates[i, 0] - coordinates[j, 0], 2) + Math.Pow(coordinates[i, 1] - coordinates[j, 1], 2)));
           distances[j, i] = distances[i, j];
@@ -38 +59 @@
       }
 
-      ProbabilityMatrix = new DoubleArray(ProblemSize);
-      for (int i = 0; i < ProblemSize; i++) {
-        ProbabilityMatrix[i] = random.NextDouble();
+      probabilities = new DoubleArray(ProblemSize);
+      for (var i = 0; i < ProblemSize; i++) {
+        probabilities[i] = random.NextDouble();
       }
 
-      int numRealizations = 100;
-      int countOnes = 0;
-      realizations = new ItemList<ItemList<IntValue>>(numRealizations);
-      for (int i = 0; i < numRealizations; i++) {
-        ItemList<IntValue> newRealization = new ItemList<IntValue>();
+      realizations = new ItemList<BoolArray>(RealizationsSize);
+      for (var i = 0; i < RealizationsSize; i++) {
+        var countOnes = 0;
+        var newRealization = new BoolArray(ProblemSize);
         while (countOnes < 4) { //only generate realizations with at least 4 cities visited
           countOnes = 0;
-          newRealization.Clear();
-          for (int j = 0; j < ProblemSize; j++) {
-            if (ProbabilityMatrix[j] > random.NextDouble()) {
-              newRealization.Add(new IntValue(1));
-              countOnes++;
-            } else {
-              newRealization.Add(new IntValue(0));
-            }
+          for (var j = 0; j < ProblemSize; j++) {
+            newRealization[j] = random.NextDouble() < probabilities[j];
+            if (newRealization[j]) countOnes++;
           }
         }
-        countOnes = 0;
         realizations.Add(newRealization);
       }
@@ -68 +82 @@
 
     [TestMethod]
-    [TestCategory("Problems.TravelingSalesman")]
+    [TestCategory("Problems.ProbabilisticTravelingSalesman")]
     [TestProperty("Time", "short")]
     public void InversionMoveEvaluatorTest() {
+      var beforeMatrix = EstimatedProbabilisticTravelingSalesmanProblem.Evaluate(tour, distances, realizations)[0];
 
-      EstimatedProbabilisticTravelingSalesmanProblem ePTSP = new EstimatedProbabilisticTravelingSalesmanProblem();
+      for (var i = 0; i < 500; i++) {
+        var move = StochasticInversionSingleMoveGenerator.Apply(tour, random);
+        var moveMatrix = PTSPEstimatedInversionMoveEvaluator.EvaluateByDistanceMatrix(tour, move, distances, realizations);
+        InversionManipulator.Apply(tour, move.Index1, move.Index2);
+        var afterMatrix = EstimatedProbabilisticTravelingSalesmanProblem.Evaluate(tour, distances, realizations)[0];
 
-      double beforeMatrix = ePTSP.EvaluateWithParams(distances, ProbabilityMatrix, realizations, tour)[0];
-
-      for (int i = 0; i < 500; i++) {
-        var move = StochasticInversionSingleMoveGenerator.Apply(tour, random);
-
-        double moveMatrix = PTSPEstimatedInversionEvaluator.EvaluateByDistanceMatrix(tour, move, distances,realizations);
-
-        string failureString = string.Format(@"Inversion move is calculated with quality {0}, but actual difference is {4}.
-The move would invert the tour {1} between values {2} and {3}.", moveMatrix.ToString(), tour.ToString(), tour[move.Index1].ToString(), tour[move.Index2].ToString(), "{0}");
-
-        InversionManipulator.Apply(tour, move.Index1, move.Index2);
-
-        double afterMatrix = ePTSP.EvaluateWithParams(distances, ProbabilityMatrix, realizations, tour)[0];
-
-        Assert.IsTrue(Math.Abs(moveMatrix).IsAlmost(Math.Abs(afterMatrix - beforeMatrix)), string.Format(failureString, (Math.Abs(afterMatrix - beforeMatrix)).ToString()));
+        Assert.IsTrue(Math.Abs(moveMatrix).IsAlmost(Math.Abs(afterMatrix - beforeMatrix)),
+          string.Format(@"Inversion move is calculated with quality {0}, but actual difference is {4}.
+The move would invert the tour {1} between values {2} and {3}.",
+          moveMatrix, tour, tour[move.Index1], tour[move.Index2], Math.Abs(afterMatrix - beforeMatrix)));
 
         beforeMatrix = afterMatrix;
@@ -95 +103 @@
 
     [TestMethod]
-    [TestCategory("Problems.TravelingSalesman")]
+    [TestCategory("Problems.ProbabilisticTravelingSalesman")]
     [TestProperty("Time", "short")]
     public void InsertionMoveEvaluatorTest() {
+      var beforeMatrix = EstimatedProbabilisticTravelingSalesmanProblem.Evaluate(tour, distances, realizations)[0];
 
-      EstimatedProbabilisticTravelingSalesmanProblem ePTSP = new EstimatedProbabilisticTravelingSalesmanProblem();
+      for (var i = 0; i < 500; i++) {
+        var move = StochasticTranslocationSingleMoveGenerator.Apply(tour, random);
+        var moveMatrix = PTSPEstimatedInsertionMoveEvaluator.EvaluateByDistanceMatrix(tour, move, distances, realizations);
+        TranslocationManipulator.Apply(tour, move.Index1, move.Index1, move.Index3);
+        var afterMatrix = EstimatedProbabilisticTravelingSalesmanProblem.Evaluate(tour, distances, realizations)[0];
 
-      double beforeMatrix = ePTSP.EvaluateWithParams(distances, ProbabilityMatrix, realizations, tour)[0];
-
-      for (int i = 0; i < 500; i++) {
-        var move = StochasticTranslocationSingleMoveGenerator.Apply(tour, random);
-
-        double moveMatrix = PTSPEstimatedInsertionEvaluator.EvaluateByDistanceMatrix(tour, move, distances, realizations);
-
-        string failureString = string.Format(@"Inversion move is calculated with quality {0}, but actual difference is {4}.
-The move would invert the tour {1} between values {2} and {3}.", moveMatrix.ToString(), tour.ToString(), tour[move.Index1].ToString(), tour[move.Index2].ToString(), "{0}");
-
-        TranslocationManipulator.Apply(tour, move.Index1, move.Index1, move.Index3);
-
-        double afterMatrix = ePTSP.EvaluateWithParams(distances, ProbabilityMatrix, realizations, tour)[0];
-
-        Assert.IsTrue(Math.Abs(moveMatrix).IsAlmost(Math.Abs(afterMatrix - beforeMatrix)), string.Format(failureString, (Math.Abs(afterMatrix - beforeMatrix)).ToString()));
+        Assert.IsTrue(Math.Abs(moveMatrix).IsAlmost(Math.Abs(afterMatrix - beforeMatrix)),
+          string.Format(@"Insertion move is calculated with quality {0}, but actual difference is {4}.
+The move would invert the tour {1} between values {2} and {3}.",
+          moveMatrix, tour, tour[move.Index1], tour[move.Index2], Math.Abs(afterMatrix - beforeMatrix)));
 
         beforeMatrix = afterMatrix;
@@ -122 +124 @@
 
     [TestMethod]
-    [TestCategory("Problems.TravelingSalesman")]
+    [TestCategory("Problems.ProbabilisticTravelingSalesman")]
     [TestProperty("Time", "short")]
     public void AnalyticalTest() {
-      for (int i = 0; i < 10; i++) {
-        tour = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
-        EstimatedProbabilisticTravelingSalesmanProblem ePTSP = new EstimatedProbabilisticTravelingSalesmanProblem();
-        double estimated = ePTSP.EvaluateWithParams(distances, ProbabilityMatrix, realizations, tour)[0];
+      for (var i = 0; i < 10; i++) {
+        var perm = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
+        var estimated = EstimatedProbabilisticTravelingSalesmanProblem.Evaluate(perm, distances, realizations)[0];
 
-        AnalyticalProbabilisticTravelingSalesmanProblem aPTSP = new AnalyticalProbabilisticTravelingSalesmanProblem();
-        double analytical = aPTSP.EvaluateWithParams(distances, ProbabilityMatrix, tour);
-        Console.WriteLine(Math.Abs(analytical-estimated));
+        var analytical = AnalyticalProbabilisticTravelingSalesmanProblem.Evaluate(perm, distances, probabilities);
+        Console.WriteLine(Math.Abs(analytical - estimated));
       }
     }