Changeset 17661
 Timestamp:
 07/09/20 15:55:03 (4 years ago)
 Location:
 branches/2825NSGA3/HeuristicLab.Algorithms.NSGA3/3.3
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

branches/2825NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/NSGA3.cs
r17657 r17661 144 144 public List<ReferencePoint> ReferencePoints { get; private set; } 145 145 146 // todo: create one property for the Generated Reference Points and one for the current 147 // generations reference points 148 146 149 #endregion Properties 147 150 … … 236 239 { 237 240 // Generate reference points and add them to results 238 int nDiv = 5; // todo: figure out the correct number of divisions 239 ReferencePoints = ReferencePoint.GenerateReferencePoints(random, Problem.Encoding.Length, nDiv); 241 ReferencePoints = ReferencePoint.GenerateReferencePoints(random, Problem.Maximization.Length); 240 242 ResultsGeneratedReferencePoints = Utility.ConvertToDoubleMatrix(ReferencePoints); 241 243 } … … 253 255 protected override void Run(CancellationToken cancellationToken) 254 256 { 255 ReferencePoints = new List<ReferencePoint>(); // todo: use existing list of reference points256 257 while (generation != MaximumGenerations.Value) 257 258 { 258 ToNextGeneration(); 259 // create copies of generated reference points (to preserve the original ones for 260 // the next generation) maybe todo: use cloner? 261 ToNextGeneration(CreateCopyOfReferencePoints()); 259 262 generation++; 260 263 } … … 264 267 265 268 #region Private Methods 269 270 private List<ReferencePoint> CreateCopyOfReferencePoints() 271 { 272 if (ReferencePoints == null) return null; 273 274 List<ReferencePoint> referencePoints = new List<ReferencePoint>(); 275 foreach (var referencePoint in ReferencePoints) 276 referencePoints.Add(new ReferencePoint(referencePoint)); 277 278 return referencePoints; 279 } 266 280 267 281 private void Analyze() … … 287 301 } 288 302 289 private void ToNextGeneration( )303 private void ToNextGeneration(List<ReferencePoint> referencePoints) 290 304 { 291 305 List<Solution> st = new List<Solution>(); … … 320 334 int k = PopulationSize.Value  nextGeneration.Count; 321 335 Normalize(st); 322 Associate( );323 List<Solution> solutionsToAdd = Niching(k );336 Associate(referencePoints); 337 List<Solution> solutionsToAdd = Niching(k, referencePoints); 324 338 nextGeneration = Utility.Concat(nextGeneration, solutionsToAdd); 325 339 } … … 380 394 } 381 395 382 private void Associate( )396 private void Associate(List<ReferencePoint> referencePoints) 383 397 { 384 398 for (int f = 0; f < Fronts.Count; f++) … … 388 402 // find reference point for which the perpendicular distance to the current 389 403 // solution is the lowest 390 var rpAndDist = Utility.MinArgMin(rp => GetPerpendicularDistance(rp.Values, solution.Fitness), ReferencePoints);404 var rpAndDist = Utility.MinArgMin(rp => GetPerpendicularDistance(rp.Values, solution.Fitness), referencePoints); 391 405 // associated reference point 392 406 var arp = rpAndDist.Item1; … … 394 408 var dist = rpAndDist.Item2; 395 409 396 //// todo: delete this397 //int min_rp = 1;398 //double min_dist = double.MaxValue;399 //for (int r = 0; r < referencePoints.Count; r++)400 //{401 // double d = GetPerpendicularDistance(referencePoints[r].Values, solution.Fitness);402 // if (d < min_dist)403 // {404 // min_dist = d;405 // min_rp = r;406 // }407 //}408 410 if (f + 1 != Fronts.Count) 409 411 { … … 420 422 } 421 423 422 private List<Solution> Niching(int k )424 private List<Solution> Niching(int k, List<ReferencePoint> referencePoints) 423 425 { 424 426 List<Solution> solutions = new List<Solution>(); 425 427 while (solutions.Count != k) 426 428 { 427 ReferencePoint min_rp = FindNicheReferencePoint( );429 ReferencePoint min_rp = FindNicheReferencePoint(referencePoints); 428 430 429 431 Solution chosen = SelectClusterMember(min_rp); 430 432 if (chosen == null) 431 433 { 432 ReferencePoints.Remove(min_rp);434 referencePoints.Remove(min_rp); 433 435 } 434 436 else … … 443 445 } 444 446 445 private ReferencePoint FindNicheReferencePoint( )447 private ReferencePoint FindNicheReferencePoint(List<ReferencePoint> referencePoints) 446 448 { 447 449 // the minimum number of associated solutions for a reference point over all reference points 448 int minNumber = Utility.Min(rp => rp.NumberOfAssociatedSolutions, ReferencePoints); 450 int minNumber = Utility.Min(rp => rp.NumberOfAssociatedSolutions, referencePoints); 451 449 452 // the reference points that share the number of associated solutions where that number 450 453 // is equal to minNumber 451 List<ReferencePoint> referencePoints = new List<ReferencePoint>();452 foreach (var referencePoint in ReferencePoints)454 List<ReferencePoint> minAssociatedReferencePoints = new List<ReferencePoint>(); 455 foreach (var referencePoint in referencePoints) 453 456 if (referencePoint.NumberOfAssociatedSolutions == minNumber) 454 referencePoints.Add(referencePoint);455 456 if ( referencePoints.Count > 1)457 return referencePoints[random.Next(referencePoints.Count)];457 minAssociatedReferencePoints.Add(referencePoint); 458 459 if (minAssociatedReferencePoints.Count > 1) 460 return minAssociatedReferencePoints[random.Next(minAssociatedReferencePoints.Count)]; 458 461 else 459 return referencePoints.Single();462 return minAssociatedReferencePoints.Single(); 460 463 } 461 464 
branches/2825NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/ReferencePoint.cs
r17619 r17661 6 6 namespace HeuristicLab.Algorithms.NSGA3 7 7 { 8 /*9 * The method for generating the reference points is based on the NSGA3 implementation in the jMetal framework (http://jmetal.sourceforge.net/).10 * That implementation in return is based on TsungChe Chiang's code11 * http://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm12 */13 14 8 public class ReferencePoint 15 9 { 10 // The potentially associated solutions to this reference point and the distance to that solution 16 11 private readonly Dictionary<Solution, double> potentialAssociatedSolutions = new Dictionary<Solution, double>(); 17 12 18 13 #region Properties 19 14 20 p ublicIRandom random;15 private readonly IRandom random; 21 16 public double[] Values { get; } 22 17 public int NumberOfDimensions => Values.Length; … … 37 32 random = other.random; 38 33 Values = new double[other.NumberOfDimensions]; 39 for (int i = 0; i < other.NumberOfDimensions; i++) 40 Values[i] = other.Values[i]; 34 other.Values.CopyTo(Values, 0); 41 35 } 42 36 … … 45 39 #region Static methods 46 40 47 // todo: use this (for optimization)48 41 /// <summary> 49 /// Returns the number of reference points that are generated by <see 50 /// cref="GenerateReferencePoints(List{ReferencePoint}, int, int)" /> for the given number 51 /// of dimensions and divisions. 42 /// Generate reference points that are evenly distributed over a hyperplane with dimensions 43 /// <paramref name="nDim" />  1 with the sum of the values in all dimensions being equal to 44 /// 1 for each reference point. <paramref name="nDim" /> may only be one of {3, 5, 8, 10, 15} 45 /// > The number of inner divisions and outer divisions are determined based on the 46 /// values provided in the NSGAIII paper, chapter V: Results. If different dimensions are 47 /// given, null is returned. 52 48 /// </summary> 53 /// <param name="nDim">The number of dimensions</param> 54 /// <param name="nDiv">The number of divisions</param> 49 /// <param name="random"> 50 /// The <see cref="IRandom" /> to give as a parameter to the ReferencePoint constructors. 51 /// </param> 52 /// <param name="nDim">The dimensionality of the Reference Points</param> 55 53 /// <returns></returns> 56 internal static int GetNumberOfReferencePoints(int nDim, int nDiv)54 internal static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim) 57 55 { 58 return Utility.NCR(nDim + nDiv  1, nDiv); 56 List<ReferencePoint> referencePoints; 57 switch (nDim) 58 { 59 case 3: 60 referencePoints = GenerateReferencePoints(random, nDim, 12, 0); 61 break; 62 63 case 5: 64 referencePoints = GenerateReferencePoints(random, nDim, 6, 0); 65 break; 66 67 case 8: 68 referencePoints = GenerateReferencePoints(random, nDim, 3, 2); 69 break; 70 71 case 10: 72 referencePoints = GenerateReferencePoints(random, nDim, 3, 2); 73 break; 74 75 case 15: 76 referencePoints = GenerateReferencePoints(random, nDim, 2, 1); 77 break; 78 79 default: 80 referencePoints = null; 81 break; 82 } 83 84 return referencePoints; 59 85 } 60 86 61 // maybe todo: move this to another class? 87 internal static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim, int outerDiv) 88 { 89 return GenerateReferencePoints(random, nDim, outerDiv, 0); 90 } 91 92 /* 93 * This method is based on TsungChe Chiang's NSGAIII implementation (version 1.20) 94 * http://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm 95 */ 96 62 97 /// <summary> 63 98 /// Generate reference points that are evenly distributed over a hyperplane with dimensions … … 65 100 /// 1 for each reference point. 66 101 /// </summary> 67 /// <param name="nDim">The number of dimensions for the reference points</param> 68 /// <param name="nDiv">The number of divisions to use to generate reference points</param> 69 /// <returns>The generated reference points</returns> 70 internal static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim, int nDiv) 102 /// <param name="nDim">The number of dimensions for the reference points.</param> 103 /// <param name="outerDiv">The number of divisions for the outer reference points</param> 104 /// <returns>The generated reference points (Check Fig. 4 in NSGAIII paper).</returns> 105 /// <param name="innerDiv">The number of divisions for the inner reference points</param> 106 /// <returns> 107 /// The generated reference points (Check Fig. 4 in NSGAIII paper). Set to 0, in order to 108 /// not have inner reference points 109 /// </returns> 110 internal static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim, int outerDiv, int innerDiv) 71 111 { 112 if (nDim <= 0) throw new ArgumentException("nDim must be greater than 0"); 113 if (outerDiv <= 1) throw new ArgumentException("outerDiv must be greater than 1"); 114 72 115 List<ReferencePoint> referencePoints = new List<ReferencePoint>(); 73 116 ReferencePoint refPoint = new ReferencePoint(random, nDim); 74 GenerateRecursive(referencePoints, refPoint, nDim, nDiv, nDiv, 0); 117 GenerateRecursive(referencePoints, refPoint, nDim, outerDiv, outerDiv, 0); 118 119 if (innerDiv > 0) 120 { 121 List<ReferencePoint> insideReferencePoints = new List<ReferencePoint>(); 122 GenerateRecursive(insideReferencePoints, refPoint, nDim, innerDiv, innerDiv, 0); 123 124 double center = 1.0 / nDim; 125 126 for (int i = 0; i < insideReferencePoints.Count; i++) 127 { 128 for (int j = 0; j < insideReferencePoints[i].Values.Length; j++) 129 { 130 insideReferencePoints[i].Values[j] = (center + insideReferencePoints[i].Values[j]) / 2; 131 } 132 referencePoints.Add(insideReferencePoints[i]); 133 } 134 } 75 135 76 136 return referencePoints; 77 137 } 138 139 /* 140 * This method is based on TsungChe Chiang's NSGAIII implementation (version 1.20) 141 * http://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm 142 */ 78 143 79 144 private static void GenerateRecursive(List<ReferencePoint> referencePoints, ReferencePoint refPoint, int numberOfObjectives, int left, int total, int element) … … 100 165 { 101 166 if (potentialAssociatedSolutions.ContainsKey(s)) 102 throw new InvalidOperationException(" Attempt to add potential solution to reference point failed: Thatsolution was already added as a potential solution");167 throw new InvalidOperationException("Given solution was already added as a potential solution"); 103 168 104 169 potentialAssociatedSolutions.Add(s, distance);
Note: See TracChangeset
for help on using the changeset viewer.