Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/NSGA3.cs @ 17688

Last change on this file since 17688 was 17688, checked in by dleko, 4 years ago

#2825 Bugfix NSGA3 can now be cloned.

File size: 18.5 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4using System.Linq;
5using System.Threading;
6using HEAL.Attic;
7using HeuristicLab.Common;
8using HeuristicLab.Core;
9using HeuristicLab.Data;
10using HeuristicLab.Encodings.RealVectorEncoding;
11using HeuristicLab.Optimization;
12using HeuristicLab.Parameters;
13using HeuristicLab.Problems.TestFunctions.MultiObjective;
14using HeuristicLab.Random;
15
16namespace HeuristicLab.Algorithms.NSGA3
17{
18    /// <summary>
19    /// The Reference Point Based Non-dominated Sorting Genetic Algorithm III was introduced in Deb
20    /// et al. 2013. An Evolutionary Many-Objective Optimization Algorithm Using Reference Point
21    /// Based Non-dominated Sorting Approach. IEEE Transactions on Evolutionary Computation, 18(4),
22    /// pp. 577-601.
23    /// </summary>
24    [Item("NSGA-III", "The Reference Point Based Non-dominated Sorting Genetic Algorithm III was introduced in Deb et al. 2013. An Evolutionary Many-Objective Optimization Algorithm Using Reference Point Based Non-dominated Sorting Approach. IEEE Transactions on Evolutionary Computation, 18(4), pp. 577-601.")]
25    [Creatable(Category = CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 136)]
26    [StorableType("07C745F7-A8A3-4F99-8B2C-F97E639F9AC3")]
27    public class NSGA3 : BasicAlgorithm
28    {
29        public override bool SupportsPause => false;
30
31        #region ProblemProperties
32
33        public override Type ProblemType
34        {
35            get { return typeof(MultiObjectiveBasicProblem<RealVectorEncoding>); }
36        }
37
38        public new MultiObjectiveBasicProblem<RealVectorEncoding> Problem
39        {
40            get { return (MultiObjectiveBasicProblem<RealVectorEncoding>)base.Problem; }
41            set { base.Problem = value; }
42        }
43
44        public int NumberOfObjectives
45        {
46            get
47            {
48                if (!(Problem is MultiObjectiveTestFunctionProblem testFunctionProblem)) throw new NotSupportedException("Only Multi Objective Test Function problems are supported");
49                return testFunctionProblem.Objectives;
50            }
51        }
52
53        #endregion ProblemProperties
54
55        #region Storable fields
56
57        [Storable]
58        private IRandom random;
59
60        [Storable]
61        private List<Solution> solutions; // maybe todo: rename to nextGeneration (see Run method)
62
63        [Storable]
64        private List<ReferencePoint> referencePoints;
65
66        #endregion Storable fields
67
68        #region ParameterAndResultsNames
69
70        // Parameter Names
71
72        private const string SeedName = "Seed";
73        private const string SetSeedRandomlyName = "Set Seed Randomly";
74        private const string PopulationSizeName = "Population Size";
75        private const string CrossoverProbabilityName = "Crossover Probability";
76        private const string CrossoverContiguityName = "Crossover Contiguity";
77        private const string MutationProbabilityName = "Mutation Probability";
78        private const string MaximumGenerationsName = "Maximum Generations";
79        private const string DominateOnEqualQualitiesName = "Dominate On Equal Qualities";
80
81        // Results Names
82
83        private const string GeneratedReferencePointsResultName = "Generated Reference Points";
84        private const string CurrentGenerationResultName = "Generations";
85        private const string GenerationalDistanceResultName = "Generational Distance";
86        private const string InvertedGenerationalDistanceResultName = "Inverted Generational Distance";
87        private const string ScatterPlotResultName = "Scatter Plot";
88        private const string CurrentFrontResultName = "Pareto Front"; // Do not touch this
89
90        #endregion ParameterAndResultsNames
91
92        #region ParameterProperties
93
94        private IFixedValueParameter<IntValue> SeedParameter
95        {
96            get { return (IFixedValueParameter<IntValue>)Parameters[SeedName]; }
97        }
98
99        private IFixedValueParameter<BoolValue> SetSeedRandomlyParameter
100        {
101            get { return (IFixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyName]; }
102        }
103
104        private IFixedValueParameter<IntValue> PopulationSizeParameter
105        {
106            get { return (IFixedValueParameter<IntValue>)Parameters[PopulationSizeName]; }
107        }
108
109        private IFixedValueParameter<PercentValue> CrossoverProbabilityParameter
110        {
111            get { return (IFixedValueParameter<PercentValue>)Parameters[CrossoverProbabilityName]; }
112        }
113
114        private IFixedValueParameter<DoubleValue> CrossoverContiguityParameter
115        {
116            get { return (IFixedValueParameter<DoubleValue>)Parameters[CrossoverContiguityName]; }
117        }
118
119        private IFixedValueParameter<PercentValue> MutationProbabilityParameter
120        {
121            get { return (IFixedValueParameter<PercentValue>)Parameters[MutationProbabilityName]; }
122        }
123
124        private IFixedValueParameter<IntValue> MaximumGenerationsParameter
125        {
126            get { return (IFixedValueParameter<IntValue>)Parameters[MaximumGenerationsName]; }
127        }
128
129        private IFixedValueParameter<BoolValue> DominateOnEqualQualitiesParameter
130        {
131            get { return (IFixedValueParameter<BoolValue>)Parameters[DominateOnEqualQualitiesName]; }
132        }
133
134        #endregion ParameterProperties
135
136        #region Properties
137
138        public IntValue Seed => SeedParameter.Value;
139
140        public BoolValue SetSeedRandomly => SetSeedRandomlyParameter.Value;
141
142        public IntValue PopulationSize => PopulationSizeParameter.Value;
143
144        public PercentValue CrossoverProbability => CrossoverProbabilityParameter.Value;
145
146        public DoubleValue CrossoverContiguity => CrossoverContiguityParameter.Value;
147
148        public PercentValue MutationProbability => MutationProbabilityParameter.Value;
149
150        public IntValue MaximumGenerations => MaximumGenerationsParameter.Value;
151
152        public BoolValue DominateOnEqualQualities => DominateOnEqualQualitiesParameter.Value;
153
154        // todo: create one property for the Generated Reference Points and one for the current
155        // generations reference points
156
157        #endregion Properties
158
159        #region ResultsProperties
160
161        public DoubleMatrix ResultsGeneratedReferencePoints
162        {
163            get { return (DoubleMatrix)Results[GeneratedReferencePointsResultName].Value; }
164            set { Results[GeneratedReferencePointsResultName].Value = value; }
165        }
166
167        public DoubleMatrix ResultsSolutions
168        {
169            get { return (DoubleMatrix)Results[CurrentFrontResultName].Value; }
170            set { Results[CurrentFrontResultName].Value = value; }
171        }
172
173        public IntValue ResultsCurrentGeneration
174        {
175            get { return (IntValue)Results[CurrentGenerationResultName].Value; }
176            set { Results[CurrentGenerationResultName].Value = value; }
177        }
178
179        public DoubleValue ResultsGenerationalDistance
180        {
181            get { return (DoubleValue)Results[GenerationalDistanceResultName].Value;}
182            set { Results[GenerationalDistanceResultName].Value = value; }
183        }
184
185        public DoubleValue ResultsInvertedGenerationalDistance
186        {
187            get { return (DoubleValue)Results[InvertedGenerationalDistanceResultName].Value; }
188            set { Results[InvertedGenerationalDistanceResultName].Value = value; }
189        }
190
191        public ParetoFrontScatterPlot ResultsScatterPlot
192        {
193            get { return (ParetoFrontScatterPlot)Results[ScatterPlotResultName].Value; }
194            set { Results[ScatterPlotResultName].Value = value; }
195        }
196
197        #endregion ResultsProperties
198
199        #region Constructors
200
201        public NSGA3() : base()
202        {
203            Parameters.Add(new FixedValueParameter<IntValue>(SeedName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
204            Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
205            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)));
207            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]."));
208            Parameters.Add(new FixedValueParameter<PercentValue>(MutationProbabilityName, "The probability that the mutation operator is applied on a Individual.", new PercentValue(0.05)));
209            Parameters.Add(new FixedValueParameter<IntValue>(MaximumGenerationsName, "The maximum number of generations which should be processed.", new IntValue(1000)));
210            Parameters.Add(new FixedValueParameter<BoolValue>(DominateOnEqualQualitiesName, "Flag which determines wether Individuals with equal quality values should be treated as dominated.", new BoolValue(false)));
211        }
212
213        // Persistence uses this ctor to improve deserialization efficiency. If we would use the
214        // default ctor instead this would completely initialize the object (e.g. creating
215        // parameters) even though the data is later overwritten by the stored data.
216        [StorableConstructor]
217        public NSGA3(StorableConstructorFlag _) : base(_) { }
218
219        // Each clonable item must have a cloning ctor (deep cloning, the cloner is used to handle
220        // cyclic object references). Don't forget to call the cloning ctor of the base class
221        public NSGA3(NSGA3 original, Cloner cloner) : base(original, cloner)
222        {
223            // todo: don't forget to clone storable fields
224            random = cloner.Clone(original.random);
225            solutions = original.solutions != null ? original.solutions.Select(cloner.Clone).ToList() : null;
226            referencePoints = original.referencePoints != null ? original.referencePoints.Select(r => {
227                var refPoint = new ReferencePoint(random, r.NumberOfDimensions);
228                r.Values.CopyTo(refPoint.Values, 0);
229                return refPoint;
230            }).ToList() : null;
231        }
232
233        public override IDeepCloneable Clone(Cloner cloner)
234        {
235            return new NSGA3(this, cloner);
236        }
237
238        #endregion Constructors
239
240        #region Initialization
241
242        protected override void Initialize(CancellationToken cancellationToken)
243        {
244            base.Initialize(cancellationToken);
245
246            int numberOfGeneratedReferencePoints = ReferencePoint.GetNumberOfGeneratedReferencePoints(NumberOfObjectives);
247            int pop = ((numberOfGeneratedReferencePoints + 3) / 4) * 4;
248            PopulationSize.Value = pop;
249            InitResults();
250            InitFields();
251            Analyze();
252        }
253
254        private void InitResults()
255        {
256            Results.Add(new Result(GeneratedReferencePointsResultName, "The initially generated reference points", new DoubleMatrix()));
257            Results.Add(new Result(CurrentFrontResultName, "The Pareto Front", new DoubleMatrix()));
258            Results.Add(new Result(CurrentGenerationResultName, "The current generation", new IntValue(1)));
259            Results.Add(new Result(GenerationalDistanceResultName, "The generational distance to an optimal pareto front defined in the Problem", new DoubleValue(double.NaN)));
260            Results.Add(new Result(InvertedGenerationalDistanceResultName, "The inverted generational distance to an optimal pareto front defined in the Problem", new DoubleValue(double.NaN)));
261            Results.Add(new Result(ScatterPlotResultName, "A scatterplot displaying the evaluated solutions and (if available) the analytically optimal front", new ParetoFrontScatterPlot()));
262
263            var problem = Problem as MultiObjectiveTestFunctionProblem;
264            if (problem == null) return;
265            // todo: add BestKnownFront parameter
266            ResultsScatterPlot = new ParetoFrontScatterPlot(new double[0][], new double[0][], problem.BestKnownFront.ToJaggedArray(), problem.Objectives, problem.ProblemSize);
267        }
268
269        private void InitFields()
270        {
271            random = new MersenneTwister();
272            InitSolutions();
273            InitReferencePoints();
274        }
275        private void InitReferencePoints()
276        {
277            // Generate reference points and add them to results
278            referencePoints = ReferencePoint.GenerateReferencePoints(random, NumberOfObjectives);
279            ResultsGeneratedReferencePoints = Utility.ConvertToDoubleMatrix(referencePoints);
280        }
281
282
283        private void InitSolutions()
284        {
285            int minBound = 0;
286            int maxBound = 1;
287
288            // Initialise solutions
289            solutions = new List<Solution>(PopulationSize.Value);
290            for (int i = 0; i < PopulationSize.Value; i++)
291            {
292                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);
296            }
297        }
298
299        #endregion Initialization
300
301        #region Overriden Methods
302
303        protected override void Run(CancellationToken cancellationToken)
304        {
305            while (ResultsCurrentGeneration.Value < MaximumGenerations.Value)
306            {
307
308                try
309                {
310                    List<Solution> qt = Mutate(Recombine(solutions));
311                    List<Solution> rt = Utility.Concat(solutions, qt);
312
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);
316
317                    ResultsCurrentGeneration.Value++;
318                    Analyze();
319                }
320                catch (Exception ex)
321                {
322                    throw new Exception($"Failed in generation {ResultsCurrentGeneration}", ex);
323                }
324            }
325        }
326
327        #endregion Overriden Methods
328
329        #region Private Methods
330
331        private List<ReferencePoint> GetCopyOfReferencePoints()
332        {
333            if (referencePoints == null) return null;
334
335            List<ReferencePoint> referencePointsCopy = new List<ReferencePoint>();
336            foreach (var referencePoint in referencePoints)
337                referencePointsCopy.Add(new ReferencePoint(referencePoint));
338
339            return referencePointsCopy;
340        }
341
342        private void Analyze()
343        {
344            ResultsScatterPlot = new ParetoFrontScatterPlot(solutions.Select(x => x.Fitness).ToArray(), solutions.Select(x => x.Chromosome.ToArray()).ToArray(), ResultsScatterPlot.ParetoFront, ResultsScatterPlot.Objectives, ResultsScatterPlot.ProblemSize);
345            ResultsSolutions = solutions.Select(s => s.Chromosome.ToArray()).ToMatrix();
346
347            var problem = Problem as MultiObjectiveTestFunctionProblem;
348            if (problem == null) return;
349
350            ResultsGenerationalDistance = new DoubleValue(problem.BestKnownFront != null ? GenerationalDistance.Calculate(solutions.Select(s => s.Fitness), problem.BestKnownFront.ToJaggedArray(), 1) : double.NaN);
351            ResultsInvertedGenerationalDistance = new DoubleValue(problem.BestKnownFront != null ? InvertedGenerationalDistance.Calculate(solutions.Select(s => s.Fitness), problem.BestKnownFront.ToJaggedArray(), 1) : double.NaN);
352
353            Problem.Analyze(
354                solutions.Select(s => (Individual)new SingleEncodingIndividual(Problem.Encoding, new Scope { Variables = { new Variable(Problem.Encoding.Name, s.Chromosome) } })).ToArray(),
355                solutions.Select(s => s.Fitness).ToArray(),
356                Results,
357                random
358                );
359        }
360
361        /// <summary>
362        /// Returns the fitness of the given <paramref name="chromosome" /> by applying the Evaluate
363        /// method of the Problem.
364        /// </summary>
365        /// <param name="chromosome"></param>
366        /// <returns></returns>
367        private double[] Evaluate(RealVector chromosome)
368        {
369            return Problem.Evaluate(new SingleEncodingIndividual(Problem.Encoding, new Scope { Variables = { new Variable(Problem.Encoding.Name, chromosome) } }), random);
370        }
371
372        private List<Solution> Recombine(List<Solution> solutions)
373        {
374            List<Solution> childSolutions = new List<Solution>();
375
376            for (int i = 0; i < solutions.Count; i += 2)
377            {
378                int parentIndex1 = random.Next(solutions.Count);
379                int parentIndex2 = random.Next(solutions.Count);
380                // ensure that the parents are not the same object
381                if (parentIndex1 == parentIndex2) parentIndex2 = (parentIndex2 + 1) % solutions.Count;
382                var parent1 = solutions[parentIndex1];
383                var parent2 = solutions[parentIndex2];
384
385                // 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);
396            }
397
398            return childSolutions;
399        }
400
401        private List<Solution> Mutate(List<Solution> solutions)
402        {
403            foreach (var solution in solutions)
404            {
405                UniformOnePositionManipulator.Apply(random, solution.Chromosome, Problem.Encoding.Bounds);
406            }
407            return solutions;
408        }
409
410        #endregion Private Methods
411    }
412}
Note: See TracBrowser for help on using the repository browser.