Changeset 14018 for branches

Timestamp:

07/07/16 14:13:46 (8 years ago)

Author:

mkommend

Message:

#1087: Rewrote and adapted the multi-objective calculators.

Location:

branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3

Files:

• Calculators/Crowding.cs (modified) (3 diffs)
• Calculators/GenerationalDistance.cs (modified) (2 diffs)
• Calculators/HyperVolume.cs (modified) (5 diffs)
• Calculators/InvertedGenerationalDistance.cs (modified) (1 diff)
• Calculators/MultiDimensionalHypervolume.cs (modified) (1 diff)
• Calculators/Spacing.cs (modified) (2 diffs)
• Calculators/Utilities.cs (modified) (3 diffs)
• NonDominatedSelect.cs (modified) (2 diffs)

branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/Calculators/Crowding.cs

@@ -32 +32 @@
   /// C(A) = mean(d(x,A)) where x in A  and d(x,A) is not infinite 
   /// </summary>
-  public class Crowding {
+  public static class Crowding {
 
     public static double Calculate(IEnumerable<double[]> front, double[,] bounds) {
-      double sum = 0;
-      int c = 0;
+
       double[] pointsums = new double[front.Count()];
 
       for (int dim = 0; dim < front.First().Length; dim++) {
+
         double[] arr = front.Select(x => x[dim]).ToArray();
         Array.Sort(arr);
+
         double fmax = bounds[dim % bounds.GetLength(0), 1];
         double fmin = bounds[dim % bounds.GetLength(0), 0];
+
         int pointIdx = 0;
         foreach (double[] point in front) {
@@ -55 +57 @@
       }
 
+      double sum = 0;
+      int c = 0;
       foreach (double d in pointsums) {
         if (!Double.IsInfinity(d)) {
@@ -61 +65 @@
         }
       }
+
       return c == 0 ? Double.PositiveInfinity : sum / c;
     }

branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/Calculators/GenerationalDistance.cs

@@ -21 +21 @@
 using System;
 using System.Collections.Generic;
+using System.Linq;
 
 namespace HeuristicLab.Problems.MultiObjectiveTestFunctions {
@@ -28 +29 @@
   ///  where d[i] is the minimal distance the ith point of the evaluated front has to any point in the optimal pareto front.   
   /// </summary>
-  public class GenerationalDistance {
+  public static class GenerationalDistance {
 
     public static double Calculate(IEnumerable<double[]> front, IEnumerable<double[]> optimalFront, double p) {
-      //TODO build a kd-tree, sort the array, do someting intelligent here
-      if (front == null || optimalFront == null) throw new ArgumentException("Fronts must not be null");
+      //TODO build a kd-tree, sort the array, do something intelligent here
+      if (front == null || optimalFront == null) throw new ArgumentNullException("Fronts must not be null.");
+      if (!front.Any()) throw new ArgumentException("Front must not be empty.");
+      if (p == 0.0) throw new ArgumentException("p must not be 0.0.");
+
       double sum = 0;
       int c = 0;
       foreach (double[] r in front) {
-        sum += Utilities.minDistance(r, optimalFront, true);
+        sum += Utilities.MinimumDistance(r, optimalFront);
         c++;
       }
-      if (c == 0) throw new ArgumentException("Fronts must not be empty");
+
       return Math.Pow(sum, 1 / p) / c;
     }
 
-
-
   }
 }

branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/Calculators/HyperVolume.cs

@@ -19 +19 @@
  */
 #endregion
-using HeuristicLab.Common;
 using System;
 using System.Collections.Generic;
 using System.Linq;
+using HeuristicLab.Common;
 
 namespace HeuristicLab.Problems.MultiObjectiveTestFunctions {
 
-  public class Hypervolume {
+  public static class Hypervolume {
 
     /// <summary>
@@ -33 +33 @@
     /// 
     /// Example:
-    /// r is the reference Point at (1|1)  and every Point p is part of the evaluated front
-    /// The filled Area labled HV is the 2 diensional Hypervolume enclosed by this front. 
+    /// r is the reference Point at (1|1) and every Point p is part of the evaluated front
+    /// The filled Area labled HV is the 2 dimensional Hypervolume enclosed by this front. 
     /// 
     /// (0|1)                (1|1)
@@ -52 +52 @@
     /// </summary>
     /// 
-    public static double Calculate(IEnumerable<double[]> points, IEnumerable<double> reference, bool[] maximization) {
-      var front = NonDominatedSelect.removeNonReferenceDominatingVectors(points, reference.ToArray<double>(), maximization, false);
-      if (maximization.Length == 2) { //Hypervolume analysis only with 2 objectives for now
-        return Hypervolume.Calculate2D(front, reference, maximization);
-      } else if (Array.TrueForAll(maximization, x => !x)) {
-        return Hypervolume.CalculateMD(front, reference);
-      } else {
-        throw new NotImplementedException("Hypervolume calculation for more than two dimensions is supported only with minimization problems");
-      }
-    }
-
-
-    private static double Calculate2D(IEnumerable<double[]> front, IEnumerable<double> reference, bool[] maximization) {
-      List<double> list = new List<double>();
-      foreach (double d in reference) list.Add(d);
-      double[] refp = list.ToArray<double>();
-      if (front == null) throw new ArgumentException("Fronts must not be null");
+    public static double Calculate(IEnumerable<double[]> points, double[] referencePoint, bool[] maximization) {
+      var front = NonDominatedSelect.removeNonReferenceDominatingVectors(points, referencePoint, maximization, false);
+      if (maximization.Length == 2)
+        return Calculate2D(front, referencePoint, maximization);
+
+      if (Array.TrueForAll(maximization, x => !x))
+        return CalculateMD(front, referencePoint);
+      else throw new NotImplementedException("Hypervolume calculation for more than two dimensions is supported only with minimization problems.");
+    }
+
+
+    private static double Calculate2D(IEnumerable<double[]> front, double[] referencePoint, bool[] maximization) {
+      if (front == null) throw new ArgumentNullException("Front must not be null.");
+      if (!front.Any()) throw new ArgumentException("Front must not be empty.");
+
+      if (referencePoint == null) throw new ArgumentNullException("ReferencePoint must not be null.");
+      if (referencePoint.Length != 2) throw new ArgumentException("ReferencePoint must have exactly two dimensions.");
+
       double[][] set = front.ToArray();   //Still no Good
-      if (set.Length == 0) throw new ArgumentException("Fronts must not be empty");
-      if (refp.Length != set[0].Length) throw new ArgumentException("Front and referencepoint need to be of the same dimensionality");
-      Array.Sort<double[]>(set, Utilities.getDimensionComparer(0, maximization[0]));
-      double[] last = set[set.Length - 1];
-      CheckConsistency(last, 0, refp, maximization);
-      CheckConsistency(last, 1, refp, maximization);
+      if (set.Any(s => s.Length != 2)) throw new ArgumentException("Points in front must have exactly two dimensions.");
+
+      Array.Sort<double[]>(set, new Utilities.DimensionComparer(0, maximization[0]));
 
       double sum = 0;
       for (int i = 0; i < set.Length - 1; i++) {
-        CheckConsistency(set[i], 1, refp, maximization);
-        sum += Math.Abs((set[i][0] - set[i + 1][0])) * Math.Abs((set[i][1] - refp[1]));
-      }
-
-      sum += Math.Abs(refp[0] - last[0]) * Math.Abs(refp[1] - last[1]);
+        if (NonDominatedSelect.Dominates(referencePoint, set[i], maximization, true) == NonDominatedSelect.DominationResult.Dominates)
+          throw new ArgumentException("Reference Point must be dominated by all points of the front");
+        sum += Math.Abs((set[i][0] - set[i + 1][0])) * Math.Abs((set[i][1] - referencePoint[1]));
+      }
+
+      double[] lastPoint = set[set.Length - 1];
+      if (NonDominatedSelect.Dominates(referencePoint, lastPoint, maximization, true) == NonDominatedSelect.DominationResult.Dominates)
+        throw new ArgumentException("Reference Point must be dominated by all points of the front");
+      sum += Math.Abs(lastPoint[0] - referencePoint[0]) * Math.Abs(lastPoint[1] - referencePoint[1]);
+
       return sum;
     }
 
-    private static void CheckConsistency(double[] point, int dim, double[] reference, bool[] maximization) {
-      if (!maximization[dim] && point[dim] > reference[dim]) throw new ArgumentException("Reference Point must be dominated by all points of the front");
-      if (maximization[dim] && point[dim] < reference[dim]) throw new ArgumentException("Reference Point must be dominated by all points of the front");
-      if (point.Length != 2) throw new ArgumentException("Only 2-dimensional cases are supported yet");
-    }
-
-    private static double CalculateMD(IEnumerable<double[]> points, IEnumerable<double> reference) {
-      double[] referencePoint = reference.ToArray<double>();
+
+
+    private static double CalculateMD(IEnumerable<double[]> points, double[] referencePoint) {
       if (referencePoint == null || referencePoint.Length < 3) throw new ArgumentException("ReferencePoint unfit for complex Hypervolume calculation");
       if (!IsDominated(referencePoint, points)) {
         throw new ArgumentException("ReferencePoint unfit for complex Hypervolume calculation");
       }
+
       int objectives = referencePoint.Length;
-      List<double[]> lpoints = new List<double[]>();
-      foreach (double[] p in points) {
-        lpoints.Add(p);
-      }
-      lpoints.StableSort(Utilities.getDimensionComparer(objectives - 1, false));
-
-      double[] regLow = new double[objectives];
-      for (int i = 0; i < objectives; i++) {
-        regLow[i] = 1E15;
-      }
-      foreach (double[] p in lpoints) {
+      var front = points.ToList();
+      front.StableSort(new Utilities.DimensionComparer(objectives - 1, false));
+
+      double[] regLow = Enumerable.Repeat(1E15, objectives).ToArray();
+      foreach (double[] p in front) {
         for (int i = 0; i < regLow.Length; i++) {
-          if (regLow[i] > p[i]) regLow[i] = p[i];
-        }
-      }
-
-      return Stream(regLow, referencePoint, lpoints, 0, referencePoint[objectives - 1], (int)Math.Sqrt(points.Count()), objectives);
+          if (p[i] < regLow[i]) regLow[i] = p[i];
+        }
+      }
+
+      return Stream(regLow, referencePoint, front, 0, referencePoint[objectives - 1], (int)Math.Sqrt(front.Count), objectives);
     }
 
@@ -209 +202 @@
         //this could/should be done in Parallel
 
-        if (pointsChildUp.Count() > 0) result += Stream(regionLow, regionUpC, pointsChildUp, split, cover, sqrtNoPoints, objectives);
-        if (pointsChildLow.Count() > 0) result += Stream(regionLowC, regionUp, pointsChildLow, split, cover, sqrtNoPoints, objectives);
+        if (pointsChildUp.Count > 0) result += Stream(regionLow, regionUpC, pointsChildUp, split, cover, sqrtNoPoints, objectives);
+        if (pointsChildLow.Count > 0) result += Stream(regionLowC, regionUp, pointsChildLow, split, cover, sqrtNoPoints, objectives);
       }
       return result;
@@ -216 +209 @@
 
     private static double GetMedian(double[] vector, int length) {
-      if (vector.Length != length) {
-        double[] vec = new double[length];
-        Array.Copy(vector, vec, length);
-        vector = vec;
-      }
-      return vector.Median();
-
+      return vector.Take(length).Median();
     }
 

branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/Calculators/InvertedGenerationalDistance.cs

@@ -27 +27 @@
   ///  where d[i] is the minimal distance the ith point of the optimal pareto front has to any point in the evaluated front.   
   /// </summary>
-  public class InvertedGenerationalDistance {
-
+  public static class InvertedGenerationalDistance {
     public static double Calculate(IEnumerable<double[]> front, IEnumerable<double[]> optimalFront, double p) {
       return GenerationalDistance.Calculate(optimalFront, front, p);

branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/Calculators/MultiDimensionalHypervolume.cs

@@ -69 +69 @@
         lpoints.Add(p);
       }
-      lpoints.StableSort(Utilities.getDimensionComparer(objectives - 1, false));
+      lpoints.StableSort(new Utilities.DimensionComparer(objectives - 1, false));
 
       double[] regLow = new double[objectives];

branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/Calculators/Spacing.cs

@@ -21 +21 @@
 using System;
 using System.Collections.Generic;
+using System.Linq;
 using HeuristicLab.Common;
 
@@ -30 +31 @@
   /// to all OTHER points in the same front 
   /// </summary>
-  public class Spacing {
+  public static class Spacing {
 
-    public static double Calculate(IEnumerable<double[]> front) {
-      if (front == null) throw new ArgumentException("Fronts must not be null");
+    public static double Calculate(IEnumerable<double[]> points) {
+      if (points == null) throw new ArgumentException("Front must not be null.");
+      if (!points.Any()) throw new ArgumentException("Front must  not be empty.");
+
       List<double> d = new List<double>();
-      foreach (double[] r in front) {
-        double dist = Utilities.minDistance(r, front, false);
-        d.Add(dist >= 0 ? dist : 0);
+      foreach (double[] r in points) {
+        var point = r;
+        var otherPoints = points.Where(p => p != point).DefaultIfEmpty(point);
+        double dist = Utilities.MinimumDistance(point, otherPoints);
+        d.Add(dist);
       }
-      int n = d.Count;
-      if (n == 0) throw new ArgumentException("Fronts must not be empty");
-      return Math.Sqrt(d.Variance() * (n - 1) / n);
 
+      return d.StandardDeviationPop();
     }
 

branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/Calculators/Utilities.cs

@@ -21 +21 @@
 using System;
 using System.Collections.Generic;
+using System.Linq;
 
 namespace HeuristicLab.Problems.MultiObjectiveTestFunctions {
-  internal class Utilities {
+  internal static class Utilities {
+    internal static double MinimumDistance(double[] point, IEnumerable<double[]> points) {
+      if (point == null) throw new ArgumentNullException("Point must not be null.");
+      if (points == null) throw new ArgumentNullException("Points must not be null.");
+      if (!points.Any()) throw new ArgumentException("Points must not be empty.");
 
-    /// <summary>
-    /// 
-    /// </summary>
-    /// <param name="point"></param>
-    /// <param name="list"></param>
-    /// <param name="reflexive"></param>
-    /// <returns>return -1 if list contains only rejected points</returns>
-    internal static double minDistance(double[] point, IEnumerable<double[]> list, bool reflexive) {
-      double min = double.MaxValue;
-      bool empty = true;
-      foreach (double[] r in list) {
-        empty = false;
-        if (!reflexive && ReferenceEquals(r, point)) continue;
-        double d = 0;
-        if (r.Length != point.Length) throw new ArgumentException("dimensions of Front and Point do not match");
+      double minDistance = double.MaxValue;
+      foreach (double[] r in points) {
+        if (r.Length != point.Length) throw new ArgumentException("Dimensions of Points and Point do not match.");
+
+        double squaredDistance = 0;
         for (int i = 0; i < r.Length; i++) {
-          d += (point[i] - r[i]) * (point[i] - r[i]);
+          squaredDistance += (point[i] - r[i]) * (point[i] - r[i]);
         }
-        min = Math.Min(d, min);
+        minDistance = Math.Min(squaredDistance, minDistance);
       }
-      if (empty) throw new ArgumentException("Fronts must not be empty");
-      if (min == double.MaxValue) { return -1; }
-      return Math.Sqrt(min);
+
+      return Math.Sqrt(minDistance);
     }
 
-    internal static IComparer<double[]> getDimensionComparer(int dim, bool descending) {
-      return new DimensionComparer(dim, descending);
-    }
-
-
     internal class DimensionComparer : IComparer<double[]> {
-      private int dim;
-      private int descending;
+      private readonly int dim;
+      private readonly int descending;
 
       public DimensionComparer(int dimension, bool descending) {
@@ -64 +53 @@
       }
 
-      #region IComparer<DoubleArray> Members
-
       public int Compare(double[] x, double[] y) {
         if (x[dim] < y[dim]) return -descending;
@@ -71 +58 @@
         else return 0;
       }
-
-      #endregion
     }
   }
-
-
-
-
-
 }

branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/NonDominatedSelect.cs

@@ -27 +27 @@
 
   public class NonDominatedSelect {
-    private enum DominationResult { Dominates, IsDominated, IsNonDominated };
+    public enum DominationResult { Dominates, IsDominated, IsNonDominated };
 
     public static IEnumerable<double[]> selectNonDominatedVectors(IEnumerable<double[]> qualities, bool[] maximization, bool dominateOnEqualQualities) {
@@ -60 +60 @@
     }
 
-    private static DominationResult Dominates(double[] left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
+    public static DominationResult Dominates(double[] left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
       //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
       if (dominateOnEqualQualities) {