Changeset 16649 for branches/2987_MOEAD_Algorithm

Timestamp:

03/01/19 12:51:59 (6 years 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:

• HeuristicLab.Algorithms.MOEAD-3.4.csproj (modified) (1 diff)
• MOEADAlgorithmBase.cs (modified) (17 diffs)
• MOEADUtil.cs (modified) (2 diffs)
• app.config (added)

branches/2987_MOEAD_Algorithm/HeuristicLab.Algorithms.MOEAD/3.4/HeuristicLab.Algorithms.MOEAD-3.4.csproj

@@ -171 +171 @@
   </ItemGroup>
   <ItemGroup>
+    <None Include="app.config" />
     <None Include="HeuristicLab.snk" />
     <None Include="packages.config" />

branches/2987_MOEAD_Algorithm/HeuristicLab.Algorithms.MOEAD/3.4/MOEADAlgorithmBase.cs

@@ -29 +29 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Problems.DataAnalysis;
+using HeuristicLab.Problems.TestFunctions.MultiObjective;
 using HeuristicLab.Random;
 using System;
 using System.Collections.Generic;
+using System.Drawing;
 using System.Linq;
 using CancellationToken = System.Threading.CancellationToken;
@@ -40 +42 @@
   public abstract class MOEADAlgorithmBase : BasicAlgorithm {
     #region data members
+    [StorableType("C04DB21A-316F-4210-9CA7-A915BE8EBC96")]
     protected enum NeighborType { NEIGHBOR, POPULATION }
+
+    [StorableType("FE35F480-E522-45E0-A229-99E61DA7B8BC")]
     // TCHE = Chebyshev (Tchebyshev)
     // PBI  = Penalty-based boundary intersection
@@ -58 +63 @@
 
     [Storable]
-    protected IList<IMOEADSolution> solutions;
+    protected IMOEADSolution[] solutions;
 
     [Storable]
@@ -64 +69 @@
 
     [Storable]
-    protected List<IMOEADSolution> population;
-
-    [Storable]
-    protected List<IMOEADSolution> offspringPopulation;
-
-    [Storable]
-    protected List<IMOEADSolution> jointPopulation;
+    protected IMOEADSolution[] population;
+
+    [Storable]
+    protected IMOEADSolution[] offspringPopulation;
+
+    [Storable]
+    protected IMOEADSolution[] jointPopulation;
 
     [Storable]
@@ -232 +237 @@
       Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each generation.", new MultiAnalyzer()));
       Parameters.Add(new ValueParameter<IntValue>(MaximumEvaluatedSolutionsParameterName, "The maximum number of evaluated solutions (approximately).", new IntValue(100_000)));
-      Parameters.Add(new ValueParameter<IRandom>(RandomParameterName, new MersenneTwister()));
+      Parameters.Add(new ValueParameter<IRandom>(RandomParameterName, new FastRandom()));
       Parameters.Add(new FixedValueParameter<IntValue>(NeighbourSizeParameterName, new IntValue(20)));
       Parameters.Add(new FixedValueParameter<IntValue>(MaximumNumberOfReplacedSolutionsParameterName, new IntValue(2)));
@@ -271 +276 @@
 
       if (original.population != null) {
-        population = original.population.Select(cloner.Clone).ToList();
+        population = original.population.Select(cloner.Clone).ToArray();
       }
 
       if (original.offspringPopulation != null) {
-        offspringPopulation = original.offspringPopulation.Select(cloner.Clone).ToList();
+        offspringPopulation = original.offspringPopulation.Select(cloner.Clone).ToArray();
       }
 
       if (original.jointPopulation != null) {
-        jointPopulation = original.jointPopulation.Select(x => cloner.Clone(x)).ToList();
+        jointPopulation = original.jointPopulation.Select(x => cloner.Clone(x)).ToArray();
       }
 
@@ -300 +305 @@
 
     [StorableConstructor]
-    protected MOEADAlgorithmBase(StorableConstructorFlag _) : base(_) { }
+    protected MOEADAlgorithmBase(StorableConstructorFlag deserializing) : base(deserializing) { }
     #endregion
 
@@ -309 +314 @@
       var dimensions = maximization.Length;
       var populationSize = PopulationSize.Value;
-      population = new List<IMOEADSolution>(populationSize);
+      population = new IMOEADSolution[populationSize];
 
       var parentScope = executionContext.Scope;
@@ -329 +334 @@
           solution.Qualities[j] = maximization[j] ? 1 - qualities[j] : qualities[j];
         }
-        population.Add(solution);
+        population[i] = solution;
       }
     }
@@ -351 +356 @@
       IdealPoint.UpdateIdeal(population);
 
-      //NadirPoint = Enumerable.Repeat(double.MinValue, dimensions).ToArray();
-      NadirPoint = new double[dimensions];
+      NadirPoint = Enumerable.Repeat(double.MinValue, dimensions).ToArray();
+      //NadirPoint = new double[dimensions];
       NadirPoint.UpdateNadir(population);
 
@@ -469 +474 @@
     protected void UpdateNeighbourHood(IRandom random, IMOEADSolution individual, int subProblemId, NeighborType neighbourType) {
       int replacedSolutions = 0;
-      int size = neighbourType == NeighborType.NEIGHBOR ? NeighbourSize : population.Count;
+      int size = neighbourType == NeighborType.NEIGHBOR ? NeighbourSize : population.Length;
 
       foreach (var i in Enumerable.Range(0, size).Shuffle(random)) {
@@ -491 +496 @@
 
     private double CalculateFitness(double[] qualities, double[] lambda) {
-      double fitness;
       int dim = qualities.Length;
       switch (functionType) {
@@ -510 +514 @@
             }
 
-            fitness = maxFun;
-            return fitness;
+            return maxFun;
           }
         case FunctionType.AGG: {
@@ -518 +521 @@
               sum += lambda[n] * qualities[n];
             }
-
-            fitness = sum;
-            return fitness;
+            return sum;
           }
         case FunctionType.PBI: {
@@ -540 +541 @@
             }
             d2 = Math.Sqrt(d2);
-
-            fitness = (d1 + theta * d2);
-            return fitness;
+            return d1 + theta * d2;
           }
         default: {
@@ -562 +561 @@
 
     protected void UpdateParetoFronts() {
-      bool dominates(Point2D<double> x, Point2D<double> y) => x.X <= y.X && x.Y <= y.Y;
-      // get all non-dominated points
-      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();
-      var dominated = new bool[points.Length];
-
-      for (int i = 0; i < points.Length; ++i) {
-        if (dominated[i]) { continue; }
-        for (int j = 0; j < points.Length; ++j) {
-          if (i == j) { continue; }
-          if (dominated[j]) { continue; }
-          dominated[j] = dominates(points[i], points[j]);
-        }
-      }
-
-      var pf = Enumerable.Range(0, dominated.Length).Where(x => !dominated[x]).Select(x => points[x]);
+      var qualities = population.Select(x => Enumerable.Range(0, NadirPoint.Length).Select(i => x.Qualities[i] / NadirPoint[i]).ToArray()).ToArray();
+      var maximization = Enumerable.Repeat(false, IdealPoint.Length).ToArray(); // MOEA/D minimizes everything internally\
+      var pf = DominationCalculator<IMOEADSolution>.CalculateBestParetoFront(population, qualities, maximization);
+
+      var n = (int)EnumerableExtensions.BinomialCoefficient(IdealPoint.Length, 2);
+      var hypervolumes = new DoubleMatrix(n == 1 ? 1 : n + 1, 2) { ColumnNames = new[] { "PF hypervolume", "PF size" } };
+      hypervolumes[0, 0] = Hypervolume.Calculate(pf.Select(x => x.Item2), Enumerable.Repeat(1d, NadirPoint.Length).ToArray(), maximization);
+      hypervolumes[0, 1] = pf.Count;
+      var elementNames = new List<string>() { "Pareto Front" };
+
+      ResultCollection results;
+      if (Results.ContainsKey("Hypervolume Analysis")) {
+        results = (ResultCollection)Results["Hypervolume Analysis"].Value;
+      } else {
+        results = new ResultCollection();
+        Results.AddOrUpdateResult("Hypervolume Analysis", results);
+      }
 
       ScatterPlot sp;
-      if (!Results.ContainsKey("Pareto Front")) {
-        sp = new ScatterPlot();
-        sp.Rows.Add(new ScatterPlotDataRow("Pareto Front", "", pf) { VisualProperties = { PointSize = 5 } });
-        Results.AddOrUpdateResult("Pareto Front", sp);
-      } else {
-        sp = (ScatterPlot)Results["Pareto Front"].Value;
-        sp.Rows["Pareto Front"].Points.Replace(pf);
-      }
+      if (IdealPoint.Length == 2) {
+        var points = pf.Select(x => new Point2D<double>(x.Item2[0], x.Item2[1]));
+        var r = OnlinePearsonsRCalculator.Calculate(points.Select(x => x.X), points.Select(x => x.Y), out OnlineCalculatorError error);
+        if (error != OnlineCalculatorError.None) { r = double.NaN; }
+        var resultName = "Pareto Front Analysis ";
+        if (!results.ContainsKey(resultName)) {
+          sp = new ScatterPlot() {
+            VisualProperties = {
+              XAxisMinimumAuto = false, XAxisMinimumFixedValue = 0d, XAxisMaximumAuto = false, XAxisMaximumFixedValue = 1d,
+              YAxisMinimumAuto = false, YAxisMinimumFixedValue = 0d, YAxisMaximumAuto = false, YAxisMaximumFixedValue = 1d
+            }
+          };
+          sp.Rows.Add(new ScatterPlotDataRow(resultName, "", points) { VisualProperties = { PointSize = 8 } });
+          results.AddOrUpdateResult(resultName, sp);
+        } else {
+          sp = (ScatterPlot)results[resultName].Value;
+          sp.Rows[resultName].Points.Replace(points);
+        }
+        sp.Name = $"Dimensions [0, 1], correlation: {r.ToString("N2")}";
+      } else if (IdealPoint.Length > 2) {
+        var indices = Enumerable.Range(0, IdealPoint.Length).ToArray();
+        var visualProperties = new ScatterPlotDataRowVisualProperties { PointSize = 8, Color = Color.LightGray };
+        var combinations = indices.Combinations(2).ToArray();
+        var maximization2d = new[] { false, false };
+        var solutions2d = pf.Select(x => x.Item1).ToArray();
+        for (int i = 0; i < combinations.Length; ++i) {
+          var c = combinations[i].ToArray();
+
+          // calculate the hypervolume in the 2d coordinate space
+          var reference2d = new[] { 1d, 1d };
+          var qualities2d = pf.Select(x => new[] { x.Item2[c[0]], x.Item2[c[1]] }).ToArray();
+          var pf2d = DominationCalculator<IMOEADSolution>.CalculateBestParetoFront(solutions2d, qualities2d, maximization2d);
+
+          hypervolumes[i + 1, 0] = pf2d.Count > 0 ? Hypervolume.Calculate(pf2d.Select(x => x.Item2), reference2d, maximization2d) : 0d;
+          hypervolumes[i + 1, 1] = pf2d.Count;
+
+          var resultName = $"Pareto Front Analysis [{c[0]}, {c[1]}]";
+          elementNames.Add(resultName);
+
+          var points = pf.Select(x => new Point2D<double>(x.Item2[c[0]], x.Item2[c[1]]));
+          var pf2dPoints = pf2d.Select(x => new Point2D<double>(x.Item2[0], x.Item2[1]));
+
+          if (!results.ContainsKey(resultName)) {
+            sp = new ScatterPlot() {
+              VisualProperties = {
+                XAxisMinimumAuto = false, XAxisMinimumFixedValue = 0d, XAxisMaximumAuto = false, XAxisMaximumFixedValue = 1d,
+                YAxisMinimumAuto = false, YAxisMinimumFixedValue = 0d, YAxisMaximumAuto = false, YAxisMaximumFixedValue = 1d
+              }
+            };
+            sp.Rows.Add(new ScatterPlotDataRow("Pareto Front", "", points) { VisualProperties = visualProperties });
+            sp.Rows.Add(new ScatterPlotDataRow($"Pareto Front [{c[0]}, {c[1]}]", "", pf2dPoints) { VisualProperties = { PointSize = 10, Color = Color.OrangeRed } });
+            results.AddOrUpdateResult(resultName, sp);
+          } else {
+            sp = (ScatterPlot)results[resultName].Value;
+            sp.Rows["Pareto Front"].Points.Replace(points);
+            sp.Rows[$"Pareto Front [{c[0]}, {c[1]}]"].Points.Replace(pf2dPoints);
+          }
+          var r = OnlinePearsonsRCalculator.Calculate(points.Select(x => x.X), points.Select(x => x.Y), out OnlineCalculatorError error);
+          if (error != OnlineCalculatorError.None) { r = double.NaN; }
+          sp.Name = $"Pareto Front [{c[0]}, {c[1]}], correlation: {r.ToString("N2")}";
+        }
+      }
+      hypervolumes.RowNames = elementNames;
+      results.AddOrUpdateResult("Hypervolumes", hypervolumes);
     }
 
@@ -668 +725 @@
 
     public void ClearState() {
-      if (solutions != null) {
-        solutions.Clear();
-      }
-      if (population != null) {
-        population.Clear();
-      }
-      if (offspringPopulation != null) {
-        offspringPopulation.Clear();
-      }
-      if (jointPopulation != null) {
-        jointPopulation.Clear();
-      }
+      solutions = null;
+      population = null;
+      offspringPopulation = null;
+      jointPopulation = null;
       lambda = null;
       neighbourhood = null;

branches/2987_MOEAD_Algorithm/HeuristicLab.Algorithms.MOEAD/3.4/MOEADUtil.cs

@@ -175 +175 @@
     public static void UpdateIdeal(this double[] idealPoint, double[] point) {
       for (int i = 0; i < point.Length; ++i) {
+        if (double.IsInfinity(point[i]) || double.IsNaN(point[i])) {
+          continue;
+        }
+
         if (idealPoint[i] > point[i]) {
           idealPoint[i] = point[i];
@@ -183 +187 @@
     public static void UpdateNadir(this double[] nadirPoint, double[] point) {
       for (int i = 0; i < point.Length; ++i) {
+        if (double.IsInfinity(point[i]) || double.IsNaN(point[i])) {
+          continue;
+        }
+
         if (nadirPoint[i] < point[i]) {
           nadirPoint[i] = point[i];