Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/13/20 00:08:32 (4 years ago)
Author:
dleko
Message:

#2825 Refactoring: Move selection logic to its own static class.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/NSGA3.cs

    r17664 r17665  
    2626    public class NSGA3 : BasicAlgorithm
    2727    {
    28         private const double EPSILON = 10e-6; // a tiny number that is greater than 0
    29 
    3028        public override bool SupportsPause => false;
    3129
     
    5351
    5452        [Storable]
    55         private List<Solution> solutions;
     53        private List<Solution> solutions; // maybe todo: rename to nextGeneration (see Run method)
    5654
    5755        #endregion Storable fields
     
    266264                // create copies of generated reference points (to preserve the original ones for
    267265                // the next generation) maybe todo: use cloner?
    268                 ToNextGeneration(CreateCopyOfReferencePoints());
     266                //ToNextGeneration(CreateCopyOfReferencePoints());
     267
     268                List<Solution> qt = Mutate(Recombine(solutions));
     269                List<Solution> rt = Utility.Concat(solutions, qt);
     270
     271                solutions = NSGA3Selection.SelectSolutionsForNextGeneration(rt, GetCopyOfReferencePoints(), Problem.Maximization, random);
     272
    269273                ResultsCurrentGeneration.Value++;
    270274            }
     
    275279        #region Private Methods
    276280
    277         private List<ReferencePoint> CreateCopyOfReferencePoints()
     281        private List<ReferencePoint> GetCopyOfReferencePoints()
    278282        {
    279283            if (ReferencePoints == null) return null;
     
    306310        {
    307311            return Problem.Evaluate(new SingleEncodingIndividual(Problem.Encoding, new Scope { Variables = { new Variable(Problem.Encoding.Name, chromosome) } }), random);
    308         }
    309 
    310         private void ToNextGeneration(List<ReferencePoint> referencePoints)
    311         {
    312             List<Solution> st = new List<Solution>();
    313             List<Solution> qt = Mutate(Recombine(solutions));
    314             List<Solution> rt = Utility.Concat(solutions, qt);
    315             List<Solution> nextGeneration;
    316 
    317             // Do non-dominated sort
    318             var qualities = Utility.ToFitnessMatrix(rt);
    319             // compute the pareto fronts using the DominationCalculator and discard the qualities
    320             // part in the inner tuples
    321             Fronts = DominationCalculator<Solution>.CalculateAllParetoFronts(rt.ToArray(), qualities, Problem.Maximization, out int[] rank, true)
    322                 .Select(list => new List<Solution>(list.Select(pair => pair.Item1))).ToList();
    323 
    324             int i = 0;
    325             List<Solution> lf = null; // last front to be included
    326             while (i < Fronts.Count && st.Count < PopulationSize.Value)
    327             {
    328                 lf = Fronts[i];
    329                 st = Utility.Concat(st, lf);
    330                 i++;
    331             }
    332 
    333             if (st.Count == PopulationSize.Value) // no selection needs to be done
    334                 nextGeneration = st;
    335             else
    336             {
    337                 int l = i - 1;
    338                 nextGeneration = new List<Solution>();
    339                 for (int f = 0; f < l; f++)
    340                     nextGeneration = Utility.Concat(nextGeneration, Fronts[f]);
    341                 int k = PopulationSize.Value - nextGeneration.Count;
    342                 Normalize(st);
    343                 Associate(referencePoints);
    344                 List<Solution> solutionsToAdd = Niching(k, referencePoints);
    345                 nextGeneration = Utility.Concat(nextGeneration, solutionsToAdd);
    346             }
    347         }
    348 
    349         private void Normalize(List<Solution> population)
    350         {
    351             // Find the ideal point
    352             double[] idealPoint = new double[NumberOfObjectives];
    353             for (int j = 0; j < NumberOfObjectives; j++)
    354             {
    355                 // Compute ideal point
    356                 idealPoint[j] = Utility.Min(s => s.Fitness[j], population);
    357 
    358                 // Translate objectives
    359                 foreach (var solution in population)
    360                     solution.Fitness[j] -= idealPoint[j];
    361             }
    362 
    363             // Find the extreme points
    364             Solution[] extremePoints = new Solution[NumberOfObjectives];
    365             for (int j = 0; j < NumberOfObjectives; j++)
    366             {
    367                 // Compute extreme points
    368                 double[] weights = new double[NumberOfObjectives];
    369                 for (int i = 0; i < NumberOfObjectives; i++) weights[i] = EPSILON;
    370                 weights[j] = 1;
    371                 double func(Solution s) => ASF(s.Fitness, weights);
    372                 extremePoints[j] = Utility.ArgMin(func, population);
    373             }
    374 
    375             // Compute intercepts
    376             List<double> intercepts = GetIntercepts(extremePoints.ToList());
    377 
    378             // Normalize objectives
    379             NormalizeObjectives(intercepts, idealPoint);
    380         }
    381 
    382         private void NormalizeObjectives(List<double> intercepts, double[] idealPoint)
    383         {
    384             for (int f = 0; f < Fronts.Count; f++)
    385             {
    386                 foreach (var solution in Fronts[f])
    387                 {
    388                     for (int i = 0; i < NumberOfObjectives; i++)
    389                     {
    390                         if (Math.Abs(intercepts[i] - idealPoint[i]) > EPSILON)
    391                         {
    392                             solution.Fitness[i] = solution.Fitness[i] / (intercepts[i] - idealPoint[i]);
    393                         }
    394                         else
    395                         {
    396                             solution.Fitness[i] = solution.Fitness[i] / EPSILON;
    397                         }
    398                     }
    399                 }
    400             }
    401         }
    402 
    403         private void Associate(List<ReferencePoint> referencePoints)
    404         {
    405             for (int f = 0; f < Fronts.Count; f++)
    406             {
    407                 foreach (var solution in Fronts[f])
    408                 {
    409                     // find reference point for which the perpendicular distance to the current
    410                     // solution is the lowest
    411                     var rpAndDist = Utility.MinArgMin(rp => GetPerpendicularDistance(rp.Values, solution.Fitness), referencePoints);
    412                     // associated reference point
    413                     var arp = rpAndDist.Item1;
    414                     // distance to that reference point
    415                     var dist = rpAndDist.Item2;
    416 
    417                     if (f + 1 != Fronts.Count)
    418                     {
    419                         // Todo: Add member for reference point on index min_rp
    420                         arp.NumberOfAssociatedSolutions++;
    421                     }
    422                     else
    423                     {
    424                         // Todo: Add potential member for reference point on index min_rp
    425                         arp.AddPotentialAssociatedSolution(solution, dist);
    426                     }
    427                 }
    428             }
    429         }
    430 
    431         private List<Solution> Niching(int k, List<ReferencePoint> referencePoints)
    432         {
    433             List<Solution> solutions = new List<Solution>();
    434             while (solutions.Count != k)
    435             {
    436                 ReferencePoint min_rp = FindNicheReferencePoint(referencePoints);
    437 
    438                 Solution chosen = SelectClusterMember(min_rp);
    439                 if (chosen == null)
    440                 {
    441                     referencePoints.Remove(min_rp);
    442                 }
    443                 else
    444                 {
    445                     min_rp.NumberOfAssociatedSolutions++;
    446                     min_rp.RemovePotentialAssociatedSolution(chosen);
    447                     solutions.Add(chosen);
    448                 }
    449             }
    450 
    451             return solutions;
    452         }
    453 
    454         private ReferencePoint FindNicheReferencePoint(List<ReferencePoint> referencePoints)
    455         {
    456             // the minimum number of associated solutions for a reference point over all reference points
    457             int minNumber = Utility.Min(rp => rp.NumberOfAssociatedSolutions, referencePoints);
    458 
    459             // the reference points that share the number of associated solutions where that number
    460             // is equal to minNumber
    461             List<ReferencePoint> minAssociatedReferencePoints = new List<ReferencePoint>();
    462             foreach (var referencePoint in referencePoints)
    463                 if (referencePoint.NumberOfAssociatedSolutions == minNumber)
    464                     minAssociatedReferencePoints.Add(referencePoint);
    465 
    466             if (minAssociatedReferencePoints.Count > 1)
    467                 return minAssociatedReferencePoints[random.Next(minAssociatedReferencePoints.Count)];
    468             else
    469                 return minAssociatedReferencePoints.Single();
    470         }
    471 
    472         private Solution SelectClusterMember(ReferencePoint referencePoint)
    473         {
    474             Solution chosen = null;
    475             if (referencePoint.HasPotentialMember())
    476             {
    477                 if (referencePoint.NumberOfAssociatedSolutions == 0)
    478                     chosen = referencePoint.FindClosestMember();
    479                 else
    480                     chosen = referencePoint.RandomMember();
    481             }
    482             return chosen;
    483         }
    484 
    485         private double GetPerpendicularDistance(double[] values, double[] fitness)
    486         {
    487             double numerator = 0;
    488             double denominator = 0;
    489             for (int i = 0; i < values.Length; i++)
    490             {
    491                 numerator += values[i] * fitness[i];
    492                 denominator += Math.Pow(values[i], 2);
    493             }
    494             double k = numerator / denominator;
    495 
    496             double d = 0;
    497             for (int i = 0; i < values.Length; i++)
    498             {
    499                 d += Math.Pow(k * values[i] - fitness[i], 2);
    500             }
    501             return Math.Sqrt(d);
    502         }
    503 
    504         private double ASF(double[] x, double[] weight)
    505         {
    506             List<int> dimensions = new List<int>();
    507             for (int i = 0; i < NumberOfObjectives; i++) dimensions.Add(i);
    508             double f(int dim) => x[dim] / weight[dim];
    509             return Utility.Max(f, dimensions);
    510         }
    511 
    512         private List<double> GetIntercepts(List<Solution> extremePoints)
    513         {
    514             // Check whether there are duplicate extreme points. This might happen but the original
    515             // paper does not mention how to deal with it.
    516             bool duplicate = false;
    517             for (int i = 0; !duplicate && i < extremePoints.Count; i++)
    518             {
    519                 for (int j = i + 1; !duplicate && j < extremePoints.Count; j++)
    520                 {
    521                     // maybe todo: override Equals method of solution?
    522                     duplicate = extremePoints[i].Equals(extremePoints[j]);
    523                 }
    524             }
    525 
    526             List<double> intercepts = new List<double>();
    527 
    528             if (duplicate)
    529             { // cannot construct the unique hyperplane (this is a casual method to deal with the condition)
    530                 for (int f = 0; f < NumberOfObjectives; f++)
    531                 {
    532                     // extreme_points[f] stands for the individual with the largest value of
    533                     // objective f
    534                     intercepts.Add(extremePoints[f].Fitness[f]);
    535                 }
    536             }
    537             else
    538             {
    539                 // Find the equation of the hyperplane
    540                 List<double> b = new List<double>(); //(pop[0].objs().size(), 1.0);
    541                 for (int i = 0; i < NumberOfObjectives; i++)
    542                 {
    543                     b.Add(1.0);
    544                 }
    545 
    546                 List<List<double>> a = new List<List<double>>();
    547                 foreach (Solution s in extremePoints)
    548                 {
    549                     List<double> aux = new List<double>();
    550                     for (int i = 0; i < NumberOfObjectives; i++)
    551                         aux.Add(s.Fitness[i]);
    552                     a.Add(aux);
    553                 }
    554                 List<double> x = GaussianElimination(a, b);
    555 
    556                 // Find intercepts
    557                 for (int f = 0; f < NumberOfObjectives; f++)
    558                 {
    559                     intercepts.Add(1.0 / x[f]);
    560                 }
    561             }
    562 
    563             return intercepts;
    564         }
    565 
    566         private List<double> GaussianElimination(List<List<double>> a, List<double> b)
    567         {
    568             List<double> x = new List<double>();
    569 
    570             int n = a.Count;
    571             for (int i = 0; i < n; i++)
    572                 a[i].Add(b[i]);
    573 
    574             for (int @base = 0; @base < n - 1; @base++)
    575                 for (int target = @base + 1; target < n; target++)
    576                 {
    577                     double ratio = a[target][@base] / a[@base][@base];
    578                     for (int term = 0; term < a[@base].Count; term++)
    579                         a[target][term] = a[target][term] - a[@base][term] * ratio;
    580                 }
    581 
    582             for (int i = 0; i < n; i++)
    583                 x.Add(0.0);
    584 
    585             for (int i = n - 1; i >= 0; i--)
    586             {
    587                 for (int known = i + 1; known < n; known++)
    588                     a[i][n] = a[i][n] - a[i][known] * x[known];
    589                 x[i] = a[i][n] / a[i][i];
    590             }
    591 
    592             return x;
    593312        }
    594313
Note: See TracChangeset for help on using the changeset viewer.