source: branches/PTSP/HeuristicLab.Problems.PTSP.Tests-3.3/PTSPMoveEvaluatorTest.cs @ 12760

using System;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Random;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System.Diagnostics;

namespace HeuristicLab.Problems.PTSP.Tests_3._3 {
  /// <summary>
  ///This is a test class for PTSP move evaluators
  ///</summary>
  [TestClass()]
  public class PTSPMoveEvaluatorTest {
    private const int ProblemSize = 10;
    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;

    [ClassInitialize]
    public static void MyClassInitialize(TestContext testContext) {
      random = new MersenneTwister();
      coordinates = new DoubleMatrix(ProblemSize, 2);
      distances = new DistanceMatrix(ProblemSize, ProblemSize);
      for (int 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++) {
          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];
        }
      }

      ProbabilityMatrix = new DoubleArray(ProblemSize);
      for (int i = 0; i < ProblemSize; i++) {
        ProbabilityMatrix[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>();
        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));
            }
          }
        }
        countOnes = 0;
        realizations.Add(newRealization);
      }

      tour = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
    }

    [TestMethod]
    [TestCategory("Problems.TravelingSalesman")]
    [TestProperty("Time", "short")]
    public void InversionMoveEvaluatorTest() {

      EstimatedProbabilisticTravelingSalesmanProblem ePTSP = new EstimatedProbabilisticTravelingSalesmanProblem();

      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()));

        beforeMatrix = afterMatrix;
      }
    }

    [TestMethod]
    [TestCategory("Problems.TravelingSalesman")]
    [TestProperty("Time", "short")]
    public void InsertionMoveEvaluatorTest() {

      EstimatedProbabilisticTravelingSalesmanProblem ePTSP = new EstimatedProbabilisticTravelingSalesmanProblem();

      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()));

        beforeMatrix = afterMatrix;
      }
    }

    [TestMethod]
    [TestCategory("Problems.TravelingSalesman")]
    [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];

        AnalyticalProbabilisticTravelingSalesmanProblem aPTSP = new AnalyticalProbabilisticTravelingSalesmanProblem();
        double analytical = aPTSP.EvaluateWithParams(distances, ProbabilityMatrix, tour);
        Console.WriteLine(Math.Abs(analytical-estimated));
      }
    }
  }
}