Changeset 15859

Timestamp:

03/23/18 15:41:02 (7 years ago)

Author:

lkammere

Message:

#2886: Add simple constant optimization to evaluation of solutions.

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/RSquaredEvaluator.cs (modified) (3 diffs)
• Test/GrammarEnumerationTest.cs (modified) (1 diff)

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

@@ -1 +1 @@
 using System;
+using System.Diagnostics;
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
 using HeuristicLab.Common;
@@ -63 +64 @@
 
     private void EvaluateSentence(GrammarEnumerationAlgorithm algorithm, SymbolString symbolString) {
+      var problemData = algorithm.Problem.ProblemData;
+
       SymbolicExpressionTree tree = algorithm.Grammar.ParseSymbolicExpressionTree(symbolString);
+      Debug.Assert(SymbolicRegressionConstantOptimizationEvaluator.CanOptimizeConstants(tree));
 
-      var problemData = algorithm.Problem.ProblemData;
+      // TODO: Initialize constant values randomly
+      // TODO: Restarts
+
+      double r2 = SymbolicRegressionConstantOptimizationEvaluator.OptimizeConstants(expressionTreeLinearInterpreter,
+        tree,
+        problemData,
+        problemData.TrainingIndices,
+        applyLinearScaling: false,
+        maxIterations: 200,
+        updateVariableWeights: true,
+        updateConstantsInTree: true);
+
+      foreach (var symbolicExpressionTreeNode in tree.IterateNodesPostfix()) {
+        ConstantTreeNode constTreeNode = symbolicExpressionTreeNode as ConstantTreeNode;
+        if (constTreeNode != null && constTreeNode.Value.IsAlmost(0.0)) {
+          constTreeNode.Value = 0.0;
+        }
+      }
+
       SymbolicRegressionModel model = new SymbolicRegressionModel(
         problemData.TargetVariable,
@@ -71 +93 @@
         expressionTreeLinearInterpreter);
 
-      var target = problemData.TargetVariableTrainingValues;
-      var estVals = model.GetEstimatedValues(problemData.Dataset, problemData.TrainingIndices);
-      OnlineCalculatorError error;
-      var r2 = OnlinePearsonsRCalculator.Calculate(target, estVals, out error);
-      if (error != OnlineCalculatorError.None) r2 = 0.0;
+      //var target = problemData.TargetVariableTrainingValues;
+      //var estVals = model.GetEstimatedValues(problemData.Dataset, problemData.TrainingIndices);
+      //OnlineCalculatorError error;
+      //r2 = OnlinePearsonsRCalculator.Calculate(target, estVals, out error);
+      //if (error != OnlineCalculatorError.None) r2 = 0.0;
 
       var bestR2Result = (DoubleValue)algorithm.Results[BestTrainingQualityResultName].Value;
-      if (r2 > bestR2Result.Value) {
+      bool better = r2 > bestR2Result.Value;
+      bool equallyGood = r2.IsAlmost(bestR2Result.Value);
+      bool shorter = algorithm.BestTrainingSentence != null && symbolString.Count() < algorithm.BestTrainingSentence.Count();
+      if (better || (equallyGood && shorter)) {
         bestR2Result.Value = r2;
         algorithm.Results.AddOrUpdateResult(BestTrainingModelResultName, model);

branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

@@ -200 +200 @@
       EvaluateGrammarEnumeration();
     }
+
+    [TestMethod]
+    [TestProperty("Goal", "structure search + const op")]
+    public void Constants_Nguyen7() {
+      // log(x+1) + log(x*x + 1)
+      alg.MaxTreeSize = 22;
+      alg.Problem.ProblemData = new NguyenFunctionSeven().GenerateRegressionData();
+
+      alg.Start();
+
+      TerminalSymbol constSymbol = alg.Grammar.Const;
+      TerminalSymbol varSymbol = alg.Grammar.VarTerminals.First();
+      TerminalSymbol mulSymbol = alg.Grammar.Multiplication;
+      TerminalSymbol addSymbol = alg.Grammar.Addition;
+      TerminalSymbol logSymbol = alg.Grammar.Log;
+
+      SymbolString targetSolution = new SymbolString(new[] {
+        varSymbol, constSymbol, mulSymbol, constSymbol, addSymbol, logSymbol, constSymbol, mulSymbol,
+        varSymbol, varSymbol, mulSymbol, constSymbol, mulSymbol, constSymbol, addSymbol, logSymbol, constSymbol, mulSymbol, addSymbol,
+        constSymbol, addSymbol
+      });
+
+      int targetSolutionHash = alg.Grammar.Hasher.CalcHashCode(targetSolution);
+      int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
+
+      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+      Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
+
+
+      // Evaluate
+      EvaluateGrammarEnumeration();
+    }
+
+    [TestMethod]
+    [TestProperty("Goal", "structure search + const op")]
+    public void Constants_Nguyen12() {
+      // x*x*x*x - x*x*x + y*y/2 -y
+      alg.MaxTreeSize = 28;
+      alg.Problem.ProblemData = new NguyenFunctionTwelve().GenerateRegressionData();
+
+      alg.Start();
+
+      // Evaluate
+      EvaluateGrammarEnumeration();
+    }
+
+    [TestMethod]
+    [TestProperty("Goal", "structure search + const op")]
+    public void Constants_Keijzer3() {
+      // 0.3*x*sin(2*pi*x)
+      alg.MaxTreeSize = 20;
+      alg.Problem.ProblemData = new KeijzerFunctionThree().GenerateRegressionData();
+
+      alg.Start();
+
+      TerminalSymbol constSymbol = alg.Grammar.Const;
+      TerminalSymbol varSymbol = alg.Grammar.VarTerminals.First();
+      TerminalSymbol mulSymbol = alg.Grammar.Multiplication;
+      TerminalSymbol addSymbol = alg.Grammar.Addition;
+
+      SymbolString targetSolution = new SymbolString(new[] {
+        constSymbol, varSymbol, mulSymbol, constSymbol, addSymbol, alg.Grammar.Sin,
+        varSymbol, mulSymbol,
+        constSymbol, mulSymbol,
+        constSymbol, addSymbol
+      });
+
+      int targetSolutionHash = alg.Grammar.Hasher.CalcHashCode(targetSolution);
+      int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
+
+      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+
+      Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
+
+      // Evaluate
+      EvaluateGrammarEnumeration();
+    }
+
+    [TestMethod]
+    [TestProperty("Goal", "structure search + const op")]
+    public void Constants_Keijzer5() {
+      // (30*x*z) / ((x - 10)*y*y)
+      alg.MaxTreeSize = 24;
+      alg.Problem.ProblemData = new KeijzerFunctionFive().GenerateRegressionData();
+
+      alg.Start();
+
+      TerminalSymbol constSymbol = alg.Grammar.Const;
+      TerminalSymbol xSymbol = alg.Grammar.VarTerminals.First(s => s.StringRepresentation == "X");
+      TerminalSymbol ySymbol = alg.Grammar.VarTerminals.First(s => s.StringRepresentation == "Y");
+      TerminalSymbol zSymbol = alg.Grammar.VarTerminals.First(s => s.StringRepresentation == "Z");
+      TerminalSymbol mulSymbol = alg.Grammar.Multiplication;
+      TerminalSymbol addSymbol = alg.Grammar.Addition;
+      TerminalSymbol invSymbol = alg.Grammar.Inv;
+
+      // 30 * x * z * 1/(x*y*y - 10*y*y)
+      // --> x z * c *     x y * y * c *  y y * c * + c + inv c +
+      SymbolString targetSolution = new SymbolString(new[] {
+        xSymbol, zSymbol, mulSymbol, constSymbol, mulSymbol,
+        xSymbol, ySymbol, mulSymbol, ySymbol, mulSymbol, constSymbol, mulSymbol,
+        ySymbol, ySymbol, mulSymbol, constSymbol, mulSymbol, addSymbol, constSymbol, addSymbol, invSymbol,
+        constSymbol, addSymbol 
+      });
+
+      int targetSolutionHash = alg.Grammar.Hasher.CalcHashCode(targetSolution);
+      int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
+
+      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+
+      Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
+
+      // Evaluate
+      EvaluateGrammarEnumeration();
+    }
+
+
+    [TestMethod]
+    [TestProperty("Goal", "structure search + const op")]
+    public void Constants_Keijzer12() {
+      // x*x*x*x - x*x*x + y*y/2 - y
+      alg.MaxTreeSize = 29;
+      alg.Problem.ProblemData = new KeijzerFunctionTwelve().GenerateRegressionData();
+
+      alg.Start();
+
+      TerminalSymbol constSymbol = alg.Grammar.Const;
+      TerminalSymbol xSymbol = alg.Grammar.VarTerminals.First();
+      TerminalSymbol ySymbol = alg.Grammar.VarTerminals.Last();
+      TerminalSymbol mulSymbol = alg.Grammar.Multiplication;
+      TerminalSymbol addSymbol = alg.Grammar.Addition;
+
+      SymbolString targetSolution = new SymbolString(new[] {
+        xSymbol, xSymbol, mulSymbol, xSymbol, mulSymbol, xSymbol, mulSymbol, constSymbol, mulSymbol,
+        xSymbol, xSymbol, mulSymbol, xSymbol, mulSymbol, constSymbol, mulSymbol, addSymbol,
+        ySymbol, ySymbol, mulSymbol, constSymbol, mulSymbol, addSymbol,
+        ySymbol, constSymbol, mulSymbol, addSymbol,
+        constSymbol, addSymbol 
+      });
+
+      var x = alg.Grammar.ToInfixString(targetSolution);
+
+      int targetSolutionHash = alg.Grammar.Hasher.CalcHashCode(targetSolution);
+      int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
+
+      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+      Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
+
+      // Evaluate
+      EvaluateGrammarEnumeration();
+    }
+
+    [TestMethod]
+    [TestProperty("Goal", "structure search + const op")]
+    public void Constants_Keijzer14() {
+      // 8 / (2 + x*x + y*y
+      alg.MaxTreeSize = 19;
+      alg.Problem.ProblemData = new KeijzerFunctionFourteen().GenerateRegressionData();
+
+      alg.Start();
+      
+      TerminalSymbol constSymbol = alg.Grammar.Const;
+      TerminalSymbol xSymbol = alg.Grammar.VarTerminals.First();
+      TerminalSymbol ySymbol = alg.Grammar.VarTerminals.Last();
+      TerminalSymbol mulSymbol = alg.Grammar.Multiplication;
+      TerminalSymbol addSymbol = alg.Grammar.Addition;
+      TerminalSymbol divSymbol = alg.Grammar.Inv;
+
+      
+      // x x mul c mul y y mul c mul add const add inv const mul const add
+      SymbolString targetSolution = new SymbolString(new[] {
+        xSymbol, xSymbol, mulSymbol, constSymbol, mulSymbol,  
+        ySymbol, ySymbol, mulSymbol, constSymbol, mulSymbol, addSymbol,
+        constSymbol, addSymbol, divSymbol,
+        constSymbol, mulSymbol,
+        constSymbol, addSymbol
+      });
+
+      int targetSolutionHash = alg.Grammar.Hasher.CalcHashCode(targetSolution);
+      int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
+
+      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+      Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
+
+      // Evaluate
+      EvaluateGrammarEnumeration();
+    }
+
+
+    [TestMethod]
+    [TestProperty("Goal", "structure search + const op")]
+    public void Constants_Keijzer15() {
+      // x*x*x / 5 + y*y*y / 2 - y - x
+      alg.MaxTreeSize = 25;
+      alg.Problem.ProblemData = new KeijzerFunctionFifteen().GenerateRegressionData();
+
+      alg.Start();
+
+      TerminalSymbol constSymbol = alg.Grammar.Const;
+      TerminalSymbol xSymbol = alg.Grammar.VarTerminals.First();
+      TerminalSymbol ySymbol = alg.Grammar.VarTerminals.Last();
+      TerminalSymbol mulSymbol = alg.Grammar.Multiplication;
+      TerminalSymbol addSymbol = alg.Grammar.Addition;
+
+      // x x * x * const * y y * y * const * + y const * + x const * const +
+      SymbolString targetSolution = new SymbolString(new[] {
+        xSymbol, xSymbol, mulSymbol, xSymbol, mulSymbol, constSymbol, mulSymbol,
+        ySymbol, ySymbol, mulSymbol, ySymbol, mulSymbol, constSymbol, mulSymbol, addSymbol,
+        ySymbol, constSymbol, mulSymbol, addSymbol, 
+        xSymbol, constSymbol, mulSymbol, addSymbol,
+        constSymbol, addSymbol
+      });
+
+      int targetSolutionHash = alg.Grammar.Hasher.CalcHashCode(targetSolution);
+      int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
+
+      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+      Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
+
+      // Evaluate
+      EvaluateGrammarEnumeration();
+    }
+
+