Changeset 11895 for branches/HeuristicLab.Problems.GrammaticalOptimization

Timestamp:

02/05/15 07:03:15 (10 years ago)

Author:

gkronber

Message:

#2283: constant opt, expressioncompiler, autodiff, fixes in GP solvers

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization

Files:

• HeuristicLab.Algorithms.GeneticProgramming/GenericSymbExprEvaluator.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.GeneticProgramming/HeuristicLab.Algorithms.GeneticProgramming.csproj (modified) (3 diffs)
• HeuristicLab.Algorithms.GeneticProgramming/IGPSolver.cs (added)
• HeuristicLab.Algorithms.GeneticProgramming/OffspringSelectionGP.cs (modified) (7 diffs)
• HeuristicLab.Algorithms.GeneticProgramming/StandardGP.cs (modified) (7 diffs)
• HeuristicLab.Problems.GrammaticalOptimization.SymbReg/ExpressionCompiler.cs (added)
• HeuristicLab.Problems.GrammaticalOptimization.SymbReg/HeuristicLab.Problems.GrammaticalOptimization.SymbReg.csproj (modified) (3 diffs)
• HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs (modified) (11 diffs)
• HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs (modified) (4 diffs)
• Main/Program.cs (modified) (7 diffs)
• Test/TestSolvers.cs (modified) (3 diffs)
• Test/TestSymbRegInstances.cs (modified) (2 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GeneticProgramming/GenericSymbExprEvaluator.cs

@@ -6 +6 @@
 using HeuristicLab.Operators;
 using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.PluginInfrastructure;
 
 namespace HeuristicLab.Problems.GrammaticalOptimization {
-  // this type is not storable because we use a func<ITree,double> for evaluation, which references back to the original grammatical optimization problem
   [NonDiscoverableType]
+  [StorableClass]
   [Item("GenericSymbExprEvaluator", "Evaluator for grammatical optimization problems (using a symbolic expression tree encoding).")]
   public class GenericSymbExprEvaluator : SingleSuccessorOperator, IGenericSymbExprEvaluator {
@@ -22 +23 @@
     }
 
+    // cannot save these (eval won't work when loaded from file
     private Func<string, double> evalFunc;
     private Func<ISymbolicExpressionTree, string> toStringFunc;
 
+    [StorableConstructor]
+    private GenericSymbExprEvaluator(bool deserializing) : base(deserializing) { }
     public GenericSymbExprEvaluator(GenericSymbExprEvaluator original, Cloner cloner)
       : base(original, cloner) {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GeneticProgramming/HeuristicLab.Algorithms.GeneticProgramming.csproj

@@ -36 +36 @@
     <Reference Include="HeuristicLab.Algorithms.OffspringSelectionGeneticAlgorithm-3.3">
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Algorithms.OffspringSelectionGeneticAlgorithm-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Analysis-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Analysis-3.3.dll</HintPath>
     </Reference>
     <Reference Include="HeuristicLab.Collections-3.3">
@@ -75 +79 @@
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Selection-3.3.dll</HintPath>
     </Reference>
+    <Reference Include="HeuristicLab.SequentialEngine-3.3">
+      <HintPath>..\..\..\..\..\Program Files\HeuristicLab 3.3\HeuristicLab.SequentialEngine-3.3.dll</HintPath>
+    </Reference>
     <Reference Include="System" />
     <Reference Include="System.Core" />
@@ -80 +87 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="IGPSolver.cs" />
     <Compile Include="GenericSymbExprEvaluator.cs" />
     <Compile Include="GenericSymbExprGrammar.cs" />

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GeneticProgramming/OffspringSelectionGP.cs

@@ -1 +1 @@
 using System;
+using System.IO;
+using System.IO.Compression;
 using System.Linq;
 using System.Threading;
 using HeuristicLab.Algorithms.GrammaticalOptimization;
+using HeuristicLab.Analysis;
+using HeuristicLab.Common;
 using HeuristicLab.Data;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
-using HeuristicLab.Optimization;
+using HeuristicLab.Persistence.Default.Xml;
 using HeuristicLab.Problems.GrammaticalOptimization;
-using HeuristicLab.Selection;
-using HeuristicLab.Algorithms.GeneticAlgorithm;
 
 namespace HeuristicLab.Algorithms.GeneticProgramming {
-  public class OffspringSelectionGP : SolverBase {
+  public class OffspringSelectionGP : SolverBase, IGPSolver {
     public int PopulationSize { get; set; }
     public double MutationRate { get; set; }
@@ -19 +21 @@
     private readonly ISymbolicExpressionTreeProblem problem;
     private readonly Random random;
+    private readonly bool saveAlg;
 
-    public OffspringSelectionGP(ISymbolicExpressionTreeProblem problem, Random random) {
+    public OffspringSelectionGP(ISymbolicExpressionTreeProblem problem, Random random, bool saveAlg = false) {
       this.problem = problem;
       this.random = random;
@@ -28 +31 @@
       MaxSolutionSize = 100;
       MaxSolutionDepth = 17;
+      this.saveAlg = saveAlg;
     }
 
@@ -33 +37 @@
       var hlProblem = new GenericSymbExprProblem(problem);
       var onEvalLocker = new object();
-      hlProblem.Evaluator.SolutionEvaluated += (sentence, quality) => {
-        // raise solution evaluated event for each GP solution, don't scale quality to 0..1 
-        // need to synchronize in case we are using a parallel engine
-        lock (onEvalLocker) {
-          OnSolutionEvaluated(sentence, quality);
-        }
-      };
       hlProblem.MaximumSymbolicExpressionTreeLength.Value = MaxSolutionSize;
       hlProblem.MaximumSymbolicExpressionTreeDepth.Value = MaxSolutionDepth;
@@ -45 +42 @@
       using (var wh = new AutoResetEvent(false)) {
         var osga = new OffspringSelectionGeneticAlgorithm.OffspringSelectionGeneticAlgorithm();
-        osga.Engine = new ParallelEngine.ParallelEngine();
+        // osga.Engine = new ParallelEngine.ParallelEngine();
+        osga.Engine = new SequentialEngine.SequentialEngine();
         osga.ExceptionOccurred += (sender, args) => { Console.WriteLine(args.Value.Message); wh.Set(); };
         osga.Stopped += (sender, args) => { wh.Set(); };
+
+        int numEvals = 0;
+        hlProblem.Evaluator.SolutionEvaluated += (sentence, quality) => {
+          // raise solution evaluated event for each GP solution, don't scale quality to 0..1 
+          // need to synchronize in case we are using a parallel engine
+          lock (onEvalLocker) {
+            OnSolutionEvaluated(sentence, quality);
+
+            // stop when maxEvals has been reached
+            if (numEvals++ >= maxEvaluations) {
+              osga.Stop();
+            }
+          }
+        };
+
 
         osga.Problem = hlProblem;
@@ -59 +72 @@
         osga.Crossover = osga.CrossoverParameter.ValidValues.Single(op => op.Name == "SubtreeSwappingCrossover");
         osga.Selector = osga.SelectorParameter.ValidValues.Single(op => op.Name == "GenderSpecificSelection");
+        var multiAnalzer = (MultiAnalyzer)osga.Analyzer;
+        multiAnalzer.Operators.Add(new BestSymbolicExpressionTreeAnalyzer());
 
         osga.PopulationSize.Value = PopulationSize;
-        osga.MaximumGenerations.Value = 100000; // some very large value (we stop based on evaluations)
-        osga.MaximumSelectionPressure.Value = 1000;
+        osga.MaximumGenerations.Value = 1000000; // some very large value (we stop based on evaluations)
+        osga.MaximumSelectionPressure.Value = 1000000;
         osga.MaximumEvaluatedSolutions.Value = maxEvaluations;
         osga.MutationProbability.Value = MutationRate;
+        osga.ComparisonFactorLowerBound.Value = 1.0;
+        osga.ComparisonFactorUpperBound.Value = 1.0;
+        osga.SuccessRatio.Value = 1.0;
 
         osga.SetSeedRandomly = new BoolValue(false);
@@ -73 +91 @@
 
         wh.WaitOne();
+
+
+        if (saveAlg) {
+          var path = @"C:\Users\P24581\Desktop";
+          var fileName = string.Format("osgp-{0}{1:D2}{2:D2}{3:D2}{4:D2}.hl", DateTime.Now.Year, DateTime.Now.Month, DateTime.Now.Day, DateTime.Now.Hour, DateTime.Now.Minute);
+          var fullPath = Path.Combine(path, fileName);
+          HeuristicLab.Persistence.Core.ConfigurationService.Instance.LoadSettings();
+          XmlGenerator.Serialize(osga, fullPath, CompressionLevel.Fastest);
+        }
       }
     }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GeneticProgramming/StandardGP.cs

@@ -1 +1 @@
 using System;
+using System.IO;
+using System.IO.Compression;
 using System.Linq;
 using System.Threading;
 using HeuristicLab.Algorithms.GrammaticalOptimization;
+using HeuristicLab.Common;
 using HeuristicLab.Data;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
-using HeuristicLab.Optimization;
+using HeuristicLab.Persistence.Default.Xml;
 using HeuristicLab.Problems.GrammaticalOptimization;
 using HeuristicLab.Selection;
-using HeuristicLab.Algorithms.GeneticAlgorithm;
 
 namespace HeuristicLab.Algorithms.GeneticProgramming {
-  public class StandardGP : SolverBase {
+  public class StandardGP : SolverBase, IGPSolver {
     public int PopulationSize { get; set; }
     public double MutationRate { get; set; }
@@ -20 +22 @@
     private readonly ISymbolicExpressionTreeProblem problem;
     private readonly Random random;
+    private readonly bool saveAlg;
 
-    public StandardGP(ISymbolicExpressionTreeProblem problem, Random random) {
+    public StandardGP(ISymbolicExpressionTreeProblem problem, Random random, bool saveAlg = false) {
       this.problem = problem;
       this.random = random;
@@ -30 +33 @@
       MaxSolutionSize = 100;
       MaxSolutionDepth = 17;
+      this.saveAlg = saveAlg;
     }
 
@@ -35 +39 @@
       var hlProblem = new GenericSymbExprProblem(problem);
       var onEvalLocker = new object();
-      hlProblem.Evaluator.SolutionEvaluated += (sentence, quality) => {
-        // raise solution evaluated event for each GP solution, don't scale quality to 0..1 
-        // need to synchronize in case we are using a parallel engine
-        lock (onEvalLocker) {
-          OnSolutionEvaluated(sentence, quality);
-        }
-      };
       hlProblem.MaximumSymbolicExpressionTreeLength.Value = MaxSolutionSize;
       hlProblem.MaximumSymbolicExpressionTreeDepth.Value = MaxSolutionDepth;
@@ -51 +48 @@
         ga.ExceptionOccurred += (sender, args) => { Console.WriteLine(args.Value.Message); wh.Set(); };
         ga.Stopped += (sender, args) => { wh.Set(); };
+
+        int numEvals = 0;
+        hlProblem.Evaluator.SolutionEvaluated += (sentence, quality) => {
+          // raise solution evaluated event for each GP solution, don't scale quality to 0..1 
+          // need to synchronize in case we are using a parallel engine
+          lock (onEvalLocker) {
+            OnSolutionEvaluated(sentence, quality);
+
+            // stop when maxEvals has been reached
+            if (numEvals++ >= maxEvaluations) {
+              ga.Stop();
+            }
+          }
+        };
+
 
         ga.Problem = hlProblem;
@@ -66 +78 @@
 
         ga.PopulationSize.Value = PopulationSize;
-        ga.MaximumGenerations.Value = maxEvaluations / PopulationSize + 1; // one extra generation in case maxEvaluations is not a multiple of PopulationSize
+        ga.MaximumGenerations.Value = 1000000; // very large value (we stop in the evaluate handler)
         ga.MutationProbability.Value = MutationRate;
 
@@ -76 +88 @@
 
         wh.WaitOne();
+
+
+        if (saveAlg) {
+          var path = @"C:\Users\P24581\Desktop";
+          var fileName = string.Format("osgp-{0}{1:D2}{2:D2}{3:D2}{4:D2}.hl", DateTime.Now.Year, DateTime.Now.Month, DateTime.Now.Day, DateTime.Now.Hour, DateTime.Now.Minute);
+          var fullPath = Path.Combine(path, fileName);
+          HeuristicLab.Persistence.Core.ConfigurationService.Instance.LoadSettings();
+          XmlGenerator.Serialize(ga, fullPath, CompressionLevel.Fastest);
+        }
       }
     }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/HeuristicLab.Problems.GrammaticalOptimization.SymbReg.csproj

@@ -31 +31 @@
   </PropertyGroup>
   <ItemGroup>
+    <Reference Include="ALGLIB-3.7.0, Version=3.7.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\ALGLIB-3.7.0.dll</HintPath>
+    </Reference>
+    <Reference Include="AutoDiff-1.0">
+      <HintPath>..\..\..\trunk\sources\bin\AutoDiff-1.0.dll</HintPath>
+    </Reference>
     <Reference Include="HeuristicLab.Common-3.3">
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Common-3.3.dll</HintPath>
@@ -39 +46 @@
     <Reference Include="HeuristicLab.Data-3.3">
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Data-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll</HintPath>
     </Reference>
     <Reference Include="HeuristicLab.Problems.DataAnalysis-3.4">
@@ -53 +64 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="ExpressionCompiler.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
     <Compile Include="SymbolicRegressionProblem.cs" />

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs

@@ -1 +1 @@
 using System;
+using System.CodeDom.Compiler;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Security;
 using System.Security.AccessControl;
+using System.Security.Authentication.ExtendedProtection.Configuration;
 using System.Text;
+using AutoDiff;
 using HeuristicLab.Common;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Problems.DataAnalysis;
 using HeuristicLab.Problems.Instances;
@@ -12 +17 @@
 namespace HeuristicLab.Problems.GrammaticalOptimization.SymbReg {
   // provides bridge to HL regression problem instances
-  public class SymbolicRegressionProblem : IProblem {
+  public class SymbolicRegressionProblem : ISymbolicExpressionTreeProblem {
 
     private const string grammarString = @"
         G(E):
-        E -> V | V+E | V-E | V*E | V/E | (E) | C | C+E | C-E | C*E | C/E 
+        E -> V | C | V+E | V-E | V*E | V%E | (E) | C+E | C-E | C*E | C%E 
         C -> 0..9
         V -> <variables>
@@ -22 +27 @@
     // C represents Koza-style ERC (the symbol is the index of the ERC), the values are initialized below
 
+    // S .. Sum (+), N .. Neg. sum (-), P .. Product (*), D .. Division (%)
+    private const string treeGrammarString = @"
+        G(E):
+        E -> V | C | S | N | P | D 
+        S -> EE | EEE
+        N -> EE | EEE
+        P -> EE | EEE
+        D -> EE
+        C -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
+        V -> <variables>
+        ";
+
+    // when we use constants optimization we can completely ignore all constants by a simple strategy:
+    // introduce a constant factor for each complete term
+    // introduce a constant offset for each complete expression (including expressions in brackets)
+    // e.g. 1*(2*a + b - 3 + 4) is the same as c0*a + c1*b + c2
+
     private readonly IGrammar grammar;
 
     private readonly int N;
-    private readonly double[][] x;
+    private readonly double[,] x;
     private readonly double[] y;
     private readonly int d;
@@ -40 +62 @@
       this.d = problemData.AllowedInputVariables.Count();
       if (d > 26) throw new NotSupportedException(); // we only allow single-character terminal symbols so far
-      this.x = new double[N][];
+      this.x = new double[N, d];
       this.y = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TrainingIndices).ToArray();
 
       int i = 0;
       foreach (var r in problemData.TrainingIndices) {
-        x[i] = new double[d];
         int j = 0;
         foreach (var inputVariable in problemData.AllowedInputVariables) {
-          x[i][j++] = problemData.Dataset.GetDoubleValue(inputVariable, r);
+          x[i, j++] = problemData.Dataset.GetDoubleValue(inputVariable, r);
         }
         i++;
@@ -58 +79 @@
       char lastVar = Convert.ToChar(Convert.ToByte('a') + d - 1);
       this.grammar = new Grammar(grammarString.Replace("<variables>", firstVar + " .. " + lastVar));
+      this.TreeBasedGPGrammar = new Grammar(treeGrammarString.Replace("<variables>", firstVar + " .. " + lastVar));
     }
 
@@ -71 +93 @@
 
     public double Evaluate(string sentence) {
+      return OptimizeConstantsAndEvaluate(sentence);
+    }
+
+    public double SimpleEvaluate(string sentence) {
       var interpreter = new ExpressionInterpreter();
-      return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i], erc)));
+      var rowData = new double[d];
+      return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => {
+        for (int j = 0; j < d; j++) rowData[j] = x[i, j];
+        return interpreter.Interpret(sentence, rowData, erc);
+      }));
     }
 
@@ -83 +113 @@
     }
 
-    public IEnumerable<Feature> GetFeatures(string phrase)
-    {
+    public IEnumerable<Feature> GetFeatures(string phrase) {
       throw new NotImplementedException();
     }
 
 
-    /*
-    public static double OptimizeConstants(string sentence) {
-
-      List<AutoDiff.Variable> variables = new List<AutoDiff.Variable>();
-      List<AutoDiff.Variable> parameters = new List<AutoDiff.Variable>();
-      List<string> variableNames = new List<string>();
-
+
+    public double OptimizeConstantsAndEvaluate(string sentence) {
       AutoDiff.Term func;
-      if (!TryTransformToAutoDiff(sentence, 0, variables, parameters, out func))
-        throw new NotSupportedException("Could not optimize constants of symbolic expression tree due to not supported symbols used in the tree.");
-      if (variableNames.Count == 0) return 0.0;
-
-      AutoDiff.IParametricCompiledTerm compiledFunc = AutoDiff.TermUtils.Compile(func, variables.ToArray(), parameters.ToArray());
-
-      List<SymbolicExpressionTreeTerminalNode> terminalNodes = tree.Root.IterateNodesPrefix().OfType<SymbolicExpressionTreeTerminalNode>().ToList();
-      double[] c = new double[variables.Count];
-
-      {
-        c[0] = 0.0;
-        c[1] = 1.0;
-        //extract inital constants
-        int i = 2;
-        foreach (var node in terminalNodes) {
-          ConstantTreeNode constantTreeNode = node as ConstantTreeNode;
-          VariableTreeNode variableTreeNode = node as VariableTreeNode;
-          if (constantTreeNode != null)
-            c[i++] = constantTreeNode.Value;
-          else if (variableTreeNode != null)
-            c[i++] = variableTreeNode.Weight;
-        }
-      }
-      double[] originalConstants = (double[])c.Clone();
-      double originalQuality = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(interpreter, tree, lowerEstimationLimit, upperEstimationLimit, problemData, rows, applyLinearScaling);
+      int pos = 0;
+
+      var compiler = new ExpressionCompiler();
+      Variable[] variables;
+      Variable[] constants;
+      compiler.Compile(sentence, out func, out variables, out constants);
+
+      // constants are manipulated 
+
+      if (!constants.Any()) return SimpleEvaluate(sentence);
+
+      AutoDiff.IParametricCompiledTerm compiledFunc = func.Compile(constants, variables); // variate constants leave variables fixed to data
+
+      double[] c = constants.Select(_ => 1.0).ToArray(); // start with ones
 
       alglib.lsfitstate state;
@@ -127 +140 @@
       int info;
 
-      Dataset ds = problemData.Dataset;
-      double[,] x = new double[rows.Count(), variableNames.Count];
-      int row = 0;
-      foreach (var r in rows) {
-        for (int col = 0; col < variableNames.Count; col++) {
-          x[row, col] = ds.GetDoubleValue(variableNames[col], r);
-        }
-        row++;
-      }
-      double[] y = ds.GetDoubleValues(problemData.TargetVariable, rows).ToArray();
       int n = x.GetLength(0);
       int m = x.GetLength(1);
@@ -144 +147 @@
       alglib.ndimensional_pgrad function_cx_1_grad = CreatePGrad(compiledFunc);
 
+      const int maxIterations = 10;
       try {
         alglib.lsfitcreatefg(x, y, c, n, m, k, false, out state);
@@ -151 +155 @@
         alglib.lsfitresults(state, out info, out c, out rep);
       } catch (ArithmeticException) {
-        return originalQuality;
+        return 0.0;
       } catch (alglib.alglibexception) {
-        return originalQuality;
+        return 0.0;
       }
 
       //info == -7  => constant optimization failed due to wrong gradient
-      if (info != -7) throw new ArgumentException();
+      if (info == -7) throw new ArgumentException();
+      {
+        var rowData = new double[d];
+        return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => {
+          for (int j = 0; j < d; j++) rowData[j] = x[i, j];
+          return compiledFunc.Evaluate(c, rowData);
+        }));
+      }
     }
 
@@ -175 +186 @@
     }
 
-    private static bool TryTransformToAutoDiff(string phrase, int symbolPos, List<AutoDiff.Variable> variables, List<AutoDiff.Variable> parameters, out AutoDiff.Term term)
-    {
-      var curSy = phrase[0];
-      if () {
-        var var = new AutoDiff.Variable();
-        variables.Add(var);
-        term = var;
-        return true;
-      }
-      if (node.Symbol is Variable) {
-        var varNode = node as VariableTreeNode;
-        var par = new AutoDiff.Variable();
-        parameters.Add(par);
-        variableNames.Add(varNode.VariableName);
-        var w = new AutoDiff.Variable();
-        variables.Add(w);
-        term = AutoDiff.TermBuilder.Product(w, par);
-        return true;
-      }
-      if (node.Symbol is Addition) {
-        List<AutoDiff.Term> terms = new List<Term>();
-        foreach (var subTree in node.Subtrees) {
-          AutoDiff.Term t;
-          if (!TryTransformToAutoDiff(subTree, variables, parameters, variableNames, out t)) {
-            term = null;
-            return false;
-          }
-          terms.Add(t);
+    public IGrammar TreeBasedGPGrammar { get; private set; }
+    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
+      var sb = new StringBuilder();
+
+      TreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
+
+      return sb.ToString();
+    }
+
+    private void TreeToSentence(ISymbolicExpressionTreeNode treeNode, StringBuilder sb) {
+      if (treeNode.SubtreeCount == 0) {
+        // terminal
+        sb.Append(treeNode.Symbol.Name);
+      } else {
+        string op = string.Empty;
+        switch (treeNode.Symbol.Name) {
+          case "S": op = "+"; break;
+          case "N": op = "-"; break;
+          case "P": op = "*"; break;
+          case "D": op = "%"; break;
+          default: {
+              Debug.Assert(treeNode.SubtreeCount == 1);
+              break;
+            }
         }
-        term = AutoDiff.TermBuilder.Sum(terms);
-        return true;
-      }
-      if (node.Symbol is Subtraction) {
-        List<AutoDiff.Term> terms = new List<Term>();
-        for (int i = 0; i < node.SubtreeCount; i++) {
-          AutoDiff.Term t;
-          if (!TryTransformToAutoDiff(node.GetSubtree(i), variables, parameters, variableNames, out t)) {
-            term = null;
-            return false;
-          }
-          if (i > 0) t = -t;
-          terms.Add(t);
+        // nonterminal
+        if (op == "+" || op == "-") sb.Append("(");
+        TreeToSentence(treeNode.Subtrees.First(), sb);
+        foreach (var subTree in treeNode.Subtrees.Skip(1)) {
+          sb.Append(op);
+          TreeToSentence(subTree, sb);
         }
-        term = AutoDiff.TermBuilder.Sum(terms);
-        return true;
-      }
-      if (node.Symbol is Multiplication) {
-        AutoDiff.Term a, b;
-        if (!TryTransformToAutoDiff(node.GetSubtree(0), variables, parameters, variableNames, out a) ||
-          !TryTransformToAutoDiff(node.GetSubtree(1), variables, parameters, variableNames, out b)) {
-          term = null;
-          return false;
-        } else {
-          List<AutoDiff.Term> factors = new List<Term>();
-          foreach (var subTree in node.Subtrees.Skip(2)) {
-            AutoDiff.Term f;
-            if (!TryTransformToAutoDiff(subTree, variables, parameters, variableNames, out f)) {
-              term = null;
-              return false;
-            }
-            factors.Add(f);
-          }
-          term = AutoDiff.TermBuilder.Product(a, b, factors.ToArray());
-          return true;
-        }
-      }
-      if (node.Symbol is Division) {
-        // only works for at least two subtrees
-        AutoDiff.Term a, b;
-        if (!TryTransformToAutoDiff(node.GetSubtree(0), variables, parameters, variableNames, out a) ||
-          !TryTransformToAutoDiff(node.GetSubtree(1), variables, parameters, variableNames, out b)) {
-          term = null;
-          return false;
-        } else {
-          List<AutoDiff.Term> factors = new List<Term>();
-          foreach (var subTree in node.Subtrees.Skip(2)) {
-            AutoDiff.Term f;
-            if (!TryTransformToAutoDiff(subTree, variables, parameters, variableNames, out f)) {
-              term = null;
-              return false;
-            }
-            factors.Add(1.0 / f);
-          }
-          term = AutoDiff.TermBuilder.Product(a, 1.0 / b, factors.ToArray());
-          return true;
-        }
-      }
-      
-      if (node.Symbol is StartSymbol) {
-        var alpha = new AutoDiff.Variable();
-        var beta = new AutoDiff.Variable();
-        variables.Add(beta);
-        variables.Add(alpha);
-        AutoDiff.Term branchTerm;
-        if (TryTransformToAutoDiff(node.GetSubtree(0), variables, parameters, variableNames, out branchTerm)) {
-          term = branchTerm * alpha + beta;
-          return true;
-        } else {
-          term = null;
-          return false;
-        }
-      }
-      term = null;
-      return false;
-    }
-     */
+        if (op == "+" || op == "-") sb.Append(")");
+      }
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs

@@ -17 +17 @@
     // interprets sentences from L(G(Expr)):
     // Expr -> Term { ('+' | '-' | '^' ) Term } 
-    // Term -> Fact { ('*' | '/') Fact }
+    // Term -> Fact { ('*' | '%') Fact }
     // Fact -> '!' Expr | '(' Expr ')' | Var | const
     // Var -> 'a'..'z'
     // const -> '0' .. '9'
 
+    // uses protected division symbol %
     // constants are Koza-style ephemeral random constants (ERC). for now we only allow up to 10 constants.
     // The constant symbols '0' .. '9' are treated as ERC indices
@@ -35 +36 @@
       var d = new double[vars.Length];
       for (int i = 0; i < vars.Length; i++) d[i] = vars[i] ? 1.0 : 0.0;
-      return ! DoubleExtensions.IsAlmost(Expr(d, erc), 0);
+      return !DoubleExtensions.IsAlmost(Expr(d, erc), 0);
     }
 
@@ -73 +74 @@
         if (curSy == '+') {
           NewSy();
-          r += Expr(d, erc);
+          r += Term(d, erc);
         } else if (curSy == '-') {
           NewSy();
-          r -= Expr(d, erc);
+          r -= Term(d, erc);
         } else {
           NewSy();
-          var e = Expr(d, erc);
-          r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
+          throw new NotImplementedException();
+          // var e = Expr(d, erc);
+          // r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
         }
         curSy = CurSy();
@@ -91 +93 @@
       r = Fact(d, erc);
       var curSy = CurSy();
-      while (curSy == '*' || curSy == '/') {
+      while (curSy == '*' || curSy == '%') {
         if (curSy == '*') {
           NewSy();
-          r *= Term(d, erc);
+          r *= Fact(d, erc);
         } else {
           NewSy();
-          r /= Term(d, erc);
+          var nom = Fact(d, erc);
+          if (HeuristicLab.Common.Extensions.IsAlmost(nom, 0.0)) nom = 1.0;
+          r /= nom;
         }
         curSy = CurSy();

branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs

@@ -3 +3 @@
 using System.Diagnostics;
 using System.Globalization;
+using System.Runtime.Remoting.Messaging;
 using System.Text;
 using System.Threading;
@@ -13 +14 @@
 using HeuristicLab.Algorithms.GrammaticalOptimization;
 using HeuristicLab.Problems.GrammaticalOptimization;
+using HeuristicLab.Problems.GrammaticalOptimization.SymbReg;
 using BoltzmannExplorationPolicy = HeuristicLab.Algorithms.Bandits.BanditPolicies.BoltzmannExplorationPolicy;
 using EpsGreedyPolicy = HeuristicLab.Algorithms.Bandits.BanditPolicies.EpsGreedyPolicy;
@@ -25 +27 @@
 
       //RunDemo();
-      //RunGpDemo();
+      RunGpDemo();
       // RunGridTest();
-      RunGpGridTest();
+      //RunGpGridTest();
     }
 
@@ -297 +299 @@
       const int maxIterations = 100000;
 
+      //var prob = new SymbolicRegressionProblem(new Random(31415), "Tower");
+      var prob = new SymbolicRegressionPoly10Problem();
+      var sgp = new OffspringSelectionGP(prob, new Random(seed), true);
+      RunGP(sgp, prob, 200000, 500, 0.15, 50);
     }
 
@@ -303 +309 @@
       const int nReps = 20;
       const int seed = 31415;
-      const int maxIters = 100000;
+      const int maxIters = 200000;
       var rand = new Random(seed);
       var problemFactories = new Func<ISymbolicExpressionTreeProblem>[]
       {
+        () => new SymbolicRegressionPoly10Problem(), 
         () => new SantaFeAntProblem(), 
-        () => new SymbolicRegressionPoly10Problem(), 
-      };
-      foreach (var popSize in new int[] { 50, 100, 250, 500, 1000, 2500, 5000 }) {
-        foreach (var mutationRate in new double[] {/* 0.05, 0.10, */ 0.15, /* 0.25, 0.3 */ }) {
-          foreach (var maxSize in new int[] { 30, 50, 100 }) {
-            foreach (var problemFactory in problemFactories)
-              for (int i = 0; i < nReps; i++) {
-                var solverSeed = rand.Next();
-                {
-                  var prob = problemFactory();
-                  RunStandardGP(prob, solverSeed, maxIters, popSize, mutationRate, maxSize);
+      };
+      foreach (var popSize in new int[] { 50, 100, 250, 500, 1000, 2500, 5000, 10000 }) {
+        foreach (var mutationRate in new double[] { /* 0.05, /* 0.10, */ 0.15, /* 0.25, 0.3 */}) {
+          foreach (var maxSize in new int[] { 30, 50, 100, 150, 250 }) {
+            // skip experiments that are already done
+            if (popSize == 10000 || maxSize == 150 || maxSize == 250) {
+              foreach (var problemFactory in problemFactories)
+                for (int i = 0; i < nReps; i++) {
+                  var solverSeed = rand.Next();
+                  {
+                    var prob = problemFactory();
+                    var sgp = new StandardGP(prob, new Random(solverSeed));
+                    RunGP(sgp, prob, maxIters, popSize, mutationRate, maxSize);
+                  }
+                  // {
+                  //   var prob = problemFactory();
+                  //   var osgp = new OffspringSelectionGP(prob, new Random(solverSeed));
+                  //   RunGP(osgp, prob, maxIters, popSize, mutationRate, maxSize);
+                  // }
                 }
-                {
-                  var prob = problemFactory();
-                  RunOSGP(prob, solverSeed, maxIters, popSize, mutationRate, maxSize);
-                }
-              }
+            }
           }
         }
@@ -330 +341 @@
     }
 
-    private static void RunStandardGP(ISymbolicExpressionTreeProblem prob, int solverSeed, int maxIters, int popSize, double mutationRate, int maxSize) {
+    private static void RunGP(IGPSolver gp, ISymbolicExpressionTreeProblem prob, int maxIters, int popSize, double mutationRate, int maxSize) {
       int iterations = 0;
       var globalStatistics = new SentenceSetStatistics(prob.BestKnownQuality(maxSize));
-
-      var gp = new StandardGP(prob, new Random(solverSeed));
+      var gpName = gp.GetType().Name;
+      var probName = prob.GetType().Name;
       gp.SolutionEvaluated += (sentence, quality) => {
         iterations++;
         globalStatistics.AddSentence(sentence, quality);
 
-        if (iterations % 10000 == 0) {
-          Console.WriteLine("\"{0,25}\" \"{1,25}\" {2}", gp, prob, globalStatistics);
+        if (iterations % 1000 == 0) {
+          Console.WriteLine("\"{0,25}\" {1} {2:N2} {3} \"{4,25}\" {5}", gpName, popSize, mutationRate, maxSize, probName, globalStatistics);
         }
       };
@@ -349 +360 @@
       gp.MaxSolutionDepth = maxSize + 2;
 
-      var sw = new Stopwatch();
-
-      sw.Start();
       gp.Run(maxIters);
-      sw.Stop();
-
-      Console.WriteLine("\"{0,25}\" \"{1,25}\" {2}", gp, prob, globalStatistics);
-
-      // Console.WriteLine("{0:F2} sec {1,10:F1} sols/sec {2,10:F1} ns/sol",
-      //   sw.Elapsed.TotalSeconds,
-      //   maxIters / (double)sw.Elapsed.TotalSeconds,
-      //   (double)sw.ElapsedMilliseconds * 1000 / maxIters);
-    }
-
-    private static void RunOSGP(ISymbolicExpressionTreeProblem prob, int solverSeed, int maxIters, int popSize, double mutationRate, int maxSize) {
-      int iterations = 0;
-      var globalStatistics = new SentenceSetStatistics(prob.BestKnownQuality(maxSize));
-
-      var gp = new OffspringSelectionGP(prob, new Random(solverSeed));
-      gp.SolutionEvaluated += (sentence, quality) => {
-        iterations++;
-        globalStatistics.AddSentence(sentence, quality);
-
-        if (iterations % 10000 == 0) {
-          Console.WriteLine("\"{0,25}\" \"{1,25}\" {2}", gp, prob, globalStatistics);
-        }
-      };
-
-      gp.PopulationSize = popSize;
-      gp.MutationRate = mutationRate;
-      gp.MaxSolutionSize = maxSize + 2;
-      gp.MaxSolutionDepth = maxSize + 2;
-
-      var sw = new Stopwatch();
-
-      sw.Start();
-      gp.Run(maxIters);
-      sw.Stop();
-
-      Console.WriteLine("\"{0,25}\" \"{1,25}\" {2}", gp, prob, globalStatistics);
-
-      // Console.WriteLine("{0:F2} sec {1,10:F1} sols/sec {2,10:F1} ns/sol",
-      //   sw.Elapsed.TotalSeconds,
-      //   maxIters / (double)sw.Elapsed.TotalSeconds,
-      //   (double)sw.ElapsedMilliseconds * 1000 / maxIters);
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSolvers.cs

@@ -2 +2 @@
 using HeuristicLab.Algorithms.GeneticProgramming;
 using HeuristicLab.Algorithms.GrammaticalOptimization;
+using HeuristicLab.Problems.GrammaticalOptimization.SymbReg;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
 
@@ -154 +155 @@
 
     [TestMethod]
-    public void TestOSGP() {
-      var prob = new SymbolicRegressionPoly10Problem();
+    public void TestOSGP()
+    {
+      const int seed = 31415;
+      var prob = new SymbolicRegressionProblem(new Random(seed), "Tower");
       var rand = new Random(31415);
       var osgp = new OffspringSelectionGP(prob, rand);
-      osgp.PopulationSize = 1000;
-      osgp.MaxSolutionSize = 50;
+      osgp.PopulationSize = 500;
+      osgp.MaxSolutionSize = 100;
       osgp.MaxSolutionDepth = 20;
 
@@ -166 +169 @@
 
       osgp.FoundNewBestSolution += (sentence, quality) => {
-        Assert.Inconclusive(string.Format("{0:N3} {1}", quality, sentence));
+        // Assert.Inconclusive(string.Format("{0:N3} {1}", quality, sentence));
         bestSentence = sentence;
         bestQuality = quality;

branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSymbRegInstances.cs

@@ -1 +1 @@
 using System;
 using System.Linq;
+using HeuristicLab.Algorithms.GeneticProgramming;
 using HeuristicLab.Algorithms.GrammaticalOptimization;
 using HeuristicLab.Problems.GrammaticalOptimization.SymbReg;
@@ -13 +14 @@
 
       var problem = new SymbolicRegressionProblem(new Random(), "Tower");
-
+      double r2;
+      Assert.AreEqual(problem.Evaluate("a*b"), problem.OptimizeConstantsAndEvaluate("a*b"));
+      Assert.AreEqual(problem.OptimizeConstantsAndEvaluate("a*b"), problem.Evaluate("a*b"));
+      Assert.AreEqual(problem.OptimizeConstantsAndEvaluate("0*a*b"), problem.Evaluate("a*b"), 1E-6);
+      Assert.AreEqual(problem.OptimizeConstantsAndEvaluate("0*a*b+1"), problem.Evaluate("a*b"), 1E-6);
+      Assert.IsTrue(problem.OptimizeConstantsAndEvaluate("0*a+b") >= problem.Evaluate("a+b"));
+      Assert.AreEqual(problem.OptimizeConstantsAndEvaluate("0*a+0*b"), problem.Evaluate("a+b"), 1E-6);
+      Assert.IsTrue(problem.OptimizeConstantsAndEvaluate("0*a+1*b") >= problem.Evaluate("a+b"));
     }
   }