Free cookie consent management tool by TermsFeed Policy Generator

# source:branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/Comparators/HyperVolumeFast.cs@13620

Last change on this file since 13620 was 13620, checked in by bwerth, 7 years ago

#1087 regorganized testfunctions, added view for qualities

File size: 10.3 KB
Line
1using System;
2using System.Collections.Generic;
3using HeuristicLab.Common;
4using HeuristicLab.Problems.MultiObjectiveTestFunctions.Comparators;
5
6namespace HeuristicLab.Problems.MultiObjectiveTestFunctions {
7  /// <summary>
8  /// The Hyprevolume-metric is defined as the Hypervolume enclosed between a given reference point,
9  /// that is fixed for every evaluation function and the evaluated front.
10  ///
11  /// Example:
12  /// r is the reference Point at (1|1)  and every Point p is part of the evaluated front
13  /// The filled Area labled HV is the 2 diensional Hypervolume enclosed by this front.
14  ///
15  /// (0|1)                (1|1)
16  ///   +      +-------------r
17  ///   |      |###### HV ###|
18  ///   |      p------+######|
19  ///   |             p+#####|
20  ///   |              |#####|
21  ///   |              p-+###|
22  ///   |                p---+
23  ///   |
24  ///   +--------------------1
25  /// (0|0)                (1|0)
26  ///
27  ///  Please note that in this example both dimensions are minimized. The reference Point need to be dominated by EVERY point in the evaluated front
28  ///
29  /// </summary>
30  public class FastHypervolume {
31
32    private double[] reference;
33    private bool[] maximization;
34    public FastHypervolume(double[] reference, bool[] maximization) {
35      if (reference.Length != 2) throw new NotSupportedException("Only 2-dimensional cases are supported yet");
36      this.reference = reference;
37      this.maximization = maximization;
38    }
39
40    public double Compare(IEnumerable<double[]> front, IEnumerable<double[]> optimalFront, double[,] bounds) {
41      return GetHypervolume(optimalFront, bounds) - GetHypervolume(front, bounds);
42
43    }
44
45
46    /// <summary>
47    ///
48    /// </summary>
49    /// <param name="front"></param>
50    /// <param name="bounds">also called region</param>
51    /// <returns></returns>
52    public double GetHypervolume(IEnumerable<double[]> front, double[,] bounds) {
53      //TODO what to do if set contains dominated points
54      if (front == null) throw new ArgumentException("Fronts must not be null");
55      var list = new List<double[]>();
57      list.Sort(Utilities.getDimensionComparer(reference.Length - 1, maximization[reference.Length - 1]));
58      var results = new ExPrivates(this);
59      GetHV(SpanRegion(), list, 0, reference[reference.Length - 1], results);
60      return results.Volume;
61
62    }
63
64    private double[][] SpanRegion(double[,] bounds, int length) {
65      if (bounds.GetLength(1) != 2) throw new ArgumentException();
66      double[][] copy = new double[length][];
67      for (int i = 0; i < copy.Length; i++) {
68        copy[i] = new double[2];
69        for (int j = 0; j < 2; j++) {
70          copy[i][j] = bounds[i%bounds.GetLength(0),j];
71        }
72      }
73      return copy;
74    }
75
76    private double[][] SpanRegion() {
77      double[][] copy = new double[reference.Length][];
78      for (int i = 0; i < copy.Length; i++) {
79        copy[i] = new double[2];
80        copy[i][0] = 0;
81        copy[i][1] = reference[i];
82      }
83      return copy;
84
85    }
86
87
88    private double[][] DeepClone(double[][] array) {
89      double[][] copy = new double[array.Length][];
90      for (int i = 0; i < copy.Length; i++) {
91        copy[i] = new double[array[i].Length];
92        for (int j = 0; j < array[i].Length; j++) {
93          copy[i][j] = array[i][j];
94        }
95      }
96      return copy;
97    }
98
99    private class ExPrivates {
100      private double volume;
101      public double Volume {
102        get { return volume; }
103        set { volume = value; }
104      }
105      private int d;
106
107      public int D {
108        get { return d; }
109      }
110      public ExPrivates(FastHypervolume hv) {
111        volume = 0;
112        d = hv.reference.Length;
113      }
114
115
116
117    }
118
119    private void GetHV(double[][] region, List<double[]> points, int split, double cover, ExPrivates results) {
120      double coverNew = cover;
121      int coverIndex = 0;
122      bool allPiles = true;
123      double bound = -1;
124
125      /* is the region completely covered? */
126      while (coverNew == cover && coverIndex != points.Count) {
127        if (covers(points[coverIndex], region, results)) {
128          coverNew = points[coverIndex][results.D];
129          results.Volume += GetMeasure(region,results) * (cover - coverNew);
130        } else coverIndex++;
131      }
132      if (coverIndex == 0) return;
133
134      for (int i = 0; i < coverIndex; i++) { if (checkPile(points[i], region, results) == -1) allPiles = false; }
135
136      if (allPiles) {
137        /* calculate volume by sweeping along dimension d */
138        var trellis = new double[reference.Length];
139        int i = 0;
140        for (int j = 0; j < results.D-1; j++) trellis[j] = reference[j];
141
142        double next;//bernhard
143        do {
144          double current = points[i][results.D-1];
145          do {
146            int pile = checkPile(points[i], region,results);
147            if (points[i][pile] < trellis[pile]) trellis[pile] = points[i][pile];
148            i++;
149            if (i < coverIndex - 1) next = points[i][results.D-1]; else next = coverNew;
150          } while (current == next);
151          results.Volume += measure(trellis, region, results) * (next - current);
152        } while (next != coverNew);
153
154      } else {
155        /* split region in two children regions */
156        do {
157          var intersect = new List<Double>(); var nonIntersect = new List<Double>();
158          for (int i = 0; i < coverIndex; i++) {
159            var intersection = intersects(points[i], region, split);
160            if (intersection == 1) intersect.Add(points[i][split]);
161            if (intersection == 0) nonIntersect.Add(points[i][split]);
162          }
163          if (intersect.Count != 0) bound = intersect.Median();
164          else if (nonIntersect.Count > Math.Sqrt(points.Count)) bound = nonIntersect.Median();
165          else split++;
166        } while (bound == -1);
167      }
168
169
170      var regionC = DeepClone(region);
171      regionC[split][1] = bound;
172      var pointsC = new List<double[]>();
173      for (int i = 0; i < coverIndex; i++) {
174        if (partCovers(points[i], regionC, results)) move(points,i, pointsC);
175      }
176      if (pointsC.Count != 0) GetHV(regionC, pointsC, split, coverNew, results);
177      reinsert(pointsC, points);
178      regionC = region;
179      regionC[split][0] = bound;
180      pointsC = new List<double[]>();
181      for (int i = 1; i < coverIndex; i++) {
182        if (partCovers(points[i], regionC, results)) move(points,i, pointsC);
183      }
184      if (pointsC.Count != 0) GetHV(regionC, pointsC, split, coverNew, results);
185      reinsert(pointsC, points);
186    }
187
188    private void reinsert(List<double[]> pointsC, List<double[]> points) {
190      pointsC.Clear();
191    }
192
193    private double GetMeasure(double[][] region,ExPrivates result) {
194      double volume = 1.0;
195      // for ( std::size_t i = 0; i < regionLow.size(); i++ ) {
196      for (int i = 1; i < result.D; i++) {
197      volume *= (region[1][i] - region[0][i]);
198      }
199      return (volume);
200    }
201
202    private void move(List<double[]> points, int i, List<double[]> pointsC) {
203      double[] v = points[i];
204      points.Remove(v);
206    }
207
208    private double measure(double[] trellis, double[][] region, ExPrivates results) {
209      double volume=0;
210      bool[] indicator = new bool[results.D];
211      for (int i = 0; i < results.D-1; i++) indicator[i] = true;
212      int numberSummands = integerValue(indicator);
213
214      for (int i = 0; i <= numberSummands; i++) {
215        indicator = binaryValue(i);
216        int oneCounter = 0;
217        double summand = 0;
218        for (int j = 1; j < results.D; j++) {
219          if (indicator[i] == true) {
220            summand += region[1][j] - trellis[j];
221            oneCounter++;
222          } else {
223            summand += region[1][j] - region[0][j];
224          }
225        }
226        if(oneCounter%2 == 0) {
227          volume -= summand;
228        } else {
229          volume += summand;
230        }
231      }
232      return volume;
233    }
234
235    private int integerValue(bool[] binary) {
236      int sum=0;
237      foreach (bool b in binary) {
238        sum = (sum << 1) + (b ? 1 : 0);
239      }
240      return sum;
241    }
242
243    private bool[] binaryValue(int integer) {
244      bool[] res = new bool[32];
245      int i = 0;
246      while (integer != 0) {
247        res[i++]= (integer & 1)==1;
248        integer >>= 1;
249      }
250      return res;
251
252    }
253
254    private int checkPile(double[] point, double[][] region, ExPrivates results) {
255      int pile = -1;
256      for (int j = 0; j < results.D-1; j++) {
257        if (point[j] > region[j][0]) {
258          if (pile != -1) return -1;
259        }
260        pile = j;
261      }
262      return pile;
263
264    }
265
266    private int intersects(double[] point, double[][] region, int split) {
267      if (region[split][0] >= point[split]) return -1;
268      for (int j = 1; j < split; j++) {
269        if (point[j] > region[j][0]) return 1;
270      }
271      return 0;
272
273    }
274
275    private bool covers(double[] point, double[][] region, ExPrivates results) {
276      for (int j = 1; j < results.D; j++) {
277        if (point[j] > region[j][0]) return false;
278      }
279      return true;
280
281    }
282
283    private bool partCovers(double[] point, double[][] region, ExPrivates results) {
284      for (int j = 1; j < results.D; j++) {
285        if (point[j] >= region[j][1]) return false;
286      }
287      return true;
288    }
289
290    public static double GetHypervolume(IEnumerable<double[]> front, double[] reference, bool[] maximization, double[,] bounds) {
291      FastHypervolume comp = new FastHypervolume(reference, maximization);
292      return comp.GetHypervolume(front,bounds);
293    }
294
295    public static double GetDistance(IEnumerable<double[]> front, IEnumerable<double[]> optimalFront, double[] reference, bool[] maximization, double[,] bounds) {
296      return GetHypervolume(optimalFront, reference, maximization, bounds) - GetHypervolume(front, reference, maximization,bounds);
297    }
298
299    private void CheckConsistency(double[] point, int dim) {
300      if (!maximization[dim] && point[dim] > reference[dim]) throw new Exception("Reference Point must be dominated by all points of the front");
301      if (maximization[dim] && point[dim] < reference[dim]) throw new Exception("Reference Point must be dominated by all points of the front");
302    }
303
304
305
306
307
308
309
310
311
312
313  }
314}
Note: See TracBrowser for help on using the repository browser.