Changeset 16649


Ignore:
Timestamp:
03/01/19 12:51:59 (5 months ago)
Author:
bburlacu
Message:

#2987: Prevent updating the Ideal and Nadir points with NaN or Infinity values. Simplify algorithm code (use arrays instead of lists). Add missing StorableType attributes. Add hypervolume analysis for the pareto fronts.

Location:
branches/2987_MOEAD_Algorithm/HeuristicLab.Algorithms.MOEAD/3.4
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • branches/2987_MOEAD_Algorithm/HeuristicLab.Algorithms.MOEAD/3.4/HeuristicLab.Algorithms.MOEAD-3.4.csproj

    r16630 r16649  
    171171  </ItemGroup>
    172172  <ItemGroup>
     173    <None Include="app.config" />
    173174    <None Include="HeuristicLab.snk" />
    174175    <None Include="packages.config" />
  • branches/2987_MOEAD_Algorithm/HeuristicLab.Algorithms.MOEAD/3.4/MOEADAlgorithmBase.cs

    r16630 r16649  
    2929using HeuristicLab.Parameters;
    3030using HeuristicLab.Problems.DataAnalysis;
     31using HeuristicLab.Problems.TestFunctions.MultiObjective;
    3132using HeuristicLab.Random;
    3233using System;
    3334using System.Collections.Generic;
     35using System.Drawing;
    3436using System.Linq;
    3537using CancellationToken = System.Threading.CancellationToken;
     
    4042  public abstract class MOEADAlgorithmBase : BasicAlgorithm {
    4143    #region data members
     44    [StorableType("C04DB21A-316F-4210-9CA7-A915BE8EBC96")]
    4245    protected enum NeighborType { NEIGHBOR, POPULATION }
     46
     47    [StorableType("FE35F480-E522-45E0-A229-99E61DA7B8BC")]
    4348    // TCHE = Chebyshev (Tchebyshev)
    4449    // PBI  = Penalty-based boundary intersection
     
    5863
    5964    [Storable]
    60     protected IList<IMOEADSolution> solutions;
     65    protected IMOEADSolution[] solutions;
    6166
    6267    [Storable]
     
    6469
    6570    [Storable]
    66     protected List<IMOEADSolution> population;
    67 
    68     [Storable]
    69     protected List<IMOEADSolution> offspringPopulation;
    70 
    71     [Storable]
    72     protected List<IMOEADSolution> jointPopulation;
     71    protected IMOEADSolution[] population;
     72
     73    [Storable]
     74    protected IMOEADSolution[] offspringPopulation;
     75
     76    [Storable]
     77    protected IMOEADSolution[] jointPopulation;
    7378
    7479    [Storable]
     
    232237      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each generation.", new MultiAnalyzer()));
    233238      Parameters.Add(new ValueParameter<IntValue>(MaximumEvaluatedSolutionsParameterName, "The maximum number of evaluated solutions (approximately).", new IntValue(100_000)));
    234       Parameters.Add(new ValueParameter<IRandom>(RandomParameterName, new MersenneTwister()));
     239      Parameters.Add(new ValueParameter<IRandom>(RandomParameterName, new FastRandom()));
    235240      Parameters.Add(new FixedValueParameter<IntValue>(NeighbourSizeParameterName, new IntValue(20)));
    236241      Parameters.Add(new FixedValueParameter<IntValue>(MaximumNumberOfReplacedSolutionsParameterName, new IntValue(2)));
     
    271276
    272277      if (original.population != null) {
    273         population = original.population.Select(cloner.Clone).ToList();
     278        population = original.population.Select(cloner.Clone).ToArray();
    274279      }
    275280
    276281      if (original.offspringPopulation != null) {
    277         offspringPopulation = original.offspringPopulation.Select(cloner.Clone).ToList();
     282        offspringPopulation = original.offspringPopulation.Select(cloner.Clone).ToArray();
    278283      }
    279284
    280285      if (original.jointPopulation != null) {
    281         jointPopulation = original.jointPopulation.Select(x => cloner.Clone(x)).ToList();
     286        jointPopulation = original.jointPopulation.Select(x => cloner.Clone(x)).ToArray();
    282287      }
    283288
     
    300305
    301306    [StorableConstructor]
    302     protected MOEADAlgorithmBase(StorableConstructorFlag _) : base(_) { }
     307    protected MOEADAlgorithmBase(StorableConstructorFlag deserializing) : base(deserializing) { }
    303308    #endregion
    304309
     
    309314      var dimensions = maximization.Length;
    310315      var populationSize = PopulationSize.Value;
    311       population = new List<IMOEADSolution>(populationSize);
     316      population = new IMOEADSolution[populationSize];
    312317
    313318      var parentScope = executionContext.Scope;
     
    329334          solution.Qualities[j] = maximization[j] ? 1 - qualities[j] : qualities[j];
    330335        }
    331         population.Add(solution);
     336        population[i] = solution;
    332337      }
    333338    }
     
    351356      IdealPoint.UpdateIdeal(population);
    352357
    353       //NadirPoint = Enumerable.Repeat(double.MinValue, dimensions).ToArray();
    354       NadirPoint = new double[dimensions];
     358      NadirPoint = Enumerable.Repeat(double.MinValue, dimensions).ToArray();
     359      //NadirPoint = new double[dimensions];
    355360      NadirPoint.UpdateNadir(population);
    356361
     
    469474    protected void UpdateNeighbourHood(IRandom random, IMOEADSolution individual, int subProblemId, NeighborType neighbourType) {
    470475      int replacedSolutions = 0;
    471       int size = neighbourType == NeighborType.NEIGHBOR ? NeighbourSize : population.Count;
     476      int size = neighbourType == NeighborType.NEIGHBOR ? NeighbourSize : population.Length;
    472477
    473478      foreach (var i in Enumerable.Range(0, size).Shuffle(random)) {
     
    491496
    492497    private double CalculateFitness(double[] qualities, double[] lambda) {
    493       double fitness;
    494498      int dim = qualities.Length;
    495499      switch (functionType) {
     
    510514            }
    511515
    512             fitness = maxFun;
    513             return fitness;
     516            return maxFun;
    514517          }
    515518        case FunctionType.AGG: {
     
    518521              sum += lambda[n] * qualities[n];
    519522            }
    520 
    521             fitness = sum;
    522             return fitness;
     523            return sum;
    523524          }
    524525        case FunctionType.PBI: {
     
    540541            }
    541542            d2 = Math.Sqrt(d2);
    542 
    543             fitness = (d1 + theta * d2);
    544             return fitness;
     543            return d1 + theta * d2;
    545544          }
    546545        default: {
     
    562561
    563562    protected void UpdateParetoFronts() {
    564       bool dominates(Point2D<double> x, Point2D<double> y) => x.X <= y.X && x.Y <= y.Y;
    565       // get all non-dominated points
    566       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();
    567       var dominated = new bool[points.Length];
    568 
    569       for (int i = 0; i < points.Length; ++i) {
    570         if (dominated[i]) { continue; }
    571         for (int j = 0; j < points.Length; ++j) {
    572           if (i == j) { continue; }
    573           if (dominated[j]) { continue; }
    574           dominated[j] = dominates(points[i], points[j]);
    575         }
    576       }
    577 
    578       var pf = Enumerable.Range(0, dominated.Length).Where(x => !dominated[x]).Select(x => points[x]);
     563      var qualities = population.Select(x => Enumerable.Range(0, NadirPoint.Length).Select(i => x.Qualities[i] / NadirPoint[i]).ToArray()).ToArray();
     564      var maximization = Enumerable.Repeat(false, IdealPoint.Length).ToArray(); // MOEA/D minimizes everything internally\
     565      var pf = DominationCalculator<IMOEADSolution>.CalculateBestParetoFront(population, qualities, maximization);
     566
     567      var n = (int)EnumerableExtensions.BinomialCoefficient(IdealPoint.Length, 2);
     568      var hypervolumes = new DoubleMatrix(n == 1 ? 1 : n + 1, 2) { ColumnNames = new[] { "PF hypervolume", "PF size" } };
     569      hypervolumes[0, 0] = Hypervolume.Calculate(pf.Select(x => x.Item2), Enumerable.Repeat(1d, NadirPoint.Length).ToArray(), maximization);
     570      hypervolumes[0, 1] = pf.Count;
     571      var elementNames = new List<string>() { "Pareto Front" };
     572
     573      ResultCollection results;
     574      if (Results.ContainsKey("Hypervolume Analysis")) {
     575        results = (ResultCollection)Results["Hypervolume Analysis"].Value;
     576      } else {
     577        results = new ResultCollection();
     578        Results.AddOrUpdateResult("Hypervolume Analysis", results);
     579      }
    579580
    580581      ScatterPlot sp;
    581       if (!Results.ContainsKey("Pareto Front")) {
    582         sp = new ScatterPlot();
    583         sp.Rows.Add(new ScatterPlotDataRow("Pareto Front", "", pf) { VisualProperties = { PointSize = 5 } });
    584         Results.AddOrUpdateResult("Pareto Front", sp);
    585       } else {
    586         sp = (ScatterPlot)Results["Pareto Front"].Value;
    587         sp.Rows["Pareto Front"].Points.Replace(pf);
    588       }
     582      if (IdealPoint.Length == 2) {
     583        var points = pf.Select(x => new Point2D<double>(x.Item2[0], x.Item2[1]));
     584        var r = OnlinePearsonsRCalculator.Calculate(points.Select(x => x.X), points.Select(x => x.Y), out OnlineCalculatorError error);
     585        if (error != OnlineCalculatorError.None) { r = double.NaN; }
     586        var resultName = "Pareto Front Analysis ";
     587        if (!results.ContainsKey(resultName)) {
     588          sp = new ScatterPlot() {
     589            VisualProperties = {
     590              XAxisMinimumAuto = false, XAxisMinimumFixedValue = 0d, XAxisMaximumAuto = false, XAxisMaximumFixedValue = 1d,
     591              YAxisMinimumAuto = false, YAxisMinimumFixedValue = 0d, YAxisMaximumAuto = false, YAxisMaximumFixedValue = 1d
     592            }
     593          };
     594          sp.Rows.Add(new ScatterPlotDataRow(resultName, "", points) { VisualProperties = { PointSize = 8 } });
     595          results.AddOrUpdateResult(resultName, sp);
     596        } else {
     597          sp = (ScatterPlot)results[resultName].Value;
     598          sp.Rows[resultName].Points.Replace(points);
     599        }
     600        sp.Name = $"Dimensions [0, 1], correlation: {r.ToString("N2")}";
     601      } else if (IdealPoint.Length > 2) {
     602        var indices = Enumerable.Range(0, IdealPoint.Length).ToArray();
     603        var visualProperties = new ScatterPlotDataRowVisualProperties { PointSize = 8, Color = Color.LightGray };
     604        var combinations = indices.Combinations(2).ToArray();
     605        var maximization2d = new[] { false, false };
     606        var solutions2d = pf.Select(x => x.Item1).ToArray();
     607        for (int i = 0; i < combinations.Length; ++i) {
     608          var c = combinations[i].ToArray();
     609
     610          // calculate the hypervolume in the 2d coordinate space
     611          var reference2d = new[] { 1d, 1d };
     612          var qualities2d = pf.Select(x => new[] { x.Item2[c[0]], x.Item2[c[1]] }).ToArray();
     613          var pf2d = DominationCalculator<IMOEADSolution>.CalculateBestParetoFront(solutions2d, qualities2d, maximization2d);
     614
     615          hypervolumes[i + 1, 0] = pf2d.Count > 0 ? Hypervolume.Calculate(pf2d.Select(x => x.Item2), reference2d, maximization2d) : 0d;
     616          hypervolumes[i + 1, 1] = pf2d.Count;
     617
     618          var resultName = $"Pareto Front Analysis [{c[0]}, {c[1]}]";
     619          elementNames.Add(resultName);
     620
     621          var points = pf.Select(x => new Point2D<double>(x.Item2[c[0]], x.Item2[c[1]]));
     622          var pf2dPoints = pf2d.Select(x => new Point2D<double>(x.Item2[0], x.Item2[1]));
     623
     624          if (!results.ContainsKey(resultName)) {
     625            sp = new ScatterPlot() {
     626              VisualProperties = {
     627                XAxisMinimumAuto = false, XAxisMinimumFixedValue = 0d, XAxisMaximumAuto = false, XAxisMaximumFixedValue = 1d,
     628                YAxisMinimumAuto = false, YAxisMinimumFixedValue = 0d, YAxisMaximumAuto = false, YAxisMaximumFixedValue = 1d
     629              }
     630            };
     631            sp.Rows.Add(new ScatterPlotDataRow("Pareto Front", "", points) { VisualProperties = visualProperties });
     632            sp.Rows.Add(new ScatterPlotDataRow($"Pareto Front [{c[0]}, {c[1]}]", "", pf2dPoints) { VisualProperties = { PointSize = 10, Color = Color.OrangeRed } });
     633            results.AddOrUpdateResult(resultName, sp);
     634          } else {
     635            sp = (ScatterPlot)results[resultName].Value;
     636            sp.Rows["Pareto Front"].Points.Replace(points);
     637            sp.Rows[$"Pareto Front [{c[0]}, {c[1]}]"].Points.Replace(pf2dPoints);
     638          }
     639          var r = OnlinePearsonsRCalculator.Calculate(points.Select(x => x.X), points.Select(x => x.Y), out OnlineCalculatorError error);
     640          if (error != OnlineCalculatorError.None) { r = double.NaN; }
     641          sp.Name = $"Pareto Front [{c[0]}, {c[1]}], correlation: {r.ToString("N2")}";
     642        }
     643      }
     644      hypervolumes.RowNames = elementNames;
     645      results.AddOrUpdateResult("Hypervolumes", hypervolumes);
    589646    }
    590647
     
    668725
    669726    public void ClearState() {
    670       if (solutions != null) {
    671         solutions.Clear();
    672       }
    673       if (population != null) {
    674         population.Clear();
    675       }
    676       if (offspringPopulation != null) {
    677         offspringPopulation.Clear();
    678       }
    679       if (jointPopulation != null) {
    680         jointPopulation.Clear();
    681       }
     727      solutions = null;
     728      population = null;
     729      offspringPopulation = null;
     730      jointPopulation = null;
    682731      lambda = null;
    683732      neighbourhood = null;
  • branches/2987_MOEAD_Algorithm/HeuristicLab.Algorithms.MOEAD/3.4/MOEADUtil.cs

    r16630 r16649  
    175175    public static void UpdateIdeal(this double[] idealPoint, double[] point) {
    176176      for (int i = 0; i < point.Length; ++i) {
     177        if (double.IsInfinity(point[i]) || double.IsNaN(point[i])) {
     178          continue;
     179        }
     180
    177181        if (idealPoint[i] > point[i]) {
    178182          idealPoint[i] = point[i];
     
    183187    public static void UpdateNadir(this double[] nadirPoint, double[] point) {
    184188      for (int i = 0; i < point.Length; ++i) {
     189        if (double.IsInfinity(point[i]) || double.IsNaN(point[i])) {
     190          continue;
     191        }
     192
    185193        if (nadirPoint[i] < point[i]) {
    186194          nadirPoint[i] = point[i];
Note: See TracChangeset for help on using the changeset viewer.