Free cookie consent management tool by TermsFeed Policy Generator

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

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

#1886 fixed a bug in metric mds and added another unit test
File size: 14.6 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 = 10;
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, true);
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 = orgDm[i][j] - newDm[i][j];
181          Assert.IsTrue(diff.IsAlmost(0.0));
182        }
183      }
184    }
185
186    [TestMethod]
187    public void TestMetricMDSForPermutationsStatic() {
188      int nrOfPoints = 15;
189      int dim = 5;
190
191      double[][] orgDm = StaticPermutationDM();
192      double[][] newDm = new double[nrOfPoints][];
193      double[][] newPoints = null;
194
195      AllocArray(newDm, nrOfPoints);
196
197      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm, dim, true);
198
199      CalculateDistanceMatrix(newDm, newPoints);
200      Console.WriteLine("orgDm:");
201      PrintDM(orgDm);
202      Console.WriteLine("newDm:");
203      PrintDM(newDm);
204
205      for (int i = 0; i < orgDm.Length; i++) {
206        for (int j = 0; j < orgDm.Length; j++) {
207          double diff = Math.Abs(orgDm[i][j] - newDm[i][j]);
208          if (diff < 0.000001) diff = 0.0;
209          Assert.IsTrue(diff.IsAlmost(0.0));
210        }
211      }
212    }
213
214    [TestMethod]
215    public void TestMetricMDSForSmallDistances() {
216      int nrOfPoints = 4;
217      int dim = 2;
218      double[][] orgPoints = new double[nrOfPoints][];
219      double[][] orgDm = new double[nrOfPoints][];
220      double[][] newDm = new double[nrOfPoints][];
221      double[][] newPoints = null;
222
223      AllocArray(orgPoints, dim);
224      AllocArray(orgDm, nrOfPoints);
225      AllocArray(newDm, nrOfPoints);
226      SmallDiffStaticPoints(orgPoints);
227      CalculateDistanceMatrix(orgDm, orgPoints);
228
229      Console.WriteLine("orgDm:");
230      PrintDM(orgDm);
231
232      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm, dim, true);
233
234      CalculateDistanceMatrix(newDm, newPoints);
235      Console.WriteLine("newDm:");
236      PrintDM(newDm);
237
238      for (int i = 0; i < orgDm.Length; i++) {
239        for (int j = 0; j < orgDm.Length; j++) {
240          double diff = orgDm[i][j] - newDm[i][j];
241          Assert.IsTrue(diff.IsAlmost(0.0));
242        }
243      }
244    }
245
246    private static void SmallDiffStaticPoints(double[][] points) {
247      points[0][0] = 1;
248      points[0][1] = 1;
249
250      points[1][0] = 1.03;
251      points[1][1] = 1.2;
252
253      points[2][0] = 1.05;
254      points[2][1] = 1.01;
255
256      points[3][0] = 1.5;
257      points[3][1] = 1.1;
258    }
259
260    private static double[][] StaticPermutationDM() {
261      double[][] dm = new double[15][];
262      AllocArray(dm, 15);
263
264      dm[0] = new[] {
265        0, 1.09544511501033, 1.09544511501033, 0.894427190999916, 0.894427190999916, 1.4142135623731, 0.894427190999916,
266        0, 1.09544511501033, 1.09544511501033, 0, 1.09544511501033, 1.09544511501033,
267        1.4142135623731, 0.894427190999916 };
268      dm[1] = new[]
269      {
270        1.09544511501033, 0, 1.09544511501033, 0.894427190999916, 0.894427190999916, 0.894427190999916, 0.894427190999916,
271        1.09544511501033, 1.09544511501033, 1.09544511501033, 1.09544511501033, 1.09544511501033, 1.09544511501033,
272        0.894427190999916, 0.894427190999916
273      };
274      dm[2] = new[]
275      {
276        1.09544511501033, 1.09544511501033, 0, 0.894427190999916, 0.894427190999916, 0.894427190999916, 1.4142135623731,
277        1.09544511501033, 1.09544511501033, 1.09544511501033, 1.09544511501033, 0, 1.09544511501033, 0.894427190999916,
278        0.894427190999916
279      };
280      dm[3] = new[]
281      {
282        0.894427190999916, 0.894427190999916, 0.894427190999916, 0, 1.09544511501033, 1.09544511501033, 1.09544511501033,
283        0.894427190999916, 1.4142135623731, 0.894427190999916, 0.894427190999916, 0.894427190999916, 0.894427190999916,
284        1.09544511501033, 1.09544511501033
285      };
286      dm[4] = new[]
287      {
288        0.894427190999916, 0.894427190999916, 0.894427190999916, 1.09544511501033, 0, 1.09544511501033, 1.09544511501033,
289        0.894427190999916, 0.894427190999916, 1.4142135623731, 0.894427190999916, 0.894427190999916, 1.4142135623731,
290        1.09544511501033, 0
291      };
292      dm[5] = new[]
293      {
294        1.4142135623731, 0.894427190999916, 0.894427190999916, 1.09544511501033, 1.09544511501033, 0, 1.09544511501033,
295        1.4142135623731, 0.894427190999916, 0.894427190999916, 1.4142135623731, 0.894427190999916, 0.894427190999916, 0,
296        1.09544511501033
297      };
298      dm[6] = new[]
299      {
300        0.894427190999916, 0.894427190999916, 1.4142135623731, 1.09544511501033, 1.09544511501033, 1.09544511501033, 0,
301        0.894427190999916, 0.894427190999916, 0.894427190999916, 0.894427190999916, 1.4142135623731, 0.894427190999916,
302        1.09544511501033, 1.09544511501033
303      };
304      dm[7] = new[]
305      {
306        0, 1.09544511501033, 1.09544511501033, 0.894427190999916, 0.894427190999916, 1.4142135623731, 0.894427190999916,
307        0, 1.09544511501033, 1.09544511501033, 0, 1.09544511501033, 1.09544511501033, 1.4142135623731, 0.894427190999916
308      };
309      dm[8] = new[]
310      {
311        1.09544511501033, 1.09544511501033, 1.09544511501033, 1.4142135623731, 0.894427190999916, 0.894427190999916,
312        0.894427190999916, 1.09544511501033, 0, 1.09544511501033, 1.09544511501033, 1.09544511501033, 1.09544511501033,
313        0.894427190999916, 0.894427190999916
314      };
315      dm[9] = new[]
316      {
317        1.09544511501033, 1.09544511501033, 1.09544511501033, 0.894427190999916, 1.4142135623731, 0.894427190999916,
318        0.894427190999916, 1.09544511501033, 1.09544511501033, 0, 1.09544511501033, 1.09544511501033, 0,
319        0.894427190999916, 1.4142135623731
320      };
321      dm[10] = new[]
322      {
323        0, 1.09544511501033, 1.09544511501033, 0.894427190999916, 0.894427190999916, 1.4142135623731, 0.894427190999916,
324        0, 1.09544511501033, 1.09544511501033, 0, 1.09544511501033, 1.09544511501033, 1.4142135623731, 0.894427190999916
325      };
326      dm[11] = new[]
327      {
328        1.09544511501033, 1.09544511501033, 0, 0.894427190999916, 0.894427190999916, 0.894427190999916, 1.4142135623731,
329        1.09544511501033, 1.09544511501033, 1.09544511501033, 1.09544511501033, 0, 1.09544511501033, 0.894427190999916,
330        0.894427190999916
331      };
332      dm[12] = new[]
333      {
334        1.09544511501033, 1.09544511501033, 1.09544511501033, 0.894427190999916, 1.4142135623731, 0.894427190999916,
335        0.894427190999916, 1.09544511501033, 1.09544511501033, 0, 1.09544511501033, 1.09544511501033, 0,
336        0.894427190999916, 1.4142135623731
337      };
338      dm[13] = new[]
339      {
340        1.4142135623731, 0.894427190999916, 0.894427190999916, 1.09544511501033, 1.09544511501033, 0, 1.09544511501033,
341        1.4142135623731, 0.894427190999916, 0.894427190999916, 1.4142135623731, 0.894427190999916, 0.894427190999916, 0,
342        1.09544511501033
343      };
344      dm[14] = new[]
345      {
346        0.894427190999916, 0.894427190999916, 0.894427190999916, 1.09544511501033, 0, 1.09544511501033, 1.09544511501033,
347        0.894427190999916, 0.894427190999916, 1.4142135623731, 0.894427190999916, 0.894427190999916, 1.4142135623731,
348        1.09544511501033, 0
349      };
350      return dm;
351    }
352
353    private static void PrintDM(double[][] dm) {
354      for (int i = 0; i < dm.Length; i++) {
355        for (int j = 0; j < dm.Length; j++) {
356          Console.Write(dm[i][j] + " ");
357        }
358        Console.WriteLine();
359      }
360    }
361
362    private static void SamplePoints(double[][] points) {
363      Random rand = new Random();
364
365      for (int i = 0; i < points.Length; i++) {
366        for (int j = 0; j < points[i].Length; j++) {
367          points[i][j] = rand.NextDouble() * 100;
368        }
369      }
370    }
371
372    private static void SamplePermutations(Permutation[] points, int dim) {
373      var rand = new HeuristicLab.Random.FastRandom();
374
375      for (int i = 0; i < points.Length; i++) {
376        var p = new Permutation(PermutationTypes.RelativeUndirected, dim, rand);
377        points[i] = p;
378      }
379    }
380
381    private static void StaticPoints(double[][] points) {
382      points[0][0] = 2;
383      points[0][1] = 1;
384
385      points[1][0] = 5;
386      points[1][1] = 5;
387
388      points[2][0] = 3;
389      points[2][1] = 7;
390    }
391
392    private static void CalculateDistanceMatrix(double[][] dm, double[][] points) {
393      for (int i = 0; i < points.Length; i++) {
394        for (int j = 0; j < points.Length; j++) {
395          dm[i][j] = points[i].EuclideanDistance(points[j]);
396        }
397      }
398    }
399
400    private static double[][] CalculateDistanceMatrixFromPermutations(Permutation[] points) {
401      double[][] tmpDm = new double[points.Length][];
402      AllocArray(tmpDm, points.Length);
403
404      for (int i = 0; i < points.Length; i++) {
405        for (int j = 0; j < points.Length; j++) {
406          double diversity = TSPSimilarityCalculator.CalculateSimilarity(points[i], points[j]);
407          tmpDm[i][j] = diversity;
408        }
409      }
410
411      return DistanceMatrixToPoints.TransformToDistances(tmpDm);
412    }
413
414    private static void AllocArray(double[][] arr, int size) {
415      for (int i = 0; i < arr.Length; i++) {
416        arr[i] = new double[size];
417      }
418    }
419  }
420}
Note: See TracBrowser for help on using the repository browser.