1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  * HeuristicLab is free software: you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation, either version 3 of the License, or


10  * (at your option) any later version.


11  *


12  * HeuristicLab is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


19  */


20  #endregion


21 


22  using System;


23  using HeuristicLab.Common;


24  using HeuristicLab.Data;


25  using HeuristicLab.Encodings.PermutationEncoding;


26  using HeuristicLab.Random;


27  using Microsoft.VisualStudio.TestTools.UnitTesting;


28 


29  namespace HeuristicLab.Problems.TravelingSalesman.Tests {


30  /// <summary>


31  ///This is a test class for TSP move evaluators


32  ///</summary>


33  [TestClass()]


34  public class TSPMoveEvaluatorTest {


35  private const int ProblemSize = 10;


36  private static DoubleMatrix coordinates;


37  private static DistanceMatrix distances;


38  private static Permutation tour;


39  private static MersenneTwister random;


40 


41  [ClassInitialize]


42  public static void MyClassInitialize(TestContext testContext) {


43  random = new MersenneTwister();


44  coordinates = new DoubleMatrix(ProblemSize, 2);


45  distances = new DistanceMatrix(ProblemSize, ProblemSize);


46  for (int i = 0; i < ProblemSize; i++) {


47  coordinates[i, 0] = random.Next(ProblemSize * 10);


48  coordinates[i, 1] = random.Next(ProblemSize * 10);


49  }


50  for (int i = 0; i < ProblemSize  1; i++) {


51  for (int j = i + 1; j < ProblemSize; j++) {


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


53  distances[j, i] = distances[i, j];


54  }


55  }


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


57  }


58 


59  [TestMethod]


60  [TestCategory("Problems.TravelingSalesman")]


61  [TestProperty("Time", "short")]


62  public void InversionMoveEvaluatorTest() {


63  var evaluator = new TSPRoundedEuclideanPathEvaluator();


64  var moveEvaluator = new TSPInversionMoveRoundedEuclideanPathEvaluator();


65  double beforeMatrix = TSPDistanceMatrixEvaluator.Apply(distances, tour);


66  double beforeCoordinates = TSPCoordinatesPathEvaluator.Apply(evaluator, coordinates, tour);


67  Assert.IsTrue(beforeMatrix.IsAlmost(beforeCoordinates), "Evaluation differs between using the coordinates and using the distance matrix.");


68 


69  for (int i = 0; i < 500; i++) {


70  var move = StochasticInversionSingleMoveGenerator.Apply(tour, random);


71 


72  double moveMatrix = TSPInversionMovePathEvaluator.EvaluateByDistanceMatrix(tour, move, distances);


73  double moveCoordinates = TSPInversionMovePathEvaluator.EvaluateByCoordinates(tour, move, coordinates, moveEvaluator);


74  Assert.IsTrue(moveMatrix.IsAlmost(moveCoordinates), "Evaluation differs between using the coordinates and using the distance matrix.");


75 


76  string failureString = string.Format(@"Inversion move is calculated with quality {0}, but actual difference is {4}.


77  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}");


78 


79  InversionManipulator.Apply(tour, move.Index1, move.Index2);


80 


81  double afterMatrix = TSPDistanceMatrixEvaluator.Apply(distances, tour);


82  double afterCoordinates = TSPCoordinatesPathEvaluator.Apply(evaluator, coordinates, tour);


83  Assert.IsTrue(afterMatrix.IsAlmost(afterCoordinates), "Evaluation differs between using the coordinates and using the distance matrix.");


84 


85  Assert.IsTrue(moveMatrix.IsAlmost(afterMatrix  beforeMatrix), string.Format(failureString, (afterMatrix  beforeMatrix).ToString()));


86 


87  beforeMatrix = afterMatrix;


88  beforeCoordinates = afterCoordinates;


89  }


90  }


91 


92  [TestMethod]


93  [TestCategory("Problems.TravelingSalesman")]


94  [TestProperty("Time", "short")]


95  public void TranslocationMoveEvaluatorTest() {


96  var evaluator = new TSPRoundedEuclideanPathEvaluator();


97  var moveEvaluator = new TSPTranslocationMoveRoundedEuclideanPathEvaluator();


98  double beforeMatrix = TSPDistanceMatrixEvaluator.Apply(distances, tour);


99  double beforeCoordinates = TSPCoordinatesPathEvaluator.Apply(evaluator, coordinates, tour);


100  Assert.IsTrue(beforeMatrix.IsAlmost(beforeCoordinates), "Evaluation differs between using the coordinates and using the distance matrix.");


101 


102  for (int i = 0; i < 500; i++) {


103  var move = StochasticTranslocationSingleMoveGenerator.Apply(tour, random);


104 


105  double moveMatrix = TSPTranslocationMovePathEvaluator.EvaluateByDistanceMatrix(tour, move, distances);


106  double moveCoordinates = TSPTranslocationMovePathEvaluator.EvaluateByCoordinates(tour, move, coordinates, moveEvaluator);


107  Assert.IsTrue(moveMatrix.IsAlmost(moveCoordinates), "Evaluation differs between using the coordinates and using the distance matrix.");


108 


109  string failureString = string.Format(@"Translocation move is calculated with quality {0}, but actual difference is {5}.


110  The move would move the segment between {1} and {2} in the tour {3} to the new index {4}.", moveMatrix.ToString(), tour[move.Index1].ToString(), tour[move.Index2].ToString(), tour.ToString(), move.Index3.ToString(), "{0}");


111  TranslocationManipulator.Apply(tour, move.Index1, move.Index2, move.Index3);


112 


113  double afterMatrix = TSPDistanceMatrixEvaluator.Apply(distances, tour);


114  double afterCoordinates = TSPCoordinatesPathEvaluator.Apply(evaluator, coordinates, tour);


115  Assert.IsTrue(afterMatrix.IsAlmost(afterCoordinates), "Evaluation differs between using the coordinates and using the distance matrix.");


116 


117  Assert.IsTrue(moveMatrix.IsAlmost(afterMatrix  beforeMatrix), string.Format(failureString, (afterMatrix  beforeMatrix).ToString()));


118 


119  beforeMatrix = afterMatrix;


120  beforeCoordinates = afterCoordinates;


121  }


122  }


123 


124  }


125  }

