Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Analysis.AlgorithmBehavior/AlgorithmBehaviorUnitTests/DistanceMatrixToPointsTest.cs @ 10743

Last change on this file since 10743 was 10132, checked in by ascheibe, 11 years ago

#1886 updated unit test to take account for rounding errors
File size: 14.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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.Analysis.AlgorithmBehavior.Analyzers;
24using HeuristicLab.Common;
25using HeuristicLab.Encodings.PermutationEncoding;
26using HeuristicLab.Problems.TravelingSalesman;
27using Microsoft.VisualStudio.TestTools.UnitTesting;
28
29namespace AlgorithmBehaviorUnitTests {
30  [TestClass]
31  public class DistanceMatrixToPointsTest {
32    [TestMethod]
33    public void TestMetricMDSStatic() {
34      int nrOfPoints = 3;
35      int dim = 2;
36      double[][] orgPoints = new double[nrOfPoints][];
37      double[][] orgDm = new double[nrOfPoints][];
38      double[][] newDm = new double[nrOfPoints][];
39      double[][] newPoints = null;
40
41      AllocArray(orgPoints, dim);
42      AllocArray(orgDm, nrOfPoints);
43      AllocArray(newDm, nrOfPoints);
44      StaticPoints(orgPoints);
45      CalculateDistanceMatrix(orgDm, orgPoints);
46
47      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm, dim, true);
48
49      CalculateDistanceMatrix(newDm, newPoints);
50      Console.WriteLine("orgDm:");
51      PrintDM(orgDm);
52      Console.WriteLine("newDm:");
53      PrintDM(newDm);
54
55      for (int i = 0; i < orgDm.Length; i++) {
56        for (int j = 0; j < orgDm.Length; j++) {
57          double diff = orgDm[i][j] - newDm[i][j];
58          Assert.IsTrue(diff.IsAlmost(0.0));
59        }
60      }
61    }
62
63    [TestMethod]
64    public void TestMetricMDSRandom() {
65      int nrOfPoints = 30;
66      int dim = 10;
67      double[][] orgPoints = new double[nrOfPoints][];
68      double[][] orgDm = new double[nrOfPoints][];
69      double[][] newDm = new double[nrOfPoints][];
70      double[][] newPoints = null;
71
72      AllocArray(orgPoints, dim);
73      AllocArray(orgDm, nrOfPoints);
74      AllocArray(newDm, nrOfPoints);
75      SamplePoints(orgPoints);
76      CalculateDistanceMatrix(orgDm, orgPoints);
77
78      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm, dim);
79
80      CalculateDistanceMatrix(newDm, newPoints);
81      Console.WriteLine("orgDm:");
82      PrintDM(orgDm);
83      Console.WriteLine("newDm:");
84      PrintDM(newDm);
85
86      for (int i = 0; i < orgDm.Length; i++) {
87        for (int j = 0; j < orgDm.Length; j++) {
88          double diff = orgDm[i][j] - newDm[i][j];
89          Assert.IsTrue(diff.IsAlmost(0.0));
90        }
91      }
92    }
93
94    [TestMethod]
95    public void TestDistanceMatrixConversionStatic() {
96      int nrOfPoints = 3;
97      int dim = 2;
98      double[][] orgPoints = new double[nrOfPoints][];
99      double[][] orgDm = new double[nrOfPoints][];
100      double[][] newDm = new double[nrOfPoints][];
101      double[][] newPoints = null;
102
103      AllocArray(orgPoints, dim);
104      AllocArray(orgDm, nrOfPoints);
105      AllocArray(newDm, nrOfPoints);
106      StaticPoints(orgPoints);
107      CalculateDistanceMatrix(orgDm, orgPoints);
108
109      newPoints = DistanceMatrixToPoints.ConvertDistanceMatrixToPoints(orgDm);
110
111      CalculateDistanceMatrix(newDm, newPoints);
112      Console.WriteLine("orgDm:");
113      PrintDM(orgDm);
114      Console.WriteLine("newDm:");
115      PrintDM(newDm);
116
117      for (int i = 0; i < orgDm.Length; i++) {
118        for (int j = 0; j < orgDm.Length; j++) {
119          double diff = orgDm[i][j] - newDm[i][j];
120          Assert.IsTrue(diff.IsAlmost(0.0));
121        }
122      }
123    }
124
125    [TestMethod]
126    public void TestDistanceMatrixConversionDynamic() {
127      int nrOfPoints = 30;
128      int dim = 20;
129      double[][] orgPoints = new double[nrOfPoints][];
130      double[][] orgDm = new double[nrOfPoints][];
131      double[][] newDm = new double[nrOfPoints][];
132      double[][] newPoints = null;
133
134      AllocArray(orgPoints, dim);
135      AllocArray(orgDm, nrOfPoints);
136      AllocArray(newDm, nrOfPoints);
137      SamplePoints(orgPoints);
138      CalculateDistanceMatrix(orgDm, orgPoints);
139
140      newPoints = DistanceMatrixToPoints.ConvertDistanceMatrixToPoints(orgDm, dim);
141
142      CalculateDistanceMatrix(newDm, newPoints);
143      Console.WriteLine("orgDm:");
144      PrintDM(orgDm);
145      Console.WriteLine("newDm:");
146      PrintDM(newDm);
147
148      for (int i = 0; i < orgDm.Length; i++) {
149        for (int j = 0; j < orgDm.Length; j++) {
150          double diff = orgDm[i][j] - newDm[i][j];
151          Assert.IsTrue(diff.IsAlmost(0.0));
152        }
153      }
154    }
155
156    [TestMethod]
157    public void TestMetricMDSForPermutations() {
158      int nrOfPoints = 30;
159      int dim = 5;
160      Permutation[] orgPoints = new Permutation[nrOfPoints];
161      double[][] orgDm;
162      double[][] newDm = new double[nrOfPoints][];
163      double[][] newPoints = null;
164
165      AllocArray(newDm, nrOfPoints);
166
167      SamplePermutations(orgPoints, dim);
168      orgDm = CalculateDistanceMatrixFromPermutations(orgPoints);
169
170      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm, dim);
171
172      CalculateDistanceMatrix(newDm, newPoints);
173      Console.WriteLine("orgDm:");
174      PrintDM(orgDm);
175      Console.WriteLine("newDm:");
176      PrintDM(newDm);
177
178      for (int i = 0; i < orgDm.Length; i++) {
179        for (int j = 0; j < orgDm.Length; j++) {
180          double diff = Math.Abs(orgDm[i][j] - newDm[i][j]);
181          if (diff < 0.0000001) diff = 0.0;
182          Assert.IsTrue(diff.IsAlmost(0.0));
183        }
184      }
185    }
186
187    [TestMethod]
188    public void TestMetricMDSForPermutationsStatic() {
189      int nrOfPoints = 10;
190      int dim = 5;
191
192      double[][] orgDm = StaticPermutationDM();
193      double[][] newDm = new double[nrOfPoints][];
194      double[][] newPoints = null;
195
196      AllocArray(newDm, nrOfPoints);
197
198      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm, dim, false);
199
200      CalculateDistanceMatrix(newDm, newPoints);
201      Console.WriteLine("orgDm:");
202      PrintDM(orgDm);
203      Console.WriteLine("newDm:");
204      PrintDM(newDm);
205
206      double[][] resultDMFromR = StaticPermutationDMResult();
207
208      for (int i = 0; i < orgDm.Length; i++) {
209        for (int j = 0; j < orgDm.Length; j++) {
210          double diff = Math.Abs(resultDMFromR[i][j] - Math.Round(newDm[i][j], 7));
211          if (diff < 0.000001) diff = 0.0;
212          Assert.IsTrue(diff.IsAlmost(0.0));
213
214          diff = Math.Abs(orgDm[i][j] - newDm[i][j]);
215          if (diff < 0.00000001) diff = 0.0;
216          Assert.IsTrue(diff.IsAlmost(0.0));
217        }
218      }
219    }
220
221    [TestMethod]
222    public void TestMetricMDSForSmallDistances() {
223      int nrOfPoints = 4;
224      int dim = 2;
225      double[][] orgPoints = new double[nrOfPoints][];
226      double[][] orgDm = new double[nrOfPoints][];
227      double[][] newDm = new double[nrOfPoints][];
228      double[][] newPoints = null;
229
230      AllocArray(orgPoints, dim);
231      AllocArray(orgDm, nrOfPoints);
232      AllocArray(newDm, nrOfPoints);
233      SmallDiffStaticPoints(orgPoints);
234      CalculateDistanceMatrix(orgDm, orgPoints);
235
236      Console.WriteLine("orgDm:");
237      PrintDM(orgDm);
238
239      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm, dim, false);
240
241      CalculateDistanceMatrix(newDm, newPoints);
242      Console.WriteLine("newDm:");
243      PrintDM(newDm);
244
245      for (int i = 0; i < orgDm.Length; i++) {
246        for (int j = 0; j < orgDm.Length; j++) {
247          double diff = Math.Abs(orgDm[i][j] - newDm[i][j]);
248          if (diff < 0.00000001) diff = 0.0;
249          Assert.IsTrue(diff.IsAlmost(0.0));
250        }
251      }
252    }
253
254    private static void SmallDiffStaticPoints(double[][] points) {
255      points[0][0] = 1;
256      points[0][1] = 1;
257
258      points[1][0] = 1.03;
259      points[1][1] = 1.2;
260
261      points[2][0] = 1.05;
262      points[2][1] = 1.01;
263
264      points[3][0] = 1.5;
265      points[3][1] = 1.1;
266    }
267
268    private static double[][] StaticPermutationDM() {
269      double[][] dm = new double[10][];
270      AllocArray(dm, 10);
271
272      dm[0] = new[]
273      {
274        0, 1.09544511501033, 1.09544511501033, 0.894427190999916, 0.894427190999916, 1.09544511501033, 0.894427190999916,
275        1.09544511501033, 0.894427190999916, 0.894427190999916
276      };
277      dm[1] = new[]
278      {
279        1.09544511501033, 0, 1.09544511501033, 1.4142135623731, 0.894427190999916, 1.09544511501033, 0.894427190999916,
280        1.09544511501033, 0.894427190999916, 0.894427190999916
281      };
282      dm[2] = new[]
283      {
284        1.09544511501033, 1.09544511501033, 0, 0.894427190999916, 0.894427190999916, 1.09544511501033, 0.894427190999916,
285        1.09544511501033, 0.894427190999916, 0.894427190999916
286      };
287      dm[3] = new[]
288      {
289        0.894427190999916, 1.4142135623731, 0.894427190999916, 0, 1.09544511501033, 0.894427190999916, 1.09544511501033,
290        0.894427190999916, 1.09544511501033, 1.09544511501033
291      };
292      dm[4] = new[]
293      {
294        0.894427190999916, 0.894427190999916, 0.894427190999916, 1.09544511501033, 0, 0.894427190999916, 0,
295        0.894427190999916, 1.09544511501033, 1.09544511501033
296      };
297      dm[5] = new[]
298      {
299        1.09544511501033, 1.09544511501033, 1.09544511501033, 0.894427190999916, 0.894427190999916, 0, 0.894427190999916,
300        1.09544511501033, 0.894427190999916, 1.4142135623731
301      };
302      dm[6] = new[]
303      {
304        0.894427190999916, 0.894427190999916, 0.894427190999916, 1.09544511501033, 0, 0.894427190999916, 0,
305        0.894427190999916, 1.09544511501033, 1.09544511501033
306      };
307      dm[7] = new[]
308      {
309        1.09544511501033, 1.09544511501033, 1.09544511501033, 0.894427190999916, 0.894427190999916, 1.09544511501033,
310        0.894427190999916, 0, 1.4142135623731, 0.894427190999916
311      };
312      dm[8] = new[]
313      {
314        0.894427190999916, 0.894427190999916, 0.894427190999916, 1.09544511501033, 1.09544511501033, 0.894427190999916,
315        1.09544511501033, 1.4142135623731, 0, 1.09544511501033
316      };
317      dm[9] = new[]
318      {
319        0.894427190999916, 0.894427190999916, 0.894427190999916, 1.09544511501033, 1.09544511501033, 1.4142135623731,
320        1.09544511501033, 0.894427190999916, 1.09544511501033, 0
321      };
322
323      return dm;
324    }
325
326    private static double[][] StaticPermutationDMResult() {
327      double[][] dm = new double[10][];
328      AllocArray(dm, 10);
329
330      dm[0] = new[]
331      {
332        0.0000000,1.0954451,1.0954451,0.8944272,8.944272e-01,1.0954451,8.944272e-01,1.0954451,0.8944272,0.8944272
333      };
334      dm[1] = new[]
335      {
336        1.0954451,0.0000000,1.0954451,1.4142136,8.944272e-01,1.0954451,8.944272e-01,1.0954451,0.8944272,0.8944272       
337      };
338      dm[2] = new[]
339      {
340        1.0954451,1.0954451,0.0000000,0.8944272,8.944272e-01,1.0954451,8.944272e-01,1.0954451,0.8944272,0.8944272
341      };
342      dm[3] = new[]
343      {
344        0.8944272,1.4142136,0.8944272,0.0000000,1.095445e+00,0.8944272,1.095445e+00,0.8944272,1.0954451,1.0954451       
345      };
346      dm[4] = new[]
347      {
348        0.8944272,0.8944272,0.8944272,1.0954451,0.000000e+00,0.8944272,4.331115e-16,0.8944272,1.0954451,1.0954451
349      };
350      dm[5] = new[]
351      {
352        1.0954451,1.0954451,1.0954451,0.8944272,8.944272e-01,0.0000000,8.944272e-01,1.0954451,0.8944272,1.4142136 
353      };
354      dm[6] = new[]
355      {
356        0.8944272,0.8944272,0.8944272,1.0954451,4.331115e-16,0.8944272,0.000000e+00,0.8944272,1.0954451,1.0954451       
357      };
358      dm[7] = new[]
359      {
360        1.0954451,1.0954451,1.0954451,0.8944272,8.944272e-01,1.0954451,8.944272e-01,0.0000000,1.4142136,0.8944272
361      };
362      dm[8] = new[]
363      {
364        0.8944272,0.8944272,0.8944272,1.0954451,1.095445e+00,0.8944272,1.095445e+00,1.4142136,0.0000000,1.0954451       
365      };
366      dm[9] = new[]
367      {
368        0.8944272,0.8944272,0.8944272,1.0954451,1.095445e+00,1.4142136,1.095445e+00,0.8944272,1.0954451,0.0000000       
369      };
370
371      return dm;
372    }
373
374    private static void PrintDM(double[][] dm) {
375      for (int i = 0; i < dm.Length; i++) {
376        for (int j = 0; j < dm.Length; j++) {
377          Console.Write(dm[i][j] + " ");
378        }
379        Console.WriteLine();
380      }
381    }
382
383    private static void SamplePoints(double[][] points) {
384      Random rand = new Random();
385
386      for (int i = 0; i < points.Length; i++) {
387        for (int j = 0; j < points[i].Length; j++) {
388          points[i][j] = rand.NextDouble() * 100;
389        }
390      }
391    }
392
393    private static void SamplePermutations(Permutation[] points, int dim) {
394      var rand = new HeuristicLab.Random.FastRandom();
395
396      for (int i = 0; i < points.Length; i++) {
397        var p = new Permutation(PermutationTypes.RelativeUndirected, dim, rand);
398        points[i] = p;
399      }
400    }
401
402    private static void StaticPoints(double[][] points) {
403      points[0][0] = 2;
404      points[0][1] = 1;
405
406      points[1][0] = 5;
407      points[1][1] = 5;
408
409      points[2][0] = 3;
410      points[2][1] = 7;
411    }
412
413    private static void CalculateDistanceMatrix(double[][] dm, double[][] points) {
414      for (int i = 0; i < points.Length; i++) {
415        for (int j = 0; j < points.Length; j++) {
416          dm[i][j] = points[i].EuclideanDistance(points[j]);
417        }
418      }
419    }
420
421    private static double[][] CalculateDistanceMatrixFromPermutations(Permutation[] points) {
422      double[][] tmpDm = new double[points.Length][];
423      AllocArray(tmpDm, points.Length);
424
425      for (int i = 0; i < points.Length; i++) {
426        for (int j = 0; j < points.Length; j++) {
427          double diversity = TSPSimilarityCalculator.CalculateSimilarity(points[i], points[j]);
428          tmpDm[i][j] = diversity;
429        }
430      }
431
432      return DistanceMatrixToPoints.TransformToDistances(tmpDm);
433    }
434
435    private static void AllocArray(double[][] arr, int size) {
436      for (int i = 0; i < arr.Length; i++) {
437        arr[i] = new double[size];
438      }
439    }
440  }
441}
Note: See TracBrowser for help on using the repository browser.