Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2987_MOEAD_Algorithm/HeuristicLab.Algorithms.DataAnalysis/3.4/MoeaD/MOEADAlgorithmBase.cs @ 16557

Last change on this file since 16557 was 16557, checked in by bburlacu, 5 years ago

#2987: Branch HeuristicLab.Algorithms.DataAnalysis and add initial implementation.
File size: 20.5 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using HeuristicLab.Analysis;
5using HeuristicLab.Common;
6using HeuristicLab.Core;
7using HeuristicLab.Data;
8using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
9using HeuristicLab.Optimization;
10using HeuristicLab.Parameters;
11using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
12using HeuristicLab.Problems.DataAnalysis;
13using HeuristicLab.Problems.DataAnalysis.Symbolic;
14using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
15using HeuristicLab.Random;
16using CancellationToken = System.Threading.CancellationToken;
17
18namespace HeuristicLab.Algorithms.DataAnalysis.MoeaD {
19  [Item("MOEADAlgorithmBase", "Base class for all MOEA/D algorithm variants.")]
20  [StorableClass]
21  public abstract class MOEADAlgorithmBase : FixedDataAnalysisAlgorithm<ISymbolicDataAnalysisMultiObjectiveProblem> {
22    #region data members
23    protected enum NeighborType { NEIGHBOR, POPULATION }
24    // TCHE = Chebyshev (Tchebyshev)
25    // PBI  = Penalty-based boundary intersection
26    // AGG  = Weighted sum
27    public enum FunctionType { TCHE, PBI, AGG }
28
29    protected double[] IdealPoint { get; set; }
30    protected double[] NadirPoint { get; set; } // potentially useful for objective normalization
31
32    protected double[][] lambda;
33    protected int[][] neighbourhood;
34
35    protected IList<IMOEADSolution> solutions;
36    protected FunctionType functionType;
37
38    protected IList<IMOEADSolution> population;
39    protected IList<IMOEADSolution> offspringPopulation;
40    protected IList<IMOEADSolution> jointPopulation;
41    #endregion
42
43    #region parameters
44    private const string SeedParameterName = "Seed";
45    private const string SetSeedRandomlyParameterName = "SetSeedRandomly";
46    private const string PopulationSizeParameterName = "PopulationSize";
47    private const string ResultPopulationSizeParameterName = "ResultPopulationSize";
48    private const string CrossoverProbabilityParameterName = "CrossoverProbability";
49    private const string CrossoverParameterName = "Crossover";
50    private const string MutationProbabilityParameterName = "MutationProbability";
51    private const string MutatorParameterName = "Mutator";
52    private const string MaximumEvaluatedSolutionsParameterName = "MaximumEvaluatedSolutions";
53    private const string RandomParameterName = "Random";
54    private const string AnalyzerParameterName = "Analyzer";
55    // MOEA-D parameters
56    private const string NeighbourSizeParameterName = "NeighbourSize";
57    private const string NeighbourhoodSelectionProbabilityParameterName = "NeighbourhoodSelectionProbability";
58    private const string MaximumNumberOfReplacedSolutionsParameterName = "MaximumNumberOfReplacedSolutions";
59    private const string FunctionTypeParameterName = "FunctionType";
60
61    public IValueParameter<MultiAnalyzer> AnalyzerParameter {
62      get { return (ValueParameter<MultiAnalyzer>)Parameters[AnalyzerParameterName]; }
63    }
64
65    public IConstrainedValueParameter<StringValue> FunctionTypeParameter {
66      get { return (IConstrainedValueParameter<StringValue>)Parameters[FunctionTypeParameterName]; }
67    }
68    public IFixedValueParameter<IntValue> NeighbourSizeParameter {
69      get { return (IFixedValueParameter<IntValue>)Parameters[NeighbourSizeParameterName]; }
70    }
71    public IFixedValueParameter<IntValue> MaximumNumberOfReplacedSolutionsParameter {
72      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumNumberOfReplacedSolutionsParameterName]; }
73    }
74    public IFixedValueParameter<DoubleValue> NeighbourhoodSelectionProbabilityParameter {
75      get { return (IFixedValueParameter<DoubleValue>)Parameters[NeighbourhoodSelectionProbabilityParameterName]; }
76    }
77    public IFixedValueParameter<IntValue> SeedParameter {
78      get { return (IFixedValueParameter<IntValue>)Parameters[SeedParameterName]; }
79    }
80    public IFixedValueParameter<BoolValue> SetSeedRandomlyParameter {
81      get { return (IFixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; }
82    }
83    private IValueParameter<IntValue> PopulationSizeParameter {
84      get { return (IValueParameter<IntValue>)Parameters[PopulationSizeParameterName]; }
85    }
86    private IValueParameter<IntValue> ResultPopulationSizeParameter {
87      get { return (IValueParameter<IntValue>)Parameters[ResultPopulationSizeParameterName]; }
88    }
89    public IValueParameter<PercentValue> CrossoverProbabilityParameter {
90      get { return (IValueParameter<PercentValue>)Parameters[CrossoverProbabilityParameterName]; }
91    }
92    public IConstrainedValueParameter<ICrossover> CrossoverParameter {
93      get { return (IConstrainedValueParameter<ICrossover>)Parameters[CrossoverParameterName]; }
94    }
95    public IValueParameter<PercentValue> MutationProbabilityParameter {
96      get { return (IValueParameter<PercentValue>)Parameters[MutationProbabilityParameterName]; }
97    }
98    public IConstrainedValueParameter<IManipulator> MutatorParameter {
99      get { return (IConstrainedValueParameter<IManipulator>)Parameters[MutatorParameterName]; }
100    }
101    public IValueParameter<IntValue> MaximumEvaluatedSolutionsParameter {
102      get { return (IValueParameter<IntValue>)Parameters[MaximumEvaluatedSolutionsParameterName]; }
103    }
104    public IValueParameter<IRandom> RandomParameter {
105      get { return (IValueParameter<IRandom>)Parameters[RandomParameterName]; }
106    }
107    #endregion
108
109    #region parameter properties
110    public int Seed {
111      get { return SeedParameter.Value.Value; }
112      set { SeedParameter.Value.Value = value; }
113    }
114    public bool SetSeedRandomly {
115      get { return SetSeedRandomlyParameter.Value.Value; }
116      set { SetSeedRandomlyParameter.Value.Value = value; }
117    }
118    public IntValue PopulationSize {
119      get { return PopulationSizeParameter.Value; }
120      set { PopulationSizeParameter.Value = value; }
121    }
122    public IntValue ResultPopulationSize {
123      get { return ResultPopulationSizeParameter.Value; }
124      set { ResultPopulationSizeParameter.Value = value; }
125    }
126    public PercentValue CrossoverProbability {
127      get { return CrossoverProbabilityParameter.Value; }
128      set { CrossoverProbabilityParameter.Value = value; }
129    }
130    public ICrossover Crossover {
131      get { return CrossoverParameter.Value; }
132      set { CrossoverParameter.Value = value; }
133    }
134    public PercentValue MutationProbability {
135      get { return MutationProbabilityParameter.Value; }
136      set { MutationProbabilityParameter.Value = value; }
137    }
138    public IManipulator Mutator {
139      get { return MutatorParameter.Value; }
140      set { MutatorParameter.Value = value; }
141    }
142    public MultiAnalyzer Analyzer {
143      get { return AnalyzerParameter.Value; }
144      set { AnalyzerParameter.Value = value; }
145    }
146    public IntValue MaximumEvaluatedSolutions {
147      get { return MaximumEvaluatedSolutionsParameter.Value; }
148      set { MaximumEvaluatedSolutionsParameter.Value = value; }
149    }
150    public int NeighbourSize {
151      get { return NeighbourSizeParameter.Value.Value; }
152      set { NeighbourSizeParameter.Value.Value = value; }
153    }
154    public int MaximumNumberOfReplacedSolutions {
155      get { return MaximumNumberOfReplacedSolutionsParameter.Value.Value; }
156      set { MaximumNumberOfReplacedSolutionsParameter.Value.Value = value; }
157    }
158    public double NeighbourhoodSelectionProbability {
159      get { return NeighbourhoodSelectionProbabilityParameter.Value.Value; }
160      set { NeighbourhoodSelectionProbabilityParameter.Value.Value = value; }
161    }
162    #endregion
163
164    #region constructors
165    public MOEADAlgorithmBase() {
166      Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
167      Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
168      Parameters.Add(new ValueParameter<IntValue>(PopulationSizeParameterName, "The size of the population of solutions.", new IntValue(100)));
169      Parameters.Add(new ValueParameter<IntValue>(ResultPopulationSizeParameterName, "The size of the population of solutions.", new IntValue(100)));
170      Parameters.Add(new ValueParameter<PercentValue>(CrossoverProbabilityParameterName, "The probability that the crossover operator is applied.", new PercentValue(0.9)));
171      Parameters.Add(new ConstrainedValueParameter<ICrossover>(CrossoverParameterName, "The operator used to cross solutions."));
172      Parameters.Add(new ValueParameter<PercentValue>(MutationProbabilityParameterName, "The probability that the mutation operator is applied on a solution.", new PercentValue(0.25)));
173      Parameters.Add(new ConstrainedValueParameter<IManipulator>(MutatorParameterName, "The operator used to mutate solutions."));
174      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each generation.", new MultiAnalyzer()));
175      Parameters.Add(new ValueParameter<IntValue>(MaximumEvaluatedSolutionsParameterName, "The maximum number of evaluated solutions (approximately).", new IntValue(100_000)));
176      Parameters.Add(new ValueParameter<IRandom>(RandomParameterName, new MersenneTwister()));
177      Parameters.Add(new FixedValueParameter<IntValue>(NeighbourSizeParameterName, new IntValue(20)));
178      Parameters.Add(new FixedValueParameter<IntValue>(MaximumNumberOfReplacedSolutionsParameterName, new IntValue(2)));
179      Parameters.Add(new FixedValueParameter<DoubleValue>(NeighbourhoodSelectionProbabilityParameterName, new DoubleValue(0.1)));
180
181      var functionTypeParameter = new ConstrainedValueParameter<StringValue>(FunctionTypeParameterName);
182      foreach (var s in new[] { "Chebyshev", "PBI", "Weighted Sum" }) {
183        functionTypeParameter.ValidValues.Add(new StringValue(s));
184      }
185      Parameters.Add(functionTypeParameter);
186    }
187
188    protected MOEADAlgorithmBase(MOEADAlgorithmBase original, Cloner cloner) : base(original, cloner) {
189    }
190
191    [StorableConstructor]
192    protected MOEADAlgorithmBase(bool deserializing) : base(deserializing) { }
193    #endregion
194
195    public override bool SupportsPause => false;
196
197    protected void InitializeUniformWeights(IRandom random, int populationSize, int dimensions) {
198      if (dimensions > 2) {
199        throw new ArgumentException("The current implementation doesn't support more than 2 dimensions.");
200      }
201
202      lambda = new double[populationSize][];
203      var values = SequenceGenerator.GenerateSteps(0m, 1m, 1m / populationSize).ToArray();
204
205      for (int i = 0; i < populationSize; ++i) {
206        var w = (double)values[i];
207        lambda[i] = new[] { w, 1 - w };
208      }
209      lambda.ShuffleInPlace(random);
210    }
211
212    protected void InitializeNeighbourHood(double[][] lambda, int populationSize, int neighbourSize) {
213      neighbourhood = new int[populationSize][];
214
215      var x = new double[populationSize];
216      var idx = new int[populationSize];
217
218      for (int i = 0; i < populationSize; ++i) {
219        for (int j = 0; j < populationSize; ++j) {
220          x[j] = EuclideanDistance.GetDistance(lambda[i], lambda[j]);
221          idx[j] = j;
222        }
223
224        MOEADUtil.MinFastSort(x, idx, populationSize, neighbourSize);
225        neighbourhood[i] = (int[])idx.Clone();
226      }
227    }
228
229    protected NeighborType ChooseNeighborType(IRandom random, double neighbourhoodSelectionProbability) {
230      return random.NextDouble() < neighbourhoodSelectionProbability
231        ? NeighborType.NEIGHBOR
232        : NeighborType.POPULATION;
233    }
234
235    protected IList<IMOEADSolution> ParentSelection(IRandom random, int subProblemId, NeighborType neighbourType) {
236      List<int> matingPool = MatingSelection(random, subProblemId, 2, neighbourType);
237
238      var parents = new IMOEADSolution[3];
239
240      parents[0] = population[matingPool[0]];
241      parents[1] = population[matingPool[1]];
242      parents[2] = population[subProblemId];
243
244      return parents;
245    }
246
247    protected List<int> MatingSelection(IRandom random, int subproblemId, int numberOfSolutionsToSelect, NeighborType neighbourType) {
248      int populationSize = PopulationSize.Value;
249
250      var listOfSolutions = new List<int>(numberOfSolutionsToSelect);
251
252      int neighbourSize = neighbourhood[subproblemId].Length;
253      while (listOfSolutions.Count < numberOfSolutionsToSelect) {
254        var selectedSolution = neighbourType == NeighborType.NEIGHBOR
255          ? neighbourhood[subproblemId][random.Next(neighbourSize)]
256          : random.Next(populationSize);
257
258        bool flag = true;
259        foreach (int individualId in listOfSolutions) {
260          if (individualId == selectedSolution) {
261            flag = false;
262            break;
263          }
264        }
265
266        if (flag) {
267          listOfSolutions.Add(selectedSolution);
268        }
269      }
270
271      return listOfSolutions;
272    }
273
274    protected void UpdateNeighbourHood(IRandom random, IMOEADSolution individual, int subProblemId, NeighborType neighbourType) {
275      int replacedSolutions = 0;
276      int size = neighbourType == NeighborType.NEIGHBOR ? NeighbourSize : population.Count;
277
278      foreach (var i in Enumerable.Range(0, size).Shuffle(random)) {
279        int k = neighbourType == NeighborType.NEIGHBOR
280          ? neighbourhood[subProblemId][i]
281          : i;
282
283        double f1 = CalculateFitness(population[k].Qualities, lambda[k]);
284        double f2 = CalculateFitness(individual.Qualities, lambda[k]);
285
286        if (f2 < f1) {
287          population[k] = (IMOEADSolution)individual.Clone();
288          replacedSolutions++;
289        }
290
291        if (replacedSolutions >= MaximumNumberOfReplacedSolutions) {
292          return;
293        }
294      }
295    }
296
297    private double CalculateFitness(double[] qualities, double[] lambda) {
298      double fitness;
299      int dim = qualities.Length;
300      switch (functionType) {
301        case FunctionType.TCHE: {
302            double maxFun = -1.0e+30;
303
304            for (int n = 0; n < dim; n++) {
305              double diff = Math.Abs(qualities[n] - IdealPoint[n]);
306
307              double feval = lambda[n] == 0 ? 0.0001 * diff : diff * lambda[n];
308              if (feval > maxFun) {
309                maxFun = feval;
310              }
311            }
312
313            fitness = maxFun;
314            return fitness;
315          }
316        case FunctionType.AGG: {
317            double sum = 0.0;
318            for (int n = 0; n < dim; n++) {
319              sum += lambda[n] * qualities[n];
320            }
321
322            fitness = sum;
323            return fitness;
324          }
325        case FunctionType.PBI: {
326            double d1, d2, nl;
327            double theta = 5.0;
328            int dimensions = dim;
329
330            d1 = d2 = nl = 0.0;
331
332            for (int i = 0; i < dimensions; i++) {
333              d1 += (qualities[i] - IdealPoint[i]) * lambda[i];
334              nl += Math.Pow(lambda[i], 2.0);
335            }
336            nl = Math.Sqrt(nl);
337            d1 = Math.Abs(d1) / nl;
338
339            for (int i = 0; i < dimensions; i++) {
340              d2 += Math.Pow((qualities[i] - IdealPoint[i]) - d1 * (lambda[i] / nl), 2.0);
341            }
342            d2 = Math.Sqrt(d2);
343
344            fitness = (d1 + theta * d2);
345            return fitness;
346          }
347        default: {
348            throw new ArgumentException($"Unknown function type: {functionType}");
349          }
350      }
351    }
352
353    public IList<IMOEADSolution> GetResult(IRandom random) {
354      var populationSize = PopulationSize.Value;
355      var resultPopulationSize = ResultPopulationSize.Value;
356
357      if (populationSize > resultPopulationSize) {
358        return MOEADUtil.GetSubsetOfEvenlyDistributedSolutions(random, population, resultPopulationSize);
359      } else {
360        return population;
361      }
362    }
363
364    protected IMOEADSolution previousBest = null;
365    protected void UpdateBestSolution() {
366      var best = population.OrderBy(x => x.Qualities[0]).ThenBy(x => x.Qualities[1]).First();
367
368      if (previousBest == null
369        || best.Qualities[0] < previousBest.Qualities[0]
370        || (best.Qualities[0].IsAlmost(previousBest.Qualities[0]) && best.Qualities[1] < previousBest.Qualities[1])) {
371        previousBest = best;
372
373        var bestScope = (IScope)best.Individual.Clone();
374        var tree = (ISymbolicExpressionTree)bestScope.Variables["SymbolicExpressionTree"].Value;
375        var problemData = (IRegressionProblemData)Problem.ProblemData;
376        var model = new SymbolicRegressionModel(problemData.TargetVariable, tree, Problem.SymbolicExpressionTreeInterpreter);
377        model.Scale(problemData);
378        var solution = new SymbolicRegressionSolution(model, problemData);
379        Results.AddOrUpdateResult("Best training solution", solution);
380      }
381    }
382
383    protected void UpdateParetoFronts() {
384      bool dominates(Point2D<double> x, Point2D<double> y) => x.X <= y.X && x.Y <= y.Y;
385      // get all non-dominated points
386      var points = population.Select(x => new Point2D<double>(Math.Round(x.Qualities[0], 6), Math.Round(x.Qualities[1], 6))).OrderBy(_ => _.X).ThenBy(_ => _.Y).ToArray();
387      var dominated = new bool[points.Length];
388
389      for (int i = 0; i < points.Length; ++i) {
390        if (dominated[i]) { continue; }
391        for (int j = 0; j < points.Length; ++j) {
392          if (i == j) { continue; }
393          if (dominated[j]) { continue; }
394          dominated[j] = dominates(points[i], points[j]);
395        }
396      }
397
398      var pf = Enumerable.Range(0, dominated.Length).Where(x => !dominated[x]).Select(x => points[x]);
399
400      ScatterPlot sp;
401      if (!Results.ContainsKey("Pareto Front")) {
402        sp = new ScatterPlot();
403        sp.Rows.Add(new ScatterPlotDataRow("Pareto Front", "", pf) { VisualProperties = { PointSize = 5 } });
404        Results.AddOrUpdateResult("Pareto Front", sp);
405      } else {
406        sp = (ScatterPlot)Results["Pareto Front"].Value;
407        sp.Rows["Pareto Front"].Points.Replace(pf);
408      }
409    }
410
411    #region operator wiring
412    protected void ExecuteOperation(ExecutionContext executionContext, CancellationToken cancellationToken, IOperation operation) {
413      Stack<IOperation> executionStack = new Stack<IOperation>();
414      executionStack.Push(operation);
415      while (executionStack.Count > 0) {
416        cancellationToken.ThrowIfCancellationRequested();
417        IOperation next = executionStack.Pop();
418        if (next is OperationCollection) {
419          OperationCollection coll = (OperationCollection)next;
420          for (int i = coll.Count - 1; i >= 0; i--)
421            if (coll[i] != null) executionStack.Push(coll[i]);
422        } else if (next is IAtomicOperation) {
423          IAtomicOperation op = (IAtomicOperation)next;
424          next = op.Operator.Execute((IExecutionContext)op, cancellationToken);
425          if (next != null) executionStack.Push(next);
426        }
427      }
428    }
429
430    private void UpdateCrossovers() {
431      ICrossover oldCrossover = CrossoverParameter.Value;
432      CrossoverParameter.ValidValues.Clear();
433      ICrossover defaultCrossover = Problem.Operators.OfType<ICrossover>().FirstOrDefault();
434
435      foreach (ICrossover crossover in Problem.Operators.OfType<ICrossover>().OrderBy(x => x.Name))
436        CrossoverParameter.ValidValues.Add(crossover);
437
438      if (oldCrossover != null) {
439        ICrossover crossover = CrossoverParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldCrossover.GetType());
440        if (crossover != null) CrossoverParameter.Value = crossover;
441        else oldCrossover = null;
442      }
443      if (oldCrossover == null && defaultCrossover != null)
444        CrossoverParameter.Value = defaultCrossover;
445    }
446
447    private void UpdateMutators() {
448      IManipulator oldMutator = MutatorParameter.Value;
449      MutatorParameter.ValidValues.Clear();
450      IManipulator defaultMutator = Problem.Operators.OfType<IManipulator>().FirstOrDefault();
451
452      foreach (IManipulator mutator in Problem.Operators.OfType<IManipulator>().OrderBy(x => x.Name))
453        MutatorParameter.ValidValues.Add(mutator);
454
455      if (oldMutator != null) {
456        IManipulator mutator = MutatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMutator.GetType());
457        if (mutator != null) MutatorParameter.Value = mutator;
458        else oldMutator = null;
459      }
460
461      if (oldMutator == null && defaultMutator != null)
462        MutatorParameter.Value = defaultMutator;
463    }
464
465    protected override void OnProblemChanged() {
466      UpdateCrossovers();
467      UpdateMutators();
468      base.OnProblemChanged();
469    }
470    #endregion
471  }
472}
Note: See TracBrowser for help on using the repository browser.