Changeset 13620 for branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/Comparators/HyperVolumeFast.cs

Timestamp:

02/15/16 17:19:34 (8 years ago)

Author:

bwerth

Message:

#1087 regorganized testfunctions, added view for qualities

File:

• branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/Comparators/HyperVolumeFast.cs (modified) (15 diffs)

branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/Comparators/HyperVolumeFast.cs

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
-using HeuristicLab.Encodings.RealVectorEncoding;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.MultiObjectiveTestFunctions.Comparators;
 
 namespace HeuristicLab.Problems.MultiObjectiveTestFunctions {
@@ -29 +30 @@
   public class FastHypervolume {
 
-    private RealVector reference;
+    private double[] reference;
     private bool[] maximization;
-    public FastHypervolume(RealVector reference, bool[] maximization) {
-      if (reference.Length != 2) throw new Exception("Only 2-dimensional cases are supported yet");
+    public FastHypervolume(double[] reference, bool[] maximization) {
+      if (reference.Length != 2) throw new NotSupportedException("Only 2-dimensional cases are supported yet");
       this.reference = reference;
       this.maximization = maximization;
     }
 
-    public double Compare(RealVector[] front, RealVector[] optimalFront, double[][] bounds) {
+    public double Compare(IEnumerable<double[]> front, IEnumerable<double[]> optimalFront, double[,] bounds) {
       return GetHypervolume(optimalFront, bounds) - GetHypervolume(front, bounds);
 
@@ -49 +50 @@
     /// <param name="bounds">also called region</param>
     /// <returns></returns>
-    public double GetHypervolume(RealVector[] front, double[][] bounds) {
+    public double GetHypervolume(IEnumerable<double[]> front, double[,] bounds) {
       //TODO what to do if set contains dominated points
-      var list = new List<RealVector>();
+      if (front == null) throw new ArgumentException("Fronts must not be null");
+      var list = new List<double[]>();
       list.AddRange(front);
-      list.Sort(new DimensionComparer(reference.Length - 1, maximization[reference.Length - 1]));
+      list.Sort(Utilities.getDimensionComparer(reference.Length - 1, maximization[reference.Length - 1]));
       var results = new ExPrivates(this);
-      GetHV(DeepClone(bounds), list, 1, reference[reference.Length - 1], results);
+      GetHV(SpanRegion(), list, 0, reference[reference.Length - 1], results);
       return results.Volume;
 
     }
+
+    private double[][] SpanRegion(double[,] bounds, int length) {
+      if (bounds.GetLength(1) != 2) throw new ArgumentException();
+      double[][] copy = new double[length][];
+      for (int i = 0; i < copy.Length; i++) {
+        copy[i] = new double[2];
+        for (int j = 0; j < 2; j++) {
+          copy[i][j] = bounds[i%bounds.GetLength(0),j];
+        }
+      }
+      return copy;
+    }
+
+    private double[][] SpanRegion() {
+      double[][] copy = new double[reference.Length][];
+      for (int i = 0; i < copy.Length; i++) {
+        copy[i] = new double[2];
+        copy[i][0] = 0;
+        copy[i][1] = reference[i];
+      }
+      return copy;
+
+    }
+
 
     private double[][] DeepClone(double[][] array) {
@@ -64 +90 @@
       for (int i = 0; i < copy.Length; i++) {
         copy[i] = new double[array[i].Length];
-        for (int j = 0; i < array[i].Length; j++) {
+        for (int j = 0; j < array[i].Length; j++) {
           copy[i][j] = array[i][j];
         }
@@ -80 +106 @@
 
       public int D {
-        get { return D; }
+        get { return d; }
       }
       public ExPrivates(FastHypervolume hv) {
@@ -91 +117 @@
     }
 
-    private void GetHV(double[][] region, List<RealVector> points, int split, double cover, ExPrivates results) {
+    private void GetHV(double[][] region, List<double[]> points, int split, double cover, ExPrivates results) {
       double coverNew = cover;
-      int coverIndex = 1;
+      int coverIndex = 0;
       bool allPiles = true;
-      int bound = -1;
+      double bound = -1;
 
       /* is the region completely covered? */
@@ -101 +127 @@
         if (covers(points[coverIndex], region, results)) {
           coverNew = points[coverIndex][results.D];
-          results.Volume += getMeasure(region) * (cover - coverNew);
-        } else { }
-        coverIndex++;
-      }
-      if (coverIndex == 1) return;
-
-      for (int i = 1; i < coverIndex; i++) { if (checkPile(points[i], region) == -1) allPiles = false; }
+          results.Volume += GetMeasure(region,results) * (cover - coverNew);
+        } else coverIndex++;
+      }
+      if (coverIndex == 0) return;
+
+      for (int i = 0; i < coverIndex; i++) { if (checkPile(points[i], region, results) == -1) allPiles = false; }
 
       if (allPiles) {
         /* calculate volume by sweeping along dimension d */
         var trellis = new double[reference.Length];
-        int i = 1;
-        for (int j = 1; j < results.D; j++) trellis[j] = reference[j];
+        int i = 0;
+        for (int j = 0; j < results.D-1; j++) trellis[j] = reference[j];
 
         double next;//bernhard
         do {
-          double current = points[i][results.D];
+          double current = points[i][results.D-1];
           do {
-            int pile = getPile(points[i], region);
+            int pile = checkPile(points[i], region,results);
             if (points[i][pile] < trellis[pile]) trellis[pile] = points[i][pile];
             i++;
-            if (i < coverIndex - 1) next = points[i][results.D]; else next = coverNew;
+            if (i < coverIndex - 1) next = points[i][results.D-1]; else next = coverNew;
           } while (current == next);
-          results.Volume += measure(trellis, region) * (next - current);
+          results.Volume += measure(trellis, region, results) * (next - current);
         } while (next != coverNew);
 
@@ -131 +156 @@
         do {
           var intersect = new List<Double>(); var nonIntersect = new List<Double>();
-          for (int i = 1; i < coverIndex; i++) {
+          for (int i = 0; i < coverIndex; i++) {
             var intersection = intersects(points[i], region, split);
             if (intersection == 1) intersect.Add(points[i][split]);
             if (intersection == 0) nonIntersect.Add(points[i][split]);
           }
-          if (intersect.Count != 0) bound = median(intersect);
-          else if (nonIntersect.Count > Math.Sqrt(n)) bound = median(nonIntersect);
+          if (intersect.Count != 0) bound = intersect.Median();
+          else if (nonIntersect.Count > Math.Sqrt(points.Count)) bound = nonIntersect.Median();
           else split++;
         } while (bound == -1);
@@ -145 +170 @@
       var regionC = DeepClone(region);
       regionC[split][1] = bound;
-      var pointsC = new List<RealVector>();
-      for (int i = 1; i < coverIndex; i++) {
-        if (partCovers(points[i], regionC, results)) move(points[i], pointsC);
+      var pointsC = new List<double[]>();
+      for (int i = 0; i < coverIndex; i++) {
+        if (partCovers(points[i], regionC, results)) move(points,i, pointsC);
       }
       if (pointsC.Count != 0) GetHV(regionC, pointsC, split, coverNew, results);
@@ -153 +178 @@
       regionC = region;
       regionC[split][0] = bound;
-      pointsC = new List<RealVector>();
+      pointsC = new List<double[]>();
       for (int i = 1; i < coverIndex; i++) {
-        if (partCovers(points[i], regionC, results)) move(points[i], pointsC);
+        if (partCovers(points[i], regionC, results)) move(points,i, pointsC);
       }
       if (pointsC.Count != 0) GetHV(regionC, pointsC, split, coverNew, results);
@@ -161 +186 @@
     }
 
-    private int checkPile(RealVector point, double[][] region, ExPrivates results) {
+    private void reinsert(List<double[]> pointsC, List<double[]> points) {
+      points.AddRange(pointsC);
+      pointsC.Clear();
+    }
+
+    private double GetMeasure(double[][] region,ExPrivates result) {
+      double volume = 1.0;
+      // for ( std::size_t i = 0; i < regionLow.size(); i++ ) {
+      for (int i = 1; i < result.D; i++) {
+      volume *= (region[1][i] - region[0][i]);
+      }
+      return (volume);
+    }
+
+    private void move(List<double[]> points, int i, List<double[]> pointsC) {
+      double[] v = points[i];
+      points.Remove(v);
+      pointsC.Add(v);
+    }
+
+    private double measure(double[] trellis, double[][] region, ExPrivates results) {
+      double volume=0;
+      bool[] indicator = new bool[results.D];
+      for (int i = 0; i < results.D-1; i++) indicator[i] = true;
+      int numberSummands = integerValue(indicator);
+
+      for (int i = 0; i <= numberSummands; i++) {
+        indicator = binaryValue(i);
+        int oneCounter = 0;
+        double summand = 0;
+        for (int j = 1; j < results.D; j++) {
+          if (indicator[i] == true) {
+            summand += region[1][j] - trellis[j];
+            oneCounter++;
+          } else {
+            summand += region[1][j] - region[0][j];
+          }
+        }
+        if(oneCounter%2 == 0) {
+          volume -= summand;
+        } else {
+          volume += summand;
+        }
+      }
+      return volume;
+    }
+
+    private int integerValue(bool[] binary) {
+      int sum=0;
+      foreach (bool b in binary) {
+        sum = (sum << 1) + (b ? 1 : 0);
+      }
+      return sum;
+    }
+
+    private bool[] binaryValue(int integer) {
+      bool[] res = new bool[32];
+      int i = 0;
+      while (integer != 0) {
+        res[i++]= (integer & 1)==1;
+        integer >>= 1;
+      }
+      return res;
+
+    }
+
+    private int checkPile(double[] point, double[][] region, ExPrivates results) {
       int pile = -1;
-      for (int j = 1; j < results.D; j++) {
+      for (int j = 0; j < results.D-1; j++) {
         if (point[j] > region[j][0]) {
           if (pile != -1) return -1;
@@ -173 +264 @@
     }
 
-    private int intersects(RealVector point, double[][] region, int split) {
+    private int intersects(double[] point, double[][] region, int split) {
       if (region[split][0] >= point[split]) return -1;
       for (int j = 1; j < split; j++) {
@@ -182 +273 @@
     }
 
-    private bool covers(RealVector point, double[][] region, ExPrivates results) {
+    private bool covers(double[] point, double[][] region, ExPrivates results) {
       for (int j = 1; j < results.D; j++) {
         if (point[j] > region[j][0]) return false;
@@ -190 +281 @@
     }
 
-    private bool partCovers(RealVector point, double[][] region, ExPrivates results) {
+    private bool partCovers(double[] point, double[][] region, ExPrivates results) {
       for (int j = 1; j < results.D; j++) {
         if (point[j] >= region[j][1]) return false;
@@ -197 +288 @@
     }
 
-    public static double GetHypervolume(RealVector[] front, RealVector reference, bool[] maximization) {
-      Hypervolume comp = new Hypervolume(reference, maximization);
-      return comp.GetHypervolume(front);
-    }
-
-    public static double GetDistance(RealVector[] front, RealVector[] optimalFront, RealVector reference, bool[] maximization) {
-      return GetHypervolume(optimalFront, reference, maximization) - GetHypervolume(front, reference, maximization);
-    }
-
-    private void CheckConsistency(RealVector point, int dim) {
+    public static double GetHypervolume(IEnumerable<double[]> front, double[] reference, bool[] maximization, double[,] bounds) {
+      FastHypervolume comp = new FastHypervolume(reference, maximization);
+      return comp.GetHypervolume(front,bounds);
+    }
+
+    public static double GetDistance(IEnumerable<double[]> front, IEnumerable<double[]> optimalFront, double[] reference, bool[] maximization, double[,] bounds) {
+      return GetHypervolume(optimalFront, reference, maximization, bounds) - GetHypervolume(front, reference, maximization,bounds);
+    }
+
+    private void CheckConsistency(double[] point, int dim) {
       if (!maximization[dim] && point[dim] > reference[dim]) throw new Exception("Reference Point must be dominated by all points of the front");
       if (maximization[dim] && point[dim] < reference[dim]) throw new Exception("Reference Point must be dominated by all points of the front");
     }
 
-    private class DimensionComparer : IComparer<RealVector> {
-      private int dim;
-      private int descending;
-
-      public DimensionComparer(int dimension, bool descending) {
-        this.dim = dimension;
-        this.descending = descending ? -1 : 1;
-      }
-
-      #region IComparer<DoubleArray> Members
-
-      public int Compare(RealVector x, RealVector y) {
-        if (x[dim] < y[dim]) return -descending;
-        else if (x[dim] > y[dim]) return descending;
-        else return 0;
-      }
-
-      #endregion
-    }
+
+
+
+
+
+
+   
+
 
   }