# source:branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/Calculators/HyperVolume.cs@14081

Last change on this file since 14081 was 14081, checked in by mkommend, 6 years ago

#1087: Refactored utility class NonDominatedSelect.

File size: 10.8 KB
Line
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21using System;
22using System.Collections.Generic;
23using System.Linq;
24using HeuristicLab.Common;
25
26namespace HeuristicLab.Problems.MultiObjectiveTestFunctions {
27
28  public static class Hypervolume {
29
30    /// <summary>
31    /// The Hyprevolume-metric is defined as the Hypervolume enclosed between a given reference point,
32    /// that is fixed for every evaluation function and the evaluated front.
33    ///
34    /// 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 dimensional Hypervolume enclosed by this front.
37    ///
38    /// (0|1)                (1|1)
39    ///   +      +-------------r
40    ///   |      |###### HV ###|
41    ///   |      p------+######|
42    ///   |             p+#####|
43    ///   |              |#####|
44    ///   |              p-+###|
45    ///   |                p---+
46    ///   |
47    ///   +--------------------1
48    /// (0|0)                (1|0)
49    ///
50    ///  Please note that in this example both dimensions are minimized. The reference Point need to be dominated by EVERY point in the evaluated front
51    ///
52    /// </summary>
53    ///
54    public static double Calculate(IEnumerable<double[]> front, double[] referencePoint, bool[] maximization) {
55      front = NonDominatedSelect.GetDominatingVectors(front, referencePoint, maximization, false);
56      if (maximization.Length == 2)
57        return Calculate2D(front, referencePoint, maximization);
58
59      if (Array.TrueForAll(maximization, x => !x))
60        return CalculateMulitDimensional(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
72      double[][] set = front.ToArray();
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]));
76
77      double sum = 0;
78      for (int i = 0; i < set.Length - 1; i++) {
79        sum += Math.Abs((set[i][0] - set[i + 1][0])) * Math.Abs((set[i][1] - referencePoint[1]));
80      }
81
82      double[] lastPoint = set[set.Length - 1];
83      sum += Math.Abs(lastPoint[0] - referencePoint[0]) * Math.Abs(lastPoint[1] - referencePoint[1]);
84
85      return sum;
86    }
87
88
89
90    private static double CalculateMulitDimensional(IEnumerable<double[]> front, double[] referencePoint) {
91      if (referencePoint == null || referencePoint.Length < 3) throw new ArgumentException("ReferencePoint unfit for complex Hypervolume calculation");
92
93      int objectives = referencePoint.Length;
94      var fronList = front.ToList();
95      fronList.StableSort(new Utilities.DimensionComparer(objectives - 1, false));
96
97      double[] regLow = Enumerable.Repeat(1E15, objectives).ToArray();
98      foreach (double[] p in fronList) {
99        for (int i = 0; i < regLow.Length; i++) {
100          if (p[i] < regLow[i]) regLow[i] = p[i];
101        }
102      }
103
104      return Stream(regLow, referencePoint, fronList, 0, referencePoint[objectives - 1], (int)Math.Sqrt(fronList.Count), objectives);
105    }
106
107    private static double Stream(double[] regionLow, double[] regionUp, List<double[]> front, int split, double cover, int sqrtNoPoints, int objectives) {
108      double coverOld = cover;
109      int coverIndex = 0;
110      int coverIndexOld = -1;
111      int c;
112      double result = 0;
113
114      double dMeasure = GetMeasure(regionLow, regionUp, objectives);
115      while (cover == coverOld && coverIndex < front.Count()) {
116        if (coverIndexOld == coverIndex) break;
117        coverIndexOld = coverIndex;
118        if (Covers(front[coverIndex], regionLow, objectives)) {
119          cover = front[coverIndex][objectives - 1];
120          result += dMeasure * (coverOld - cover);
121        } else coverIndex++;
122
123      }
124
125      for (c = coverIndex; c > 0; c--) if (front[c - 1][objectives - 1] == cover) coverIndex--;
126      if (coverIndex == 0) return result;
127
128      bool allPiles = true;
129      int[] piles = new int[coverIndex];
130      for (int i = 0; i < coverIndex; i++) {
131        piles[i] = IsPile(front[i], regionLow, regionUp, objectives);
132        if (piles[i] == -1) {
133          allPiles = false;
134          break;
135        }
136      }
137
138      if (allPiles) {
139        double[] trellis = new double[regionUp.Length];
140        for (int j = 0; j < trellis.Length; j++) trellis[j] = regionUp[j];
141        double current = 0;
142        double next = 0;
143        int i = 0;
144        do {
145          current = front[i][objectives - 1];
146          do {
147            if (front[i][piles[i]] < trellis[piles[i]]) trellis[piles[i]] = front[i][piles[i]];
148            i++;
149            if (i < coverIndex) next = front[i][objectives - 1];
150            else { next = cover; break; }
151          } while (next == current);
152          result += ComputeTrellis(regionLow, regionUp, trellis, objectives) * (next - current);
153        } while (next != cover);
154      } else {
155        double bound = -1;
156        double[] boundaries = new double[coverIndex];
157        double[] noBoundaries = new double[coverIndex];
158        int boundIdx = 0;
159        int noBoundIdx = 0;
160
161        do {
162          for (int i = 0; i < coverIndex; i++) {
163            int contained = ContainesBoundary(front[i], regionLow, split);
164            if (contained == 0) boundaries[boundIdx++] = front[i][split];
165            else if (contained == 1) noBoundaries[noBoundIdx++] = front[i][split];
166          }
167          if (boundIdx > 0) bound = GetMedian(boundaries, boundIdx);
168          else if (noBoundIdx > sqrtNoPoints) bound = GetMedian(noBoundaries, noBoundIdx);
169          else split++;
170        } while (bound == -1.0);
171
172        List<double[]> pointsChildLow, pointsChildUp;
173        pointsChildLow = new List<double[]>();
174        pointsChildUp = new List<double[]>();
175        double[] regionUpC = new double[regionUp.Length];
176        for (int j = 0; j < regionUpC.Length; j++) regionUpC[j] = regionUp[j];
177        double[] regionLowC = new double[regionLow.Length];
178        for (int j = 0; j < regionLowC.Length; j++) regionLowC[j] = regionLow[j];
179
180        for (int i = 0; i < coverIndex; i++) {
181          if (PartCovers(front[i], regionUpC, objectives)) pointsChildUp.Add(front[i]);
182          if (PartCovers(front[i], regionUp, objectives)) pointsChildLow.Add(front[i]);
183        }
184        //this could/should be done in Parallel
185
186        if (pointsChildUp.Count > 0) result += Stream(regionLow, regionUpC, pointsChildUp, split, cover, sqrtNoPoints, objectives);
187        if (pointsChildLow.Count > 0) result += Stream(regionLowC, regionUp, pointsChildLow, split, cover, sqrtNoPoints, objectives);
188      }
189      return result;
190    }
191
192    private static double GetMedian(double[] vector, int length) {
193      return vector.Take(length).Median();
194    }
195
196    private static double ComputeTrellis(double[] regionLow, double[] regionUp, double[] trellis, int objectives) {
197      bool[] bs = new bool[objectives - 1];
198      for (int i = 0; i < bs.Length; i++) bs[i] = true;
199
200      double result = 0;
201      uint noSummands = BinarayToInt(bs);
202      int oneCounter; double summand;
203      for (uint i = 1; i <= noSummands; i++) {
204        summand = 1;
205        IntToBinary(i, bs);
206        oneCounter = 0;
207        for (int j = 0; j < objectives - 1; j++) {
208          if (bs[j]) {
209            summand *= regionUp[j] - trellis[j];
210            oneCounter++;
211          } else {
212            summand *= regionUp[j] - regionLow[j];
213          }
214        }
215        if (oneCounter % 2 == 0) result -= summand;
216        else result += summand;
217
218      }
219      return result;
220    }
221
222    private static void IntToBinary(uint i, bool[] bs) {
223      for (int j = 0; j < bs.Length; j++) bs[j] = false;
224      uint rest = i;
225      int idx = 0;
226      while (rest != 0) {
227        bs[idx] = rest % 2 == 1;
228        rest = rest / 2;
229        idx++;
230      }
231
232    }
233
234    private static uint BinarayToInt(bool[] bs) {
235      uint result = 0;
236      for (int i = 0; i < bs.Length; i++) {
237        result += bs[i] ? ((uint)1 << i) : 0;
238      }
239      return result;
240    }
241
242    private static int IsPile(double[] cuboid, double[] regionLow, double[] regionUp, int objectives) {
243      int pile = cuboid.Length;
244      for (int i = 0; i < objectives - 1; i++) {
245        if (cuboid[i] > regionLow[i]) {
246          if (pile != objectives) return 1;
247          pile = i;
248        }
249      }
250      return pile;
251    }
252
253    private static double GetMeasure(double[] regionLow, double[] regionUp, int objectives) {
254      double volume = 1;
255      for (int i = 0; i < objectives - 1; i++) {
256        volume *= (regionUp[i] - regionLow[i]);
257      }
258      return volume;
259    }
260
261    private static int ContainesBoundary(double[] cub, double[] regionLow, int split) {
262      if (regionLow[split] >= cub[split]) return -1;
263      else {
264        for (int j = 0; j < split; j++) {
265          if (regionLow[j] < cub[j]) return 1;
266        }
267      }
268      return 0;
269    }
270
271    private static bool PartCovers(double[] v, double[] regionUp, int objectives) {
272      for (int i = 0; i < objectives - 1; i++) {
273        if (v[i] >= regionUp[i]) return false;
274      }
275      return true;
276    }
277
278    private static bool Covers(double[] v, double[] regionLow, int objectives) {
279      for (int i = 0; i < objectives - 1; i++) {
280        if (v[i] > regionLow[i]) return false;
281      }
282      return true;
283    }
284
285
286  }
287}
288
Note: See TracBrowser for help on using the repository browser.