- Timestamp:
- 08/12/20 23:36:45 (4 years ago)
- Location:
- branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/NSGA3.cs
r17720 r17724 63 63 private List<ReferencePoint> referencePoints; 64 64 65 [Storable] 66 private NSGA3Selection selection; 67 65 68 #endregion Storable fields 66 69 … … 222 225 Parameters.Add(new FixedValueParameter<PercentValue>(CrossoverProbabilityName, "The probability that the crossover operator is applied on two parents.", new PercentValue(1.0))); 223 226 Parameters.Add(new FixedValueParameter<PercentValue>(MutationProbabilityName, "The probability that the mutation operator is applied on a Individual.", new PercentValue(0.05))); 224 Parameters.Add(new FixedValueParameter<BoolValue>(DominateOnEqualQualitiesName, "Flag which determines wether Individuals with equal quality values should be treated as dominated.", new BoolValue( false)));227 Parameters.Add(new FixedValueParameter<BoolValue>(DominateOnEqualQualitiesName, "Flag which determines wether Individuals with equal quality values should be treated as dominated.", new BoolValue(true))); 225 228 Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true))); 226 229 Parameters.Add(new FixedValueParameter<IntValue>(SeedName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0))); … … 241 244 solutions = original.solutions?.Select(cloner.Clone).ToList(); 242 245 referencePoints = original.referencePoints?.Select(cloner.Clone).ToList(); 246 selection = cloner.Clone(original.selection); 243 247 } 244 248 … … 289 293 referencePoints = ReferencePoint.GenerateReferencePoints(random, Objectives); 290 294 ResultsGeneratedReferencePoints = Utility.ConvertToDoubleMatrix(referencePoints); 295 var problem = Problem as MultiObjectiveTestFunctionProblem; 296 297 selection = new NSGA3Selection(problem.Objectives, problem.Maximization, PopulationSize.Value, random, DominateOnEqualQualities.Value); 291 298 } 292 299 … … 328 335 List<Solution> rt = Utility.Concat(solutions, qt); 329 336 330 solutions = NSGA3Selection.SelectSolutionsForNextGeneration(rt, GetCopyOfReferencePoints(), Problem.Maximization, PopulationSize.Value, random);337 solutions = selection.SelectSolutionsForNextGeneration(rt, GetCopyOfReferencePoints()); 331 338 332 339 if (AnalyzeEveryGeneration.Value) … … 359 366 if (referencePoints == null) return null; 360 367 361 return referencePoints.Select(rp => (ReferencePoint)rp.Clone()).ToList();368 return referencePoints.Select(rp => new ReferencePoint(rp)).ToList(); 362 369 } 363 370 … … 377 384 ResultsHypervolume = new DoubleValue(Hypervolume.Calculate(front, problem.ReferencePoint.CloneAsArray(), problem.Maximization)); 378 385 ResultsDifferenceToBestKnownHypervolume = new DoubleValue(ResultsBestKnownHypervolume.Value - ResultsHypervolume.Value); 386 387 Problem.Analyze( 388 solutions.Select(s => (Individual)new SingleEncodingIndividual(Problem.Encoding, new Scope { Variables = { new Variable(Problem.Encoding.Name, s.Chromosome) } })).ToArray(), 389 solutions.Select(s => s.Fitness).ToArray(), 390 Results, 391 random); 379 392 } 380 393 … … 393 406 private List<Solution> Recombine(List<Solution> solutions) 394 407 { 408 //List<Solution> childSolutions = new List<Solution>(); 409 //for (int i = 0; i < solutions.Count; i++) 410 //{ 411 // var parent1 = solutions[random.Next(solutions.Count)]; 412 // var parent2 = solutions[random.Next(solutions.Count)]; 413 // var childChromosome = HeuristicLab.Encodings.RealVectorEncoding.SimulatedBinaryCrossover.Apply(random, parent1.Chromosome, parent2.Chromosome, new DoubleValue(5)); 414 415 // BoundsChecker.Apply(childChromosome, Problem.Encoding.Bounds); 416 417 // Solution child = new Solution(childChromosome); 418 // childSolutions.Add(child); 419 //} 420 421 //return childSolutions; 422 395 423 List<Solution> childSolutions = new List<Solution>(); 396 for (int i = 0; i < solutions.Count; i++) 397 { 398 var parent1 = solutions[random.Next(solutions.Count)]; 399 var parent2 = solutions[random.Next(solutions.Count)]; 400 var childChromosome = HeuristicLab.Encodings.RealVectorEncoding.SimulatedBinaryCrossover.Apply(random, parent1.Chromosome, parent2.Chromosome, new DoubleValue(5)); 401 402 BoundsChecker.Apply(childChromosome, Problem.Encoding.Bounds); 403 404 Solution child = new Solution(childChromosome); 405 childSolutions.Add(child); 424 425 for (int i = 0; i < solutions.Count; i += 2) 426 { 427 int parentIndex1 = random.Next(solutions.Count); 428 int parentIndex2 = random.Next(solutions.Count); 429 // ensure that the parents are not the same object 430 if (parentIndex1 == parentIndex2) parentIndex2 = (parentIndex2 + 1) % solutions.Count; 431 var parent1 = solutions[parentIndex1]; 432 var parent2 = solutions[parentIndex2]; 433 434 // Do crossover with crossoverProbabilty == 1 in order to guarantee that a crossover happens 435 var children = SimulatedBinaryCrossover.Apply(random, 436 Problem.Encoding.Bounds, parent1.Chromosome, parent2.Chromosome, CrossoverProbability.Value); 437 438 childSolutions.Add(new Solution(children.Item1)); 439 childSolutions.Add(new Solution(children.Item2)); 406 440 } 407 441 408 442 return childSolutions; 409 410 //List<Solution> childSolutions = new List<Solution>();411 412 //for (int i = 0; i < solutions.Count; i += 2)413 //{414 // int parentIndex1 = random.Next(solutions.Count);415 // int parentIndex2 = random.Next(solutions.Count);416 // // ensure that the parents are not the same object417 // if (parentIndex1 == parentIndex2) parentIndex2 = (parentIndex2 + 1) % solutions.Count;418 // var parent1 = solutions[parentIndex1];419 // var parent2 = solutions[parentIndex2];420 421 // // Do crossover with crossoverProbabilty == 1 in order to guarantee that a crossover422 // happens var children = SimulatedBinaryCrossover.Apply(random,423 // Problem.Encoding.Bounds, parent1.Chromosome, parent2.Chromosome, CrossoverProbability.Value);424 425 // childSolutions.Add(new Solution(children.Item1));426 // childSolutions.Add(new Solution(children.Item2));427 //}428 429 //return childSolutions;430 443 } 431 444 -
branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/NSGA3Selection.cs
r17720 r17724 2 2 using System.Collections.Generic; 3 3 using System.Linq; 4 using HEAL.Attic; 5 using HeuristicLab.Common; 4 6 using HeuristicLab.Core; 5 7 using HeuristicLab.Optimization; … … 7 9 namespace HeuristicLab.Algorithms.NSGA3 8 10 { 9 public static class NSGA3Selection 11 [StorableType("53158EA5-4D1C-42DB-90F5-EC555EC0A450")] 12 public class NSGA3Selection : IDeepCloneable 10 13 { 11 14 private const double EPSILON = 10e-6; // a tiny number that is greater than 0 15 16 [Storable] 17 private int numberOfObjectives; 18 19 [Storable] 20 private bool[] maximization; 21 22 [Storable] 23 private int populationSize; 24 25 [Storable] 26 private IRandom random; 27 28 [Storable] 29 private bool dominateOnEqualQualities; 30 31 [StorableConstructor] 32 public NSGA3Selection(StorableConstructorFlag _) { } 33 34 public NSGA3Selection(int numberOfObjectives, bool[] maximization, int populationSize, IRandom random, bool dominateOnEqualQualities) 35 { 36 if (maximization == null) throw new ArgumentNullException(nameof(maximization)); 37 if (random == null) throw new ArgumentNullException(nameof(random)); 38 if (numberOfObjectives != maximization.Length) throw new ArgumentException($"{nameof(numberOfObjectives)} and the length of {nameof(maximization)} do not match."); 39 if (populationSize < 1) throw new ArgumentOutOfRangeException($"{nameof(populationSize)} has to be >= 1."); 40 41 this.numberOfObjectives = numberOfObjectives; 42 this.maximization = maximization; 43 this.populationSize = populationSize; 44 this.random = random; 45 this.dominateOnEqualQualities = dominateOnEqualQualities; 46 } 47 48 public NSGA3Selection(NSGA3Selection other, Cloner cloner) 49 { 50 numberOfObjectives = other.numberOfObjectives; 51 maximization = new bool[other.maximization.Length]; 52 Array.Copy(other.maximization, maximization, maximization.Length); 53 populationSize = other.populationSize; 54 random = cloner.Clone(other.random); 55 dominateOnEqualQualities = other.dominateOnEqualQualities; 56 } 57 58 public IDeepCloneable Clone(Cloner cloner) 59 { 60 return new NSGA3Selection(this, cloner); 61 } 62 63 public object Clone() 64 { 65 return new Cloner().Clone(this); 66 } 12 67 13 68 /// <summary> … … 17 72 /// <param name="rt">The previous generation and its mutated children.</param> 18 73 /// <param name="referencePoints"></param> 19 /// <param name="maximization"></param>20 /// <param name="N">Number of solutions to select.</param>21 /// <param name="random">The <see cref="IRandom" /> to use for randomness.</param>22 74 /// <returns></returns> 23 public static List<Solution> SelectSolutionsForNextGeneration(List<Solution> rt, List<ReferencePoint> referencePoints, bool[] maximization, int N, IRandom random) 24 { 25 int numberOfObjectives = rt.First().Fitness.Length; 75 public List<Solution> SelectSolutionsForNextGeneration(List<Solution> rt, List<ReferencePoint> referencePoints) 76 { 26 77 List<Solution> st = new List<Solution>(); 27 78 … … 30 81 31 82 // compute the pareto fronts using the DominationCalculator 32 var fronts = DominationCalculator<Solution>.CalculateAllParetoFronts(rt.ToArray(), qualities, maximization, out int[] rank, true)83 List<List<Solution>> fronts = DominationCalculator<Solution>.CalculateAllParetoFronts(rt.ToArray(), qualities, maximization, out int[] rank, dominateOnEqualQualities) 33 84 .Select(list => new List<Solution>(list.Select(pair => pair.Item1))).ToList(); 34 85 35 86 int lf = -1; // last front to be included 36 for (int i = 0; i < fronts.Count && st.Count < N; i++)87 for (int i = 0; i < fronts.Count && st.Count < populationSize; i++) 37 88 { 38 89 st = Utility.Concat(st, fronts[i]); … … 43 94 44 95 List<Solution> nextGeneration = new List<Solution>(); 45 if (st.Count == N) // no special selection needs to be done96 if (st.Count == populationSize) // no special selection needs to be done 46 97 nextGeneration = st; 47 98 else … … 51 102 for (int f = 0; f < lf; f++) 52 103 nextGeneration = Utility.Concat(nextGeneration, fronts[f]); 53 int k = N- nextGeneration.Count;54 Normalize( st, numberOfObjectives);104 int k = populationSize - nextGeneration.Count; 105 Normalize(rt, fronts); 55 106 Associate(fronts, referencePoints); 56 107 List<Solution> solutionsToAdd = Niching(k, referencePoints, random); … … 61 112 } 62 113 63 private static void Normalize(List<Solution> st, int numberOfObjectives)114 private void Normalize(List<Solution> solutions, List<List<Solution>> fronts) 64 115 { 65 116 // Find the ideal point 66 117 double[] idealPoint = new double[numberOfObjectives]; 67 118 68 foreach (var solution in s t)119 foreach (var solution in solutions) 69 120 solution.ConvertedFitness = new double[numberOfObjectives]; 70 121 … … 72 123 { 73 124 // Compute ideal point 74 idealPoint[j] = Utility.Min(s => s.Fitness[j], st); 125 // todo: search only in first front 126 idealPoint[j] = Utility.Min(s => s.Fitness[j], solutions); 127 var x = Utility.Min(s => s.Fitness[j], fronts.First()); 128 if (Math.Abs(idealPoint[j] - x) > 10e-5) throw new Exception("idealPoint value is not in first front"); 75 129 76 130 // Translate objectives and save the modified fitness values in ConvertedFitness 77 foreach (var solution in s t)131 foreach (var solution in solutions) 78 132 solution.ConvertedFitness[j] = solution.Fitness[j] - idealPoint[j]; 79 133 } 80 134 81 135 // Find the extreme points 82 Solution[] extremePoints = new Solution[numberOfObjectives];136 List<Solution> extremePoints = new List<Solution>(numberOfObjectives); 83 137 for (int j = 0; j < numberOfObjectives; j++) 84 138 { … … 88 142 weights[j] = 1; 89 143 90 extremePoints[j] = Utility.ArgMin(s => ASF(s.ConvertedFitness, weights), st); 144 var extremePoint = Utility.ArgMin(s => ASF(s.ConvertedFitness, weights), solutions); 145 extremePoints.Add(extremePoint); 91 146 } 92 147 93 148 // Compute intercepts 94 List<double> intercepts = GetIntercepts(extremePoints.ToList());149 double[] intercepts = GetIntercepts(extremePoints, solutions); 95 150 96 151 // Normalize objectives 97 NormalizeObjectives(st, intercepts, idealPoint); 98 } 99 100 private static void NormalizeObjectives(List<Solution> st, List<double> intercepts, double[] idealPoint) 101 { 102 int numberOfObjectives = st.First().Fitness.Length; 103 104 foreach (var solution in st) 152 NormalizeObjectives(solutions, intercepts, idealPoint); 153 } 154 155 private void NormalizeObjectives(List<Solution> solutions, double[] intercepts, double[] idealPoint) 156 { 157 foreach (var solution in solutions) 105 158 { 106 159 for (int i = 0; i < numberOfObjectives; i++) 107 160 { 108 if (Math.Abs(intercepts[i] - idealPoint[i]) > EPSILON) 109 { 110 solution.ConvertedFitness[i] = solution.ConvertedFitness[i] / (intercepts[i] - idealPoint[i]); 161 // if (Math.Abs(intercepts[i] - idealPoints[i]) > EPSILON) 162 if (Math.Abs(intercepts[i]) > EPSILON) 163 { 164 //solution.ConvertedFitness[i] = solution.ConvertedFitness[i] / (intercepts[i] - idealPoint[i]); 111 165 // todo: try this 112 //solution.ConvertedFitness[i] = solution.ConvertedFitness[i] / intercepts[i];166 solution.ConvertedFitness[i] = solution.ConvertedFitness[i] / intercepts[i]; 113 167 } 114 168 else … … 120 174 } 121 175 122 private staticvoid Associate(List<List<Solution>> fronts, List<ReferencePoint> referencePoints)176 private void Associate(List<List<Solution>> fronts, List<ReferencePoint> referencePoints) 123 177 { 124 178 for (int f = 0; f < fronts.Count; f++) … … 148 202 } 149 203 150 private staticList<Solution> Niching(int k, List<ReferencePoint> referencePoints, IRandom random)204 private List<Solution> Niching(int k, List<ReferencePoint> referencePoints, IRandom random) 151 205 { 152 206 List<Solution> solutions = new List<Solution>(); … … 171 225 } 172 226 173 private staticReferencePoint FindNicheReferencePoint(List<ReferencePoint> referencePoints, IRandom random)227 private ReferencePoint FindNicheReferencePoint(List<ReferencePoint> referencePoints, IRandom random) 174 228 { 175 229 // the minimum number of associated solutions for a reference point over all reference points 176 230 int minNumber = Utility.Min(rp => rp.NumberOfAssociatedSolutions, referencePoints); 231 232 // todo: try this instead of the current implementation 233 //var min_rps = new List<ReferencePoint>(referencePoints.Where(r => r.NumberOfAssociatedSolutions == minNumber)); 234 //if (min_rps.Count == 0) return min_rps.Single(); 235 //else return min_rps[random.Next(min_rps.Count)]; 177 236 178 237 // the reference points that share the number of associated solutions where that number … … 189 248 } 190 249 191 private staticSolution SelectClusterMember(ReferencePoint referencePoint)250 private Solution SelectClusterMember(ReferencePoint referencePoint) 192 251 { 193 252 Solution chosen = null; … … 202 261 } 203 262 204 private staticdouble GetPerpendicularDistance(double[] values, double[] fitness)263 private double GetPerpendicularDistance(double[] values, double[] fitness) 205 264 { 206 265 double numerator = 0; … … 221 280 } 222 281 223 private static double ASF(double[] x, double[] weight) 224 { 225 int numberOfObjectives = x.Length; 282 private double ASF(double[] x, double[] weight) 283 { 226 284 List<int> dimensions = new List<int>(); 227 285 for (int i = 0; i < numberOfObjectives; i++) … … 231 289 } 232 290 233 private static List<double> GetIntercepts(List<Solution> extremePoints) 234 { 235 int numberOfObjectives = extremePoints.First().Fitness.Length; 236 291 private double[] GetIntercepts(List<Solution> extremePoints, List<Solution> solutions) 292 { 237 293 // Check whether there are duplicate extreme points. This might happen but the original 238 294 // paper does not mention how to deal with it. … … 246 302 } 247 303 248 List<double> intercepts = new List<double>(); 249 250 // todo: do handling of this case as in Tsung Che Chiang's implementation 251 if (duplicate) 252 { // cannot construct the unique hyperplane (this is a casual method to deal with the condition) 304 double[] intercepts = new double[numberOfObjectives]; 305 306 bool negative_intercept = false; 307 if (!duplicate) 308 { 309 // Find the equation of the hyperplane 310 List<double> b = new List<double>(numberOfObjectives); 311 for (int i = 0; i < numberOfObjectives; i++) 312 b.Add(1.0); 313 314 List<List<double>> a = new List<List<double>>(extremePoints.Count); 315 316 for (int i = 0; i < extremePoints.Count; i++) 317 { 318 List<double> convertedFitness = new List<double>(extremePoints[i].ConvertedFitness); 319 a.Add(convertedFitness); 320 } 321 List<double> x = GaussianElimination(a, b); 322 323 // Find intercepts 324 for (int i = 0; i < intercepts.Length; i++) 325 { 326 intercepts[i] = 1.0 / x[i]; 327 328 if (x[i] < 0) 329 { 330 negative_intercept = true; 331 break; 332 } 333 } 334 } 335 336 // follow the method in Yuan et al. (GECCO 2015) 337 if (duplicate || negative_intercept) 338 { 339 double[] maxObjectives = FindMaxObjectives(solutions); 340 for (int i = 0; i < intercepts.Length; i++) 341 intercepts[i] = maxObjectives[i]; 342 } 343 344 return intercepts; 345 } 346 347 private double[] FindMaxObjectives(List<Solution> solutions) 348 { 349 double[] maxPoint = new double[numberOfObjectives]; 350 for (int i = 0; i < maxPoint.Length; i++) maxPoint[i] = double.MinValue; 351 352 foreach (var solution in solutions) 353 { 253 354 for (int f = 0; f < numberOfObjectives; f++) 254 355 { 255 // extreme_points[f] stands for the individual with the largest value of 256 // objective f 257 intercepts.Add(extremePoints[f].ConvertedFitness[f]); 258 } 259 } 260 else 261 { 262 // Find the equation of the hyperplane 263 List<double> b = new List<double>(); //(pop[0].objs().size(), 1.0); 264 for (int i = 0; i < numberOfObjectives; i++) 265 { 266 b.Add(1.0); 267 } 268 269 List<List<double>> a = extremePoints.Select(p => p.ConvertedFitness.ToList()).ToList(); 270 271 List<double> x = GaussianElimination(a, b); 272 273 // Find intercepts 274 for (int f = 0; f < numberOfObjectives; f++) 275 { 276 intercepts.Add(1.0 / x[f]); 277 } 278 } 279 280 return intercepts; 281 } 282 283 private static List<double> GaussianElimination(List<List<double>> a, List<double> b) 356 maxPoint[f] = Math.Max(maxPoint[f], solution.ConvertedFitness[f]); 357 } 358 } 359 360 return maxPoint; 361 } 362 363 private List<double> GaussianElimination(List<List<double>> a, List<double> b) 284 364 { 285 365 List<double> x = new List<double>(); -
branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/ReferencePoint.cs
r17719 r17724 25 25 public int NumberOfAssociatedSolutions { get; set; } = 0; 26 26 27 public int Objectives => Values.Length;28 29 27 #endregion Properties 30 28 … … 32 30 33 31 [StorableConstructor] 34 public ReferencePoint(StorableConstructorFlag _) 35 { 36 } 32 public ReferencePoint(StorableConstructorFlag _) { } 37 33 38 34 public ReferencePoint(IRandom random, int obj) … … 45 41 { 46 42 random = cloner.Clone(other.random); 47 Values = new double[other.Objectives]; 48 other.Values.CopyTo(Values, 0); 43 Values = new double[other.Values.Length]; 44 Array.Copy(other.Values, Values, Values.Length); 45 } 46 47 public ReferencePoint(ReferencePoint other) 48 { 49 random = other.random; 50 Values = new double[other.Values.Length]; 51 Array.Copy(other.Values, Values, Values.Length); 49 52 } 50 53 -
branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/Solution.cs
r17719 r17724 22 22 23 23 [StorableConstructor] 24 public Solution(StorableConstructorFlag _) 25 { 26 } 24 public Solution(StorableConstructorFlag _) { } 27 25 28 26 public Solution(RealVector chromosome) -
branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/Utility.cs
r17720 r17724 114 114 { 115 115 if (referencePoints == null || !referencePoints.Any()) throw new ArgumentException($"{nameof(referencePoints)} is null or empty"); 116 int obj = referencePoints.First(). Objectives;116 int obj = referencePoints.First().Values.Length; 117 117 int pointCount = referencePoints.Count; 118 118 double[,] array = new double[pointCount, obj];
Note: See TracChangeset
for help on using the changeset viewer.