Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Tests/HeuristicLab.Problems.PTSP-3.3/PTSPMoveEvaluatorTest.cs @ 13484

Last change on this file since 13484 was 13484, checked in by abeham, 8 years ago

#2221: integrated PTSP into trunk

File size: 5.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.PermutationEncoding;
27using HeuristicLab.Random;
28using Microsoft.VisualStudio.TestTools.UnitTesting;
29
30namespace HeuristicLab.Problems.PTSP.Tests {
31  /// <summary>
32  ///This is a test class for PTSP move evaluators
33  ///</summary>
34  [TestClass()]
35  public class PTSPMoveEvaluatorTest {
36    private const int ProblemSize = 10;
37    private const int RealizationsSize = 100;
38    private static DoubleMatrix coordinates;
39    private static DistanceMatrix distances;
40    private static Permutation tour;
41    private static MersenneTwister random;
42    private static ItemList<BoolArray> realizations;
43    private static DoubleArray probabilities;
44
45    [ClassInitialize]
46    public static void MyClassInitialize(TestContext testContext) {
47      random = new MersenneTwister();
48      coordinates = new DoubleMatrix(ProblemSize, 2);
49      distances = new DistanceMatrix(ProblemSize, ProblemSize);
50      for (var i = 0; i < ProblemSize; i++) {
51        coordinates[i, 0] = random.Next(ProblemSize * 10);
52        coordinates[i, 1] = random.Next(ProblemSize * 10);
53      }
54      for (var i = 0; i < ProblemSize - 1; i++) {
55        for (var j = i + 1; j < ProblemSize; j++) {
56          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)));
57          distances[j, i] = distances[i, j];
58        }
59      }
60
61      probabilities = new DoubleArray(ProblemSize);
62      for (var i = 0; i < ProblemSize; i++) {
63        probabilities[i] = random.NextDouble();
64      }
65
66      realizations = new ItemList<BoolArray>(RealizationsSize);
67      for (var i = 0; i < RealizationsSize; i++) {
68        var countOnes = 0;
69        var newRealization = new BoolArray(ProblemSize);
70        while (countOnes < 4) { //only generate realizations with at least 4 cities visited
71          countOnes = 0;
72          for (var j = 0; j < ProblemSize; j++) {
73            newRealization[j] = random.NextDouble() < probabilities[j];
74            if (newRealization[j]) countOnes++;
75          }
76        }
77        realizations.Add(newRealization);
78      }
79
80      tour = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
81    }
82
83    [TestMethod]
84    [TestCategory("Problems.ProbabilisticTravelingSalesman")]
85    [TestProperty("Time", "short")]
86    public void InversionMoveEvaluatorTest() {
87      Func<int, int, double> distance = (a, b) => distances[a, b];
88      double variance;
89      var beforeMatrix = EstimatedProbabilisticTravelingSalesmanProblem.Evaluate(tour, distance, realizations, out variance);
90
91      for (var i = 0; i < 500; i++) {
92        var move = StochasticInversionSingleMoveGenerator.Apply(tour, random);
93        var moveMatrix = PTSPEstimatedInversionMoveEvaluator.EvaluateMove(tour, move, distance, realizations);
94        InversionManipulator.Apply(tour, move.Index1, move.Index2);
95        var afterMatrix = EstimatedProbabilisticTravelingSalesmanProblem.Evaluate(tour, distance, realizations, out variance);
96
97        Assert.IsTrue(Math.Abs(moveMatrix).IsAlmost(Math.Abs(afterMatrix - beforeMatrix)),
98          string.Format(@"Inversion move is calculated with quality {0}, but actual difference is {4}.
99The move would invert the tour {1} between values {2} and {3}.",
100          moveMatrix, tour, tour[move.Index1], tour[move.Index2], Math.Abs(afterMatrix - beforeMatrix)));
101
102        beforeMatrix = afterMatrix;
103      }
104    }
105
106    [TestMethod]
107    [TestCategory("Problems.ProbabilisticTravelingSalesman")]
108    [TestProperty("Time", "short")]
109    public void InsertionMoveEvaluatorTest() {
110      Func<int, int, double> distance = (a, b) => distances[a, b];
111      double variance;
112      var beforeMatrix = EstimatedProbabilisticTravelingSalesmanProblem.Evaluate(tour, distance, realizations, out variance);
113      for (var i = 0; i < 500; i++) {
114        var move = StochasticTranslocationSingleMoveGenerator.Apply(tour, random);
115        var moveMatrix = PTSPEstimatedInsertionMoveEvaluator.EvaluateMove(tour, move, distance, realizations);
116        TranslocationManipulator.Apply(tour, move.Index1, move.Index1, move.Index3);
117        var afterMatrix = EstimatedProbabilisticTravelingSalesmanProblem.Evaluate(tour, distance, realizations, out variance);
118
119        Assert.IsTrue(Math.Abs(moveMatrix).IsAlmost(Math.Abs(afterMatrix - beforeMatrix)),
120          string.Format(@"Insertion move is calculated with quality {0}, but actual difference is {4}.
121The move would invert the tour {1} between values {2} and {3}.",
122          moveMatrix, tour, tour[move.Index1], tour[move.Index2], Math.Abs(afterMatrix - beforeMatrix)));
123
124        beforeMatrix = afterMatrix;
125      }
126    }
127  }
128}
Note: See TracBrowser for help on using the repository browser.