Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Tests/HeuristicLab.Problems.TravelingSalesman-3.3/TSPMoveEvaluatorTest.cs @ 14185

Last change on this file since 14185 was 14185, checked in by swagner, 8 years ago

#2526: Updated year of copyrights in license headers

File size: 6.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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
22using System;
23using HeuristicLab.Common;
24using HeuristicLab.Data;
25using HeuristicLab.Encodings.PermutationEncoding;
26using HeuristicLab.Random;
27using Microsoft.VisualStudio.TestTools.UnitTesting;
28
29namespace 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}.
77The 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}.
110The 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}
Note: See TracBrowser for help on using the repository browser.