Changeset 17619


Ignore:
Timestamp:
06/21/20 21:57:35 (3 weeks ago)
Author:
dleko
Message:

#2825 Implement second part of NSGA3. Add random field to ReferencePoint.

Location:
branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3
Files:
2 edited

Legend:

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

    r17618 r17619  
    230230            // Generate reference points and add them to results
    231231            int nDiv = 5; // todo: figure out the correct number of divisions
    232             ReferencePoints = ReferencePoint.GenerateReferencePoints(Problem.Encoding.Length, nDiv);
     232            ReferencePoints = ReferencePoint.GenerateReferencePoints(random, Problem.Encoding.Length, nDiv);
    233233            ResultsGeneratedReferencePoints = Utility.ConvertToDoubleMatrix(ReferencePoints);
    234234        }
     
    280280        }
    281281
    282         private List<Solution> ToNextGeneration()
     282        private void ToNextGeneration()
    283283        {
    284284            List<Solution> st = new List<Solution>();
     
    311311                for (int f = 0; f < l; f++)
    312312                    nextGeneration = Utility.Concat(nextGeneration, Fronts[f]);
     313                int k = PopulationSize.Value - nextGeneration.Count;
    313314                Normalize(st);
    314315                Associate();
    315                 throw new NotImplementedException();
    316             }
    317 
    318             throw new NotImplementedException();
     316                List<Solution> solutionsToAdd = Niching(k);
     317                nextGeneration = Utility.Concat(nextGeneration, solutionsToAdd);
     318            }
    319319        }
    320320
     
    326326            {
    327327                // Compute ideal point
    328                 idealPoint[j] = Utility.Min(s => s.Fitness[j], solutions);
     328                idealPoint[j] = Utility.Min(s => s.Fitness[j], population);
    329329
    330330                // Translate objectives
    331                 foreach (var solution in solutions)
     331                foreach (var solution in population)
    332332                    solution.Fitness[j] -= idealPoint[j];
    333333            }
     
    342342                weights[j] = 1;
    343343                double func(Solution s) => ASF(s.Fitness, weights);
    344                 extremePoints[j] = Utility.ArgMin(func, solutions);
     344                extremePoints[j] = Utility.ArgMin(func, population);
    345345            }
    346346
     
    350350            // Normalize objectives
    351351            NormalizeObjectives(intercepts, idealPoint);
    352 
    353             // Associate reference points to solutions
    354             Associate();
    355352        }
    356353
     
    385382                    // solution is the lowest
    386383                    var rpAndDist = Utility.MinArgMin(rp => GetPerpendicularDistance(rp.Values, solution.Fitness), ReferencePoints);
    387 
    388                     //// todo: use ArgMin here
     384                    // associated reference point
     385                    var arp = rpAndDist.Item1;
     386                    // distance to that reference point
     387                    var dist = rpAndDist.Item2;
     388
     389                    //// todo: delete this
    389390                    //int min_rp = -1;
    390391                    //double min_dist = double.MaxValue;
     
    401402                    {
    402403                        // Todo: Add member for reference point on index min_rp
    403                         throw new NotImplementedException();
     404                        arp.NumberOfAssociatedSolutions++;
    404405                    }
    405406                    else
    406407                    {
    407408                        // Todo: Add potential member for reference point on index min_rp
    408                         throw new NotImplementedException();
     409                        arp.AddPotentialAssociatedSolution(solution, dist);
    409410                    }
    410411                }
    411412            }
     413        }
     414
     415        private List<Solution> Niching(int k)
     416        {
     417            List<Solution> solutions = new List<Solution>();
     418            while (solutions.Count != k)
     419            {
     420                ReferencePoint min_rp = FindNicheReferencePoint();
     421
     422                Solution chosen = SelectClusterMember(min_rp);
     423                if (chosen == null)
     424                {
     425                    ReferencePoints.Remove(min_rp);
     426                }
     427                else
     428                {
     429                    min_rp.NumberOfAssociatedSolutions++;
     430                    min_rp.RemovePotentialAssociatedSolution(chosen);
     431                    solutions.Add(chosen);
     432                }
     433            }
     434
     435            return solutions;
     436        }
     437
     438        private ReferencePoint FindNicheReferencePoint()
     439        {
     440            // the minimum number of associated solutions for a reference point over all reference points
     441            int minNumber = Utility.Min(rp => rp.NumberOfAssociatedSolutions, ReferencePoints);
     442            // the reference points that share the number of associated solutions where that number
     443            // is equal to minNumber
     444            List<ReferencePoint> referencePoints = new List<ReferencePoint>();
     445            foreach (var referencePoint in ReferencePoints)
     446                if (referencePoint.NumberOfAssociatedSolutions == minNumber)
     447                    referencePoints.Add(referencePoint);
     448
     449            if (referencePoints.Count > 1)
     450                return referencePoints[random.Next(referencePoints.Count)];
     451            else
     452                return referencePoints.Single();
     453        }
     454
     455        private Solution SelectClusterMember(ReferencePoint referencePoint)
     456        {
     457            Solution chosen = null;
     458            if (referencePoint.HasPotentialMember())
     459            {
     460                if (referencePoint.NumberOfAssociatedSolutions == 0)
     461                    chosen = referencePoint.FindClosestMember();
     462                else
     463                    chosen = referencePoint.RandomMember();
     464            }
     465            return chosen;
    412466        }
    413467
  • branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/ReferencePoint.cs

    r17617 r17619  
    1 using System.Collections.Generic;
     1using System;
     2using System.Collections.Generic;
     3using System.Linq;
     4using HeuristicLab.Core;
    25
    36namespace HeuristicLab.Algorithms.NSGA3
     
    1114    public class ReferencePoint
    1215    {
     16        private readonly Dictionary<Solution, double> potentialAssociatedSolutions = new Dictionary<Solution, double>();
     17
    1318        #region Properties
    1419
     20        public IRandom random;
    1521        public double[] Values { get; }
    1622        public int NumberOfDimensions => Values.Length;
     23        public int NumberOfAssociatedSolutions { get; set; } = 0;
    1724
    1825        #endregion Properties
     
    2027        #region Constructors
    2128
    22         public ReferencePoint(int numberOfDimensions)
     29        public ReferencePoint(IRandom random, int numberOfDimensions)
    2330        {
     31            this.random = random;
    2432            Values = new double[numberOfDimensions];
    2533        }
     
    2735        public ReferencePoint(ReferencePoint other)
    2836        {
     37            random = other.random;
    2938            Values = new double[other.NumberOfDimensions];
    3039            for (int i = 0; i < other.NumberOfDimensions; i++)
     
    3342
    3443        #endregion Constructors
     44
     45        #region Static methods
    3546
    3647        // todo: use this (for optimization)
     
    5768        /// <param name="nDiv">The number of divisions to use to generate reference points</param>
    5869        /// <returns>The generated reference points</returns>
    59         internal static List<ReferencePoint> GenerateReferencePoints(int nDim, int nDiv)
     70        internal static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim, int nDiv)
    6071        {
    6172            List<ReferencePoint> referencePoints = new List<ReferencePoint>();
    62             ReferencePoint refPoint = new ReferencePoint(nDim);
     73            ReferencePoint refPoint = new ReferencePoint(random, nDim);
    6374            GenerateRecursive(referencePoints, refPoint, nDim, nDiv, nDiv, 0);
    6475
     
    8394            }
    8495        }
     96
     97        #endregion Static methods
     98
     99        public void AddPotentialAssociatedSolution(Solution s, double distance)
     100        {
     101            if (potentialAssociatedSolutions.ContainsKey(s))
     102                throw new InvalidOperationException("Attempt to add potential solution to reference point failed: That solution was already added as a potential solution");
     103
     104            potentialAssociatedSolutions.Add(s, distance);
     105        }
     106
     107        public void RemovePotentialAssociatedSolution(Solution s)
     108        {
     109            potentialAssociatedSolutions.Remove(s);
     110        }
     111
     112        public bool HasPotentialMember()
     113        {
     114            return potentialAssociatedSolutions.Any();
     115        }
     116
     117        internal Solution FindClosestMember()
     118        {
     119            if (!potentialAssociatedSolutions.Any())
     120                throw new InvalidOperationException("No potential members exist");
     121
     122            return Utility.ArgMin(pair => pair.Value, potentialAssociatedSolutions).Key;
     123        }
     124
     125        internal Solution RandomMember()
     126        {
     127            if (!potentialAssociatedSolutions.Any())
     128                throw new InvalidOperationException("No potential members exist");
     129
     130            return potentialAssociatedSolutions.Keys.ElementAt(random.Next(potentialAssociatedSolutions.Count));
     131        }
    85132    }
    86133}
Note: See TracChangeset for help on using the changeset viewer.