Changeset 17661

Timestamp:

07/09/20 15:55:03 (4 years ago)

Author:

dleko

Message:

#2825 Correct reference point generation.

Location:

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

Files:

• NSGA3.cs (modified) (11 diffs)
• ReferencePoint.cs (modified) (5 diffs)

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

@@ -144 +144 @@
         public List<ReferencePoint> ReferencePoints { get; private set; }
 
+        // todo: create one property for the Generated Reference Points and one for the current
+        // generations reference points
+
         #endregion Properties
 
@@ -236 +239 @@
         {
             // Generate reference points and add them to results
-            int nDiv = 5; // todo: figure out the correct number of divisions
-            ReferencePoints = ReferencePoint.GenerateReferencePoints(random, Problem.Encoding.Length, nDiv);
+            ReferencePoints = ReferencePoint.GenerateReferencePoints(random, Problem.Maximization.Length);
             ResultsGeneratedReferencePoints = Utility.ConvertToDoubleMatrix(ReferencePoints);
         }
@@ -253 +255 @@
         protected override void Run(CancellationToken cancellationToken)
         {
-            ReferencePoints = new List<ReferencePoint>(); // todo: use existing list of reference points
             while (generation != MaximumGenerations.Value)
             {
-                ToNextGeneration();
+                // create copies of generated reference points (to preserve the original ones for
+                // the next generation) maybe todo: use cloner?
+                ToNextGeneration(CreateCopyOfReferencePoints());
                 generation++;
             }
@@ -264 +267 @@
 
         #region Private Methods
+
+        private List<ReferencePoint> CreateCopyOfReferencePoints()
+        {
+            if (ReferencePoints == null) return null;
+
+            List<ReferencePoint> referencePoints = new List<ReferencePoint>();
+            foreach (var referencePoint in ReferencePoints)
+                referencePoints.Add(new ReferencePoint(referencePoint));
+
+            return referencePoints;
+        }
 
         private void Analyze()
@@ -287 +301 @@
         }
 
-        private void ToNextGeneration()
+        private void ToNextGeneration(List<ReferencePoint> referencePoints)
         {
             List<Solution> st = new List<Solution>();
@@ -320 +334 @@
                 int k = PopulationSize.Value - nextGeneration.Count;
                 Normalize(st);
-                Associate();
-                List<Solution> solutionsToAdd = Niching(k);
+                Associate(referencePoints);
+                List<Solution> solutionsToAdd = Niching(k, referencePoints);
                 nextGeneration = Utility.Concat(nextGeneration, solutionsToAdd);
             }
@@ -380 +394 @@
         }
 
-        private void Associate()
+        private void Associate(List<ReferencePoint> referencePoints)
         {
             for (int f = 0; f < Fronts.Count; f++)
@@ -388 +402 @@
                     // find reference point for which the perpendicular distance to the current
                     // solution is the lowest
-                    var rpAndDist = Utility.MinArgMin(rp => GetPerpendicularDistance(rp.Values, solution.Fitness), ReferencePoints);
+                    var rpAndDist = Utility.MinArgMin(rp => GetPerpendicularDistance(rp.Values, solution.Fitness), referencePoints);
                     // associated reference point
                     var arp = rpAndDist.Item1;
@@ -394 +408 @@
                     var dist = rpAndDist.Item2;
 
-                    //// todo: delete this
-                    //int min_rp = -1;
-                    //double min_dist = double.MaxValue;
-                    //for (int r = 0; r < referencePoints.Count; r++)
-                    //{
-                    //    double d = GetPerpendicularDistance(referencePoints[r].Values, solution.Fitness);
-                    //    if (d < min_dist)
-                    //    {
-                    //        min_dist = d;
-                    //        min_rp = r;
-                    //    }
-                    //}
                     if (f + 1 != Fronts.Count)
                     {
@@ -420 +422 @@
         }
 
-        private List<Solution> Niching(int k)
+        private List<Solution> Niching(int k, List<ReferencePoint> referencePoints)
         {
             List<Solution> solutions = new List<Solution>();
             while (solutions.Count != k)
             {
-                ReferencePoint min_rp = FindNicheReferencePoint();
+                ReferencePoint min_rp = FindNicheReferencePoint(referencePoints);
 
                 Solution chosen = SelectClusterMember(min_rp);
                 if (chosen == null)
                 {
-                    ReferencePoints.Remove(min_rp);
+                    referencePoints.Remove(min_rp);
                 }
                 else
@@ -443 +445 @@
         }
 
-        private ReferencePoint FindNicheReferencePoint()
+        private ReferencePoint FindNicheReferencePoint(List<ReferencePoint> referencePoints)
         {
             // the minimum number of associated solutions for a reference point over all reference points
-            int minNumber = Utility.Min(rp => rp.NumberOfAssociatedSolutions, ReferencePoints);
+            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)
+            List<ReferencePoint> minAssociatedReferencePoints = 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)];
+                    minAssociatedReferencePoints.Add(referencePoint);
+
+            if (minAssociatedReferencePoints.Count > 1)
+                return minAssociatedReferencePoints[random.Next(minAssociatedReferencePoints.Count)];
             else
-                return referencePoints.Single();
+                return minAssociatedReferencePoints.Single();
         }
 

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

@@ -6 +6 @@
 namespace HeuristicLab.Algorithms.NSGA3
 {
-    /*
-     * The method for generating the reference points is based on the NSGA3 implementation in the jMetal framework (http://jmetal.sourceforge.net/).
-     * That implementation in return is based on Tsung-Che Chiang's code
-     * http://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm
-     */
-
     public class ReferencePoint
     {
+        // The potentially associated solutions to this reference point and the distance to that solution
         private readonly Dictionary<Solution, double> potentialAssociatedSolutions = new Dictionary<Solution, double>();
 
         #region Properties
 
-        public IRandom random;
+        private readonly IRandom random;
         public double[] Values { get; }
         public int NumberOfDimensions => Values.Length;
@@ -37 +32 @@
             random = other.random;
             Values = new double[other.NumberOfDimensions];
-            for (int i = 0; i < other.NumberOfDimensions; i++)
-                Values[i] = other.Values[i];
+            other.Values.CopyTo(Values, 0);
         }
 
@@ -45 +39 @@
         #region Static methods
 
-        // todo: use this (for optimization)
         /// <summary>
-        /// Returns the number of reference points that are generated by <see
-        /// cref="GenerateReferencePoints(List{ReferencePoint}, int, int)" /> for the given number
-        /// of dimensions and divisions.
+        /// Generate reference points that are evenly distributed over a hyperplane with dimensions
+        /// <paramref name="nDim" /> - 1 with the sum of the values in all dimensions being equal to
+        /// 1 for each reference point. <paramref name="nDim" /> may only be one of {3, 5, 8, 10, 15}
+        /// -&gt; The number of inner divisions and outer divisions are determined based on the
+        /// values provided in the NSGA-III paper, chapter V: Results. If different dimensions are
+        /// given, null is returned.
         /// </summary>
-        /// <param name="nDim">The number of dimensions</param>
-        /// <param name="nDiv">The number of divisions</param>
+        /// <param name="random">
+        /// The <see cref="IRandom" /> to give as a parameter to the ReferencePoint constructors.
+        /// </param>
+        /// <param name="nDim">The dimensionality of the Reference Points</param>
         /// <returns></returns>
-        internal static int GetNumberOfReferencePoints(int nDim, int nDiv)
+        internal static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim)
         {
-            return Utility.NCR(nDim + nDiv - 1, nDiv);
+            List<ReferencePoint> referencePoints;
+            switch (nDim)
+            {
+                case 3:
+                    referencePoints = GenerateReferencePoints(random, nDim, 12, 0);
+                    break;
+
+                case 5:
+                    referencePoints = GenerateReferencePoints(random, nDim, 6, 0);
+                    break;
+
+                case 8:
+                    referencePoints = GenerateReferencePoints(random, nDim, 3, 2);
+                    break;
+
+                case 10:
+                    referencePoints = GenerateReferencePoints(random, nDim, 3, 2);
+                    break;
+
+                case 15:
+                    referencePoints = GenerateReferencePoints(random, nDim, 2, 1);
+                    break;
+
+                default:
+                    referencePoints = null;
+                    break;
+            }
+
+            return referencePoints;
         }
 
-        // maybe todo: move this to another class?
+        internal static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim, int outerDiv)
+        {
+            return GenerateReferencePoints(random, nDim, outerDiv, 0);
+        }
+
+        /*
+         * This method is based on Tsung-Che Chiang's NSGA-III implementation (version 1.20)
+         * http://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm
+         */
+
         /// <summary>
         /// Generate reference points that are evenly distributed over a hyperplane with dimensions
@@ -65 +100 @@
         /// 1 for each reference point.
         /// </summary>
-        /// <param name="nDim">The number of dimensions for the reference points</param>
-        /// <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(IRandom random, int nDim, int nDiv)
+        /// <param name="nDim">The number of dimensions for the reference points.</param>
+        /// <param name="outerDiv">The number of divisions for the outer reference points</param>
+        /// <returns>The generated reference points (Check Fig. 4 in NSGA-III paper).</returns>
+        /// <param name="innerDiv">The number of divisions for the inner reference points</param>
+        /// <returns>
+        /// The generated reference points (Check Fig. 4 in NSGA-III paper). Set to 0, in order to
+        /// not have inner reference points
+        /// </returns>
+        internal static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim, int outerDiv, int innerDiv)
         {
+            if (nDim <= 0) throw new ArgumentException("nDim must be greater than 0");
+            if (outerDiv <= 1) throw new ArgumentException("outerDiv must be greater than 1");
+
             List<ReferencePoint> referencePoints = new List<ReferencePoint>();
             ReferencePoint refPoint = new ReferencePoint(random, nDim);
-            GenerateRecursive(referencePoints, refPoint, nDim, nDiv, nDiv, 0);
+            GenerateRecursive(referencePoints, refPoint, nDim, outerDiv, outerDiv, 0);
+
+            if (innerDiv > 0)
+            {
+                List<ReferencePoint> insideReferencePoints = new List<ReferencePoint>();
+                GenerateRecursive(insideReferencePoints, refPoint, nDim, innerDiv, innerDiv, 0);
+
+                double center = 1.0 / nDim;
+
+                for (int i = 0; i < insideReferencePoints.Count; i++)
+                {
+                    for (int j = 0; j < insideReferencePoints[i].Values.Length; j++)
+                    {
+                        insideReferencePoints[i].Values[j] = (center + insideReferencePoints[i].Values[j]) / 2;
+                    }
+                    referencePoints.Add(insideReferencePoints[i]);
+                }
+            }
 
             return referencePoints;
         }
+
+        /*
+         * This method is based on Tsung-Che Chiang's NSGA-III implementation (version 1.20)
+         * http://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm
+         */
 
         private static void GenerateRecursive(List<ReferencePoint> referencePoints, ReferencePoint refPoint, int numberOfObjectives, int left, int total, int element)
@@ -100 +165 @@
         {
             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");
+                throw new InvalidOperationException("Given solution was already added as a potential solution");
 
             potentialAssociatedSolutions.Add(s, distance);