1 | using System;
|
---|
2 | using System.Collections.Generic;
|
---|
3 | using System.Linq;
|
---|
4 | using HeuristicLab.Core;
|
---|
5 |
|
---|
6 | namespace HeuristicLab.Algorithms.NSGA3
|
---|
7 | {
|
---|
8 | public class ReferencePoint
|
---|
9 | {
|
---|
10 | // The potentially associated solutions to this reference point and the distance to that solution
|
---|
11 | private readonly Dictionary<Solution, double> potentialAssociatedSolutions = new Dictionary<Solution, double>();
|
---|
12 |
|
---|
13 | #region Properties
|
---|
14 |
|
---|
15 | private readonly IRandom random;
|
---|
16 | public double[] Values { get; }
|
---|
17 | public int NumberOfDimensions => Values.Length;
|
---|
18 | public int NumberOfAssociatedSolutions { get; set; } = 0;
|
---|
19 |
|
---|
20 | #endregion Properties
|
---|
21 |
|
---|
22 | #region Constructors
|
---|
23 |
|
---|
24 | public ReferencePoint(IRandom random, int numberOfDimensions)
|
---|
25 | {
|
---|
26 | this.random = random;
|
---|
27 | Values = new double[numberOfDimensions];
|
---|
28 | }
|
---|
29 |
|
---|
30 | public ReferencePoint(ReferencePoint other)
|
---|
31 | {
|
---|
32 | random = other.random;
|
---|
33 | Values = new double[other.NumberOfDimensions];
|
---|
34 | other.Values.CopyTo(Values, 0);
|
---|
35 | }
|
---|
36 |
|
---|
37 | #endregion Constructors
|
---|
38 |
|
---|
39 | #region Static methods
|
---|
40 |
|
---|
41 | /// <summary>
|
---|
42 | /// Returns the number of reference points that would be created when using <see
|
---|
43 | /// cref="GenerateReferencePoints(IRandom, int)" />.
|
---|
44 | /// </summary>
|
---|
45 | /// <param name="nDim"></param>
|
---|
46 | /// <returns></returns>
|
---|
47 | internal static int GetNumberOfGeneratedReferencePoints(int nDim)
|
---|
48 | {
|
---|
49 | int outerDiv;
|
---|
50 | int innerDiv;
|
---|
51 | switch (nDim)
|
---|
52 | {
|
---|
53 | case 3:
|
---|
54 | outerDiv = 12;
|
---|
55 | innerDiv = 0;
|
---|
56 | break;
|
---|
57 |
|
---|
58 | case 5:
|
---|
59 | outerDiv = 6;
|
---|
60 | innerDiv = 0;
|
---|
61 | break;
|
---|
62 |
|
---|
63 | case 8:
|
---|
64 | outerDiv = 3;
|
---|
65 | innerDiv = 2;
|
---|
66 | break;
|
---|
67 |
|
---|
68 | case 10:
|
---|
69 | outerDiv = 3;
|
---|
70 | innerDiv = 2;
|
---|
71 | break;
|
---|
72 |
|
---|
73 | case 15:
|
---|
74 | outerDiv = 2;
|
---|
75 | innerDiv = 1;
|
---|
76 | break;
|
---|
77 |
|
---|
78 | default:
|
---|
79 | return -1;
|
---|
80 | }
|
---|
81 |
|
---|
82 | return GetNumberOfGeneratedReferencePoints(nDim, outerDiv, innerDiv);
|
---|
83 | }
|
---|
84 |
|
---|
85 | internal static int GetNumberOfGeneratedReferencePoints(int nDim, int outerDiv, int innerDiv = 0)
|
---|
86 | {
|
---|
87 | return Utility.NCR(nDim + outerDiv - 1, outerDiv) + (innerDiv == 0 ? 0 : Utility.NCR(nDim + innerDiv - 1, innerDiv));
|
---|
88 | }
|
---|
89 |
|
---|
90 | /// <summary>
|
---|
91 | /// Generate reference points that are evenly distributed over a hyperplane with dimensions
|
---|
92 | /// <paramref name="nDim" /> - 1 with the sum of the values in all dimensions being equal to
|
---|
93 | /// 1 for each reference point. <paramref name="nDim" /> may only be one of {3, 5, 8, 10, 15}
|
---|
94 | /// -> The number of inner divisions and outer divisions are determined based on the
|
---|
95 | /// values provided in the NSGA-III paper, chapter V: Results. If different dimensions are
|
---|
96 | /// given, a NotSupportedException is thrown.
|
---|
97 | /// </summary>
|
---|
98 | /// <param name="random">
|
---|
99 | /// The <see cref="IRandom" /> to give as a parameter to the ReferencePoint constructors.
|
---|
100 | /// </param>
|
---|
101 | /// <param name="nDim">The dimensionality of the Reference Points</param>
|
---|
102 | /// <returns></returns>
|
---|
103 | internal static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim)
|
---|
104 | {
|
---|
105 | List<ReferencePoint> referencePoints;
|
---|
106 | switch (nDim)
|
---|
107 | {
|
---|
108 | case 3:
|
---|
109 | referencePoints = GenerateReferencePoints(random, nDim, 12, 0);
|
---|
110 | break;
|
---|
111 |
|
---|
112 | case 5:
|
---|
113 | referencePoints = GenerateReferencePoints(random, nDim, 6, 0);
|
---|
114 | break;
|
---|
115 |
|
---|
116 | case 8:
|
---|
117 | referencePoints = GenerateReferencePoints(random, nDim, 3, 2);
|
---|
118 | break;
|
---|
119 |
|
---|
120 | case 10:
|
---|
121 | referencePoints = GenerateReferencePoints(random, nDim, 3, 2);
|
---|
122 | break;
|
---|
123 |
|
---|
124 | case 15:
|
---|
125 | referencePoints = GenerateReferencePoints(random, nDim, 2, 1);
|
---|
126 | break;
|
---|
127 |
|
---|
128 | default:
|
---|
129 | throw new NotSupportedException("Only the reference points for 3, 5, 8, 10 or 15 dimensions can be created.");
|
---|
130 | }
|
---|
131 |
|
---|
132 | return referencePoints;
|
---|
133 | }
|
---|
134 |
|
---|
135 | /*
|
---|
136 | * This method is based on Tsung-Che Chiang's NSGA-III implementation (version 1.20)
|
---|
137 | * http://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm
|
---|
138 | */
|
---|
139 |
|
---|
140 | /// <summary>
|
---|
141 | /// Generate reference points that are evenly distributed over a hyperplane with dimensions
|
---|
142 | /// <paramref name="nDim" /> - 1 with the sum of the values in all dimensions being equal to
|
---|
143 | /// 1 for each reference point.
|
---|
144 | /// </summary>
|
---|
145 | /// <param name="nDim">The number of dimensions for the reference points.</param>
|
---|
146 | /// <param name="outerDiv">The number of divisions for the outer reference points</param>
|
---|
147 | /// <returns>The generated reference points (Check Fig. 4 in NSGA-III paper).</returns>
|
---|
148 | /// <param name="innerDiv">The number of divisions for the inner reference points</param>
|
---|
149 | /// <returns>
|
---|
150 | /// The generated reference points (Check Fig. 4 in NSGA-III paper). Set to 0, in order to
|
---|
151 | /// not have inner reference points
|
---|
152 | /// </returns>
|
---|
153 | internal static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim, int outerDiv, int innerDiv = 0)
|
---|
154 | {
|
---|
155 | if (nDim <= 0) throw new ArgumentException("nDim must be greater than 0");
|
---|
156 | if (outerDiv <= 1) throw new ArgumentException("outerDiv must be greater than 1");
|
---|
157 |
|
---|
158 | List<ReferencePoint> referencePoints = new List<ReferencePoint>();
|
---|
159 | ReferencePoint refPoint = new ReferencePoint(random, nDim);
|
---|
160 | GenerateRecursive(referencePoints, refPoint, nDim, outerDiv, outerDiv, 0);
|
---|
161 |
|
---|
162 | if (innerDiv > 0)
|
---|
163 | {
|
---|
164 | List<ReferencePoint> insideReferencePoints = new List<ReferencePoint>();
|
---|
165 | GenerateRecursive(insideReferencePoints, refPoint, nDim, innerDiv, innerDiv, 0);
|
---|
166 |
|
---|
167 | double center = 1.0 / nDim;
|
---|
168 |
|
---|
169 | for (int i = 0; i < insideReferencePoints.Count; i++)
|
---|
170 | {
|
---|
171 | for (int j = 0; j < insideReferencePoints[i].Values.Length; j++)
|
---|
172 | {
|
---|
173 | insideReferencePoints[i].Values[j] = (center + insideReferencePoints[i].Values[j]) / 2;
|
---|
174 | }
|
---|
175 | referencePoints.Add(insideReferencePoints[i]);
|
---|
176 | }
|
---|
177 | }
|
---|
178 |
|
---|
179 | return referencePoints;
|
---|
180 | }
|
---|
181 |
|
---|
182 | /*
|
---|
183 | * This method is based on Tsung-Che Chiang's NSGA-III implementation (version 1.20)
|
---|
184 | * http://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm
|
---|
185 | */
|
---|
186 |
|
---|
187 | private static void GenerateRecursive(List<ReferencePoint> referencePoints, ReferencePoint refPoint, int numberOfObjectives, int left, int total, int element)
|
---|
188 | {
|
---|
189 | if (element == numberOfObjectives - 1)
|
---|
190 | {
|
---|
191 | refPoint.Values[element] = ((double)left) / total;
|
---|
192 | var newRefPoint = new ReferencePoint(refPoint);
|
---|
193 | referencePoints.Add(newRefPoint);
|
---|
194 | }
|
---|
195 | else
|
---|
196 | {
|
---|
197 | for (int i = 0; i <= left; i++)
|
---|
198 | {
|
---|
199 | refPoint.Values[element] = (double)i / total;
|
---|
200 | GenerateRecursive(referencePoints, refPoint, numberOfObjectives, left - i, total, element + 1);
|
---|
201 | }
|
---|
202 | }
|
---|
203 | }
|
---|
204 |
|
---|
205 | #endregion Static methods
|
---|
206 |
|
---|
207 | public void AddPotentialAssociatedSolution(Solution s, double distance)
|
---|
208 | {
|
---|
209 | if (potentialAssociatedSolutions.ContainsKey(s))
|
---|
210 | throw new InvalidOperationException("Given solution was already added as a potential solution");
|
---|
211 |
|
---|
212 | potentialAssociatedSolutions.Add(s, distance);
|
---|
213 | }
|
---|
214 |
|
---|
215 | public void RemovePotentialAssociatedSolution(Solution s)
|
---|
216 | {
|
---|
217 | potentialAssociatedSolutions.Remove(s);
|
---|
218 | }
|
---|
219 |
|
---|
220 | public bool HasPotentialMember()
|
---|
221 | {
|
---|
222 | return potentialAssociatedSolutions.Any();
|
---|
223 | }
|
---|
224 |
|
---|
225 | internal Solution FindClosestMember()
|
---|
226 | {
|
---|
227 | if (!potentialAssociatedSolutions.Any())
|
---|
228 | throw new InvalidOperationException("No potential members exist");
|
---|
229 |
|
---|
230 | return Utility.ArgMin(pair => pair.Value, potentialAssociatedSolutions).Key;
|
---|
231 | }
|
---|
232 |
|
---|
233 | internal Solution RandomMember()
|
---|
234 | {
|
---|
235 | if (!potentialAssociatedSolutions.Any())
|
---|
236 | throw new InvalidOperationException("No potential members exist");
|
---|
237 |
|
---|
238 | return potentialAssociatedSolutions.Keys.ElementAt(random.Next(potentialAssociatedSolutions.Count));
|
---|
239 | }
|
---|
240 | }
|
---|
241 | } |
---|