[17619] | 1 | using System;
|
---|
| 2 | using System.Collections.Generic;
|
---|
| 3 | using System.Linq;
|
---|
[17688] | 4 | using HeuristicLab.Common;
|
---|
[17619] | 5 | using HeuristicLab.Core;
|
---|
[17558] | 6 |
|
---|
| 7 | namespace HeuristicLab.Algorithms.NSGA3
|
---|
| 8 | {
|
---|
[17688] | 9 | public class ReferencePoint : IDeepCloneable
|
---|
[17558] | 10 | {
|
---|
[17688] | 11 | #region Properties
|
---|
| 12 |
|
---|
[17661] | 13 | // The potentially associated solutions to this reference point and the distance to that solution
|
---|
[17619] | 14 | private readonly Dictionary<Solution, double> potentialAssociatedSolutions = new Dictionary<Solution, double>();
|
---|
| 15 |
|
---|
[17688] | 16 | private readonly IRandom random;
|
---|
[17615] | 17 |
|
---|
| 18 | public double[] Values { get; }
|
---|
| 19 | public int NumberOfDimensions => Values.Length;
|
---|
[17619] | 20 | public int NumberOfAssociatedSolutions { get; set; } = 0;
|
---|
[17615] | 21 |
|
---|
| 22 | #endregion Properties
|
---|
| 23 |
|
---|
[17617] | 24 | #region Constructors
|
---|
| 25 |
|
---|
[17619] | 26 | public ReferencePoint(IRandom random, int numberOfDimensions)
|
---|
[17558] | 27 | {
|
---|
[17619] | 28 | this.random = random;
|
---|
[17615] | 29 | Values = new double[numberOfDimensions];
|
---|
[17558] | 30 | }
|
---|
| 31 |
|
---|
[17688] | 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 |
|
---|
[17617] | 49 | #endregion Constructors
|
---|
[17558] | 50 |
|
---|
[17619] | 51 | #region Static methods
|
---|
| 52 |
|
---|
[17558] | 53 | /// <summary>
|
---|
[17663] | 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>
|
---|
[17667] | 59 | public static int GetNumberOfGeneratedReferencePoints(int nDim)
|
---|
[17663] | 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 |
|
---|
[17669] | 94 | return GetNumberOfGeneratedReferencePoints(nDim, outerDiv, innerDiv);
|
---|
[17663] | 95 | }
|
---|
| 96 |
|
---|
[17667] | 97 | public static int GetNumberOfGeneratedReferencePoints(int nDim, int outerDiv, int innerDiv = 0)
|
---|
[17663] | 98 | {
|
---|
[17667] | 99 | int outerPoints = Utility.NCR(nDim + outerDiv - 1, outerDiv);
|
---|
| 100 | int innerPoints = innerDiv == 0 ? 0 : Utility.NCR(nDim + innerDiv - 1, innerDiv);
|
---|
[17668] | 101 | return outerPoints + innerPoints;
|
---|
[17663] | 102 | }
|
---|
| 103 |
|
---|
[17693] | 104 | public static int GetPopulationSizeForReferencePoints(int referencePoints)
|
---|
| 105 | {
|
---|
| 106 | return (referencePoints + 3) / 4 * 4;
|
---|
| 107 | }
|
---|
| 108 |
|
---|
[17663] | 109 | /// <summary>
|
---|
[17661] | 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
|
---|
[17663] | 115 | /// given, a NotSupportedException is thrown.
|
---|
[17558] | 116 | /// </summary>
|
---|
[17661] | 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>
|
---|
[17558] | 121 | /// <returns></returns>
|
---|
[17667] | 122 | public static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim)
|
---|
[17558] | 123 | {
|
---|
[17661] | 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:
|
---|
[17663] | 148 | throw new NotSupportedException("Only the reference points for 3, 5, 8, 10 or 15 dimensions can be created.");
|
---|
[17661] | 149 | }
|
---|
| 150 |
|
---|
| 151 | return referencePoints;
|
---|
[17558] | 152 | }
|
---|
| 153 |
|
---|
[17661] | 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 |
|
---|
[17558] | 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>
|
---|
[17661] | 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>
|
---|
[17667] | 172 | public static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim, int outerDiv, int innerDiv = 0)
|
---|
[17558] | 173 | {
|
---|
[17661] | 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 |
|
---|
[17558] | 177 | List<ReferencePoint> referencePoints = new List<ReferencePoint>();
|
---|
[17619] | 178 | ReferencePoint refPoint = new ReferencePoint(random, nDim);
|
---|
[17661] | 179 | GenerateRecursive(referencePoints, refPoint, nDim, outerDiv, outerDiv, 0);
|
---|
[17558] | 180 |
|
---|
[17661] | 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 |
|
---|
[17558] | 198 | return referencePoints;
|
---|
| 199 | }
|
---|
| 200 |
|
---|
[17661] | 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 |
|
---|
[17558] | 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;
|
---|
[17700] | 211 | var newRefPoint = (ReferencePoint)refPoint.Clone();
|
---|
[17558] | 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 | }
|
---|
[17619] | 223 |
|
---|
| 224 | #endregion Static methods
|
---|
| 225 |
|
---|
| 226 | public void AddPotentialAssociatedSolution(Solution s, double distance)
|
---|
| 227 | {
|
---|
| 228 | if (potentialAssociatedSolutions.ContainsKey(s))
|
---|
[17661] | 229 | throw new InvalidOperationException("Given solution was already added as a potential solution");
|
---|
[17619] | 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 | }
|
---|
[17558] | 259 | }
|
---|
| 260 | } |
---|