Changeset 10081

Timestamp:

10/23/13 15:56:50 (11 years ago)

Author:

ascheibe

Message:

#1886 fixed LPHull, seems to work now

Location:

branches/HeuristicLab.Analysis.AlgorithmBehavior

Files:

• AlgorithmBehaviorUnitTests/ConvexHullTest.cs (modified) (1 diff)
• AlgorithmBehaviorUnitTests/LPConvexHullTest.cs (modified) (2 diffs)
• HeuristicLab.Analysis.AlgorithmBehavior.Analyzers/3.3/LPHull.cs (modified) (7 diffs)

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

@@ -28 +28 @@
 using Microsoft.VisualStudio.TestTools.UnitTesting;
 
-namespace Visualization {
+namespace AlgorithmBehaviorUnitTests {
   [TestClass]
   public class ConvexHullTest {

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

@@ -28 +28 @@
 using Microsoft.VisualStudio.TestTools.UnitTesting;
 
-namespace Visualization {
+namespace AlgorithmBehaviorUnitTests {
   [TestClass]
   public class LPConvexHullTest {
     [TestMethod]
     public void TestMethod1() {
-      int nrOfSamples = 10;
+      int nrOfSamples = 70;
       int sampleSize = 2;
       double[][] inputs = CreateRandomData(nrOfSamples, sampleSize);
@@ -70 +70 @@
     }
 
+    [TestMethod]
+    public void TestExt() {
+      var inputs = CreateDataExtremePoint1().ToList();
+      double[] alpha = inputs.Last();
+      bool result = LPHull.EXT(inputs, alpha, inputs.Count() - 1);
+      Assert.IsTrue(result);
+
+      inputs = CreateDataExtremePoint2().ToList();
+      alpha = inputs.Last();
+      result = LPHull.EXT(inputs, alpha, inputs.Count() - 1);
+      Assert.IsTrue(result);
+
+      inputs = CreateDataNonExtremePoint1().ToList();
+      alpha = inputs.Last();
+      result = LPHull.EXT(inputs, alpha, inputs.Count() - 1);
+      Assert.IsFalse(result);
+
+      inputs = CreateDataOnHull().ToList();
+      alpha = inputs.Last();
+      result = LPHull.EXT(inputs, alpha, inputs.Count() - 1);
+      Assert.IsFalse(result);
+    }
+
+    private double[][] CreateDataExtremePoint1() {
+      double[][] result = new double[5][];
+
+      result[0] = new double[] { 0.1, 0.1 };
+      result[1] = new double[] { 1, 1 };
+      result[2] = new double[] { 1, 0 };
+      result[3] = new double[] { 0, 1 };
+      result[4] = new double[] { 2.0, 1.4 };
+
+      return result;
+    }
+
+    private double[][] CreateDataExtremePoint2() {
+      double[][] result = new double[5][];
+
+      result[0] = new double[] { 0.1, 0.1 };
+      result[1] = new double[] { 1, 1 };
+      result[2] = new double[] { 1, 0 };
+      result[3] = new double[] { 0, 1 };
+      result[4] = new double[] { 1.0, 1.4 };
+
+      return result;
+    }
+
+    private double[][] CreateDataNonExtremePoint1() {
+      double[][] result = new double[5][];
+
+      result[0] = new double[] { 0.1, 0.1 };
+      result[1] = new double[] { 1, 1 };
+      result[2] = new double[] { 1, 0 };
+      result[3] = new double[] { 0, 1 };
+      result[4] = new double[] { 0.8, 0.4 };
+
+      return result;
+    }
+
+    private double[][] CreateDataOnHull() {
+      double[][] result = new double[5][];
+
+      result[0] = new double[] { 0.1, 0.1 };
+      result[1] = new double[] { 1, 1 };
+      result[2] = new double[] { 1, 0 };
+      result[3] = new double[] { 0, 1 };
+      result[4] = new double[] { 1.0, 0.5 };
+
+      return result;
+    }
+
     private List<DefaultVertex> ConvertPermutationToVertex(double[][] data) {
       List<DefaultVertex> result = new List<DefaultVertex>();

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

@@ -23 +23 @@
 using System.Collections.Generic;
 using System.Linq;
+using HeuristicLab.Common;
 
 namespace HeuristicLab.Analysis.AlgorithmBehavior.Analyzers {
@@ -44 +45 @@
       C.Add(A[0]);
       for (int i = 1; i < A.Length; i++) {
-        if (EXT(C, A[i])) {
-          C.Add(A[i]);
+        C.Add(A[i]);
+        if (!EXT(C, A[i], C.Count - 1)) {
+          C.Remove(A[i]);
         }
       }
@@ -51 +53 @@
       //Phase 3
       for (int i = 0; i < C.Count; i++) {
-        //TODO: this is not very efficient
-        if (EXT(ExcludeRow(C, i), C[i], i)) {
+        if (EXT(C, C[i], i)) {
           E.Add(C[i]);
         }
@@ -60 +61 @@
     }
 
-    private static List<double[]> ExcludeRow(List<double[]> matrix, int row) {
-      List<double[]> result = new List<double[]>();
-
-      for (int i = 0; i < matrix.Count; i++) {
-        if (i != row) {
-          var tmpRow = new double[matrix[i].Length];
-          result.Add(tmpRow);
-          for (int j = 0; j < matrix[i].Length; j++) {
-            tmpRow[j] = matrix[i][j];
-          }
-        }
-      }
-
-      return result;
-    }
-
     //sort A decreasing by distance to center of polytope
     public static double[][] SortA(double[][] A) {
-      //TODO: sort inplace
       int length = A[0].Length;
       double[] maxs = new double[length];
@@ -121 +105 @@
     /// Returns true if alpha is an extreme point, else false. 
     /// </summary>
-    private static bool EXT(List<double[]> A, double[] alpha, int aIdx = -1) {
+    public static bool EXT(List<double[]> A, double[] alpha, int aIdx = -1) {
       alglib.minbleicstate state;
-      double diffstep = 1.0e-6;
       int N = alpha.Length;
       int K = A.Count;
-
-
-      double[] init = new double[N];
-      double[] lowerBound = new double[N];
-      double[] upperBound = new double[N];
+      double[] init = new double[K];
+      double[] lowerBound = new double[K];
+      double[] upperBound = new double[K];
       double[] x;
       alglib.minbleicreport rep;
-      double[,] c = new double[K + 1, N + 1];
-      int[] ct = new int[K + 1]; //init with 0, means equal
+      double[,] c = new double[N + 1, K + 1];
+      int[] ct = new int[N + 1]; //init with 0, means equal
 
-      for (int i = 0; i < N; i++) {
-        //TODO: this should be a feasible solution    
-        init[i] = 1.0;
+      for (int i = 0; i < K; i++) {
+        init[i] = 1.0 / K;
         lowerBound[i] = 0.0;
         upperBound[i] = double.MaxValue;
@@ -144 +124 @@
 
       //last column gets b
-      for (int i = 0; i < K; i++) {
-        c[i, N] = alpha[i];
+      for (int i = 0; i < N; i++) {
+        c[i, K] = alpha[i];
       }
       //sum(x) == 1 constraint
-      for (int i = 0; i < N + 1; i++) {
-        c[K, i] = 1.0;
+      for (int i = 0; i < K + 1; i++) {
+        c[N, i] = 1.0;
       }
 
+      //other constraints
       for (int i = 0; i < K; i++) {
         for (int j = 0; j < N; j++) {
@@ -158 +139 @@
       }
 
-      alglib.minbleiccreatef(init, diffstep, out state);
+      alglib.minbleiccreate(init, out state);
       alglib.minbleicsetbc(state, lowerBound, upperBound);
       alglib.minbleicsetlc(state, c, ct);
       alglib.minbleicsetcond(state, 0.0, 0.0, 0.0, 0);
-      alglib.minbleicoptimize(state, Func, null, new Tuple<List<double[]>, int>(A, aIdx));
+      alglib.minbleicoptimize(state, Func, null, new Tuple<List<double[]>, double[], int>(A, alpha, aIdx));
       alglib.minbleicresults(state, out x, out rep);
 
-      return x.Sum() > 0;
+      return x.Count(y => y.IsAlmost(1.0)) == 1;
     }
 
-    private static void Func(double[] x, ref double func, object obj) {
-      Tuple<List<double[]>, int> data = obj as Tuple<List<double[]>, int>;
-      int aIdx = data.Item2;
+    private static void Func(double[] x, ref double func, double[] grad, object obj) {
+      Tuple<List<double[]>, double[], int> data = obj as Tuple<List<double[]>, double[], int>;
+      int aIdx = data.Item3;
+      double[] alpha = data.Item2;
       List<double[]> A = data.Item1;
 
-      //TODO: I have no idea what I'm doing...
+      //well, this seems to work but is probably not correct
+      for (int i = 0; i < grad.Length; i++) {
+        grad[i] = 0;
+      }
+      grad[aIdx] = 1;
+
       func = 0.0;
       for (int i = 0; i < A.Count; i++) {
-        if (i != aIdx) {
-          for (int j = 0; j < A[i].Length; j++) {
-            func += A[i][j] * x[i];
-          }
+        for (int j = 0; j < A[i].Length; j++) {
+          func += A[i][j] * x[i];
         }
       }