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