Changeset 17619

Timestamp:

06/21/20 21:57:35 (4 years 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:

• NSGA3.cs (modified) (8 diffs)
• ReferencePoint.cs (modified) (7 diffs)

branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/NSGA3.cs

@@ -230 +230 @@
             // Generate reference points and add them to results
             int nDiv = 5; // todo: figure out the correct number of divisions
-            ReferencePoints = ReferencePoint.GenerateReferencePoints(Problem.Encoding.Length, nDiv);
+            ReferencePoints = ReferencePoint.GenerateReferencePoints(random, Problem.Encoding.Length, nDiv);
             ResultsGeneratedReferencePoints = Utility.ConvertToDoubleMatrix(ReferencePoints);
         }
@@ -280 +280 @@
         }
 
-        private List<Solution> ToNextGeneration()
+        private void ToNextGeneration()
         {
             List<Solution> st = new List<Solution>();
@@ -311 +311 @@
                 for (int f = 0; f < l; f++)
                     nextGeneration = Utility.Concat(nextGeneration, Fronts[f]);
+                int k = PopulationSize.Value - nextGeneration.Count;
                 Normalize(st);
                 Associate();
-                throw new NotImplementedException();
-            }
-
-            throw new NotImplementedException();
+                List<Solution> solutionsToAdd = Niching(k);
+                nextGeneration = Utility.Concat(nextGeneration, solutionsToAdd);
+            }
         }
 
@@ -326 +326 @@
             {
                 // Compute ideal point
-                idealPoint[j] = Utility.Min(s => s.Fitness[j], solutions);
+                idealPoint[j] = Utility.Min(s => s.Fitness[j], population);
 
                 // Translate objectives
-                foreach (var solution in solutions)
+                foreach (var solution in population)
                     solution.Fitness[j] -= idealPoint[j];
             }
@@ -342 +342 @@
                 weights[j] = 1;
                 double func(Solution s) => ASF(s.Fitness, weights);
-                extremePoints[j] = Utility.ArgMin(func, solutions);
+                extremePoints[j] = Utility.ArgMin(func, population);
             }
 
@@ -350 +350 @@
             // Normalize objectives
             NormalizeObjectives(intercepts, idealPoint);
-
-            // Associate reference points to solutions
-            Associate();
         }
 
@@ -385 +382 @@
                     // solution is the lowest
                     var rpAndDist = Utility.MinArgMin(rp => GetPerpendicularDistance(rp.Values, solution.Fitness), ReferencePoints);
-
-                    //// todo: use ArgMin here
+                    // associated reference point
+                    var arp = rpAndDist.Item1;
+                    // distance to that reference point
+                    var dist = rpAndDist.Item2;
+
+                    //// todo: delete this
                     //int min_rp = -1;
                     //double min_dist = double.MaxValue;
@@ -401 +402 @@
                     {
                         // Todo: Add member for reference point on index min_rp
-                        throw new NotImplementedException();
+                        arp.NumberOfAssociatedSolutions++;
                     }
                     else
                     {
                         // Todo: Add potential member for reference point on index min_rp
-                        throw new NotImplementedException();
+                        arp.AddPotentialAssociatedSolution(solution, dist);
                     }
                 }
             }
+        }
+
+        private List<Solution> Niching(int k)
+        {
+            List<Solution> solutions = new List<Solution>();
+            while (solutions.Count != k)
+            {
+                ReferencePoint min_rp = FindNicheReferencePoint();
+
+                Solution chosen = SelectClusterMember(min_rp);
+                if (chosen == null)
+                {
+                    ReferencePoints.Remove(min_rp);
+                }
+                else
+                {
+                    min_rp.NumberOfAssociatedSolutions++;
+                    min_rp.RemovePotentialAssociatedSolution(chosen);
+                    solutions.Add(chosen);
+                }
+            }
+
+            return solutions;
+        }
+
+        private ReferencePoint FindNicheReferencePoint()
+        {
+            // the minimum number of associated solutions for a reference point over all reference points
+            int minNumber = Utility.Min(rp => rp.NumberOfAssociatedSolutions, ReferencePoints);
+            // the reference points that share the number of associated solutions where that number
+            // is equal to minNumber
+            List<ReferencePoint> referencePoints = new List<ReferencePoint>();
+            foreach (var referencePoint in ReferencePoints)
+                if (referencePoint.NumberOfAssociatedSolutions == minNumber)
+                    referencePoints.Add(referencePoint);
+
+            if (referencePoints.Count > 1)
+                return referencePoints[random.Next(referencePoints.Count)];
+            else
+                return referencePoints.Single();
+        }
+
+        private Solution SelectClusterMember(ReferencePoint referencePoint)
+        {
+            Solution chosen = null;
+            if (referencePoint.HasPotentialMember())
+            {
+                if (referencePoint.NumberOfAssociatedSolutions == 0)
+                    chosen = referencePoint.FindClosestMember();
+                else
+                    chosen = referencePoint.RandomMember();
+            }
+            return chosen;
         }
 

branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/ReferencePoint.cs

@@ -1 @@
-using System.Collections.Generic;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using HeuristicLab.Core;
 
 namespace HeuristicLab.Algorithms.NSGA3
@@ -11 +14 @@
     public class ReferencePoint
     {
+        private readonly Dictionary<Solution, double> potentialAssociatedSolutions = new Dictionary<Solution, double>();
+
         #region Properties
 
+        public IRandom random;
         public double[] Values { get; }
         public int NumberOfDimensions => Values.Length;
+        public int NumberOfAssociatedSolutions { get; set; } = 0;
 
         #endregion Properties
@@ -20 +27 @@
         #region Constructors
 
-        public ReferencePoint(int numberOfDimensions)
+        public ReferencePoint(IRandom random, int numberOfDimensions)
         {
+            this.random = random;
             Values = new double[numberOfDimensions];
         }
@@ -27 +35 @@
         public ReferencePoint(ReferencePoint other)
         {
+            random = other.random;
             Values = new double[other.NumberOfDimensions];
             for (int i = 0; i < other.NumberOfDimensions; i++)
@@ -33 +42 @@
 
         #endregion Constructors
+
+        #region Static methods
 
         // todo: use this (for optimization)
@@ -57 +68 @@
         /// <param name="nDiv">The number of divisions to use to generate reference points</param>
         /// <returns>The generated reference points</returns>
-        internal static List<ReferencePoint> GenerateReferencePoints(int nDim, int nDiv)
+        internal static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim, int nDiv)
         {
             List<ReferencePoint> referencePoints = new List<ReferencePoint>();
-            ReferencePoint refPoint = new ReferencePoint(nDim);
+            ReferencePoint refPoint = new ReferencePoint(random, nDim);
             GenerateRecursive(referencePoints, refPoint, nDim, nDiv, nDiv, 0);
 
@@ -83 +94 @@
             }
         }
+
+        #endregion Static methods
+
+        public void AddPotentialAssociatedSolution(Solution s, double distance)
+        {
+            if (potentialAssociatedSolutions.ContainsKey(s))
+                throw new InvalidOperationException("Attempt to add potential solution to reference point failed: That solution was already added as a potential solution");
+
+            potentialAssociatedSolutions.Add(s, distance);
+        }
+
+        public void RemovePotentialAssociatedSolution(Solution s)
+        {
+            potentialAssociatedSolutions.Remove(s);
+        }
+
+        public bool HasPotentialMember()
+        {
+            return potentialAssociatedSolutions.Any();
+        }
+
+        internal Solution FindClosestMember()
+        {
+            if (!potentialAssociatedSolutions.Any())
+                throw new InvalidOperationException("No potential members exist");
+
+            return Utility.ArgMin(pair => pair.Value, potentialAssociatedSolutions).Key;
+        }
+
+        internal Solution RandomMember()
+        {
+            if (!potentialAssociatedSolutions.Any())
+                throw new InvalidOperationException("No potential members exist");
+
+            return potentialAssociatedSolutions.Keys.ElementAt(random.Next(potentialAssociatedSolutions.Count));
+        }
     }
 }