Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliPolicyActionInfo.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliPolicyActionInfo.cs	(revision 11832)
@@ -9,6 +9,4 @@
 namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
   public class BernoulliPolicyActionInfo : IBanditPolicyActionInfo {
-    private double knownValue;
-    public bool Disabled { get { return NumSuccess == -1; } }
     public int NumSuccess { get; private set; }
     public int NumFailure { get; private set; }
@@ -16,11 +14,8 @@
     public double Value {
       get {
-        if (Disabled) return knownValue;
-        else
-          return NumSuccess / (double)(Tries);
+        return NumSuccess / (double)(Tries);
       }
     }
     public void UpdateReward(double reward) {
-      Debug.Assert(!Disabled);
       //Debug.Assert(reward.IsAlmost(0.0) || reward.IsAlmost(1.0));
 
@@ -29,16 +24,10 @@
       else NumFailure++;
     }
-    public void Disable(double reward) {
-      this.NumSuccess = -1;
-      this.NumFailure = -1;
-      this.knownValue = reward;
-    }
     public void Reset() {
       NumSuccess = 0;
       NumFailure = 0;
-      knownValue = 0.0;
     }
     public void PrintStats() {
-      Console.WriteLine("expected value {0,5:F2} disabled {1}", Value, Disabled);
+      Console.WriteLine("expected value {0,5:F2}", Value);
     }
   }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliThompsonSamplingPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliThompsonSamplingPolicy.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BernoulliThompsonSamplingPolicy.cs	(revision 11832)
@@ -21,5 +21,4 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         var theta = Rand.BetaRand(random, aInfo.NumSuccess + alpha, aInfo.NumFailure + beta);
         if (theta > maxTheta) {
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs	(revision 11832)
@@ -14,9 +14,9 @@
     public double Value {
       get {
-          return Tries > 0 ? SumReward / Tries : 0.0;
+        return Tries > 0 ? SumReward / Tries : 0.0;
       }
     }
     public DefaultPolicyActionInfo() {
-      MaxReward = double.MinValue;
+      MaxReward = 0.0;
     }
 
@@ -33,4 +33,8 @@
     }
 
+    public override string ToString() {
+      return string.Format("{0:F3} {1:F3} {2}", Value, MaxReward, Tries);
+    }
+
     public static Func<DefaultPolicyActionInfo, double> AverageReward {
       get {
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GaussianThompsonSamplingPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GaussianThompsonSamplingPolicy.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GaussianThompsonSamplingPolicy.cs	(revision 11832)
@@ -31,5 +31,4 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
 
         var tries = aInfo.Tries;
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs	(revision 11832)
@@ -8,8 +8,5 @@
 namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
   public class MeanAndVariancePolicyActionInfo : IBanditPolicyActionInfo {
-    private bool disabled;
-    public bool Disabled { get { return disabled; } }
     private OnlineMeanAndVarianceEstimator estimator = new OnlineMeanAndVarianceEstimator();
-    private double knownValue;
     public int Tries { get { return estimator.N; } }
     public double SumReward { get { return estimator.Sum; } }
@@ -18,23 +15,13 @@
     public double Value {
       get {
-        if (disabled) return knownValue;
-        else
-          return AvgReward;
+        return AvgReward;
       }
     }
 
     public void UpdateReward(double reward) {
-      Debug.Assert(!Disabled);
       estimator.UpdateReward(reward);
     }
 
-    public void Disable(double reward) {
-      disabled = true;
-      this.knownValue = reward;
-    }
-
     public void Reset() {
-      disabled = false;
-      knownValue = 0.0;
       estimator.Reset();
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs	(revision 11832)
@@ -14,5 +14,5 @@
       var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
 
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
 
       int aIdx = -1;
@@ -21,5 +21,4 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs	(revision 11832)
@@ -12,5 +12,5 @@
     public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
       var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
       double bestQ = double.NegativeInfinity;
       int aIdx = -1;
@@ -18,5 +18,4 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (totalTries <= 1 || aInfo.Tries <= 1 || aInfo.Tries <= Math.Ceiling(8 * Math.Log(totalTries))) {
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericContextualGrammarPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericContextualGrammarPolicy.cs	(revision 11832)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericContextualGrammarPolicy.cs	(revision 11832)
@@ -0,0 +1,163 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Runtime.ExceptionServices;
+using System.Text;
+using System.Text.RegularExpressions;
+using System.Threading;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  public sealed class GenericContextualGrammarPolicy : IGrammarPolicy {
+    private Dictionary<string, IBanditPolicyActionInfo> stateInfo; // stores the necessary information for bandit policies for each state (=canonical phrase)
+    private HashSet<string> done;
+    private readonly bool useCanonicalPhrases;
+    private readonly IProblem problem;
+    private readonly IBanditPolicy banditPolicy;
+
+    public GenericContextualGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalPhrases = false) {
+      this.useCanonicalPhrases = useCanonicalPhrases;
+      this.problem = problem;
+      this.banditPolicy = banditPolicy;
+      this.stateInfo = new Dictionary<string, IBanditPolicyActionInfo>();
+      this.done = new HashSet<string>();
+    }
+
+    private IBanditPolicyActionInfo[] activeAfterStates; // don't allocate each time
+    private int[] actionIndexMap; // don't allocate each time
+
+    public bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
+      // fail if all states are done (corresponding state infos are disabled)
+      if (afterStates.All(s => Done(s))) {
+        // fail because all follow states have already been visited => also disable the current state (if we can be sure that it has been fully explored)
+        MarkAsDone(curState);
+
+        selectedStateIdx = -1;
+        return false;
+      }
+
+      // determine active actions (not done yet) and create an array to map the selected index back to original actions
+      if (activeAfterStates == null || activeAfterStates.Length < afterStates.Count()) {
+        activeAfterStates = new IBanditPolicyActionInfo[afterStates.Count()];
+        actionIndexMap = new int[afterStates.Count()];
+      }
+      var idx = 0; int originalIdx = 0;
+      foreach (var afterState in afterStates) {
+        if (!Done(afterState)) {
+          activeAfterStates[idx] = GetStateInfo(afterState);
+          actionIndexMap[idx] = originalIdx;
+          idx++;
+        }
+        originalIdx++;
+      }
+
+      selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))];
+
+      return true;
+    }
+
+
+    private IBanditPolicyActionInfo GetStateInfo(string state) {
+      var s = Context(state);
+      IBanditPolicyActionInfo info;
+      if (!stateInfo.TryGetValue(s, out info)) {
+        info = banditPolicy.CreateActionInfo();
+        stateInfo[s] = info;
+      }
+      return info;
+    }
+
+    private string Context(string state) {
+      // var cutOff = problem.Grammar.IsTerminal(state) ? 0 : 2;
+      // var contextLen = 7;
+      // var firstPos = Math.Max(0, state.Length - contextLen - cutOff);
+      // var lastPos = Math.Max(0, Math.Min(state.Length, state.Length - cutOff));
+      // var context = state.Substring(firstPos, (lastPos - firstPos));
+      var contextLen = 5;
+      var firstPos = Math.Max(0, state.Length - contextLen);
+      var lastPos = Math.Min(state.Length, firstPos + contextLen);
+      var context = state.Substring(firstPos, (lastPos - firstPos));
+      return context + Regex.Matches(state, "(?=" + Regex.Escape(context) + ")").Count;
+
+
+      //var lastPlusPos = Math.Max(0, state.LastIndexOf('+') + 1);
+      //var context = state.Substring(lastPlusPos);
+      //return context + Regex.Matches(state, "(?=" + Regex.Escape(context) + ")").Count; 
+    }
+
+    public void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
+      foreach (var state in stateTrajectory) {
+        GetStateInfo(state).UpdateReward(reward);
+
+        // only the last state can be terminal
+        if (problem.Grammar.IsTerminal(state)) {
+          MarkAsDone(state);
+        }
+      }
+    }
+
+
+    public void Reset() {
+      stateInfo.Clear();
+      done.Clear();
+    }
+
+    public int GetTries(string state) {
+      var s = Context(state);
+      if (stateInfo.ContainsKey(s)) return stateInfo[s].Tries;
+      else return 0;
+    }
+
+    public double GetValue(string state) {
+      var s = Context(state);
+      if (stateInfo.ContainsKey(s)) return stateInfo[s].Value;
+      else return 0.0; // TODO: check alternatives
+    }
+
+    // the canonical states for the value function (banditInfos) and the done set must be distinguished
+    // sequences of different length could have the same canonical representation and can have the same value (banditInfo)
+    // however, if the canonical representation of a state is shorter than we must not mark the canonical state as done when all possible derivations from the initial state have been explored
+    // eg. in the ant problem the canonical representation for ...lllA is ...rA
+    // even though all possible derivations (of limited length) of lllA have been visited we must not mark the state rA as done
+    private void MarkAsDone(string state) {
+      var s = CanonicalState(state);
+      // when the lengths of the canonical string and the original string are the same we also disable the actions
+      // always disable terminals
+      Debug.Assert(s.Length <= state.Length);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        Debug.Assert(!done.Contains(s));
+        done.Add(s);
+      } else {
+        // for non-terminals where the canonical string is shorter than the original string we can only disable the canonical representation for all states in the same level
+        Debug.Assert(!done.Contains(s + state.Length));
+        done.Add(s + state.Length); // encode the original length of the state, states in the same level of the tree are treated as equivalent
+      }
+    }
+
+    // symmetric to MarkDone
+    private bool Done(string state) {
+      var s = CanonicalState(state);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        return done.Contains(s);
+      } else {
+        // it is not necessary to visit states if the canonical representation has already been fully explored
+        if (done.Contains(s)) return true;
+        if (done.Contains(s + state.Length)) return true;
+        for (int i = 1; i < state.Length; i++) {
+          if (done.Contains(s + i)) return true;
+        }
+        return false;
+      }
+    }
+
+    private string CanonicalState(string state) {
+      if (useCanonicalPhrases) {
+        return problem.CanonicalRepresentation(state);
+      } else
+        return state;
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericFunctionApproximationGrammarPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericFunctionApproximationGrammarPolicy.cs	(revision 11832)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericFunctionApproximationGrammarPolicy.cs	(revision 11832)
@@ -0,0 +1,171 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Runtime.ExceptionServices;
+using System.Text;
+using System.Text.RegularExpressions;
+using System.Threading;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  public sealed class GenericFunctionApproximationGrammarPolicy : IGrammarPolicy {
+    private Dictionary<string, double> featureWeigths; // stores the necessary information for bandit policies for each state (=canonical phrase)
+    private HashSet<string> done;
+    private readonly bool useCanonicalPhrases;
+    private readonly IProblem problem;
+
+
+    public GenericFunctionApproximationGrammarPolicy(IProblem problem, bool useCanonicalPhrases = false) {
+      this.useCanonicalPhrases = useCanonicalPhrases;
+      this.problem = problem;
+      this.featureWeigths = new Dictionary<string, double>();
+      this.done = new HashSet<string>();
+    }
+
+    private double[] activeAfterStates; // don't allocate each time
+    private int[] actionIndexMap; // don't allocate each time
+
+    public bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
+      // fail if all states are done (corresponding state infos are disabled)
+      if (afterStates.All(s => Done(s))) {
+        // fail because all follow states have already been visited => also disable the current state (if we can be sure that it has been fully explored)
+        MarkAsDone(curState);
+
+        selectedStateIdx = -1;
+        return false;
+      }
+
+      // determine active actions (not done yet) and create an array to map the selected index back to original actions
+      if (activeAfterStates == null || activeAfterStates.Length < afterStates.Count()) {
+        activeAfterStates = new double[afterStates.Count()];
+        actionIndexMap = new int[afterStates.Count()];
+      }
+      var maxIdx = 0; int originalIdx = 0;
+      foreach (var afterState in afterStates) {
+        if (!Done(afterState)) {
+          activeAfterStates[maxIdx] = 0.0;
+          actionIndexMap[maxIdx] = originalIdx;
+
+
+          activeAfterStates[maxIdx] = GetValue(afterState);
+
+          maxIdx++;
+        }
+        originalIdx++;
+      }
+
+      if (random.NextDouble() < 0.2) {
+        selectedStateIdx = actionIndexMap[random.Next(maxIdx)];
+      } else {
+        // find max
+        var bestQ = double.NegativeInfinity;
+        var bestIdx = -1;
+        for (int i = 0; i < maxIdx; i++) {
+          if (activeAfterStates[i] > bestQ) {
+            bestQ = activeAfterStates[i];
+            bestIdx = i;
+          }
+        }
+        selectedStateIdx = actionIndexMap[bestIdx];
+      }
+
+      return true;
+    }
+
+
+    public void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
+      foreach (var state in stateTrajectory) {
+        UpdateWeights(state, reward);
+
+        // only the last state can be terminal
+        if (problem.Grammar.IsTerminal(state)) {
+          MarkAsDone(state);
+        }
+      }
+    }
+
+
+    private IEnumerable<KeyValuePair<string, double>> Values {
+      get { return featureWeigths.OrderByDescending(p => p.Value); }
+    }
+
+    public void Reset() {
+      featureWeigths.Clear();
+      done.Clear();
+    }
+
+    public int GetTries(string state) {
+      return 1;
+    }
+
+    public double GetValue(string state) {
+      return problem.GetFeatures(state).Sum(feature => GetWeight(feature)) ;
+    }
+
+    private double GetWeight(Feature feature) {
+      double w;
+      if (featureWeigths.TryGetValue(feature.Id, out w)) return w * feature.Value;
+      else return 0.0;
+    }
+    private void UpdateWeights(string state, double reward) {
+      const double alpha = 0.01;
+      double delta = reward - GetValue(state);
+      foreach (var feature in problem.GetFeatures(state)) {
+        double w;
+        if (!featureWeigths.TryGetValue(feature.Id, out w)) {
+          featureWeigths[feature.Id] = alpha * delta;
+        } else {
+          featureWeigths[feature.Id] += alpha * delta;
+        }
+      }
+    }
+
+
+
+    // the canonical states for the value function (banditInfos) and the done set must be distinguished
+    // sequences of different length could have the same canonical representation and can have the same value (banditInfo)
+    // however, if the canonical representation of a state is shorter than we must not mark the canonical state as done when all possible derivations from the initial state have been explored
+    // eg. in the ant problem the canonical representation for ...lllA is ...rA
+    // even though all possible derivations (of limited length) of lllA have been visited we must not mark the state rA as done
+    private void MarkAsDone(string state) {
+      var s = CanonicalState(state);
+      // when the lengths of the canonical string and the original string are the same we also disable the actions
+      // always disable terminals
+      Debug.Assert(s.Length <= state.Length);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        Debug.Assert(!done.Contains(s));
+        done.Add(s);
+      } else {
+        // for non-terminals where the canonical string is shorter than the original string we can only disable the canonical representation for all states in the same level
+        Debug.Assert(!done.Contains(s + state.Length));
+        done.Add(s + state.Length); // encode the original length of the state, states in the same level of the tree are treated as equivalent
+      }
+    }
+
+    // symmetric to MarkDone
+    private bool Done(string state) {
+      var s = CanonicalState(state);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        return done.Contains(s);
+      } else {
+        // it is not necessary to visit states if the canonical representation has already been fully explored
+        if (done.Contains(s)) return true;
+        if (done.Contains(s + state.Length)) return true;
+        for (int i = 1; i < state.Length; i++) {
+          if (done.Contains(s + i)) return true;
+        }
+        return false;
+      }
+    }
+
+    private string CanonicalState(string state) {
+      if (useCanonicalPhrases) {
+        return problem.CanonicalRepresentation(state);
+      } else
+        return state;
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11832)
@@ -67,4 +67,7 @@
     <Compile Include="Bandits\IBandit.cs" />
     <Compile Include="Bandits\TruncatedNormalBandit.cs" />
+    <Compile Include="GrammarPolicies\GenericFunctionApproximationGrammarPolicy.cs" />
+    <Compile Include="GrammarPolicies\QLearningGrammarPolicy.cs" />
+    <Compile Include="GrammarPolicies\GenericContextualGrammarPolicy.cs" />
     <Compile Include="GrammarPolicies\GenericTDPolicy.cs" />
     <Compile Include="GrammarPolicies\GenericGrammarPolicy.cs">
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/HeuristicLab.Problems.GrammaticalOptimization.SymbReg.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/HeuristicLab.Problems.GrammaticalOptimization.SymbReg.csproj	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/HeuristicLab.Problems.GrammaticalOptimization.SymbReg.csproj	(revision 11832)
@@ -31,4 +31,11 @@
   </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>
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs	(revision 11832)
@@ -5,4 +5,5 @@
 using System.Security.AccessControl;
 using System.Text;
+using AutoDiff;
 using HeuristicLab.Common;
 using HeuristicLab.Problems.DataAnalysis;
@@ -13,13 +14,14 @@
   // provides bridge to HL regression problem instances
   public class SymbolicRegressionProblem : IProblem {
+
     private const string grammarString = @"
         G(E):
-        E -> V | V+E | V-E | V*E | V/E | (E)
+        E -> V | V+E | V-E | V*E | V/E | (E) | C | C+E | C-E | C*E | C/E 
+        C -> 0..9
         V -> <variables>
         ";
-
+    // C represents Koza-style ERC (the symbol is the index of the ERC), the values are initialized below
 
     private readonly IGrammar grammar;
-    private readonly ExpressionInterpreter interpreter;
 
     private readonly int N;
@@ -27,7 +29,8 @@
     private readonly double[] y;
     private readonly int d;
-
-
-    public SymbolicRegressionProblem(string partOfName) {
+    private readonly double[] erc;
+
+
+    public SymbolicRegressionProblem(Random random, string partOfName) {
       var instanceProvider = new RegressionRealWorldInstanceProvider();
       var dds = instanceProvider.GetDataDescriptors().OfType<RegressionDataDescriptor>();
@@ -50,10 +53,10 @@
         i++;
       }
+      // initialize ERC values
+      erc = Enumerable.Range(0, 10).Select(_ => Rand.RandNormal(random) * 10).ToArray();
 
       char firstVar = 'a';
       char lastVar = Convert.ToChar(Convert.ToByte('a') + d - 1);
       this.grammar = new Grammar(grammarString.Replace("<variables>", firstVar + " .. " + lastVar));
-      this.interpreter = new ExpressionInterpreter();
-
     }
 
@@ -69,15 +72,214 @@
 
     public double Evaluate(string sentence) {
-      return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])));
-    }
-
-
-    // right now only + and * is supported
-    public string CanonicalRepresentation(string terminalPhrase) {
-      //return terminalPhrase;
-      var terms = terminalPhrase.Split('+');
-      return string.Join("+", terms.Select(term => string.Join("", term.Replace("*", "").OrderBy(ch => ch)))
-        .OrderBy(term => term));
-    }
+      var interpreter = new ExpressionInterpreter();
+      return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i], erc)));
+    }
+
+
+    public string CanonicalRepresentation(string phrase) {
+      return phrase;
+      //var terms = phrase.Split('+');
+      //return string.Join("+", terms.Select(term => string.Join("", term.Replace("*", "").OrderBy(ch => ch)))
+      //  .OrderBy(term => term));
+    }
+
+    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>();
+
+      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);
+
+      alglib.lsfitstate state;
+      alglib.lsfitreport rep;
+      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);
+      int k = c.Length;
+
+      alglib.ndimensional_pfunc function_cx_1_func = CreatePFunc(compiledFunc);
+      alglib.ndimensional_pgrad function_cx_1_grad = CreatePGrad(compiledFunc);
+
+      try {
+        alglib.lsfitcreatefg(x, y, c, n, m, k, false, out state);
+        alglib.lsfitsetcond(state, 0.0, 0.0, maxIterations);
+        //alglib.lsfitsetgradientcheck(state, 0.001);
+        alglib.lsfitfit(state, function_cx_1_func, function_cx_1_grad, null, null);
+        alglib.lsfitresults(state, out info, out c, out rep);
+      } catch (ArithmeticException) {
+        return originalQuality;
+      } catch (alglib.alglibexception) {
+        return originalQuality;
+      }
+
+      //info == -7  => constant optimization failed due to wrong gradient
+      if (info != -7) throw new ArgumentException();
+    }
+
+
+    private static alglib.ndimensional_pfunc CreatePFunc(AutoDiff.IParametricCompiledTerm compiledFunc) {
+      return (double[] c, double[] x, ref double func, object o) => {
+        func = compiledFunc.Evaluate(c, x);
+      };
+    }
+
+    private static alglib.ndimensional_pgrad CreatePGrad(AutoDiff.IParametricCompiledTerm compiledFunc) {
+      return (double[] c, double[] x, ref double func, double[] grad, object o) => {
+        var tupel = compiledFunc.Differentiate(c, x);
+        func = tupel.Item2;
+        Array.Copy(tupel.Item1, grad, grad.Length);
+      };
+    }
+
+    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);
+        }
+        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);
+        }
+        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;
+    }
+     */
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestSymbRegInstances.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestSymbRegInstances.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestSymbRegInstances.cs	(revision 11832)
@@ -12,5 +12,5 @@
     public void TestGetDataDescriptors() {
 
-      var problem = new SymbolicRegressionProblem("Tower");
+      var problem = new SymbolicRegressionProblem(new Random(), "Tower");
 
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Feature.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Feature.cs	(revision 11832)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Feature.cs	(revision 11832)
@@ -0,0 +1,18 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  // for the feature extraction function for grammatical optimization problems (sparse representation)
+  public class Feature {
+    public string Id { get; private set; }
+    public double Value { get; private set; }
+
+    public Feature(string id, double val) {
+      this.Id = id;
+      this.Value = val;
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj	(revision 11832)
@@ -43,4 +43,6 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="Feature.cs" />
+    <Compile Include="Problems\KryptosProblem.cs" />
     <Compile Include="Problems\EvenParityProblem.cs" />
     <Compile Include="Problems\ExpressionInterpreter.cs" />
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs	(revision 11832)
@@ -9,5 +9,6 @@
     IGrammar Grammar { get; }
     double Evaluate(string sentence);
-    string CanonicalRepresentation(string terminalPhrase); // canonical state must use correct syntax (must be a valid input for evaluate)
+    string CanonicalRepresentation(string phrase); // canonical state must use correct syntax (must be a valid input for evaluate)
+    IEnumerable<Feature> GetFeatures(string phrase);
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs	(revision 11832)
@@ -50,7 +50,12 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       throw new NotImplementedException();
-      return terminalPhrase;
+      return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
     }
   }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/ExpressionInterpreter.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/ExpressionInterpreter.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/ExpressionInterpreter.cs	(revision 11832)
@@ -3,4 +3,5 @@
 using System.Diagnostics.Eventing.Reader;
 using System.Linq;
+using System.Runtime.CompilerServices;
 using System.Runtime.Remoting.Messaging;
 using System.Text;
@@ -10,4 +11,6 @@
 namespace HeuristicLab.Problems.GrammaticalOptimization {
   public class ExpressionInterpreter {
+    private static readonly double[] emptyErc = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
+
     private string sentence;
     private int syIdx;
@@ -15,19 +18,31 @@
     // Expr -> Term { ('+' | '-' | '^' ) Term } 
     // Term -> Fact { ('*' | '/') Fact }
-    // Fact -> '!' Expr | '(' Expr ')' | Var
+    // Fact -> '!' Expr | '(' Expr ')' | Var | const
     // Var -> 'a'..'z'
+    // const -> '0' .. '9'
+
+    // 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
 
     // for boolean problems the symbol * representes the AND operator, the symbol + represents the OR operator, ! = NOT, ^ = XOR
 
     public bool Interpret(string sentence, bool[] vars) {
+      return Interpret(sentence, vars, emptyErc);
+    }
+
+    public bool Interpret(string sentence, bool[] vars, double[] erc) {
       InitLex(sentence);
       var d = new double[vars.Length];
       for (int i = 0; i < vars.Length; i++) d[i] = vars[i] ? 1.0 : 0.0;
-      return !(Expr(d).IsAlmost(0));
+      return !(Expr(d, erc).IsAlmost(0));
     }
 
     public double Interpret(string sentence, double[] vars) {
+      return Interpret(sentence, vars, emptyErc);
+    }
+
+    public double Interpret(string sentence, double[] vars, double[] erc) {
       InitLex(sentence);
-      return Expr(vars);
+      return Expr(vars, erc);
     }
 
@@ -51,18 +66,18 @@
     }
 
-    private double Expr(double[] d) {
+    private double Expr(double[] d, double[] erc) {
       var r = 0.0;
-      r = Term(d);
+      r = Term(d, erc);
       var curSy = CurSy();
       while (curSy == '+' || curSy == '-' || curSy == '^') {
         if (curSy == '+') {
           NewSy();
-          r += Expr(d);
+          r += Expr(d, erc);
         } else if (curSy == '-') {
           NewSy();
-          r -= Expr(d);
+          r -= Expr(d, erc);
         } else {
           NewSy();
-          var e = Expr(d);
+          var e = Expr(d, erc);
           r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
         }
@@ -72,15 +87,15 @@
     }
 
-    private double Term(double[] d) {
+    private double Term(double[] d, double[] erc) {
       var r = 0.0;
-      r = Fact(d);
+      r = Fact(d, erc);
       var curSy = CurSy();
       while (curSy == '*' || curSy == '/') {
         if (curSy == '*') {
           NewSy();
-          r *= Term(d);
+          r *= Term(d, erc);
         } else {
           NewSy();
-          r /= Term(d);
+          r /= Term(d, erc);
         }
         curSy = CurSy();
@@ -89,20 +104,26 @@
     }
 
-    private double Fact(double[] d) {
+    private double Fact(double[] d, double[] erc) {
       double r = 0.0;
       var curSy = CurSy();
       if (curSy == '!') {
         NewSy();
-        r = Not(Expr(d));
+        r = Not(Expr(d, erc));
       } else if (curSy == '(') {
         NewSy();
-        r = Expr(d);
+        r = Expr(d, erc);
         if (CurSy() != ')') throw new ArgumentException();
         NewSy();
-      } else /* if (curSy >= 'a' && curSy <= 'z') */ {
+      } else if (curSy >= 'a' && curSy <= 'z') {
         int o = (byte)curSy - (byte)'a';
         //int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
         if (o < 0 || o >= d.Length) throw new ArgumentException();
         r = d[o];
+        NewSy();
+      } else /* if (curSy >= '0' && curSy <= '9') */ {
+        int o = (byte)curSy - (byte)'0';
+        //int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
+        if (o < 0 || o >= 10) throw new ArgumentException();
+        r = erc[o];
         NewSy();
       }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs	(revision 11832)
@@ -129,16 +129,16 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       // as the ordering of phrases does not matter we can reorder the phrases
       // and remove duplicates
-      var numPhrases = terminalPhrase.Length / phraseLen;
+      var numPhrases = phrase.Length / phraseLen;
       var phrases = new SortedSet<string>();
       for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
         var sentenceIdx = phraseIdx * phraseLen;
-        var phrase = terminalPhrase.Substring(sentenceIdx, phraseLen);
-        phrase = CanonicalPhrase(phrase);
-        if (!phrases.Contains(phrase)) phrases.Add(phrase);
+        var subphrase = phrase.Substring(sentenceIdx, phraseLen);
+        subphrase = CanonicalPhrase(subphrase);
+        if (!phrases.Contains(subphrase)) phrases.Add(subphrase);
       }
-      var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
+      var remainder = phrase.Substring(numPhrases * phraseLen, phrase.Length - (numPhrases * phraseLen));
       remainder = CanonicalPhrase(remainder);
       if (!phrases.Contains(remainder)) phrases.Add(remainder);
@@ -146,4 +146,14 @@
       return string.Join("", phrases);
     }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
+
+    public override string ToString() {
+      return string.Format("\"FindPhrasesProblem {0} {1} {2} {3:F2} {4} {5:F2} {6}\"", numPhrases, phraseLen,
+        optimalPhrases.Count, correctReward, decoyPhrases.Count, decoyReward, phrasesAsSets);
+    }
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs	(revision 11832)
@@ -39,6 +39,11 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
-      return terminalPhrase;
+    public string CanonicalRepresentation(string phrase) {
+      return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
     }
   }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs	(revision 11832)
@@ -80,6 +80,11 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
-      return terminalPhrase;
+    public string CanonicalRepresentation(string phrase) {
+      return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
     }
   }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs	(revision 11832)
@@ -35,7 +35,12 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
+      //throw new NotImplementedException();
+      return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
       throw new NotImplementedException();
-      return terminalPhrase;
     }
   }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs	(revision 11832)
@@ -113,16 +113,16 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       if (phrasesAsSets) {
         var sb = new StringBuilder();
-        var numPhrases = terminalPhrase.Length / phraseLen;
+        var numPhrases = phrase.Length / phraseLen;
         for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
           var sentenceIdx = phraseIdx * phraseLen;
-          var phrase = terminalPhrase.Substring(sentenceIdx, phraseLen);
-          phrase = CanonicalPhrase(phrase);
-          sb.Append(phrase);
+          var subphrase = phrase.Substring(sentenceIdx, phraseLen);
+          subphrase = CanonicalPhrase(subphrase);
+          sb.Append(subphrase);
         }
 
-        var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
+        var remainder = phrase.Substring(numPhrases * phraseLen, phrase.Length - (numPhrases * phraseLen));
         remainder = CanonicalPhrase(remainder);
         sb.Append(remainder);
@@ -130,5 +130,10 @@
         return sb.ToString();
       } else
-        return terminalPhrase;
+        return phrase;
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
     }
   }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalRoadProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalRoadProblem.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalRoadProblem.cs	(revision 11832)
@@ -29,8 +29,12 @@
       throw new NotImplementedException();
     }
-    public string CanonicalRepresentation(string terminalPhrase) {
-      return terminalPhrase;
+    public string CanonicalRepresentation(string phrase) {
+      return phrase;
     }
 
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs	(revision 11832)
@@ -77,15 +77,20 @@
 
     // in each position there could be multiple correct and incorrect symbols
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       var sb = new StringBuilder();
-      for (int i = 0; i < terminalPhrase.Length; i++) {
-        if (optimalSymbolsForPos[i].Contains(terminalPhrase[i])) {
+      for (int i = 0; i < phrase.Length; i++) {
+        if (optimalSymbolsForPos[i].Contains(phrase[i])) {
           sb.Append(optimalSymbolsForPos[i].First()); // all symbols in the set are equivalent
         } else {
-          sb.Append(terminalPhrase[i]);
+          sb.Append(phrase[i]);
         }
       }
       return sb.ToString();
     }
+
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs	(revision 11832)
@@ -34,9 +34,13 @@
       return regex.Matches(sentence).Count;
     }
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       throw new NotImplementedException();
-      return terminalPhrase;
+      return phrase;
     }
 
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs	(revision 11832)
@@ -29,9 +29,13 @@
       throw new NotImplementedException();
     }
-    public string CanonicalRepresentation(string terminalPhrase) {
+    public string CanonicalRepresentation(string phrase) {
       throw new NotImplementedException();
-      return terminalPhrase;
+      return phrase;
     }
 
+    public IEnumerable<Feature> GetFeatures(string phrase)
+    {
+      throw new NotImplementedException();
+    }
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs	(revision 11832)
@@ -102,7 +102,7 @@
     }
 
-    public string CanonicalRepresentation(string terminalPhrase) {
-      var sb = new StringBuilder(terminalPhrase);
-      string canonicalPhrase = terminalPhrase;
+    public string CanonicalRepresentation(string phrase) {
+      var sb = new StringBuilder(phrase);
+      string canonicalPhrase = phrase;
       string oldPhrase;
       do {
@@ -112,4 +112,8 @@
       } while (canonicalPhrase != oldPhrase);
       return sb.ToString();
+    }
+
+    public IEnumerable<Feature> GetFeatures(string phrase) {
+      return Enumerable.Repeat(new Feature(CanonicalRepresentation(phrase), 1.0), 1);
     }
   }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs	(revision 11832)
@@ -120,4 +120,14 @@
       return canonicalTerm;
     }
+
+    // splits the phrase into terms and creates (sparse) term-occurrance features
+    public IEnumerable<Feature> GetFeatures(string phrase) {
+      var canonicalTerms = new HashSet<string>();
+      foreach (string t in phrase.Split('+')) {
+        canonicalTerms.Add(CanonicalTerm(t));
+      }
+      return canonicalTerms.Select(entry => new Feature(entry, 1.0)).Concat(new Feature[] { new Feature(CanonicalRepresentation(phrase), 1.0) });
+    }
+
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11832)
@@ -24,13 +24,13 @@
       CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
 
-      RunDemo();
-      //RunGridTest();
+      //RunDemo();
+      RunGridTest();
     }
 
     private static void RunGridTest() {
-      int maxIterations = 50000; // for poly-10 with 50000 evaluations no successful try with hl yet
+      int maxIterations = 70000; // for poly-10 with 50000 evaluations no successful try with hl yet
       //var globalRandom = new Random(31415);
       var localRandSeed = 31415;
-      var reps = 10;
+      var reps = 30;
 
       var policyFactories = new Func<IBanditPolicy>[]
@@ -109,14 +109,14 @@
       {
         //(rand) => Tuple.Create((IProblem)new SantaFeAntProblem(), 17),
-        (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:false ), 15),
-        (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:true ), 15),
-        (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:false), 15),
-        (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:true), 15),
-        //(rand) => Tuple.Create((IProblem)new SymbolicRegressionPoly10Problem(), 23)
+        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:false ), 15),
+        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:true ), 15),
+        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:false), 15),
+        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:true), 15),
+        (rand) => Tuple.Create((IProblem)new SymbolicRegressionPoly10Problem(), 23)
       };
 
       foreach (var instanceFactory in instanceFactories) {
-        foreach (var useCanonical in new bool[] { true /*, false */ }) {
-          foreach (var randomTries in new int[] { 0, /* 1, 10, /* 5, 100 /*, 500, 1000 */}) {
+        foreach (var useCanonical in new bool[] { true /*, false */}) {
+          foreach (var randomTries in new int[] { 0 /*, 1, 10 /*, /* 5, 100 /*, 500, 1000 */}) {
             foreach (var policyFactory in policyFactories) {
               var myRandomTries = randomTries;
@@ -142,6 +142,10 @@
                 var problem = instance.Item1;
                 var maxLen = instance.Item2;
-                var alg = new SequentialSearch(problem, maxLen, myLocalRand, myRandomTries,
-                  new GenericGrammarPolicy(problem, policyFactory(), useCanonical));
+                //var alg = new SequentialSearch(problem, maxLen, myLocalRand, myRandomTries,
+                //  new GenericGrammarPolicy(problem, policyFactory(), useCanonical));
+                var alg = new SequentialSearch(problem, maxLen, myLocalRand,
+                  myRandomTries,
+                  new GenericFunctionApproximationGrammarPolicy(problem,
+                    useCanonical));
                 //var alg = new ExhaustiveBreadthFirstSearch(problem, 25);
                 //var alg = new AlternativesContextSampler(problem, 25);
@@ -150,6 +154,6 @@
                   iterations++;
                   globalStatistics.AddSentence(sentence, quality);
-                  if (iterations % 10000 == 0) {
-                    Console.WriteLine("{0,3} {1,5} \"{2,25}\" {3} {4}", i, myRandomTries, policyFactory(), useCanonical, globalStatistics);
+                  if (iterations % 1000 == 0) {
+                    Console.WriteLine("{0,3} {1,5} \"{2,25}\" {3} {4} {5}", i, myRandomTries, policyFactory(), useCanonical, problem.ToString(), globalStatistics);
                   }
                 };
@@ -190,5 +194,5 @@
 
 
-      int maxIterations = 100000;
+      int maxIterations = 1000000;
       int iterations = 0;
       var sw = new Stopwatch();
@@ -199,11 +203,11 @@
 
       //var problem = new RoyalSequenceProblem(random, 10, 30, 2, 1, 0);
+      // var phraseLen = 3;
+      // var numPhrases = 5;
+      // var problem = new RoyalPhraseSequenceProblem(random, 10, numPhrases, phraseLen: phraseLen, numCorrectPhrases: 1, correctReward: 1, incorrectReward: 0.0, phrasesAsSets: false);
+
       //var phraseLen = 3;
       //var numPhrases = 5;
-      //var problem = new RoyalPhraseSequenceProblem(random, 15, numPhrases, phraseLen: phraseLen, numCorrectPhrases: 1, correctReward: 1, incorrectReward: 0.0, phrasesAsSets: true);
-
-      // var phraseLen = 3;
-      // var numPhrases = 5;
-      // var problem = new FindPhrasesProblem(random, 10, numPhrases, phraseLen, numOptimalPhrases: numPhrases, numDecoyPhrases: 200, correctReward: 1.0, decoyReward: 0.5, phrasesAsSets: true);
+      //var problem = new FindPhrasesProblem(random, 10, numPhrases, phraseLen, numOptimalPhrases: numPhrases, numDecoyPhrases: 0, correctReward: 1.0, decoyReward: 0, phrasesAsSets: false);
 
       // good results for symb-reg
@@ -213,4 +217,9 @@
       // - GenericThompsonSamplingPolicy("")
       // - UCTPolicy(0.10) (5 of 5 runs, 35000 iters avg.), 10 successful runs of 10 with rand-tries 0, bei 40000 iters 9 / 10, bei 30000 1 / 10
+      // 2015 01 22: symb-reg: grid test on find-phrases problem showed good results for UCB1TunedPolicy and SequentialSearch with canonical states
+      // - symb-reg: consistent results with UCB1Tuned. finds optimal solution in ~50k iters (new GenericGrammarPolicy(problem, new UCB1TunedPolicy(), true));
+      // 2015 01 23: grid test with canonical states:
+      // - UCTPolicy(0.10) und UCBNormalPolicy 10/10 optimale LÃ¶sungen bei max. 50k iters, etwas schlechter: generic-thompson with variable sigma und bolzmannexploration (100)
+
 
       // good results for artificial ant:
@@ -219,11 +228,11 @@
       // - GaussianModelWithUnknownVariance (and Q= 0.99-quantil) also works well for Ant
       // 2015 01 19: grid test with canonical states (non-canonical slightly worse)
-      // - Threshold Ascent (best 100, 0.01; all variants relatively good)
-      // - Policies where the variance has a large weight compared to the mean? (Gaussian(compatible), Gaussian with fixed variance, UCT with large c, alle TA)
-
-      //var problem = new SymbolicRegressionPoly10Problem();
-
-      var problem = new SantaFeAntProblem();
-      //var problem = new SymbolicRegressionProblem("Tower"); 
+      // - ant: Threshold Ascent (best 100, 0.01; all variants relatively good)
+      // - ant: Policies where the variance has a large weight compared to the mean? (Gaussian(compatible), Gaussian with fixed variance, UCT with large c, alle TA)
+      // - ant: UCB1Tuned with canonical states also works very well for the artificial ant! constistent solutions in less than 10k iters      
+
+      var problem = new SymbolicRegressionPoly10Problem();
+      //var problem = new SantaFeAntProblem();
+      //var problem = new SymbolicRegressionProblem(random, "Tower"); 
       //var problem = new PalindromeProblem();
       //var problem = new HardPalindromeProblem();
@@ -234,7 +243,10 @@
       //var alg = new MctsSampler(problem, 23, random, 0, new EpsGreedyPolicy(0.1));
       //var alg = new SequentialSearch(problem, 23, random, 0,
-      //  new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericGrammarPolicy(problem, new ModifiedUCTPolicy(0.1), true));
-      var alg = new SequentialSearch(problem, 17, random, 0,
-        new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericTDPolicy(problem, true));
+      //  new HeuristicLab.Algorithms.Bandits.GrammarPolicies.QLearningGrammarPolicy(problem, new BoltzmannExplorationPolicy(10),
+      //    1, 1, true));
+      //var alg = new SequentialSearch(problem, 23, random, 0,
+      //  new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericContextualGrammarPolicy(problem, new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1, 1)), true));
+      var alg = new SequentialSearch(problem, 23, random, 0,
+        new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericFunctionApproximationGrammarPolicy(problem, true));
       //var alg = new MctsQLearningSampler(problem, sentenceLen, random, 0, null);
       //var alg = new MctsQLearningSampler(problem, 30, random, 0, new EpsGreedyPolicy(0.2));
@@ -249,5 +261,5 @@
 
       alg.FoundNewBestSolution += (sentence, quality) => {
-        //Console.WriteLine("{0,4} {1,7} {2}", alg.treeDepth, alg.treeSize, globalStatistics);
+        //Console.WriteLine("{0}", globalStatistics);
         //Console.ReadLine();
       };
@@ -255,4 +267,5 @@
         iterations++;
         globalStatistics.AddSentence(sentence, quality);
+
         if (iterations % 1000 == 0) {
           if (iterations % 10000 == 0) Console.Clear();
@@ -260,9 +273,10 @@
           alg.PrintStats();
         }
+
         //Console.WriteLine(sentence);
 
-        if (iterations % 10000 == 0) {
-          //Console.WriteLine("{0,4} {1,7} {2}", alg.treeDepth, alg.treeSize, globalStatistics);
-        }
+        //if (iterations % 10000 == 0) {
+        //  Console.WriteLine("{0}", globalStatistics);
+        //}
       };
 
