Changeset 10109

Timestamp:

11/05/13 23:57:18 (10 years ago)

Author:

ascheibe

Message:

#1886 fixed other MDS and added more unit tests

Location:

branches/HeuristicLab.Analysis.AlgorithmBehavior

Files:

• AlgorithmBehaviorUnitTests/AlgorithmBehaviorUnitTests.csproj (modified) (1 diff)
• AlgorithmBehaviorUnitTests/DistanceMatrixToPointsTest.cs (modified) (5 diffs)
• HeuristicLab.Analysis.AlgorithmBehavior.Analyzers.Views/3.3/PermutationConvexHullView.cs (modified) (1 diff)
• HeuristicLab.Analysis.AlgorithmBehavior.Analyzers/3.3/DistanceMatrixToPoints.cs (modified) (2 diffs)

branches/HeuristicLab.Analysis.AlgorithmBehavior/AlgorithmBehaviorUnitTests/AlgorithmBehaviorUnitTests.csproj

@@ -61 +61 @@
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Optimization-3.3.dll</HintPath>
     </Reference>
+    <Reference Include="HeuristicLab.Optimization.Operators-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Optimization.Operators-3.3.dll</HintPath>
+    </Reference>
     <Reference Include="HeuristicLab.PluginInfrastructure-3.3">
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.PluginInfrastructure-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Problems.TravelingSalesman-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Problems.TravelingSalesman-3.3.dll</HintPath>
     </Reference>
     <Reference Include="HeuristicLab.Random-3.3">

branches/HeuristicLab.Analysis.AlgorithmBehavior/AlgorithmBehaviorUnitTests/DistanceMatrixToPointsTest.cs

@@ -23 +23 @@
 using HeuristicLab.Analysis.AlgorithmBehavior.Analyzers;
 using HeuristicLab.Common;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Problems.TravelingSalesman;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
 
@@ -29 +31 @@
   public class DistanceMatrixToPointsTest {
     [TestMethod]
+    public void TestMetricMDSStatic() {
+      int nrOfPoints = 3;
+      int dim = 2;
+      double[][] orgPoints = new double[nrOfPoints][];
+      double[][] orgDm = new double[nrOfPoints][];
+      double[][] newDm = new double[nrOfPoints][];
+      double[][] newPoints = null;
+
+      AllocArray(orgPoints, dim);
+      AllocArray(orgDm, nrOfPoints);
+      AllocArray(newDm, nrOfPoints);
+      StaticPoints(orgPoints);
+      CalculateDistanceMatrix(orgDm, orgPoints);
+
+      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm);
+
+      CalculateDistanceMatrix(newDm, newPoints);
+      Console.WriteLine("orgDm:");
+      PrintDM(orgDm);
+      Console.WriteLine("newDm:");
+      PrintDM(newDm);
+
+      for (int i = 0; i < orgDm.Length; i++) {
+        for (int j = 0; j < orgDm.Length; j++) {
+          double diff = orgDm[i][j] - newDm[i][j];
+          Assert.IsTrue(diff.IsAlmost(0.0));
+        }
+      }
+    }
+
+    [TestMethod]
+    public void TestMetricMDSRandom() {
+      int nrOfPoints = 30;
+      int dim = 10;
+      double[][] orgPoints = new double[nrOfPoints][];
+      double[][] orgDm = new double[nrOfPoints][];
+      double[][] newDm = new double[nrOfPoints][];
+      double[][] newPoints = null;
+
+      AllocArray(orgPoints, dim);
+      AllocArray(orgDm, nrOfPoints);
+      AllocArray(newDm, nrOfPoints);
+      SamplePoints(orgPoints);
+      CalculateDistanceMatrix(orgDm, orgPoints);
+
+      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm, dim);
+
+      CalculateDistanceMatrix(newDm, newPoints);
+      Console.WriteLine("orgDm:");
+      PrintDM(orgDm);
+      Console.WriteLine("newDm:");
+      PrintDM(newDm);
+
+      for (int i = 0; i < orgDm.Length; i++) {
+        for (int j = 0; j < orgDm.Length; j++) {
+          double diff = orgDm[i][j] - newDm[i][j];
+          Assert.IsTrue(diff.IsAlmost(0.0));
+        }
+      }
+    }
+
+    [TestMethod]
     public void TestDistanceMatrixConversionStatic() {
       int nrOfPoints = 3;
@@ -40 +104 @@
       AllocArray(orgDm, nrOfPoints);
       AllocArray(newDm, nrOfPoints);
-      //SamplePoints(orgPoints);
       StaticPoints(orgPoints);
       CalculateDistanceMatrix(orgDm, orgPoints);
 
-      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm);
+      newPoints = DistanceMatrixToPoints.ConvertDistanceMatrixToPoints(orgDm);
+
+      CalculateDistanceMatrix(newDm, newPoints);
+      Console.WriteLine("orgDm:");
+      PrintDM(orgDm);
+      Console.WriteLine("newDm:");
+      PrintDM(newDm);
+
+      for (int i = 0; i < orgDm.Length; i++) {
+        for (int j = 0; j < orgDm.Length; j++) {
+          double diff = orgDm[i][j] - newDm[i][j];
+          Assert.IsTrue(diff.IsAlmost(0.0));
+        }
+      }
+    }
+
+    [TestMethod]
+    public void TestDistanceMatrixConversionDynamic() {
+      int nrOfPoints = 30;
+      int dim = 20;
+      double[][] orgPoints = new double[nrOfPoints][];
+      double[][] orgDm = new double[nrOfPoints][];
+      double[][] newDm = new double[nrOfPoints][];
+      double[][] newPoints = null;
+
+      AllocArray(orgPoints, dim);
+      AllocArray(orgDm, nrOfPoints);
+      AllocArray(newDm, nrOfPoints);
+      SamplePoints(orgPoints);
+      CalculateDistanceMatrix(orgDm, orgPoints);
+
+      newPoints = DistanceMatrixToPoints.ConvertDistanceMatrixToPoints(orgDm, dim);
+
+      CalculateDistanceMatrix(newDm, newPoints);
+      Console.WriteLine("orgDm:");
+      PrintDM(orgDm);
+      Console.WriteLine("newDm:");
+      PrintDM(newDm);
+
+      for (int i = 0; i < orgDm.Length; i++) {
+        for (int j = 0; j < orgDm.Length; j++) {
+          double diff = orgDm[i][j] - newDm[i][j];
+          Assert.IsTrue(diff.IsAlmost(0.0));
+        }
+      }
+    }
+
+    [TestMethod]
+    public void TestMetricMDSForPermutations() {
+      int nrOfPoints = 30;
+      int dim = 20;
+      Permutation[] orgPoints = new Permutation[nrOfPoints];
+      double[][] orgDm;
+      double[][] newDm = new double[nrOfPoints][];
+      double[][] newPoints = null;
+
+      AllocArray(newDm, nrOfPoints);
+
+      SamplePermutations(orgPoints, dim);
+      orgDm = CalculateDistanceMatrixFromPermutations(orgPoints);
+
+      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm, dim);
 
       CalculateDistanceMatrix(newDm, newPoints);
@@ -79 +203 @@
     }
 
+    private static void SamplePermutations(Permutation[] points, int dim) {
+      var rand = new HeuristicLab.Random.FastRandom();
+
+      for (int i = 0; i < points.Length; i++) {
+        var p = new Permutation(PermutationTypes.RelativeUndirected, dim, rand);
+        points[i] = p;
+      }
+    }
+
     private static void StaticPoints(double[][] points) {
       points[0][0] = 2;
@@ -98 +231 @@
     }
 
+    private static double[][] CalculateDistanceMatrixFromPermutations(Permutation[] points) {
+      double[][] tmpDm = new double[points.Length][];
+      AllocArray(tmpDm, points.Length);
+
+      for (int i = 0; i < points.Length; i++) {
+        for (int j = 0; j < points.Length; j++) {
+          double diversity = TSPSimilarityCalculator.CalculateSimilarity(points[i], points[j]);
+          tmpDm[i][j] = diversity;
+        }
+      }
+
+      return DistanceMatrixToPoints.TransformToDistances(tmpDm);
+    }
+
     private static void AllocArray(double[][] arr, int size) {
       for (int i = 0; i < arr.Length; i++) {

branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior.Analyzers.Views/3.3/PermutationConvexHullView.cs

@@ -54 +54 @@
         }
 
-        double[][] popPoints = DistanceMatrixToPoints.ConvertDistanceMatrixToPoints(dm);
+        double[][] popPoints = DistanceMatrixToPoints.ConvertDistanceMatrixToPoints(DistanceMatrixToPoints.TransformToDistances(dm));
 
         var convexHull = HyperHull.CalculateUsingSMO(popPoints);

branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior.Analyzers/3.3/DistanceMatrixToPoints.cs

@@ -33 +33 @@
      *   
      */
-    public static double[][] ConvertDistanceMatrixToPoints(double[][] dm) {
+    public static double[][] ConvertDistanceMatrixToPoints(double[][] dm, int k = 2) {
       double[][] points = new double[dm.Length][];
       double[,] m = new double[dm.Length, dm.Length];
@@ -45 +45 @@
       }
 
-      //QR decomposition to get the upper part for smatrixevd
-      double[] tau;
-      double[,] r;
-      alglib.rmatrixqr(ref m, dm.Length, dm.Length, out tau);
-      alglib.rmatrixqrunpackr(m, dm.Length, dm.Length, out r);
-
-      bool res = alglib.smatrixevd(r, dm.Length, 1, true, out q, out v);
+      bool res = alglib.smatrixevd(m, dm.Length, 1, true, out q, out v);
       if (!res) throw new Exception("Eigenvalue computation did not converge!");
 
-      int zeroCnt = q.Count(x => x.IsAlmost(0) || x < 0.0);
-      for (int i = 0; i < dm.Length; i++) {
-        points[i] = new double[dm.Length - zeroCnt];
-      }
-
-      int pi = 0;
-      for (int i = 0; i < dm.Length; i++) {
-        if (!q[i].IsAlmost(0.0) && q[i] > 0.0) {
-          for (int j = 0; j < dm.Length; j++) {
-            points[j][pi] = Math.Sqrt(q[i]) * v[j, i];
-          }
-          pi++;
+      //TODO: this should also work without allocating memory for ev and evec
+      double[] ev = new double[k];
+      double[][] evec = new double[dm.Length][];
+      AllocArray(evec, k);
+      Array.Copy(q, q.Length - k, ev, 0, k);
+      for (int i = 0; i < k; i++) {
+        for (int j = 0; j < dm.Length; j++) {
+          evec[j][i] = v[j, i + (q.Length - k)];
         }
       }
 
+      double k1 = SumIfLZero(ev);
+      if (k1 < k) {
+        throw new Exception("Zero-eigenvalues detected. This leads to a degenerate point set. Use constants. ");
+        //TODO: handling of this case; implement adding of constants
+      }
+
+      AllocArray(points, k);
+      for (int i = 0; i < k; i++) {
+        for (int j = 0; j < dm.Length; j++) {
+          points[j][i] = Math.Sqrt(ev[i]) * evec[j][i];
+        }
+      }
       return points;
     }