Changeset 17692


Ignore:
Timestamp:
07/22/20 12:53:10 (3 weeks ago)
Author:
dleko
Message:

#2825 Bugfix: NSGA3 now works as intended.

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

Legend:

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

    r17688 r17692  
    11using System;
    22using System.Collections.Generic;
    3 using System.Diagnostics;
    43using System.Linq;
    54using System.Threading;
     
    179178        public DoubleValue ResultsGenerationalDistance
    180179        {
    181             get { return (DoubleValue)Results[GenerationalDistanceResultName].Value;}
     180            get { return (DoubleValue)Results[GenerationalDistanceResultName].Value; }
    182181            set { Results[GenerationalDistanceResultName].Value = value; }
    183182        }
     
    204203            Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
    205204            Parameters.Add(new FixedValueParameter<IntValue>(PopulationSizeName, "The size of the population of Individuals.", new IntValue(200)));
    206             Parameters.Add(new FixedValueParameter<PercentValue>(CrossoverProbabilityName, "The probability that the crossover operator is applied on two parents.", new PercentValue(0.9)));
     205            Parameters.Add(new FixedValueParameter<PercentValue>(CrossoverProbabilityName, "The probability that the crossover operator is applied on two parents.", new PercentValue(1.0)));
    207206            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]."));
    208207            Parameters.Add(new FixedValueParameter<PercentValue>(MutationProbabilityName, "The probability that the mutation operator is applied on a Individual.", new PercentValue(0.05)));
     
    224223            random = cloner.Clone(original.random);
    225224            solutions = original.solutions != null ? original.solutions.Select(cloner.Clone).ToList() : null;
    226             referencePoints = original.referencePoints != null ? original.referencePoints.Select(r => {
     225            referencePoints = original.referencePoints != null ? original.referencePoints.Select(r =>
     226            {
    227227                var refPoint = new ReferencePoint(random, r.NumberOfDimensions);
    228228                r.Values.CopyTo(refPoint.Values, 0);
     
    244244            base.Initialize(cancellationToken);
    245245
     246            // Set population size
    246247            int numberOfGeneratedReferencePoints = ReferencePoint.GetNumberOfGeneratedReferencePoints(NumberOfObjectives);
    247248            int pop = ((numberOfGeneratedReferencePoints + 3) / 4) * 4;
    248249            PopulationSize.Value = pop;
     250
     251            // Set mutation probability
     252            double mutationProbability = 1.0 / Problem.Encoding.Length;
     253            MutationProbability.Value = mutationProbability;
     254
    249255            InitResults();
    250256            InitFields();
     
    273279            InitReferencePoints();
    274280        }
     281
    275282        private void InitReferencePoints()
    276283        {
     
    280287        }
    281288
    282 
    283289        private void InitSolutions()
    284290        {
     
    291297            {
    292298                RealVector randomRealVector = new RealVector(Problem.Encoding.Length, random, minBound, maxBound);
    293 
    294                 solutions.Add(new Solution(randomRealVector));
    295                 solutions[i].Fitness = Evaluate(solutions[i].Chromosome);
     299                var solution = new Solution(randomRealVector);
     300                solution.Fitness = Evaluate(solution.Chromosome);
     301                solutions.Add(solution);
    296302            }
    297303        }
     
    305311            while (ResultsCurrentGeneration.Value < MaximumGenerations.Value)
    306312            {
    307 
    308313                try
    309314                {
    310                     List<Solution> qt = Mutate(Recombine(solutions));
     315                    // todo: make parameter out of this
     316                    List<Solution> qt = Mutate(Recombine(solutions), 30);
     317                    foreach (var solution in qt)
     318                        solution.Fitness = Evaluate(solution.Chromosome);
     319
    311320                    List<Solution> rt = Utility.Concat(solutions, qt);
    312321
    313                     // create copies of generated reference points (to preserve the original ones for
    314                     // the next generation) maybe todo: use cloner?
    315                     solutions = NSGA3Selection.SelectSolutionsForNextGeneration(rt, GetCopyOfReferencePoints(), Problem.Maximization, random);
     322                    solutions = NSGA3Selection.SelectSolutionsForNextGeneration(rt, GetCopyOfReferencePoints(), Problem.Maximization, PopulationSize.Value, random);
    316323
    317324                    ResultsCurrentGeneration.Value++;
    318325                    Analyze();
     326                    cancellationToken.ThrowIfCancellationRequested();
     327                }
     328                catch (OperationCanceledException ex)
     329                {
     330                    throw new OperationCanceledException("Optimization process was cancelled.", ex);
    319331                }
    320332                catch (Exception ex)
    321333                {
    322                     throw new Exception($"Failed in generation {ResultsCurrentGeneration}", ex);
     334                    throw new Exception($"Failed in generation {ResultsCurrentGeneration}.", ex);
     335                }
     336                finally
     337                {
     338                    Analyze();
    323339                }
    324340            }
     
    384400
    385401                // Do crossover with crossoverProbabilty == 1 in order to guarantee that a crossover happens
    386                 var children = SimulatedBinaryCrossover.Apply(random, Problem.Encoding.Bounds, parent1.Chromosome, parent2.Chromosome, 1);
    387                 Debug.Assert(children != null);
    388 
    389                 var child1 = new Solution(children.Item1);
    390                 var child2 = new Solution(children.Item2);
    391                 child1.Fitness = Evaluate(child1.Chromosome);
    392                 child2.Fitness = Evaluate(child1.Chromosome);
    393 
    394                 childSolutions.Add(child1);
    395                 childSolutions.Add(child2);
     402                var children = SimulatedBinaryCrossover.Apply(random,
     403                Problem.Encoding.Bounds, parent1.Chromosome, parent2.Chromosome, CrossoverProbability.Value);
     404
     405                childSolutions.Add(new Solution(children.Item1));
     406                childSolutions.Add(new Solution(children.Item2));
    396407            }
    397408
     
    399410        }
    400411
    401         private List<Solution> Mutate(List<Solution> solutions)
     412        private List<Solution> Mutate(List<Solution> solutions, double eta)
    402413        {
    403414            foreach (var solution in solutions)
    404415            {
    405                 UniformOnePositionManipulator.Apply(random, solution.Chromosome, Problem.Encoding.Bounds);
     416                for (int i = 0; i < solution.Chromosome.Length; i++)
     417                {
     418                    if (random.NextDouble() > MutationProbability.Value) continue;
     419
     420                    double y = solution.Chromosome[i];
     421                    double lb;
     422                    double ub;
     423                    var problem = Problem as MultiObjectiveTestFunctionProblem;
     424                    if (problem.Bounds.Rows == 1) lb = problem.Bounds[0, 0];
     425                    else lb = problem.Bounds[i, 0];
     426                    if (problem.Bounds.Rows == 1) ub = problem.Bounds[0, 1];
     427                    else ub = problem.Bounds[i, 1];
     428
     429                    double delta1 = (y - lb) / (ub - lb);
     430                    double delta2 = (ub - y) / (ub - lb);
     431
     432                    double mut_pow = 1.0 / (eta + 1.0);
     433
     434                    double rnd = random.NextDouble();
     435                    var deltaq = 0.0;
     436                    if (rnd <= 0.5)
     437                    {
     438                        double xy = 1.0 - delta1;
     439                        double val = 2.0 * rnd + (1.0 - 2.0 * rnd) * (Math.Pow(xy, (eta + 1.0)));
     440                        deltaq = Math.Pow(val, mut_pow) - 1.0;
     441                    }
     442                    else
     443                    {
     444                        double xy = 1.0 - delta2;
     445                        double val = 2.0 * (1.0 - rnd) + 2.0 * (rnd - 0.5) * (Math.Pow(xy, (eta + 1.0)));
     446                        deltaq = 1.0 - (Math.Pow(val, mut_pow));
     447                    }
     448
     449                    y = y + deltaq * (ub - lb);
     450                    y = Math.Min(ub, Math.Max(lb, y));
     451
     452                    solution.Chromosome[i] = y;
     453                }
    406454            }
    407455            return solutions;
  • branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/NSGA3Selection.cs

    r17668 r17692  
    1515        /// have the same number of objectives, undefined behavior happens.
    1616        /// </summary>
    17         /// <param name="rt"></param>
     17        /// <param name="rt">The previous generation and its mutated children.</param>
    1818        /// <param name="referencePoints"></param>
    1919        /// <param name="maximization"></param>
     20        /// <param name="N">Number of solutions to select.</param>
     21        /// <param name="random">The <see cref="IRandom" /> to use for randomness.</param>
    2022        /// <returns></returns>
    21         public static List<Solution> SelectSolutionsForNextGeneration(List<Solution> rt, List<ReferencePoint> referencePoints, bool[] maximization, IRandom random)
    22         {
    23             int N = rt.Count / 2; // number of solutions in a generation
     23        public static List<Solution> SelectSolutionsForNextGeneration(List<Solution> rt, List<ReferencePoint> referencePoints, bool[] maximization, int N, IRandom random)
     24        {
    2425            int numberOfObjectives = rt.First().Fitness.Length;
    2526            List<Solution> st = new List<Solution>();
     
    6465            // Find the ideal point
    6566            double[] idealPoint = new double[numberOfObjectives];
     67
     68            foreach (var solution in st)
     69                solution.ConvertedFitness = new double[numberOfObjectives];
     70
    6671            for (int j = 0; j < numberOfObjectives; j++)
    6772            {
     
    6974                idealPoint[j] = Utility.Min(s => s.Fitness[j], st);
    7075
    71                 // Translate objectives
     76                // Translate objectives and save the modified fitness values in ConvertedFitness
    7277                foreach (var solution in st)
    73                     solution.Fitness[j] -= idealPoint[j];
     78                    solution.ConvertedFitness[j] = solution.Fitness[j] - idealPoint[j];
    7479            }
    7580
     
    8388                weights[j] = 1;
    8489
    85                 extremePoints[j] = Utility.ArgMin(s => ASF(s.Fitness, weights), st);
     90                extremePoints[j] = Utility.ArgMin(s => ASF(s.ConvertedFitness, weights), st);
    8691            }
    8792
     
    103108                    if (Math.Abs(intercepts[i] - idealPoint[i]) > EPSILON)
    104109                    {
    105                         solution.Fitness[i] = solution.Fitness[i] / (intercepts[i] - idealPoint[i]);
     110                        solution.ConvertedFitness[i] = solution.ConvertedFitness[i] / (intercepts[i] - idealPoint[i]);
    106111                    }
    107112                    else
    108113                    {
    109                         solution.Fitness[i] = solution.Fitness[i] / EPSILON;
     114                        solution.ConvertedFitness[i] = solution.ConvertedFitness[i] / EPSILON;
    110115                    }
    111116                }
     
    121126                    // find reference point for which the perpendicular distance to the current
    122127                    // solution is the lowest
    123                     var rpAndDist = Utility.MinArgMin(rp => GetPerpendicularDistance(rp.Values, solution.Fitness), referencePoints);
     128                    var rpAndDist = Utility.MinArgMin(rp => GetPerpendicularDistance(rp.Values, solution.ConvertedFitness), referencePoints);
    124129                    // associated reference point
    125130                    var arp = rpAndDist.Item1;
     
    235240                for (int j = i + 1; !duplicate && j < extremePoints.Count; j++)
    236241                {
    237                     // maybe todo: override Equals method of solution?
    238                     duplicate = extremePoints[i].Equals(extremePoints[j]);
     242                    duplicate = extremePoints[i] == extremePoints[j];
    239243                }
    240244            }
     
    242246            List<double> intercepts = new List<double>();
    243247
     248            // todo: do handling of this case as in Tsung Che Chiang's implementation
    244249            if (duplicate)
    245250            { // cannot construct the unique hyperplane (this is a casual method to deal with the condition)
     
    248253                    // extreme_points[f] stands for the individual with the largest value of
    249254                    // objective f
    250                     intercepts.Add(extremePoints[f].Fitness[f]);
     255                    intercepts.Add(extremePoints[f].ConvertedFitness[f]);
    251256                }
    252257            }
     
    260265                }
    261266
    262                 List<List<double>> a = new List<List<double>>();
    263                 foreach (Solution s in extremePoints)
    264                 {
    265                     List<double> aux = new List<double>();
    266                     for (int i = 0; i < numberOfObjectives; i++)
    267                         aux.Add(s.Fitness[i]);
    268                     a.Add(aux);
    269                 }
     267                List<List<double>> a = extremePoints.Select(p => p.ConvertedFitness.ToList()).ToList();
     268
    270269                List<double> x = GaussianElimination(a, b);
    271270
  • branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/Solution.cs

    r17657 r17692  
    1212        public RealVector Chromosome { get; set; }
    1313
    14         // Fitness
     14        // actual fitness of solution as given by Problem
    1515        public double[] Fitness { get; set; }
     16
     17        // normalized fitness used in selection process (in order to not overwrite the original Fitness)
     18        public double[] ConvertedFitness { get; set; }
    1619
    1720        public Solution(RealVector chromosome)
     
    2326        {
    2427            Chromosome = cloner.Clone(solution.Chromosome);
    25             Fitness = new double[solution.Fitness.Length];
    26             Array.Copy(solution.Fitness, Fitness, solution.Fitness.Length);
     28            if (solution.Fitness != null)
     29            {
     30                Fitness = new double[solution.Fitness.Length];
     31                Array.Copy(solution.Fitness, Fitness, solution.Fitness.Length);
     32            }
     33            if (solution.ConvertedFitness != null)
     34            {
     35                ConvertedFitness = new double[solution.ConvertedFitness.Length];
     36                Array.Copy(solution.ConvertedFitness, ConvertedFitness, solution.ConvertedFitness.Length);
     37            }
    2738        }
    2839
Note: See TracChangeset for help on using the changeset viewer.