Changeset 17692 for branches/2825-NSGA3

Timestamp:

07/22/20 12:53:10 (4 years ago)

Author:

dleko

Message:

#2825 Bugfix: NSGA3 now works as intended.

Location:

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

Files:

• NSGA3.cs (modified) (11 diffs)
• NSGA3Selection.cs (modified) (10 diffs)
• Solution.cs (modified) (2 diffs)

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

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
-using System.Diagnostics;
 using System.Linq;
 using System.Threading;
@@ -179 +178 @@
         public DoubleValue ResultsGenerationalDistance
         {
-            get { return (DoubleValue)Results[GenerationalDistanceResultName].Value;}
+            get { return (DoubleValue)Results[GenerationalDistanceResultName].Value; }
             set { Results[GenerationalDistanceResultName].Value = value; }
         }
@@ -204 +203 @@
             Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
             Parameters.Add(new FixedValueParameter<IntValue>(PopulationSizeName, "The size of the population of Individuals.", new IntValue(200)));
-            Parameters.Add(new FixedValueParameter<PercentValue>(CrossoverProbabilityName, "The probability that the crossover operator is applied on two parents.", new PercentValue(0.9)));
+            Parameters.Add(new FixedValueParameter<PercentValue>(CrossoverProbabilityName, "The probability that the crossover operator is applied on two parents.", new PercentValue(1.0)));
             Parameters.Add(new FixedValueParameter<DoubleValue>(CrossoverContiguityName, "The contiguity value for the Simulated Binary Crossover that specifies how close a child should be to its parents (larger value means closer). The value must be greater than or equal than 0. Typical values are in the range [2;5]."));
             Parameters.Add(new FixedValueParameter<PercentValue>(MutationProbabilityName, "The probability that the mutation operator is applied on a Individual.", new PercentValue(0.05)));
@@ -224 +223 @@
             random = cloner.Clone(original.random);
             solutions = original.solutions != null ? original.solutions.Select(cloner.Clone).ToList() : null;
-            referencePoints = original.referencePoints != null ? original.referencePoints.Select(r => {
+            referencePoints = original.referencePoints != null ? original.referencePoints.Select(r =>
+            {
                 var refPoint = new ReferencePoint(random, r.NumberOfDimensions);
                 r.Values.CopyTo(refPoint.Values, 0);
@@ -244 +244 @@
             base.Initialize(cancellationToken);
 
+            // Set population size
             int numberOfGeneratedReferencePoints = ReferencePoint.GetNumberOfGeneratedReferencePoints(NumberOfObjectives);
             int pop = ((numberOfGeneratedReferencePoints + 3) / 4) * 4;
             PopulationSize.Value = pop;
+
+            // Set mutation probability
+            double mutationProbability = 1.0 / Problem.Encoding.Length;
+            MutationProbability.Value = mutationProbability;
+
             InitResults();
             InitFields();
@@ -273 +279 @@
             InitReferencePoints();
         }
+
         private void InitReferencePoints()
         {
@@ -280 +287 @@
         }
 
-
         private void InitSolutions()
         {
@@ -291 +297 @@
             {
                 RealVector randomRealVector = new RealVector(Problem.Encoding.Length, random, minBound, maxBound);
-
-                solutions.Add(new Solution(randomRealVector));
-                solutions[i].Fitness = Evaluate(solutions[i].Chromosome);
+                var solution = new Solution(randomRealVector);
+                solution.Fitness = Evaluate(solution.Chromosome);
+                solutions.Add(solution);
             }
         }
@@ -305 +311 @@
             while (ResultsCurrentGeneration.Value < MaximumGenerations.Value)
             {
-
                 try
                 {
-                    List<Solution> qt = Mutate(Recombine(solutions));
+                    // todo: make parameter out of this
+                    List<Solution> qt = Mutate(Recombine(solutions), 30);
+                    foreach (var solution in qt)
+                        solution.Fitness = Evaluate(solution.Chromosome);
+
                     List<Solution> rt = Utility.Concat(solutions, qt);
 
-                    // create copies of generated reference points (to preserve the original ones for
-                    // the next generation) maybe todo: use cloner?
-                    solutions = NSGA3Selection.SelectSolutionsForNextGeneration(rt, GetCopyOfReferencePoints(), Problem.Maximization, random);
+                    solutions = NSGA3Selection.SelectSolutionsForNextGeneration(rt, GetCopyOfReferencePoints(), Problem.Maximization, PopulationSize.Value, random);
 
                     ResultsCurrentGeneration.Value++;
                     Analyze();
+                    cancellationToken.ThrowIfCancellationRequested();
+                }
+                catch (OperationCanceledException ex)
+                {
+                    throw new OperationCanceledException("Optimization process was cancelled.", ex);
                 }
                 catch (Exception ex)
                 {
-                    throw new Exception($"Failed in generation {ResultsCurrentGeneration}", ex);
+                    throw new Exception($"Failed in generation {ResultsCurrentGeneration}.", ex);
+                }
+                finally
+                {
+                    Analyze();
                 }
             }
@@ -384 +400 @@
 
                 // Do crossover with crossoverProbabilty == 1 in order to guarantee that a crossover happens
-                var children = SimulatedBinaryCrossover.Apply(random, Problem.Encoding.Bounds, parent1.Chromosome, parent2.Chromosome, 1);
-                Debug.Assert(children != null);
-
-                var child1 = new Solution(children.Item1);
-                var child2 = new Solution(children.Item2);
-                child1.Fitness = Evaluate(child1.Chromosome);
-                child2.Fitness = Evaluate(child1.Chromosome);
-
-                childSolutions.Add(child1);
-                childSolutions.Add(child2);
+                var children = SimulatedBinaryCrossover.Apply(random,
+                Problem.Encoding.Bounds, parent1.Chromosome, parent2.Chromosome, CrossoverProbability.Value);
+
+                childSolutions.Add(new Solution(children.Item1));
+                childSolutions.Add(new Solution(children.Item2));
             }
 
@@ -399 +410 @@
         }
 
-        private List<Solution> Mutate(List<Solution> solutions)
+        private List<Solution> Mutate(List<Solution> solutions, double eta)
         {
             foreach (var solution in solutions)
             {
-                UniformOnePositionManipulator.Apply(random, solution.Chromosome, Problem.Encoding.Bounds);
+                for (int i = 0; i < solution.Chromosome.Length; i++)
+                {
+                    if (random.NextDouble() > MutationProbability.Value) continue;
+
+                    double y = solution.Chromosome[i];
+                    double lb;
+                    double ub;
+                    var problem = Problem as MultiObjectiveTestFunctionProblem;
+                    if (problem.Bounds.Rows == 1) lb = problem.Bounds[0, 0];
+                    else lb = problem.Bounds[i, 0];
+                    if (problem.Bounds.Rows == 1) ub = problem.Bounds[0, 1];
+                    else ub = problem.Bounds[i, 1];
+
+                    double delta1 = (y - lb) / (ub - lb);
+                    double delta2 = (ub - y) / (ub - lb);
+
+                    double mut_pow = 1.0 / (eta + 1.0);
+
+                    double rnd = random.NextDouble();
+                    var deltaq = 0.0;
+                    if (rnd <= 0.5)
+                    {
+                        double xy = 1.0 - delta1;
+                        double val = 2.0 * rnd + (1.0 - 2.0 * rnd) * (Math.Pow(xy, (eta + 1.0)));
+                        deltaq = Math.Pow(val, mut_pow) - 1.0;
+                    }
+                    else
+                    {
+                        double xy = 1.0 - delta2;
+                        double val = 2.0 * (1.0 - rnd) + 2.0 * (rnd - 0.5) * (Math.Pow(xy, (eta + 1.0)));
+                        deltaq = 1.0 - (Math.Pow(val, mut_pow));
+                    }
+
+                    y = y + deltaq * (ub - lb);
+                    y = Math.Min(ub, Math.Max(lb, y));
+
+                    solution.Chromosome[i] = y;
+                }
             }
             return solutions;

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

@@ -15 +15 @@
         /// have the same number of objectives, undefined behavior happens.
         /// </summary>
-        /// <param name="rt"></param>
+        /// <param name="rt">The previous generation and its mutated children.</param>
         /// <param name="referencePoints"></param>
         /// <param name="maximization"></param>
+        /// <param name="N">Number of solutions to select.</param>
+        /// <param name="random">The <see cref="IRandom" /> to use for randomness.</param>
         /// <returns></returns>
-        public static List<Solution> SelectSolutionsForNextGeneration(List<Solution> rt, List<ReferencePoint> referencePoints, bool[] maximization, IRandom random)
-        {
-            int N = rt.Count / 2; // number of solutions in a generation
+        public static List<Solution> SelectSolutionsForNextGeneration(List<Solution> rt, List<ReferencePoint> referencePoints, bool[] maximization, int N, IRandom random)
+        {
             int numberOfObjectives = rt.First().Fitness.Length;
             List<Solution> st = new List<Solution>();
@@ -64 +65 @@
             // Find the ideal point
             double[] idealPoint = new double[numberOfObjectives];
+
+            foreach (var solution in st)
+                solution.ConvertedFitness = new double[numberOfObjectives];
+
             for (int j = 0; j < numberOfObjectives; j++)
             {
@@ -69 +74 @@
                 idealPoint[j] = Utility.Min(s => s.Fitness[j], st);
 
-                // Translate objectives
+                // Translate objectives and save the modified fitness values in ConvertedFitness
                 foreach (var solution in st)
-                    solution.Fitness[j] -= idealPoint[j];
+                    solution.ConvertedFitness[j] = solution.Fitness[j] - idealPoint[j];
             }
 
@@ -83 +88 @@
                 weights[j] = 1;
 
-                extremePoints[j] = Utility.ArgMin(s => ASF(s.Fitness, weights), st);
+                extremePoints[j] = Utility.ArgMin(s => ASF(s.ConvertedFitness, weights), st);
             }
 
@@ -103 +108 @@
                     if (Math.Abs(intercepts[i] - idealPoint[i]) > EPSILON)
                     {
-                        solution.Fitness[i] = solution.Fitness[i] / (intercepts[i] - idealPoint[i]);
+                        solution.ConvertedFitness[i] = solution.ConvertedFitness[i] / (intercepts[i] - idealPoint[i]);
                     }
                     else
                     {
-                        solution.Fitness[i] = solution.Fitness[i] / EPSILON;
+                        solution.ConvertedFitness[i] = solution.ConvertedFitness[i] / EPSILON;
                     }
                 }
@@ -121 +126 @@
                     // 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.ConvertedFitness), referencePoints);
                     // associated reference point
                     var arp = rpAndDist.Item1;
@@ -235 +240 @@
                 for (int j = i + 1; !duplicate && j < extremePoints.Count; j++)
                 {
-                    // maybe todo: override Equals method of solution?
-                    duplicate = extremePoints[i].Equals(extremePoints[j]);
+                    duplicate = extremePoints[i] == extremePoints[j];
                 }
             }
@@ -242 +246 @@
             List<double> intercepts = new List<double>();
 
+            // todo: do handling of this case as in Tsung Che Chiang's implementation
             if (duplicate)
             { // cannot construct the unique hyperplane (this is a casual method to deal with the condition)
@@ -248 +253 @@
                     // extreme_points[f] stands for the individual with the largest value of
                     // objective f
-                    intercepts.Add(extremePoints[f].Fitness[f]);
+                    intercepts.Add(extremePoints[f].ConvertedFitness[f]);
                 }
             }
@@ -260 +265 @@
                 }
 
-                List<List<double>> a = new List<List<double>>();
-                foreach (Solution s in extremePoints)
-                {
-                    List<double> aux = new List<double>();
-                    for (int i = 0; i < numberOfObjectives; i++)
-                        aux.Add(s.Fitness[i]);
-                    a.Add(aux);
-                }
+                List<List<double>> a = extremePoints.Select(p => p.ConvertedFitness.ToList()).ToList();
+
                 List<double> x = GaussianElimination(a, b);
 

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

@@ -12 +12 @@
         public RealVector Chromosome { get; set; }
 
-        // Fitness
+        // actual fitness of solution as given by Problem
         public double[] Fitness { get; set; }
+
+        // normalized fitness used in selection process (in order to not overwrite the original Fitness)
+        public double[] ConvertedFitness { get; set; }
 
         public Solution(RealVector chromosome)
@@ -23 +26 @@
         {
             Chromosome = cloner.Clone(solution.Chromosome);
-            Fitness = new double[solution.Fitness.Length];
-            Array.Copy(solution.Fitness, Fitness, solution.Fitness.Length);
+            if (solution.Fitness != null)
+            {
+                Fitness = new double[solution.Fitness.Length];
+                Array.Copy(solution.Fitness, Fitness, solution.Fitness.Length);
+            }
+            if (solution.ConvertedFitness != null)
+            {
+                ConvertedFitness = new double[solution.ConvertedFitness.Length];
+                Array.Copy(solution.ConvertedFitness, ConvertedFitness, solution.ConvertedFitness.Length);
+            }
         }