Changeset 16088

Timestamp:

08/27/18 19:03:10 (6 years ago)

Author:

lkammere

Message:

#2886: Store pareto-optimal sentences (quality/complexity) to grammar enumeration.

File:

• branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/BestSolutionAnalyzer.cs (modified) (6 diffs)

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/BestSolutionAnalyzer.cs

@@ -22 +22 @@
 using System;
 using System.Diagnostics;
+using System.Linq;
 using HeuristicLab.Analysis;
 using HeuristicLab.Common;
@@ -27 +28 @@
 using HeuristicLab.Data;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Optimization;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.DataAnalysis.Symbolic;
@@ -41 +43 @@
     public static readonly string BestComplexityResultName = "Best solution complexity";
     public static readonly string BestSolutions = "Best solutions";
+    public static readonly string ParetoFrontResultName = "Pareto Front";
+    public static readonly string ParetoFrontAnalysisResultName = "Pareto Front Analysis";
 
     private static readonly ISymbolicDataAnalysisExpressionTreeInterpreter expressionTreeLinearInterpreter = new SymbolicDataAnalysisExpressionTreeLinearInterpreter();
@@ -69 +73 @@
 
       var results = algorithm.Results;
-      var grammar = algorithm.Grammar;
       var problemData = algorithm.Problem.ProblemData;
 
@@ -76 +79 @@
 
       double r2 = algorithm.Evaluator.Evaluate(problemData, tree);
-      double bestR2 = results.ContainsKey(BestTrainingQualityResultName) ? GetValue<double>(results[BestTrainingQualityResultName].Value) : 0.0;
-      if (r2 < bestR2)
-        return;
+      int rank = GetRank(sentence);
 
-      var bestComplexity = results.ContainsKey(BestComplexityResultName) ? GetValue<int>(results[BestComplexityResultName].Value) : int.MaxValue;
-      var complexity = sentence.Complexity;
-
-      if (algorithm.BestTrainingSentence == null || r2 > bestR2 || (r2.IsAlmost(bestR2) && complexity < bestComplexity)) {
-        algorithm.BestTrainingSentence = sentence;
-
+      // Store solution in pareto front
+      if (IsParetoOptimal(algorithm, rank, r2)) {
         var model = new SymbolicRegressionModel(problemData.TargetVariable, tree, expressionTreeLinearInterpreter);
         model.Scale(problemData);
         var bestSolution = model.CreateRegressionSolution(problemData);
 
-        results.AddOrUpdateResult(BestTrainingQualityResultName, new DoubleValue(bestSolution.TrainingRSquared));
-        results.AddOrUpdateResult(BestTestQualityResultName, new DoubleValue(bestSolution.TestRSquared));
-        results.AddOrUpdateResult(BestTrainingModelResultName, bestSolution.Model);
-        results.AddOrUpdateResult(BestTrainingSolutionResultName, bestSolution);
-        results.AddOrUpdateResult(BestComplexityResultName, new IntValue(complexity));
+        AddToParetoFront(algorithm, rank, r2, bestSolution);
 
-        // record best sentence quality & length
-        DataTable dt;
-        if (!results.ContainsKey(BestSolutions)) {
-          var names = new[] { "Quality", "Length", "Complexity", "Timestamp" };
-          dt = new DataTable();
-          foreach (var name in names) {
-            dt.Rows.Add(new DataRow(name) { VisualProperties = { StartIndexZero = true } });
+        // Store overall best solution
+        double bestR2 = results.ContainsKey(BestTrainingQualityResultName)
+          ? GetValue<double>(results[BestTrainingQualityResultName].Value)
+          : 0.0;
+        var bestComplexity = results.ContainsKey(BestComplexityResultName) ? GetValue<int>(results[BestComplexityResultName].Value) : int.MaxValue;
+        var complexity = sentence.Complexity;
+
+        if (algorithm.BestTrainingSentence == null || r2 > bestR2 || (r2.IsAlmost(bestR2) && complexity < bestComplexity)) {
+          algorithm.BestTrainingSentence = sentence;
+
+          results.AddOrUpdateResult(BestTrainingQualityResultName, new DoubleValue(bestSolution.TrainingRSquared));
+          results.AddOrUpdateResult(BestTestQualityResultName, new DoubleValue(bestSolution.TestRSquared));
+          results.AddOrUpdateResult(BestTrainingModelResultName, bestSolution.Model);
+          results.AddOrUpdateResult(BestTrainingSolutionResultName, bestSolution);
+          results.AddOrUpdateResult(BestComplexityResultName, new IntValue(complexity));
+
+          // record best sentence quality & length
+          DataTable dt;
+          if (!results.ContainsKey(BestSolutions)) {
+            var names = new[] { "Quality", "Length", "Complexity", "Timestamp" };
+            dt = new DataTable();
+            foreach (var name in names) {
+              dt.Rows.Add(new DataRow(name) { VisualProperties = { StartIndexZero = true } });
+            }
+            results.AddOrUpdateResult(BestSolutions, dt);
           }
-          results.AddOrUpdateResult(BestSolutions, dt);
+          dt = (DataTable)results[BestSolutions].Value;
+          dt.Rows["Quality"].Values.Add(r2);
+          dt.Rows["Length"].Values.Add((double)sentence.Count);
+          dt.Rows["Complexity"].Values.Add(complexity);
+          dt.Rows["Timestamp"].Values.Add(algorithm.ExecutionTime.TotalMilliseconds / 1000d);
         }
-        dt = (DataTable)results[BestSolutions].Value;
-        dt.Rows["Quality"].Values.Add(r2);
-        dt.Rows["Length"].Values.Add((double)sentence.Count);
-        dt.Rows["Complexity"].Values.Add(complexity);
-        dt.Rows["Timestamp"].Values.Add(algorithm.ExecutionTime.TotalMilliseconds / 1000d);
       }
 
@@ -125 +135 @@
       return v.Value;
     }
+
+    private int GetRank(SymbolList s) {
+      return s.Complexity;
+    }
+
+    private bool IsParetoOptimal(GrammarEnumerationAlgorithm algorithm, int currRank, double currQuality) {
+      if (!algorithm.Results.ContainsKey(ParetoFrontResultName)) return true;
+
+      ItemList<DoubleArray> paretoFront = (ItemList<DoubleArray>)algorithm.Results[ParetoFrontResultName].Value;
+
+      DoubleArray precedingRank = paretoFront.OrderByDescending(v => v[0]).FirstOrDefault(v => v[0] <= currRank);
+
+      return precedingRank == null || currQuality > precedingRank[1];
+    }
+
+    private void AddToParetoFront(GrammarEnumerationAlgorithm algorithm, int currRank, double currQuality, ISymbolicRegressionSolution solution) {
+      if (!algorithm.Results.ContainsKey(ParetoFrontResultName)) {
+        algorithm.Results.Add(new Result(ParetoFrontResultName, new ItemList<DoubleArray>()));
+
+        var scatterPlot = new ScatterPlot(ParetoFrontAnalysisResultName, ParetoFrontAnalysisResultName);
+        algorithm.Results.Add(new Result(ParetoFrontAnalysisResultName, scatterPlot));
+        scatterPlot.Rows.Add(new ScatterPlotDataRow());
+
+        scatterPlot.VisualProperties.XAxisTitle = "Complexity";
+        scatterPlot.VisualProperties.YAxisTitle = "R²";
+        scatterPlot.Rows.First().VisualProperties.PointSize = 10;
+      }
+
+      ItemList<DoubleArray> paretoFront = (ItemList<DoubleArray>)algorithm.Results[ParetoFrontResultName].Value;
+      ScatterPlotDataRow plot = ((ScatterPlot)algorithm.Results[ParetoFrontAnalysisResultName].Value).Rows.First();
+
+
+      // Delete solutions with higher rank, which are now dominated.
+      foreach (DoubleArray succeedingRank in paretoFront.Where(k => k[0] >= currRank).ToArray()) {
+        if (succeedingRank[1] < currQuality) {
+          paretoFront.Remove(succeedingRank);
+          RemovePoint(plot, succeedingRank[0]);
+        }
+      }
+
+      paretoFront.Add(new DoubleArray(new double[] { currRank, currQuality }));
+      plot.Points.Add(new Point2D<double>(currRank, currQuality, solution));
+    }
+
+    private void RemovePoint(ScatterPlotDataRow plot, double rank) {
+      plot.Points.RemoveAll(p => p.X.IsAlmost(rank));
+    }
   }
 }