Free cookie consent management tool by TermsFeed Policy Generator

Changeset 14018


Ignore:
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:
8 edited

Legend:

Unmodified
Added
Removed

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

    r13988 r14018  
    3232  /// C(A) = mean(d(x,A)) where x in A  and d(x,A) is not infinite
    3333  /// </summary>
    34   public class Crowding {
     34  public static class Crowding {
    3535
    3636    public static double Calculate(IEnumerable<double[]> front, double[,] bounds) {
    37       double sum = 0;
    38       int c = 0;
     37
    3938      double[] pointsums = new double[front.Count()];
    4039
    4140      for (int dim = 0; dim < front.First().Length; dim++) {
     41
    4242        double[] arr = front.Select(x => x[dim]).ToArray();
    4343        Array.Sort(arr);
     44
    4445        double fmax = bounds[dim % bounds.GetLength(0), 1];
    4546        double fmin = bounds[dim % bounds.GetLength(0), 0];
     47
    4648        int pointIdx = 0;
    4749        foreach (double[] point in front) {
    … …  
    5557      }
    5658
     59      double sum = 0;
     60      int c = 0;
    5761      foreach (double d in pointsums) {
    5862        if (!Double.IsInfinity(d)) {
    … …  
    6165        }
    6266      }
     67
    6368      return c == 0 ? Double.PositiveInfinity : sum / c;
    6469    }

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

    r13672 r14018  
    2121using System;
    2222using System.Collections.Generic;
     23using System.Linq;
    2324
    2425namespace HeuristicLab.Problems.MultiObjectiveTestFunctions {
    … …  
    2829  ///  where d[i] is the minimal distance the ith point of the evaluated front has to any point in the optimal pareto front.   
    2930  /// </summary>
    30   public class GenerationalDistance {
     31  public static class GenerationalDistance {
    3132
    3233    public static double Calculate(IEnumerable<double[]> front, IEnumerable<double[]> optimalFront, double p) {
    33       //TODO build a kd-tree, sort the array, do someting intelligent here
    34       if (front == null || optimalFront == null) throw new ArgumentException("Fronts must not be null");
     34      //TODO build a kd-tree, sort the array, do something intelligent here
     35      if (front == null || optimalFront == null) throw new ArgumentNullException("Fronts must not be null.");
     36      if (!front.Any()) throw new ArgumentException("Front must not be empty.");
     37      if (p == 0.0) throw new ArgumentException("p must not be 0.0.");
     38
    3539      double sum = 0;
    3640      int c = 0;
    3741      foreach (double[] r in front) {
    38         sum += Utilities.minDistance(r, optimalFront, true);
     42        sum += Utilities.MinimumDistance(r, optimalFront);
    3943        c++;
    4044      }
    41       if (c == 0) throw new ArgumentException("Fronts must not be empty");
     45
    4246      return Math.Pow(sum, 1 / p) / c;
    4347    }
    4448
    45 
    46 
    4749  }
    4850}

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

    r13988 r14018  
    1919 */
    2020#endregion
    21 using HeuristicLab.Common;
    2221using System;
    2322using System.Collections.Generic;
    2423using System.Linq;
     24using HeuristicLab.Common;
    2525
    2626namespace HeuristicLab.Problems.MultiObjectiveTestFunctions {
    2727
    28   public class Hypervolume {
     28  public static class Hypervolume {
    2929
    3030    /// <summary>
    … …  
    3333    ///
    3434    /// Example:
    35     /// r is the reference Point at (1|1)  and every Point p is part of the evaluated front
    36     /// The filled Area labled HV is the 2 diensional Hypervolume enclosed by this front.
     35    /// r is the reference Point at (1|1) and every Point p is part of the evaluated front
     36    /// The filled Area labled HV is the 2 dimensional Hypervolume enclosed by this front.
    3737    ///
    3838    /// (0|1)                (1|1)
    … …  
    5252    /// </summary>
    5353    ///
    54     public static double Calculate(IEnumerable<double[]> points, IEnumerable<double> reference, bool[] maximization) {
    55       var front = NonDominatedSelect.removeNonReferenceDominatingVectors(points, reference.ToArray<double>(), maximization, false);
    56       if (maximization.Length == 2) { //Hypervolume analysis only with 2 objectives for now
    57         return Hypervolume.Calculate2D(front, reference, maximization);
    58       } else if (Array.TrueForAll(maximization, x => !x)) {
    59         return Hypervolume.CalculateMD(front, reference);
    60       } else {
    61         throw new NotImplementedException("Hypervolume calculation for more than two dimensions is supported only with minimization problems");
    62       }
    63     }
    64 
    65 
    66     private static double Calculate2D(IEnumerable<double[]> front, IEnumerable<double> reference, bool[] maximization) {
    67       List<double> list = new List<double>();
    68       foreach (double d in reference) list.Add(d);
    69       double[] refp = list.ToArray<double>();
    70       if (front == null) throw new ArgumentException("Fronts must not be null");
     54    public static double Calculate(IEnumerable<double[]> points, double[] referencePoint, bool[] maximization) {
     55      var front = NonDominatedSelect.removeNonReferenceDominatingVectors(points, referencePoint, maximization, false);
     56      if (maximization.Length == 2)
     57        return Calculate2D(front, referencePoint, maximization);
     58
     59      if (Array.TrueForAll(maximization, x => !x))
     60        return CalculateMD(front, referencePoint);
     61      else throw new NotImplementedException("Hypervolume calculation for more than two dimensions is supported only with minimization problems.");
     62    }
     63
     64
     65    private static double Calculate2D(IEnumerable<double[]> front, double[] referencePoint, bool[] maximization) {
     66      if (front == null) throw new ArgumentNullException("Front must not be null.");
     67      if (!front.Any()) throw new ArgumentException("Front must not be empty.");
     68
     69      if (referencePoint == null) throw new ArgumentNullException("ReferencePoint must not be null.");
     70      if (referencePoint.Length != 2) throw new ArgumentException("ReferencePoint must have exactly two dimensions.");
     71
    7172      double[][] set = front.ToArray();   //Still no Good
    72       if (set.Length == 0) throw new ArgumentException("Fronts must not be empty");
    73       if (refp.Length != set[0].Length) throw new ArgumentException("Front and referencepoint need to be of the same dimensionality");
    74       Array.Sort<double[]>(set, Utilities.getDimensionComparer(0, maximization[0]));
    75       double[] last = set[set.Length - 1];
    76       CheckConsistency(last, 0, refp, maximization);
    77       CheckConsistency(last, 1, refp, maximization);
     73      if (set.Any(s => s.Length != 2)) throw new ArgumentException("Points in front must have exactly two dimensions.");
     74
     75      Array.Sort<double[]>(set, new Utilities.DimensionComparer(0, maximization[0]));
    7876
    7977      double sum = 0;
    8078      for (int i = 0; i < set.Length - 1; i++) {
    81         CheckConsistency(set[i], 1, refp, maximization);
    82         sum += Math.Abs((set[i][0] - set[i + 1][0])) * Math.Abs((set[i][1] - refp[1]));
    83       }
    84 
    85       sum += Math.Abs(refp[0] - last[0]) * Math.Abs(refp[1] - last[1]);
     79        if (NonDominatedSelect.Dominates(referencePoint, set[i], maximization, true) == NonDominatedSelect.DominationResult.Dominates)
     80          throw new ArgumentException("Reference Point must be dominated by all points of the front");
     81        sum += Math.Abs((set[i][0] - set[i + 1][0])) * Math.Abs((set[i][1] - referencePoint[1]));
     82      }
     83
     84      double[] lastPoint = set[set.Length - 1];
     85      if (NonDominatedSelect.Dominates(referencePoint, lastPoint, maximization, true) == NonDominatedSelect.DominationResult.Dominates)
     86        throw new ArgumentException("Reference Point must be dominated by all points of the front");
     87      sum += Math.Abs(lastPoint[0] - referencePoint[0]) * Math.Abs(lastPoint[1] - referencePoint[1]);
     88
    8689      return sum;
    8790    }
    8891
    89     private static void CheckConsistency(double[] point, int dim, double[] reference, bool[] maximization) {
    90       if (!maximization[dim] && point[dim] > reference[dim]) throw new ArgumentException("Reference Point must be dominated by all points of the front");
    91       if (maximization[dim] && point[dim] < reference[dim]) throw new ArgumentException("Reference Point must be dominated by all points of the front");
    92       if (point.Length != 2) throw new ArgumentException("Only 2-dimensional cases are supported yet");
    93     }
    94 
    95     private static double CalculateMD(IEnumerable<double[]> points, IEnumerable<double> reference) {
    96       double[] referencePoint = reference.ToArray<double>();
     92
     93
     94    private static double CalculateMD(IEnumerable<double[]> points, double[] referencePoint) {
    9795      if (referencePoint == null || referencePoint.Length < 3) throw new ArgumentException("ReferencePoint unfit for complex Hypervolume calculation");
    9896      if (!IsDominated(referencePoint, points)) {
    9997        throw new ArgumentException("ReferencePoint unfit for complex Hypervolume calculation");
    10098      }
     99
    101100      int objectives = referencePoint.Length;
    102       List<double[]> lpoints = new List<double[]>();
    103       foreach (double[] p in points) {
    104         lpoints.Add(p);
    105       }
    106       lpoints.StableSort(Utilities.getDimensionComparer(objectives - 1, false));
    107 
    108       double[] regLow = new double[objectives];
    109       for (int i = 0; i < objectives; i++) {
    110         regLow[i] = 1E15;
    111       }
    112       foreach (double[] p in lpoints) {
     101      var front = points.ToList();
     102      front.StableSort(new Utilities.DimensionComparer(objectives - 1, false));
     103
     104      double[] regLow = Enumerable.Repeat(1E15, objectives).ToArray();
     105      foreach (double[] p in front) {
    113106        for (int i = 0; i < regLow.Length; i++) {
    114           if (regLow[i] > p[i]) regLow[i] = p[i];
    115         }
    116       }
    117 
    118       return Stream(regLow, referencePoint, lpoints, 0, referencePoint[objectives - 1], (int)Math.Sqrt(points.Count()), objectives);
     107          if (p[i] < regLow[i]) regLow[i] = p[i];
     108        }
     109      }
     110
     111      return Stream(regLow, referencePoint, front, 0, referencePoint[objectives - 1], (int)Math.Sqrt(front.Count), objectives);
    119112    }
    120113
    … …  
    209202        //this could/should be done in Parallel
    210203
    211         if (pointsChildUp.Count() > 0) result += Stream(regionLow, regionUpC, pointsChildUp, split, cover, sqrtNoPoints, objectives);
    212         if (pointsChildLow.Count() > 0) result += Stream(regionLowC, regionUp, pointsChildLow, split, cover, sqrtNoPoints, objectives);
     204        if (pointsChildUp.Count > 0) result += Stream(regionLow, regionUpC, pointsChildUp, split, cover, sqrtNoPoints, objectives);
     205        if (pointsChildLow.Count > 0) result += Stream(regionLowC, regionUp, pointsChildLow, split, cover, sqrtNoPoints, objectives);
    213206      }
    214207      return result;
    … …  
    216209
    217210    private static double GetMedian(double[] vector, int length) {
    218       if (vector.Length != length) {
    219         double[] vec = new double[length];
    220         Array.Copy(vector, vec, length);
    221         vector = vec;
    222       }
    223       return vector.Median();
    224 
     211      return vector.Take(length).Median();
    225212    }
    226213

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

    r13672 r14018  
    2727  ///  where d[i] is the minimal distance the ith point of the optimal pareto front has to any point in the evaluated front.   
    2828  /// </summary>
    29   public class InvertedGenerationalDistance {
    30 
     29  public static class InvertedGenerationalDistance {
    3130    public static double Calculate(IEnumerable<double[]> front, IEnumerable<double[]> optimalFront, double p) {
    3231      return GenerationalDistance.Calculate(optimalFront, front, p);

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

    r13725 r14018  
    6969        lpoints.Add(p);
    7070      }
    71       lpoints.StableSort(Utilities.getDimensionComparer(objectives - 1, false));
     71      lpoints.StableSort(new Utilities.DimensionComparer(objectives - 1, false));
    7272
    7373      double[] regLow = new double[objectives];

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

    r13672 r14018  
    2121using System;
    2222using System.Collections.Generic;
     23using System.Linq;
    2324using HeuristicLab.Common;
    2425
    … …  
    3031  /// to all OTHER points in the same front
    3132  /// </summary>
    32   public class Spacing {
     33  public static class Spacing {
    3334
    34     public static double Calculate(IEnumerable<double[]> front) {
    35       if (front == null) throw new ArgumentException("Fronts must not be null");
     35    public static double Calculate(IEnumerable<double[]> points) {
     36      if (points == null) throw new ArgumentException("Front must not be null.");
     37      if (!points.Any()) throw new ArgumentException("Front must  not be empty.");
     38
    3639      List<double> d = new List<double>();
    37       foreach (double[] r in front) {
    38         double dist = Utilities.minDistance(r, front, false);
    39         d.Add(dist >= 0 ? dist : 0);
     40      foreach (double[] r in points) {
     41        var point = r;
     42        var otherPoints = points.Where(p => p != point).DefaultIfEmpty(point);
     43        double dist = Utilities.MinimumDistance(point, otherPoints);
     44        d.Add(dist);
    4045      }
    41       int n = d.Count;
    42       if (n == 0) throw new ArgumentException("Fronts must not be empty");
    43       return Math.Sqrt(d.Variance() * (n - 1) / n);
    4446
     47      return d.StandardDeviationPop();
    4548    }
    4649

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

    r13771 r14018  
    2121using System;
    2222using System.Collections.Generic;
     23using System.Linq;
    2324
    2425namespace HeuristicLab.Problems.MultiObjectiveTestFunctions {
    25   internal class Utilities {
     26  internal static class Utilities {
     27    internal static double MinimumDistance(double[] point, IEnumerable<double[]> points) {
     28      if (point == null) throw new ArgumentNullException("Point must not be null.");
     29      if (points == null) throw new ArgumentNullException("Points must not be null.");
     30      if (!points.Any()) throw new ArgumentException("Points must not be empty.");
    2631
    27     /// <summary>
    28     ///
    29     /// </summary>
    30     /// <param name="point"></param>
    31     /// <param name="list"></param>
    32     /// <param name="reflexive"></param>
    33     /// <returns>return -1 if list contains only rejected points</returns>
    34     internal static double minDistance(double[] point, IEnumerable<double[]> list, bool reflexive) {
    35       double min = double.MaxValue;
    36       bool empty = true;
    37       foreach (double[] r in list) {
    38         empty = false;
    39         if (!reflexive && ReferenceEquals(r, point)) continue;
    40         double d = 0;
    41         if (r.Length != point.Length) throw new ArgumentException("dimensions of Front and Point do not match");
     32      double minDistance = double.MaxValue;
     33      foreach (double[] r in points) {
     34        if (r.Length != point.Length) throw new ArgumentException("Dimensions of Points and Point do not match.");
     35
     36        double squaredDistance = 0;
    4237        for (int i = 0; i < r.Length; i++) {
    43           d += (point[i] - r[i]) * (point[i] - r[i]);
     38          squaredDistance += (point[i] - r[i]) * (point[i] - r[i]);
    4439        }
    45         min = Math.Min(d, min);
     40        minDistance = Math.Min(squaredDistance, minDistance);
    4641      }
    47       if (empty) throw new ArgumentException("Fronts must not be empty");
    48       if (min == double.MaxValue) { return -1; }
    49       return Math.Sqrt(min);
     42
     43      return Math.Sqrt(minDistance);
    5044    }
    5145
    52     internal static IComparer<double[]> getDimensionComparer(int dim, bool descending) {
    53       return new DimensionComparer(dim, descending);
    54     }
    55 
    56 
    5746    internal class DimensionComparer : IComparer<double[]> {
    58       private int dim;
    59       private int descending;
     47      private readonly int dim;
     48      private readonly int descending;
    6049
    6150      public DimensionComparer(int dimension, bool descending) {
    … …  
    6453      }
    6554
    66       #region IComparer<DoubleArray> Members
    67 
    6855      public int Compare(double[] x, double[] y) {
    6956        if (x[dim] < y[dim]) return -descending;
    … …  
    7158        else return 0;
    7259      }
    73 
    74       #endregion
    7560    }
    7661  }
    77 
    78 
    79 
    80 
    81 
    8262}

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

    r13991 r14018  
    2727
    2828  public class NonDominatedSelect {
    29     private enum DominationResult { Dominates, IsDominated, IsNonDominated };
     29    public enum DominationResult { Dominates, IsDominated, IsNonDominated };
    3030
    3131    public static IEnumerable<double[]> selectNonDominatedVectors(IEnumerable<double[]> qualities, bool[] maximization, bool dominateOnEqualQualities) {
    … …  
    6060    }
    6161
    62     private static DominationResult Dominates(double[] left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
     62    public static DominationResult Dominates(double[] left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
    6363      //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
    6464      if (dominateOnEqualQualities) {
Note: See TracChangeset for help on using the changeset viewer.