1 | using System;
|
---|
2 | using System.Collections.Generic;
|
---|
3 | using HeuristicLab.Common;
|
---|
4 | using HeuristicLab.Problems.MultiObjectiveTestFunctions.Comparators;
|
---|
5 |
|
---|
6 | namespace 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[]>();
|
---|
56 | list.AddRange(front);
|
---|
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) {
|
---|
189 | points.AddRange(pointsC);
|
---|
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);
|
---|
205 | pointsC.Add(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 | }
|
---|