Changeset 10081


Ignore:
Timestamp:
10/23/13 15:56:50 (6 years ago)
Author:
ascheibe
Message:

#1886 fixed LPHull, seems to work now

Location:
branches/HeuristicLab.Analysis.AlgorithmBehavior
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Analysis.AlgorithmBehavior/AlgorithmBehaviorUnitTests/ConvexHullTest.cs

    r9945 r10081  
    2828using Microsoft.VisualStudio.TestTools.UnitTesting;
    2929
    30 namespace Visualization {
     30namespace AlgorithmBehaviorUnitTests {
    3131  [TestClass]
    3232  public class ConvexHullTest {
  • branches/HeuristicLab.Analysis.AlgorithmBehavior/AlgorithmBehaviorUnitTests/LPConvexHullTest.cs

    r10060 r10081  
    2828using Microsoft.VisualStudio.TestTools.UnitTesting;
    2929
    30 namespace Visualization {
     30namespace AlgorithmBehaviorUnitTests {
    3131  [TestClass]
    3232  public class LPConvexHullTest {
    3333    [TestMethod]
    3434    public void TestMethod1() {
    35       int nrOfSamples = 10;
     35      int nrOfSamples = 70;
    3636      int sampleSize = 2;
    3737      double[][] inputs = CreateRandomData(nrOfSamples, sampleSize);
     
    7070    }
    7171
     72    [TestMethod]
     73    public void TestExt() {
     74      var inputs = CreateDataExtremePoint1().ToList();
     75      double[] alpha = inputs.Last();
     76      bool result = LPHull.EXT(inputs, alpha, inputs.Count() - 1);
     77      Assert.IsTrue(result);
     78
     79      inputs = CreateDataExtremePoint2().ToList();
     80      alpha = inputs.Last();
     81      result = LPHull.EXT(inputs, alpha, inputs.Count() - 1);
     82      Assert.IsTrue(result);
     83
     84      inputs = CreateDataNonExtremePoint1().ToList();
     85      alpha = inputs.Last();
     86      result = LPHull.EXT(inputs, alpha, inputs.Count() - 1);
     87      Assert.IsFalse(result);
     88
     89      inputs = CreateDataOnHull().ToList();
     90      alpha = inputs.Last();
     91      result = LPHull.EXT(inputs, alpha, inputs.Count() - 1);
     92      Assert.IsFalse(result);
     93    }
     94
     95    private double[][] CreateDataExtremePoint1() {
     96      double[][] result = new double[5][];
     97
     98      result[0] = new double[] { 0.1, 0.1 };
     99      result[1] = new double[] { 1, 1 };
     100      result[2] = new double[] { 1, 0 };
     101      result[3] = new double[] { 0, 1 };
     102      result[4] = new double[] { 2.0, 1.4 };
     103
     104      return result;
     105    }
     106
     107    private double[][] CreateDataExtremePoint2() {
     108      double[][] result = new double[5][];
     109
     110      result[0] = new double[] { 0.1, 0.1 };
     111      result[1] = new double[] { 1, 1 };
     112      result[2] = new double[] { 1, 0 };
     113      result[3] = new double[] { 0, 1 };
     114      result[4] = new double[] { 1.0, 1.4 };
     115
     116      return result;
     117    }
     118
     119    private double[][] CreateDataNonExtremePoint1() {
     120      double[][] result = new double[5][];
     121
     122      result[0] = new double[] { 0.1, 0.1 };
     123      result[1] = new double[] { 1, 1 };
     124      result[2] = new double[] { 1, 0 };
     125      result[3] = new double[] { 0, 1 };
     126      result[4] = new double[] { 0.8, 0.4 };
     127
     128      return result;
     129    }
     130
     131    private double[][] CreateDataOnHull() {
     132      double[][] result = new double[5][];
     133
     134      result[0] = new double[] { 0.1, 0.1 };
     135      result[1] = new double[] { 1, 1 };
     136      result[2] = new double[] { 1, 0 };
     137      result[3] = new double[] { 0, 1 };
     138      result[4] = new double[] { 1.0, 0.5 };
     139
     140      return result;
     141    }
     142
    72143    private List<DefaultVertex> ConvertPermutationToVertex(double[][] data) {
    73144      List<DefaultVertex> result = new List<DefaultVertex>();
  • branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior.Analyzers/3.3/LPHull.cs

    r10060 r10081  
    2323using System.Collections.Generic;
    2424using System.Linq;
     25using HeuristicLab.Common;
    2526
    2627namespace HeuristicLab.Analysis.AlgorithmBehavior.Analyzers {
     
    4445      C.Add(A[0]);
    4546      for (int i = 1; i < A.Length; i++) {
    46         if (EXT(C, A[i])) {
    47           C.Add(A[i]);
     47        C.Add(A[i]);
     48        if (!EXT(C, A[i], C.Count - 1)) {
     49          C.Remove(A[i]);
    4850        }
    4951      }
     
    5153      //Phase 3
    5254      for (int i = 0; i < C.Count; i++) {
    53         //TODO: this is not very efficient
    54         if (EXT(ExcludeRow(C, i), C[i], i)) {
     55        if (EXT(C, C[i], i)) {
    5556          E.Add(C[i]);
    5657        }
     
    6061    }
    6162
    62     private static List<double[]> ExcludeRow(List<double[]> matrix, int row) {
    63       List<double[]> result = new List<double[]>();
    64 
    65       for (int i = 0; i < matrix.Count; i++) {
    66         if (i != row) {
    67           var tmpRow = new double[matrix[i].Length];
    68           result.Add(tmpRow);
    69           for (int j = 0; j < matrix[i].Length; j++) {
    70             tmpRow[j] = matrix[i][j];
    71           }
    72         }
    73       }
    74 
    75       return result;
    76     }
    77 
    7863    //sort A decreasing by distance to center of polytope
    7964    public static double[][] SortA(double[][] A) {
    80       //TODO: sort inplace
    8165      int length = A[0].Length;
    8266      double[] maxs = new double[length];
     
    121105    /// Returns true if alpha is an extreme point, else false.
    122106    /// </summary>
    123     private static bool EXT(List<double[]> A, double[] alpha, int aIdx = -1) {
     107    public static bool EXT(List<double[]> A, double[] alpha, int aIdx = -1) {
    124108      alglib.minbleicstate state;
    125       double diffstep = 1.0e-6;
    126109      int N = alpha.Length;
    127110      int K = A.Count;
    128 
    129 
    130       double[] init = new double[N];
    131       double[] lowerBound = new double[N];
    132       double[] upperBound = new double[N];
     111      double[] init = new double[K];
     112      double[] lowerBound = new double[K];
     113      double[] upperBound = new double[K];
    133114      double[] x;
    134115      alglib.minbleicreport rep;
    135       double[,] c = new double[K + 1, N + 1];
    136       int[] ct = new int[K + 1]; //init with 0, means equal
     116      double[,] c = new double[N + 1, K + 1];
     117      int[] ct = new int[N + 1]; //init with 0, means equal
    137118
    138       for (int i = 0; i < N; i++) {
    139         //TODO: this should be a feasible solution   
    140         init[i] = 1.0;
     119      for (int i = 0; i < K; i++) {
     120        init[i] = 1.0 / K;
    141121        lowerBound[i] = 0.0;
    142122        upperBound[i] = double.MaxValue;
     
    144124
    145125      //last column gets b
    146       for (int i = 0; i < K; i++) {
    147         c[i, N] = alpha[i];
     126      for (int i = 0; i < N; i++) {
     127        c[i, K] = alpha[i];
    148128      }
    149129      //sum(x) == 1 constraint
    150       for (int i = 0; i < N + 1; i++) {
    151         c[K, i] = 1.0;
     130      for (int i = 0; i < K + 1; i++) {
     131        c[N, i] = 1.0;
    152132      }
    153133
     134      //other constraints
    154135      for (int i = 0; i < K; i++) {
    155136        for (int j = 0; j < N; j++) {
     
    158139      }
    159140
    160       alglib.minbleiccreatef(init, diffstep, out state);
     141      alglib.minbleiccreate(init, out state);
    161142      alglib.minbleicsetbc(state, lowerBound, upperBound);
    162143      alglib.minbleicsetlc(state, c, ct);
    163144      alglib.minbleicsetcond(state, 0.0, 0.0, 0.0, 0);
    164       alglib.minbleicoptimize(state, Func, null, new Tuple<List<double[]>, int>(A, aIdx));
     145      alglib.minbleicoptimize(state, Func, null, new Tuple<List<double[]>, double[], int>(A, alpha, aIdx));
    165146      alglib.minbleicresults(state, out x, out rep);
    166147
    167       return x.Sum() > 0;
     148      return x.Count(y => y.IsAlmost(1.0)) == 1;
    168149    }
    169150
    170     private static void Func(double[] x, ref double func, object obj) {
    171       Tuple<List<double[]>, int> data = obj as Tuple<List<double[]>, int>;
    172       int aIdx = data.Item2;
     151    private static void Func(double[] x, ref double func, double[] grad, object obj) {
     152      Tuple<List<double[]>, double[], int> data = obj as Tuple<List<double[]>, double[], int>;
     153      int aIdx = data.Item3;
     154      double[] alpha = data.Item2;
    173155      List<double[]> A = data.Item1;
    174156
    175       //TODO: I have no idea what I'm doing...
     157      //well, this seems to work but is probably not correct
     158      for (int i = 0; i < grad.Length; i++) {
     159        grad[i] = 0;
     160      }
     161      grad[aIdx] = 1;
     162
    176163      func = 0.0;
    177164      for (int i = 0; i < A.Count; i++) {
    178         if (i != aIdx) {
    179           for (int j = 0; j < A[i].Length; j++) {
    180             func += A[i][j] * x[i];
    181           }
     165        for (int j = 0; j < A[i].Length; j++) {
     166          func += A[i][j] * x[i];
    182167        }
    183168      }
Note: See TracChangeset for help on using the changeset viewer.