Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 9596 was 9456, checked in by swagner, 12 years ago

Updated copyright year and added some missing license headers (#1889)

File size: 6.6 KB
RevLine 
[7743]1#region License Information
2/* HeuristicLab
[9456]3 * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[7743]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.Problems.TravelingSalesman;
27using HeuristicLab.Random;
28using Microsoft.VisualStudio.TestTools.UnitTesting;
29
30namespace HeuristicLab.Problems.TravelingSalesman_33.Tests {
31
32  /// <summary>
33  ///This is a test class for TSP move evaluators
34  ///</summary>
35  [TestClass()]
36  public class TSPMoveEvaluatorTest {
37    private const int ProblemSize = 10;
38    private static DoubleMatrix coordinates;
39    private static DistanceMatrix distances;
40    private static Permutation tour;
41    private static MersenneTwister random;
42
43    private TestContext testContextInstance;
44    /// <summary>
45    ///Gets or sets the test context which provides
46    ///information about and functionality for the current test run.
47    ///</summary>
48    public TestContext TestContext {
49      get { return testContextInstance; }
50      set { testContextInstance = value; }
51    }
52
53    [ClassInitialize]
54    public static void MyClassInitialize(TestContext testContext) {
55      random = new MersenneTwister();
56      coordinates = new DoubleMatrix(ProblemSize, 2);
57      distances = new DistanceMatrix(ProblemSize, ProblemSize);
58      for (int i = 0; i < ProblemSize; i++) {
59        coordinates[i, 0] = random.Next(ProblemSize * 10);
60        coordinates[i, 1] = random.Next(ProblemSize * 10);
61      }
62      for (int i = 0; i < ProblemSize - 1; i++) {
63        for (int j = i + 1; j < ProblemSize; j++) {
64          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)));
65          distances[j, i] = distances[i, j];
66        }
67      }
68      tour = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
69    }
70
71    [TestMethod]
72    public void InversionMoveEvaluatorTest() {
73      var evaluator = new TSPRoundedEuclideanPathEvaluator();
74      var moveEvaluator = new TSPInversionMoveRoundedEuclideanPathEvaluator();
75      double beforeMatrix = TSPDistanceMatrixEvaluator.Apply(distances, tour);
76      double beforeCoordinates = TSPCoordinatesPathEvaluator.Apply(evaluator, coordinates, tour);
77      Assert.IsTrue(beforeMatrix.IsAlmost(beforeCoordinates), "Evaluation differs between using the coordinates and using the distance matrix.");
78
79      for (int i = 0; i < 500; i++) {
80        var move = StochasticInversionSingleMoveGenerator.Apply(tour, random);
81
82        double moveMatrix = TSPInversionMovePathEvaluator.EvaluateByDistanceMatrix(tour, move, distances);
83        double moveCoordinates = TSPInversionMovePathEvaluator.EvaluateByCoordinates(tour, move, coordinates, moveEvaluator);
84        Assert.IsTrue(moveMatrix.IsAlmost(moveCoordinates), "Evaluation differs between using the coordinates and using the distance matrix.");
85
86        string failureString = string.Format(@"Inversion move is calculated with quality {0}, but actual difference is {4}.
87The move would invert the tour {1} between values {2} and {3}.", moveMatrix.ToString(), tour.ToString(), tour[move.Index1].ToString(), tour[move.Index2].ToString(), "{0}");
88
89        InversionManipulator.Apply(tour, move.Index1, move.Index2);
90
91        double afterMatrix = TSPDistanceMatrixEvaluator.Apply(distances, tour);
92        double afterCoordinates = TSPCoordinatesPathEvaluator.Apply(evaluator, coordinates, tour);
93        Assert.IsTrue(afterMatrix.IsAlmost(afterCoordinates), "Evaluation differs between using the coordinates and using the distance matrix.");
94
95        Assert.IsTrue(moveMatrix.IsAlmost(afterMatrix - beforeMatrix), string.Format(failureString, (afterMatrix - beforeMatrix).ToString()));
96
97        beforeMatrix = afterMatrix;
98        beforeCoordinates = afterCoordinates;
99      }
100    }
101
102    [TestMethod]
103    public void TranslocationMoveEvaluatorTest() {
104      var evaluator = new TSPRoundedEuclideanPathEvaluator();
105      var moveEvaluator = new TSPTranslocationMoveRoundedEuclideanPathEvaluator();
106      double beforeMatrix = TSPDistanceMatrixEvaluator.Apply(distances, tour);
107      double beforeCoordinates = TSPCoordinatesPathEvaluator.Apply(evaluator, coordinates, tour);
108      Assert.IsTrue(beforeMatrix.IsAlmost(beforeCoordinates), "Evaluation differs between using the coordinates and using the distance matrix.");
109
110      for (int i = 0; i < 500; i++) {
111        var move = StochasticTranslocationSingleMoveGenerator.Apply(tour, random);
112
113        double moveMatrix = TSPTranslocationMovePathEvaluator.EvaluateByDistanceMatrix(tour, move, distances);
114        double moveCoordinates = TSPTranslocationMovePathEvaluator.EvaluateByCoordinates(tour, move, coordinates, moveEvaluator);
115        Assert.IsTrue(moveMatrix.IsAlmost(moveCoordinates), "Evaluation differs between using the coordinates and using the distance matrix.");
116
117        string failureString = string.Format(@"Translocation move is calculated with quality {0}, but actual difference is {5}.
118The 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}");
119        TranslocationManipulator.Apply(tour, move.Index1, move.Index2, move.Index3);
120
121        double afterMatrix = TSPDistanceMatrixEvaluator.Apply(distances, tour);
122        double afterCoordinates = TSPCoordinatesPathEvaluator.Apply(evaluator, coordinates, tour);
123        Assert.IsTrue(afterMatrix.IsAlmost(afterCoordinates), "Evaluation differs between using the coordinates and using the distance matrix.");
124
125        Assert.IsTrue(moveMatrix.IsAlmost(afterMatrix - beforeMatrix), string.Format(failureString, (afterMatrix - beforeMatrix).ToString()));
126
127        beforeMatrix = afterMatrix;
128        beforeCoordinates = afterCoordinates;
129      }
130    }
131
132  }
133}
Note: See TracBrowser for help on using the repository browser.