Changeset 17619 for branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/NSGA3.cs

Timestamp:

06/21/20 21:57:35 (4 years ago)

Author:

dleko

Message:

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

File:

• branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/NSGA3.cs (modified) (8 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;
         }