source: branches/2987_MOEAD_Algorithm/HeuristicLab.Algorithms.MOEAD/3.4/MOEADAlgorithmBase.cs @ 16688

Last change on this file since 16688 was 16688, checked in by bburlacu, 3 months ago

#2987: Eliminate unnecessary cloning. Update to HEAL.Attic-pre4, fix AssemblyTitle

File size: 31.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2019 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using HEAL.Attic;
23using HeuristicLab.Analysis;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.ExpressionGenerator;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Problems.DataAnalysis;
31using HeuristicLab.Problems.TestFunctions.MultiObjective;
32using HeuristicLab.Random;
33using System;
34using System.Collections.Generic;
35using System.Drawing;
36using System.Linq;
37using CancellationToken = System.Threading.CancellationToken;
38
39namespace HeuristicLab.Algorithms.MOEAD {
40  [Item("MOEADAlgorithmBase", "Base class for all MOEA/D algorithm variants.")]
41  [StorableType("E00BAC79-C6F9-42B6-8468-DEEC7FFCE804")]
42  public abstract class MOEADAlgorithmBase : BasicAlgorithm {
43    #region data members
44    [StorableType("C04DB21A-316F-4210-9CA7-A915BE8EBC96")]
45    protected enum NeighborType { NEIGHBOR, POPULATION }
46
47    [StorableType("FE35F480-E522-45E0-A229-99E61DA7B8BC")]
48    // TCHE = Chebyshev (Tchebyshev)
49    // PBI  = Penalty-based boundary intersection
50    // AGG  = Weighted sum
51    public enum FunctionType { TCHE, PBI, AGG }
52
53    [Storable]
54    protected double[] IdealPoint { get; set; }
55    [Storable]
56    protected double[] NadirPoint { get; set; } // potentially useful for objective normalization
57
58    [Storable]
59    protected double[][] lambda;
60
61    [Storable]
62    protected int[][] neighbourhood;
63
64    [Storable]
65    protected IMOEADSolution[] solutions;
66
67    [Storable]
68    protected FunctionType functionType;
69
70    [Storable]
71    protected IMOEADSolution[] population;
72
73    [Storable]
74    protected IMOEADSolution[] offspringPopulation;
75
76    [Storable]
77    protected IMOEADSolution[] jointPopulation;
78
79    [Storable]
80    protected int evaluatedSolutions;
81
82    [Storable]
83    protected ExecutionContext executionContext;
84
85    [Storable]
86    protected IScope globalScope;
87
88    [Storable]
89    protected ExecutionState previousExecutionState;
90
91    [Storable]
92    protected ExecutionState executionState;
93    #endregion
94
95    #region parameters
96    private const string SeedParameterName = "Seed";
97    private const string SetSeedRandomlyParameterName = "SetSeedRandomly";
98    private const string PopulationSizeParameterName = "PopulationSize";
99    private const string ResultPopulationSizeParameterName = "ResultPopulationSize";
100    private const string CrossoverProbabilityParameterName = "CrossoverProbability";
101    private const string CrossoverParameterName = "Crossover";
102    private const string MutationProbabilityParameterName = "MutationProbability";
103    private const string MutatorParameterName = "Mutator";
104    private const string MaximumEvaluatedSolutionsParameterName = "MaximumEvaluatedSolutions";
105    private const string RandomParameterName = "Random";
106    private const string AnalyzerParameterName = "Analyzer";
107    // MOEA-D parameters
108    private const string NeighbourSizeParameterName = "NeighbourSize";
109    private const string NeighbourhoodSelectionProbabilityParameterName = "NeighbourhoodSelectionProbability";
110    private const string MaximumNumberOfReplacedSolutionsParameterName = "MaximumNumberOfReplacedSolutions";
111    private const string FunctionTypeParameterName = "FunctionType";
112    private const string NormalizeObjectivesParameterName = "NormalizeObjectives";
113
114    public IValueParameter<MultiAnalyzer> AnalyzerParameter {
115      get { return (ValueParameter<MultiAnalyzer>)Parameters[AnalyzerParameterName]; }
116    }
117
118    public IConstrainedValueParameter<StringValue> FunctionTypeParameter {
119      get { return (IConstrainedValueParameter<StringValue>)Parameters[FunctionTypeParameterName]; }
120    }
121    public IFixedValueParameter<IntValue> NeighbourSizeParameter {
122      get { return (IFixedValueParameter<IntValue>)Parameters[NeighbourSizeParameterName]; }
123    }
124    public IFixedValueParameter<BoolValue> NormalizeObjectivesParameter {
125      get { return (IFixedValueParameter<BoolValue>)Parameters[NormalizeObjectivesParameterName]; }
126    }
127    public IFixedValueParameter<IntValue> MaximumNumberOfReplacedSolutionsParameter {
128      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumNumberOfReplacedSolutionsParameterName]; }
129    }
130    public IFixedValueParameter<DoubleValue> NeighbourhoodSelectionProbabilityParameter {
131      get { return (IFixedValueParameter<DoubleValue>)Parameters[NeighbourhoodSelectionProbabilityParameterName]; }
132    }
133    public IFixedValueParameter<IntValue> SeedParameter {
134      get { return (IFixedValueParameter<IntValue>)Parameters[SeedParameterName]; }
135    }
136    public IFixedValueParameter<BoolValue> SetSeedRandomlyParameter {
137      get { return (IFixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; }
138    }
139    private IValueParameter<IntValue> PopulationSizeParameter {
140      get { return (IValueParameter<IntValue>)Parameters[PopulationSizeParameterName]; }
141    }
142    private IValueParameter<IntValue> ResultPopulationSizeParameter {
143      get { return (IValueParameter<IntValue>)Parameters[ResultPopulationSizeParameterName]; }
144    }
145    public IValueParameter<PercentValue> CrossoverProbabilityParameter {
146      get { return (IValueParameter<PercentValue>)Parameters[CrossoverProbabilityParameterName]; }
147    }
148    public IConstrainedValueParameter<ICrossover> CrossoverParameter {
149      get { return (IConstrainedValueParameter<ICrossover>)Parameters[CrossoverParameterName]; }
150    }
151    public IValueParameter<PercentValue> MutationProbabilityParameter {
152      get { return (IValueParameter<PercentValue>)Parameters[MutationProbabilityParameterName]; }
153    }
154    public IConstrainedValueParameter<IManipulator> MutatorParameter {
155      get { return (IConstrainedValueParameter<IManipulator>)Parameters[MutatorParameterName]; }
156    }
157    public IValueParameter<IntValue> MaximumEvaluatedSolutionsParameter {
158      get { return (IValueParameter<IntValue>)Parameters[MaximumEvaluatedSolutionsParameterName]; }
159    }
160    public IValueParameter<IRandom> RandomParameter {
161      get { return (IValueParameter<IRandom>)Parameters[RandomParameterName]; }
162    }
163    #endregion
164
165    #region parameter properties
166    public new IMultiObjectiveHeuristicOptimizationProblem Problem {
167      get { return (IMultiObjectiveHeuristicOptimizationProblem)base.Problem; }
168      set { base.Problem = value; }
169    }
170    public int Seed {
171      get { return SeedParameter.Value.Value; }
172      set { SeedParameter.Value.Value = value; }
173    }
174    public bool SetSeedRandomly {
175      get { return SetSeedRandomlyParameter.Value.Value; }
176      set { SetSeedRandomlyParameter.Value.Value = value; }
177    }
178    public bool NormalizeObjectives {
179      get { return NormalizeObjectivesParameter.Value.Value; }
180      set { NormalizeObjectivesParameter.Value.Value = value; }
181    }
182    public IntValue PopulationSize {
183      get { return PopulationSizeParameter.Value; }
184      set { PopulationSizeParameter.Value = value; }
185    }
186    public IntValue ResultPopulationSize {
187      get { return ResultPopulationSizeParameter.Value; }
188      set { ResultPopulationSizeParameter.Value = value; }
189    }
190    public PercentValue CrossoverProbability {
191      get { return CrossoverProbabilityParameter.Value; }
192      set { CrossoverProbabilityParameter.Value = value; }
193    }
194    public ICrossover Crossover {
195      get { return CrossoverParameter.Value; }
196      set { CrossoverParameter.Value = value; }
197    }
198    public PercentValue MutationProbability {
199      get { return MutationProbabilityParameter.Value; }
200      set { MutationProbabilityParameter.Value = value; }
201    }
202    public IManipulator Mutator {
203      get { return MutatorParameter.Value; }
204      set { MutatorParameter.Value = value; }
205    }
206    public MultiAnalyzer Analyzer {
207      get { return AnalyzerParameter.Value; }
208      set { AnalyzerParameter.Value = value; }
209    }
210    public IntValue MaximumEvaluatedSolutions {
211      get { return MaximumEvaluatedSolutionsParameter.Value; }
212      set { MaximumEvaluatedSolutionsParameter.Value = value; }
213    }
214    public int NeighbourSize {
215      get { return NeighbourSizeParameter.Value.Value; }
216      set { NeighbourSizeParameter.Value.Value = value; }
217    }
218    public int MaximumNumberOfReplacedSolutions {
219      get { return MaximumNumberOfReplacedSolutionsParameter.Value.Value; }
220      set { MaximumNumberOfReplacedSolutionsParameter.Value.Value = value; }
221    }
222    public double NeighbourhoodSelectionProbability {
223      get { return NeighbourhoodSelectionProbabilityParameter.Value.Value; }
224      set { NeighbourhoodSelectionProbabilityParameter.Value.Value = value; }
225    }
226    #endregion
227
228    #region constructors
229    public MOEADAlgorithmBase() {
230      Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
231      Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
232      Parameters.Add(new ValueParameter<IntValue>(PopulationSizeParameterName, "The size of the population of solutions.", new IntValue(100)));
233      Parameters.Add(new ValueParameter<IntValue>(ResultPopulationSizeParameterName, "The size of the population of solutions.", new IntValue(100)));
234      Parameters.Add(new ValueParameter<PercentValue>(CrossoverProbabilityParameterName, "The probability that the crossover operator is applied.", new PercentValue(0.9)));
235      Parameters.Add(new ConstrainedValueParameter<ICrossover>(CrossoverParameterName, "The operator used to cross solutions."));
236      Parameters.Add(new ValueParameter<PercentValue>(MutationProbabilityParameterName, "The probability that the mutation operator is applied on a solution.", new PercentValue(0.25)));
237      Parameters.Add(new ConstrainedValueParameter<IManipulator>(MutatorParameterName, "The operator used to mutate solutions."));
238      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each generation.", new MultiAnalyzer()));
239      Parameters.Add(new ValueParameter<IntValue>(MaximumEvaluatedSolutionsParameterName, "The maximum number of evaluated solutions (approximately).", new IntValue(100_000)));
240      Parameters.Add(new ValueParameter<IRandom>(RandomParameterName, new FastRandom()));
241      Parameters.Add(new FixedValueParameter<IntValue>(NeighbourSizeParameterName, new IntValue(20)));
242      Parameters.Add(new FixedValueParameter<IntValue>(MaximumNumberOfReplacedSolutionsParameterName, new IntValue(2)));
243      Parameters.Add(new FixedValueParameter<DoubleValue>(NeighbourhoodSelectionProbabilityParameterName, new DoubleValue(0.1)));
244      Parameters.Add(new FixedValueParameter<BoolValue>(NormalizeObjectivesParameterName, new BoolValue(true)));
245
246      var functionTypeParameter = new ConstrainedValueParameter<StringValue>(FunctionTypeParameterName);
247      foreach (var s in new[] { "Chebyshev", "PBI", "Weighted Sum" }) {
248        functionTypeParameter.ValidValues.Add(new StringValue(s));
249      }
250      Parameters.Add(functionTypeParameter);
251    }
252
253    protected MOEADAlgorithmBase(MOEADAlgorithmBase original, Cloner cloner) : base(original, cloner) {
254      functionType = original.functionType;
255      evaluatedSolutions = original.evaluatedSolutions;
256      previousExecutionState = original.previousExecutionState;
257
258      if (original.IdealPoint != null) {
259        IdealPoint = (double[])original.IdealPoint.Clone();
260      }
261
262      if (original.NadirPoint != null) {
263        NadirPoint = (double[])original.NadirPoint.Clone();
264      }
265
266      if (original.lambda != null) {
267        lambda = (double[][])original.lambda.Clone();
268      }
269
270      if (original.neighbourhood != null) {
271        neighbourhood = (int[][])original.neighbourhood.Clone();
272      }
273
274      if (original.solutions != null) {
275        solutions = original.solutions.Select(cloner.Clone).ToArray();
276      }
277
278      if (original.population != null) {
279        population = original.population.Select(cloner.Clone).ToArray();
280      }
281
282      if (original.offspringPopulation != null) {
283        offspringPopulation = original.offspringPopulation.Select(cloner.Clone).ToArray();
284      }
285
286      if (original.jointPopulation != null) {
287        jointPopulation = original.jointPopulation.Select(x => cloner.Clone(x)).ToArray();
288      }
289
290      if (original.executionContext != null) {
291        executionContext = cloner.Clone(original.executionContext);
292      }
293
294      if (original.globalScope != null) {
295        globalScope = cloner.Clone(original.globalScope);
296      }
297    }
298
299
300    [StorableHook(HookType.AfterDeserialization)]
301    private void AfterDeserialization() {
302      if (!Parameters.ContainsKey(NormalizeObjectivesParameterName)) {
303        Parameters.Add(new FixedValueParameter<BoolValue>(NormalizeObjectivesParameterName, new BoolValue(true)));
304      }
305    }
306
307    [StorableConstructor]
308    protected MOEADAlgorithmBase(StorableConstructorFlag deserializing) : base(deserializing) { }
309    #endregion
310
311    private void InitializePopulation(ExecutionContext executionContext, CancellationToken cancellationToken, IRandom random, bool[] maximization) {
312      var creator = Problem.SolutionCreator;
313      var evaluator = Problem.Evaluator;
314
315      var dimensions = maximization.Length;
316      var populationSize = PopulationSize.Value;
317      population = new IMOEADSolution[populationSize];
318
319      var parentScope = executionContext.Scope;
320      // first, create all individuals
321      for (int i = 0; i < populationSize; ++i) {
322        var childScope = new Scope(i.ToString()) { Parent = parentScope };
323        ExecuteOperation(executionContext, cancellationToken, executionContext.CreateChildOperation(creator, childScope));
324        parentScope.SubScopes.Add(childScope);
325      }
326
327      // then, evaluate them and update qualities
328      for (int i = 0; i < populationSize; ++i) {
329        var childScope = parentScope.SubScopes[i];
330        ExecuteOperation(executionContext, cancellationToken, executionContext.CreateChildOperation(evaluator, childScope));
331
332        var qualities = (DoubleArray)childScope.Variables["Qualities"].Value;
333        var solution = new MOEADSolution(childScope, dimensions, 0);
334        for (int j = 0; j < dimensions; ++j) {
335          solution.Qualities[j] = maximization[j] ? 1 - qualities[j] : qualities[j];
336        }
337        population[i] = solution;
338      }
339    }
340
341    protected void InitializeAlgorithm(CancellationToken cancellationToken) {
342      var rand = RandomParameter.Value;
343      if (SetSeedRandomly) Seed = RandomSeedGenerator.GetSeed();
344      rand.Reset(Seed);
345
346      bool[] maximization = ((BoolArray)Problem.MaximizationParameter.ActualValue).CloneAsArray();
347      var dimensions = maximization.Length;
348
349      var populationSize = PopulationSize.Value;
350
351      InitializePopulation(executionContext, cancellationToken, rand, maximization);
352      InitializeUniformWeights(rand, populationSize, dimensions);
353      InitializeNeighbourHood(lambda, populationSize, NeighbourSize);
354
355      //IdealPoint = Enumerable.Repeat(double.MaxValue, dimensions).ToArray();
356      IdealPoint = new double[dimensions];
357      IdealPoint.UpdateIdeal(population);
358
359      NadirPoint = Enumerable.Repeat(double.MinValue, dimensions).ToArray();
360      //NadirPoint = new double[dimensions];
361      NadirPoint.UpdateNadir(population);
362
363      var functionTypeString = FunctionTypeParameter.Value.Value;
364      switch (functionTypeString) {
365        case "Chebyshev":
366          functionType = FunctionType.TCHE;
367          break;
368        case "PBI":
369          functionType = FunctionType.PBI;
370          break;
371        case "Weighted Sum":
372          functionType = FunctionType.AGG;
373          break;
374      }
375
376      evaluatedSolutions = populationSize;
377    }
378
379    protected override void Initialize(CancellationToken cancellationToken) {
380      globalScope = new Scope("Global Scope");
381      executionContext = new ExecutionContext(null, this, globalScope);
382
383      // set the execution context for parameters to allow lookup
384      foreach (var parameter in Problem.Parameters.OfType<IValueParameter>()) {
385        // we need all of these in order for the wiring of the operators to work
386        globalScope.Variables.Add(new Variable(parameter.Name, parameter.Value));
387      }
388      globalScope.Variables.Add(new Variable("Results", Results)); // make results available as a parameter for analyzers etc.
389
390      base.Initialize(cancellationToken);
391    }
392
393    public override bool SupportsPause => true;
394
395    protected void InitializeUniformWeights(IRandom random, int populationSize, int dimensions) {
396      lambda = Enumerable.Range(0, populationSize).Select(_ => GenerateSample(random, dimensions)).ToArray();
397    }
398
399    // implements random number generation from https://en.wikipedia.org/wiki/Dirichlet_distribution#Random_number_generation
400    private double[] GenerateSample(IRandom random, int dim) {
401      var sum = 0d;
402      var sample = new double[dim];
403      for (int i = 0; i < dim; ++i) {
404        sample[i] = GammaDistributedRandom.NextDouble(random, 1, 1);
405        sum += sample[i];
406      }
407      for (int i = 0; i < dim; ++i) {
408        sample[i] /= sum;
409      }
410      return sample;
411    }
412
413    protected void InitializeNeighbourHood(double[][] lambda, int populationSize, int neighbourSize) {
414      neighbourhood = new int[populationSize][];
415
416      var x = new double[populationSize];
417      var idx = new int[populationSize];
418
419      for (int i = 0; i < populationSize; ++i) {
420        for (int j = 0; j < populationSize; ++j) {
421          x[j] = MOEADUtil.EuclideanDistance(lambda[i], lambda[j]);
422          idx[j] = j;
423        }
424
425        MOEADUtil.MinFastSort(x, idx, populationSize, neighbourSize);
426        neighbourhood[i] = (int[])idx.Clone();
427      }
428    }
429
430    protected NeighborType ChooseNeighborType(IRandom random, double neighbourhoodSelectionProbability) {
431      return random.NextDouble() < neighbourhoodSelectionProbability
432        ? NeighborType.NEIGHBOR
433        : NeighborType.POPULATION;
434    }
435
436    protected IList<IMOEADSolution> ParentSelection(IRandom random, int subProblemId, NeighborType neighbourType) {
437      List<int> matingPool = MatingSelection(random, subProblemId, 2, neighbourType);
438
439      var parents = new IMOEADSolution[3];
440
441      parents[0] = population[matingPool[0]];
442      parents[1] = population[matingPool[1]];
443      parents[2] = population[subProblemId];
444
445      return parents;
446    }
447
448    protected List<int> MatingSelection(IRandom random, int subproblemId, int numberOfSolutionsToSelect, NeighborType neighbourType) {
449      int populationSize = PopulationSize.Value;
450
451      var listOfSolutions = new List<int>(numberOfSolutionsToSelect);
452
453      int neighbourSize = neighbourhood[subproblemId].Length;
454      while (listOfSolutions.Count < numberOfSolutionsToSelect) {
455        var selectedSolution = neighbourType == NeighborType.NEIGHBOR
456          ? neighbourhood[subproblemId][random.Next(neighbourSize)]
457          : random.Next(populationSize);
458
459        bool flag = true;
460        foreach (int individualId in listOfSolutions) {
461          if (individualId == selectedSolution) {
462            flag = false;
463            break;
464          }
465        }
466
467        if (flag) {
468          listOfSolutions.Add(selectedSolution);
469        }
470      }
471
472      return listOfSolutions;
473    }
474
475    protected void UpdateNeighbourHood(IRandom random, IMOEADSolution individual, int subProblemId, NeighborType neighbourType, int maximumNumberOfReplacedSolutions, bool normalizeObjectives = false) {
476      int replacedSolutions = 0;
477      int size = neighbourType == NeighborType.NEIGHBOR ? NeighbourSize : population.Length;
478
479      foreach (var i in Enumerable.Range(0, size).Shuffle(random)) {
480        int k = neighbourType == NeighborType.NEIGHBOR ? neighbourhood[subProblemId][i] : i;
481
482        double f1 = CalculateFitness(population[k].Qualities, lambda[k], normalizeObjectives);
483        double f2 = CalculateFitness(individual.Qualities, lambda[k], normalizeObjectives);
484
485        if (f2 < f1) {
486          population[k] = individual;
487          replacedSolutions++;
488        }
489
490        if (replacedSolutions >= maximumNumberOfReplacedSolutions) {
491          return;
492        }
493      }
494    }
495
496    private double CalculateFitness(double[] qualities, double[] lambda, bool normalizeObjectives = false) {
497      int dim = qualities.Length;
498      switch (functionType) {
499        case FunctionType.TCHE: {
500            double maxFun = double.MinValue;
501
502            for (int n = 0; n < dim; n++) {
503              // deal with NaN and Infinity
504              var q = qualities[n];
505              if (double.IsNaN(q) || double.IsInfinity(q)) {
506                q = NadirPoint[n];
507              }
508              q -= IdealPoint[n];
509
510              if (normalizeObjectives) {
511                q /= NadirPoint[n] - IdealPoint[n];
512              }
513
514              var l = lambda[n].IsAlmost(0) ? 1e-4 : lambda[n];
515              var feval = l * Math.Abs(q);
516
517              if (feval > maxFun) {
518                maxFun = feval;
519              }
520            }
521
522            return maxFun;
523          }
524        case FunctionType.AGG: {
525            double sum = 0.0;
526            for (int n = 0; n < dim; n++) {
527              sum += lambda[n] * qualities[n];
528            }
529            return sum;
530          }
531        case FunctionType.PBI: {
532            double d1, d2, nl;
533            double theta = 5.0;
534            int dimensions = dim;
535
536            d1 = d2 = nl = 0.0;
537
538            for (int i = 0; i < dimensions; i++) {
539              d1 += (qualities[i] - IdealPoint[i]) * lambda[i];
540              nl += Math.Pow(lambda[i], 2.0);
541            }
542            nl = Math.Sqrt(nl);
543            d1 = Math.Abs(d1) / nl;
544
545            for (int i = 0; i < dimensions; i++) {
546              d2 += Math.Pow((qualities[i] - IdealPoint[i]) - d1 * (lambda[i] / nl), 2.0);
547            }
548            d2 = Math.Sqrt(d2);
549            return d1 + theta * d2;
550          }
551        default: {
552            throw new ArgumentException($"Unknown function type: {functionType}");
553          }
554      }
555    }
556
557    public IList<IMOEADSolution> GetResult(IRandom random) {
558      var populationSize = PopulationSize.Value;
559      var resultPopulationSize = ResultPopulationSize.Value;
560
561      if (populationSize > resultPopulationSize) {
562        return MOEADUtil.GetSubsetOfEvenlyDistributedSolutions(random, population, resultPopulationSize);
563      } else {
564        return population;
565      }
566    }
567
568    protected void UpdateParetoFronts() {
569      var qualities = population.Select(x => Enumerable.Range(0, NadirPoint.Length).Select(i => x.Qualities[i] / NadirPoint[i]).ToArray()).ToArray();
570      var maximization = Enumerable.Repeat(false, IdealPoint.Length).ToArray(); // MOEA/D minimizes everything internally
571      var pf = DominationCalculator<IMOEADSolution>.CalculateBestParetoFront(population, qualities, maximization);
572
573      var n = (int)EnumerableExtensions.BinomialCoefficient(IdealPoint.Length, 2);
574      var hypervolumes = new DoubleMatrix(n == 1 ? 1 : n + 1, 2) { ColumnNames = new[] { "PF hypervolume", "PF size" } };
575      hypervolumes[0, 0] = Hypervolume.Calculate(pf.Select(x => x.Item2), Enumerable.Repeat(1d, NadirPoint.Length).ToArray(), maximization);
576      hypervolumes[0, 1] = pf.Count;
577      var elementNames = new List<string>() { "Pareto Front" };
578
579      ResultCollection results;
580      if (Results.ContainsKey("Hypervolume Analysis")) {
581        results = (ResultCollection)Results["Hypervolume Analysis"].Value;
582      } else {
583        results = new ResultCollection();
584        Results.AddOrUpdateResult("Hypervolume Analysis", results);
585      }
586
587      ScatterPlot sp;
588      if (IdealPoint.Length == 2) {
589        var points = pf.Select(x => new Point2D<double>(x.Item2[0], x.Item2[1]));
590        var r = OnlinePearsonsRCalculator.Calculate(points.Select(x => x.X), points.Select(x => x.Y), out OnlineCalculatorError error);
591        if (error != OnlineCalculatorError.None) { r = double.NaN; }
592        var resultName = "Pareto Front Analysis ";
593        if (!results.ContainsKey(resultName)) {
594          sp = new ScatterPlot() {
595            VisualProperties = {
596              XAxisMinimumAuto = false, XAxisMinimumFixedValue = 0d, XAxisMaximumAuto = false, XAxisMaximumFixedValue = 1d,
597              YAxisMinimumAuto = false, YAxisMinimumFixedValue = 0d, YAxisMaximumAuto = false, YAxisMaximumFixedValue = 1d
598            }
599          };
600          sp.Rows.Add(new ScatterPlotDataRow(resultName, "", points) { VisualProperties = { PointSize = 8 } });
601          results.AddOrUpdateResult(resultName, sp);
602        } else {
603          sp = (ScatterPlot)results[resultName].Value;
604          sp.Rows[resultName].Points.Replace(points);
605        }
606        sp.Name = $"Dimensions [0, 1], correlation: {r.ToString("N2")}";
607      } else if (IdealPoint.Length > 2) {
608        var indices = Enumerable.Range(0, IdealPoint.Length).ToArray();
609        var visualProperties = new ScatterPlotDataRowVisualProperties { PointSize = 8, Color = Color.LightGray };
610        var combinations = indices.Combinations(2).ToArray();
611        var maximization2d = new[] { false, false };
612        var solutions2d = pf.Select(x => x.Item1).ToArray();
613        for (int i = 0; i < combinations.Length; ++i) {
614          var c = combinations[i].ToArray();
615
616          // calculate the hypervolume in the 2d coordinate space
617          var reference2d = new[] { 1d, 1d };
618          var qualities2d = pf.Select(x => new[] { x.Item2[c[0]], x.Item2[c[1]] }).ToArray();
619          var pf2d = DominationCalculator<IMOEADSolution>.CalculateBestParetoFront(solutions2d, qualities2d, maximization2d);
620
621          hypervolumes[i + 1, 0] = pf2d.Count > 0 ? Hypervolume.Calculate(pf2d.Select(x => x.Item2), reference2d, maximization2d) : 0d;
622          hypervolumes[i + 1, 1] = pf2d.Count;
623
624          var resultName = $"Pareto Front Analysis [{c[0]}, {c[1]}]";
625          elementNames.Add(resultName);
626
627          var points = pf.Select(x => new Point2D<double>(x.Item2[c[0]], x.Item2[c[1]]));
628          var pf2dPoints = pf2d.Select(x => new Point2D<double>(x.Item2[0], x.Item2[1]));
629
630          if (!results.ContainsKey(resultName)) {
631            sp = new ScatterPlot() {
632              VisualProperties = {
633                XAxisMinimumAuto = false, XAxisMinimumFixedValue = 0d, XAxisMaximumAuto = false, XAxisMaximumFixedValue = 1d,
634                YAxisMinimumAuto = false, YAxisMinimumFixedValue = 0d, YAxisMaximumAuto = false, YAxisMaximumFixedValue = 1d
635              }
636            };
637            sp.Rows.Add(new ScatterPlotDataRow("Pareto Front", "", points) { VisualProperties = visualProperties });
638            sp.Rows.Add(new ScatterPlotDataRow($"Pareto Front [{c[0]}, {c[1]}]", "", pf2dPoints) { VisualProperties = { PointSize = 10, Color = Color.OrangeRed } });
639            results.AddOrUpdateResult(resultName, sp);
640          } else {
641            sp = (ScatterPlot)results[resultName].Value;
642            sp.Rows["Pareto Front"].Points.Replace(points);
643            sp.Rows[$"Pareto Front [{c[0]}, {c[1]}]"].Points.Replace(pf2dPoints);
644          }
645          var r = OnlinePearsonsRCalculator.Calculate(points.Select(x => x.X), points.Select(x => x.Y), out OnlineCalculatorError error);
646          var r2 = r * r;
647          sp.Name = $"Pareto Front [{c[0]}, {c[1]}], correlation: {r2.ToString("N2")}";
648        }
649      }
650      hypervolumes.RowNames = elementNames;
651      results.AddOrUpdateResult("Hypervolumes", hypervolumes);
652    }
653
654    #region operator wiring and events
655    protected void ExecuteOperation(ExecutionContext executionContext, CancellationToken cancellationToken, IOperation operation) {
656      Stack<IOperation> executionStack = new Stack<IOperation>();
657      executionStack.Push(operation);
658      while (executionStack.Count > 0) {
659        cancellationToken.ThrowIfCancellationRequested();
660        IOperation next = executionStack.Pop();
661        if (next is OperationCollection) {
662          OperationCollection coll = (OperationCollection)next;
663          for (int i = coll.Count - 1; i >= 0; i--)
664            if (coll[i] != null) executionStack.Push(coll[i]);
665        } else if (next is IAtomicOperation) {
666          IAtomicOperation op = (IAtomicOperation)next;
667          next = op.Operator.Execute((IExecutionContext)op, cancellationToken);
668          if (next != null) executionStack.Push(next);
669        }
670      }
671    }
672
673    private void UpdateAnalyzers() {
674      Analyzer.Operators.Clear();
675      if (Problem != null) {
676        foreach (IAnalyzer analyzer in Problem.Operators.OfType<IAnalyzer>()) {
677          foreach (IScopeTreeLookupParameter param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
678            param.Depth = 1;
679          Analyzer.Operators.Add(analyzer, analyzer.EnabledByDefault);
680        }
681      }
682    }
683
684    private void UpdateCrossovers() {
685      ICrossover oldCrossover = CrossoverParameter.Value;
686      CrossoverParameter.ValidValues.Clear();
687      ICrossover defaultCrossover = Problem.Operators.OfType<ICrossover>().FirstOrDefault();
688
689      foreach (ICrossover crossover in Problem.Operators.OfType<ICrossover>().OrderBy(x => x.Name))
690        CrossoverParameter.ValidValues.Add(crossover);
691
692      if (oldCrossover != null) {
693        ICrossover crossover = CrossoverParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldCrossover.GetType());
694        if (crossover != null) CrossoverParameter.Value = crossover;
695        else oldCrossover = null;
696      }
697      if (oldCrossover == null && defaultCrossover != null)
698        CrossoverParameter.Value = defaultCrossover;
699    }
700
701    private void UpdateMutators() {
702      IManipulator oldMutator = MutatorParameter.Value;
703      MutatorParameter.ValidValues.Clear();
704      IManipulator defaultMutator = Problem.Operators.OfType<IManipulator>().FirstOrDefault();
705
706      foreach (IManipulator mutator in Problem.Operators.OfType<IManipulator>().OrderBy(x => x.Name))
707        MutatorParameter.ValidValues.Add(mutator);
708
709      if (oldMutator != null) {
710        IManipulator mutator = MutatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMutator.GetType());
711        if (mutator != null) MutatorParameter.Value = mutator;
712        else oldMutator = null;
713      }
714
715      if (oldMutator == null && defaultMutator != null)
716        MutatorParameter.Value = defaultMutator;
717    }
718
719    protected override void OnProblemChanged() {
720      UpdateCrossovers();
721      UpdateMutators();
722      UpdateAnalyzers();
723      base.OnProblemChanged();
724    }
725
726    protected override void OnExecutionStateChanged() {
727      previousExecutionState = executionState;
728      executionState = ExecutionState;
729      base.OnExecutionStateChanged();
730    }
731
732    public void ClearState() {
733      solutions = null;
734      population = null;
735      offspringPopulation = null;
736      jointPopulation = null;
737      lambda = null;
738      neighbourhood = null;
739      if (executionContext != null && executionContext.Scope != null) {
740        executionContext.Scope.SubScopes.Clear();
741      }
742    }
743
744    protected override void OnStopped() {
745      ClearState();
746      base.OnStopped();
747    }
748    #endregion
749  }
750}
Note: See TracBrowser for help on using the repository browser.