Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/EvenParityProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/EvenParityProblem.cs	(revision 11802)
+++ 	(revision )
@@ -1,57 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Diagnostics;
-using System.Linq;
-using System.Text;
-using System.Text.RegularExpressions;
-
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  // 4-bit even parity
-  public class EvenParityProblem : IProblem {
-    // + == OR
-    // * == AND
-    private const string grammarString = @"
-G(S):
-S -> a | b | c | d | a*S | b*S | c*S | d*S | a+S | b+S | c+S | d+S | !S | (S)
-";
-
-    private readonly IGrammar grammar;
-    private readonly ExpressionInterpreter interpreter = new ExpressionInterpreter();
-    public EvenParityProblem() {
-      this.grammar = new Grammar(grammarString);
-    }
-
-    public double BestKnownQuality(int maxLen) {
-      // for now only an upper bound is returned, ideally all fitness cases are predicted correctly
-      return Math.Pow(2, 4);
-    }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    public double Evaluate(string sentence) {
-      var vars = new bool[4];
-      var nCorrect = 0;
-      for (int b0 = 0; b0 <= 1; b0++)
-        for (int b1 = 0; b1 <= 1; b1++)
-          for (int b2 = 0; b2 <= 1; b2++)
-            for (int b3 = 0; b3 <= 1; b3++) {
-              vars[0] = b0 > 0;
-              vars[1] = b1 > 0;
-              vars[2] = b2 > 0;
-              vars[3] = b3 > 0;
-
-              var pred = interpreter.Interpret(sentence, vars);
-              var target = (b0 > 0) ^ (b1 > 0) ^ (b2 > 0) ^ (b3 > 0);
-              if (pred == target) nCorrect++;
-            }
-      return nCorrect;
-    }
-
-    public string CanonicalRepresentation(string terminalPhrase) {
-      throw new NotImplementedException();
-      return terminalPhrase;
-    }
-  }
-}
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs	(revision 11802)
+++ 	(revision )
@@ -1,114 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Diagnostics.Eventing.Reader;
-using System.Linq;
-using System.Runtime.Remoting.Messaging;
-using System.Text;
-using System.Threading.Tasks;
-using HeuristicLab.Common;
-
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  public class ExpressionInterpreter {
-    private string sentence;
-    private int syIdx;
-    // interprets sentences from L(G(Expr)):
-    // Expr -> Term { ('+' | '-' | '^' ) Term } 
-    // Term -> Fact { ('*' | '/') Fact }
-    // Fact -> '!' Expr | '(' Expr ')' | Var
-    // Var -> 'a'..'z'
-
-    // for boolean problems the symbol * representes the AND operator, the symbol + represents the OR operator, ! = NOT, ^ = XOR
-
-    public bool Interpret(string sentence, bool[] vars) {
-      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));
-    }
-
-    public double Interpret(string sentence, double[] vars) {
-      InitLex(sentence);
-      return Expr(vars);
-    }
-
-
-    private void InitLex(string sentence) {
-      this.sentence = sentence;
-      this.syIdx = 0;
-    }
-
-    private char CurSy() {
-      if (syIdx >= sentence.Length) return '\0';
-      return sentence[syIdx];
-    }
-    private void NewSy() {
-      if (syIdx < sentence.Length) syIdx++;
-    }
-
-    // helper for xor
-    private double Not(double x) {
-      return x.IsAlmost(0) ? 1.0 : 0.0;
-    }
-
-    private double Expr(double[] d) {
-      var r = 0.0;
-      r = Term(d);
-      var curSy = CurSy();
-      while (curSy == '+' || curSy == '-' || curSy == '^') {
-        if (curSy == '+') {
-          NewSy();
-          r += Expr(d);
-        } else if (curSy == '-') {
-          NewSy();
-          r -= Expr(d);
-        } else {
-          NewSy();
-          var e = Expr(d);
-          r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
-        }
-        curSy = CurSy();
-      }
-      return r;
-    }
-
-    private double Term(double[] d) {
-      var r = 0.0;
-      r = Fact(d);
-      var curSy = CurSy();
-      while (curSy == '*' || curSy == '/') {
-        if (curSy == '*') {
-          NewSy();
-          r *= Term(d);
-        } else {
-          NewSy();
-          r /= Term(d);
-        }
-        curSy = CurSy();
-      }
-      return r;
-    }
-
-    private double Fact(double[] d) {
-      double r = 0.0;
-      var curSy = CurSy();
-      if (curSy == '!') {
-        NewSy();
-        r = Not(Expr(d));
-      } else if (curSy == '(') {
-        NewSy();
-        r = Expr(d);
-        if (CurSy() != ')') throw new ArgumentException();
-        NewSy();
-      } 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 throw new ArgumentException();
-      return r;
-    }
-
-  }
-}
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/FindPhrasesProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/FindPhrasesProblem.cs	(revision 11802)
+++ 	(revision )
@@ -1,149 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Data.Odbc;
-using System.Diagnostics;
-using System.Linq;
-using System.Text;
-using System.Text.RegularExpressions;
-using HeuristicLab.Common;
-
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  // must find a set of phrases where the ordering of phrases is irrelevant
-  // Parameters
-  // - size of the alphabet
-  // - phrase length
-  // - number of phrases in the sequence
-  // - number of optimal phrases
-  // - reward for optimal phrases
-  // - number of decoy (sub-optimal) phrases
-  // - reward for decoy phrases (must be smaller than reward for optimal phrases)
-  // - phrasesAsSets: a switch to determine wether symbols in a phrase can be shuffled (sets) or if the ordering is relevant (non-sets)
-
-  // this problem should be similar to symbolic regression and should be easier for approaches using a state esimation value and the canoncial state 
-  // when phrases are symbol sets instead of sequences then value-estimation routines should be better (TD)
-  public class FindPhrasesProblem : IProblem {
-
-    private readonly IGrammar grammar;
-    private readonly int numPhrases;
-    private readonly int phraseLen;
-    private readonly double correctReward;
-    private readonly double decoyReward;
-    private readonly bool phrasesAsSets;
-    private readonly SortedSet<string> optimalPhrases;
-    private readonly SortedSet<string> decoyPhrases;
-
-    public FindPhrasesProblem(Random rand, int alphabetSize, int numPhrases, int phraseLen, int numOptimalPhrases, int numDecoyPhrases = 1,
-      double correctReward = 1.0, double decoyReward = 0.0, bool phrasesAsSets = false) {
-      if (alphabetSize <= 0 || alphabetSize > 26) throw new ArgumentException();
-      if (numPhrases <= 0) throw new ArgumentException();
-      if (phraseLen < 1) throw new ArgumentException();
-      if (numOptimalPhrases < numPhrases) throw new ArgumentException();
-      if (numDecoyPhrases < 0) throw new ArgumentException();
-      if (correctReward <= decoyReward) throw new ArgumentException();
-
-      this.numPhrases = numPhrases;
-      this.phraseLen = phraseLen;
-      this.correctReward = correctReward;
-      this.decoyReward = decoyReward;
-      this.phrasesAsSets = phrasesAsSets;
-
-      // create grammar
-      var sentenceSymbol = 'S';
-      var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray();
-      var nonTerminalSymbols = new char[] { 'S' };
-      var rules = terminalSymbols.Select(t => Tuple.Create('S', t.ToString()))
-        .Concat(terminalSymbols.Select(t => Tuple.Create('S', t + "S")));
-
-      this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
-
-      // generate optimal phrases
-      optimalPhrases = new SortedSet<string>();
-      while (optimalPhrases.Count < numOptimalPhrases) {
-        string phrase = "";
-        for (int l = 0; l < phraseLen; l++) {
-          phrase += terminalSymbols.SelectRandom(rand);
-        }
-        phrase = CanonicalPhrase(phrase);
-
-        // don't allow dups
-        if (!optimalPhrases.Contains(phrase)) optimalPhrases.Add(phrase);
-      }
-
-      // generate decoy phrases
-      decoyPhrases = new SortedSet<string>();
-      while (decoyPhrases.Count < numDecoyPhrases) {
-        string phrase = "";
-        for (int l = 0; l < phraseLen; l++) {
-          phrase += terminalSymbols.SelectRandom(rand);
-        }
-        phrase = CanonicalPhrase(phrase);
-
-        // don't allow dups
-        if (!optimalPhrases.Contains(phrase) && !decoyPhrases.Contains(phrase)) decoyPhrases.Add(phrase);
-      }
-
-      Debug.Assert(Evaluate(BestKnownSolution) / BestKnownQuality(phraseLen * numPhrases) == 1.0);
-    }
-
-    public double BestKnownQuality(int maxLen) {
-      return Math.Min(maxLen / phraseLen, numPhrases) * correctReward; // integer division
-    }
-
-    public string BestKnownSolution {
-      get { return string.Join("", optimalPhrases.Take(numPhrases)); }
-    }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    public double Evaluate(string sentence) {
-      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
-      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
-
-
-      // split the sentence in phrases
-      // phrases must not overlap in the sentence, multiple occurences of a phrase are not counted
-      // the order of phrases is not relevant
-      var numPhrases = sentence.Length / phraseLen;
-      var phrases = new SortedSet<string>();
-      for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
-        var sentenceIdx = phraseIdx * phraseLen;
-        var phrase = sentence.Substring(sentenceIdx, phraseLen);
-        phrase = CanonicalPhrase(phrase);
-        if (!phrases.Contains(phrase)) phrases.Add(phrase);
-      }
-
-      // add reward for each correct phrase that occurs in the sentence 
-      // add reward for each decoy phrase that occurs in the sentence
-      var reward = phrases.Intersect(optimalPhrases).Count() * correctReward
-               + phrases.Intersect(decoyPhrases).Count() * decoyReward;
-
-      return reward;
-    }
-
-    // TODO: cache canonical phrases in most-recently used dictionary for increased performance (see symbolicregressionpoly10problem)
-    private string CanonicalPhrase(string phrase) {
-      if (phrasesAsSets) return string.Join("", phrase.OrderBy(ch => (byte)ch));
-      else return phrase;
-    }
-
-    public string CanonicalRepresentation(string terminalPhrase) {
-      // as the ordering of phrases does not matter we can reorder the phrases
-      // and remove duplicates
-      var numPhrases = terminalPhrase.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 remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
-      remainder = CanonicalPhrase(remainder);
-      if (!phrases.Contains(remainder)) phrases.Add(remainder);
-
-      return string.Join("", phrases);
-    }
-  }
-}
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HardPalindromeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HardPalindromeProblem.cs	(revision 11802)
+++ 	(revision )
@@ -1,45 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  public class HardPalindromeProblem : IProblem {
-    // length of the longest palindrome in the sentence + number of different symbols occurring in the palindrome
-    private const string grammarString = @"
-G(S):
-S -> T | TS
-T -> a .. z
-";
-
-    private readonly IGrammar grammar;
-    public HardPalindromeProblem() {
-      this.grammar = new Grammar(grammarString);
-    }
-
-    public double BestKnownQuality(int maxLen) {
-      // the whole sentence is a palindrome + each symbol occurs only once or twice
-      // for odd total length the number of different characters can be larger than len/2 (aba)
-      // the second part is limited to 26 different characters
-      return maxLen + Math.Min(26, (maxLen + 1) / 2);
-    }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    public double Evaluate(string sentence) {
-      var palindrome = PalindromeProblem.LongestPalindromicSubstring(sentence);
-      var palindromeBytes = ASCIIEncoding.ASCII.GetBytes(palindrome);
-      var chrCount = new int[256];
-      foreach (var b in palindromeBytes) {
-        chrCount[b]++;
-      }
-      return palindrome.Length + chrCount.Count(c => c > 0);
-    }
-
-    public string CanonicalRepresentation(string terminalPhrase) {
-      return terminalPhrase;
-    }
-  }
-}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj	(revision 11802)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj	(revision 11803)
@@ -43,24 +43,24 @@
   </ItemGroup>
   <ItemGroup>
-    <Compile Include="FindPhrasesProblem.cs" />
-    <Compile Include="RoyalPhraseSequenceProblem.cs" />
-    <Compile Include="RoyalSequenceProblem.cs" />
-    <Compile Include="ExpressionInterpreter.cs" />
+    <Compile Include="Problems\EvenParityProblem.cs" />
+    <Compile Include="Problems\ExpressionInterpreter.cs" />
+    <Compile Include="Problems\FindPhrasesProblem.cs" />
+    <Compile Include="Problems\HardPalindromeProblem.cs" />
+    <Compile Include="Problems\PalindromeProblem.cs" />
+    <Compile Include="Problems\RoyalPairProblem.cs" />
+    <Compile Include="Problems\RoyalPhraseSequenceProblem.cs" />
+    <Compile Include="Problems\RoyalRoadProblem.cs" />
+    <Compile Include="Problems\RoyalSequenceProblem.cs" />
+    <Compile Include="Problems\RoyalSymbolProblem.cs" />
+    <Compile Include="Problems\RoyalTreeProblem.cs" />
+    <Compile Include="Problems\SantaFeAntProblem.cs" />
+    <Compile Include="Problems\SymbolicRegressionPoly10Problem.cs" />
     <Compile Include="Grammar.cs" />
-    <Compile Include="EvenParityProblem.cs" />
     <Compile Include="ReadonlySequence.cs" />
     <Compile Include="SentenceSetStatistics.cs" />
     <Compile Include="Sequence.cs" />
-    <Compile Include="SymbolicRegressionPoly10Problem.cs" />
-    <Compile Include="SantaFeAntProblem.cs" />
     <Compile Include="IProblem.cs" />
-    <Compile Include="HardPalindromeProblem.cs" />
     <Compile Include="IGrammar.cs" />
-    <Compile Include="PalindromeProblem.cs" />
-    <Compile Include="RoyalPairProblem.cs" />
-    <Compile Include="RoyalSymbolProblem.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
-    <Compile Include="RoyalRoadProblem.cs" />
-    <Compile Include="RoyalTreeProblem.cs" />
   </ItemGroup>
   <ItemGroup>
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/PalindromeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/PalindromeProblem.cs	(revision 11802)
+++ 	(revision )
@@ -1,86 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  public class PalindromeProblem : IProblem {
-    // length of the longest palindrome in the sentence
-    private const string grammarString = @"
-G(S):
-S -> T | TS
-T -> a .. z
-";
-
-    private readonly IGrammar grammar;
-    public PalindromeProblem() {
-      this.grammar = new Grammar(grammarString);
-    }
-
-    public double BestKnownQuality(int maxLen) {
-      // the whole sentence is a palindrome
-      return maxLen;
-    }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    public double Evaluate(string sentence) {
-      return LongestPalindromicSubstring(sentence).Length;
-    }
-
-
-    private static string Preprocess(string s) {
-      var t = new char[2 * s.Length + 3];
-      t[0] = '$';
-      t[t.Length - 2] = '#';
-      t[t.Length - 1] = '@';
-      for (int i = 0; i < s.Length; i++) {
-        t[2 * (i) + 1] = '#';
-        t[2 * i + 2] = s[i];
-      }
-
-      return new string(t);
-    }
-
-    public static string LongestPalindromicSubstring(string str) {
-      var tLen = 2 * str.Length + 3;
-      var p = new int[tLen];
-      var t = Preprocess(str);
-
-      var center = 0;
-      var right = 0;
-      for (int i = 1; i < t.Length - 1; i++) {
-        var mirror = 2 * center - i;
-        if (right > i) p[i] = Math.Min(right - i, p[mirror]);
-        while (t[i + (1 + p[i])] == t[i - (1 + p[i])]) {
-          p[i]++;
-        }
-        if (i + p[i] > right) {
-          center = i;
-          right = i + p[i];
-        }
-      }
-      var len = 0;
-      center = 0;
-      for (int i = 0; i < t.Length - 1; i++) {
-        if (p[i] > len) {
-          center = i;
-          len = p[i];
-        }
-      }
-
-      var start = (center - 1 - len) / 2;
-      var result = new StringBuilder();
-      for (int i = 0; i < len; i++) {
-        result.Append(str[start + i]);
-      }
-      return result.ToString();
-    }
-
-    public string CanonicalRepresentation(string terminalPhrase) {
-      return terminalPhrase;
-    }
-  }
-}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs	(revision 11803)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs	(revision 11803)
@@ -0,0 +1,57 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Text.RegularExpressions;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  // 4-bit even parity
+  public class EvenParityProblem : IProblem {
+    // + == OR
+    // * == AND
+    private const string grammarString = @"
+G(S):
+S -> a | b | c | d | a*S | b*S | c*S | d*S | a+S | b+S | c+S | d+S | !S | (S)
+";
+
+    private readonly IGrammar grammar;
+    private readonly ExpressionInterpreter interpreter = new ExpressionInterpreter();
+    public EvenParityProblem() {
+      this.grammar = new Grammar(grammarString);
+    }
+
+    public double BestKnownQuality(int maxLen) {
+      // for now only an upper bound is returned, ideally all fitness cases are predicted correctly
+      return Math.Pow(2, 4);
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      var vars = new bool[4];
+      var nCorrect = 0;
+      for (int b0 = 0; b0 <= 1; b0++)
+        for (int b1 = 0; b1 <= 1; b1++)
+          for (int b2 = 0; b2 <= 1; b2++)
+            for (int b3 = 0; b3 <= 1; b3++) {
+              vars[0] = b0 > 0;
+              vars[1] = b1 > 0;
+              vars[2] = b2 > 0;
+              vars[3] = b3 > 0;
+
+              var pred = interpreter.Interpret(sentence, vars);
+              var target = (b0 > 0) ^ (b1 > 0) ^ (b2 > 0) ^ (b3 > 0);
+              if (pred == target) nCorrect++;
+            }
+      return nCorrect;
+    }
+
+    public string CanonicalRepresentation(string terminalPhrase) {
+      throw new NotImplementedException();
+      return terminalPhrase;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/ExpressionInterpreter.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/ExpressionInterpreter.cs	(revision 11803)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/ExpressionInterpreter.cs	(revision 11803)
@@ -0,0 +1,114 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics.Eventing.Reader;
+using System.Linq;
+using System.Runtime.Remoting.Messaging;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class ExpressionInterpreter {
+    private string sentence;
+    private int syIdx;
+    // interprets sentences from L(G(Expr)):
+    // Expr -> Term { ('+' | '-' | '^' ) Term } 
+    // Term -> Fact { ('*' | '/') Fact }
+    // Fact -> '!' Expr | '(' Expr ')' | Var
+    // Var -> 'a'..'z'
+
+    // for boolean problems the symbol * representes the AND operator, the symbol + represents the OR operator, ! = NOT, ^ = XOR
+
+    public bool Interpret(string sentence, bool[] vars) {
+      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));
+    }
+
+    public double Interpret(string sentence, double[] vars) {
+      InitLex(sentence);
+      return Expr(vars);
+    }
+
+
+    private void InitLex(string sentence) {
+      this.sentence = sentence;
+      this.syIdx = 0;
+    }
+
+    private char CurSy() {
+      if (syIdx >= sentence.Length) return '\0';
+      return sentence[syIdx];
+    }
+    private void NewSy() {
+      if (syIdx < sentence.Length) syIdx++;
+    }
+
+    // helper for xor
+    private double Not(double x) {
+      return x.IsAlmost(0) ? 1.0 : 0.0;
+    }
+
+    private double Expr(double[] d) {
+      var r = 0.0;
+      r = Term(d);
+      var curSy = CurSy();
+      while (curSy == '+' || curSy == '-' || curSy == '^') {
+        if (curSy == '+') {
+          NewSy();
+          r += Expr(d);
+        } else if (curSy == '-') {
+          NewSy();
+          r -= Expr(d);
+        } else {
+          NewSy();
+          var e = Expr(d);
+          r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
+        }
+        curSy = CurSy();
+      }
+      return r;
+    }
+
+    private double Term(double[] d) {
+      var r = 0.0;
+      r = Fact(d);
+      var curSy = CurSy();
+      while (curSy == '*' || curSy == '/') {
+        if (curSy == '*') {
+          NewSy();
+          r *= Term(d);
+        } else {
+          NewSy();
+          r /= Term(d);
+        }
+        curSy = CurSy();
+      }
+      return r;
+    }
+
+    private double Fact(double[] d) {
+      double r = 0.0;
+      var curSy = CurSy();
+      if (curSy == '!') {
+        NewSy();
+        r = Not(Expr(d));
+      } else if (curSy == '(') {
+        NewSy();
+        r = Expr(d);
+        if (CurSy() != ')') throw new ArgumentException();
+        NewSy();
+      } 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 throw new ArgumentException();
+      return r;
+    }
+
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs	(revision 11803)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs	(revision 11803)
@@ -0,0 +1,149 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Data.Odbc;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Text.RegularExpressions;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  // must find a set of phrases where the ordering of phrases is irrelevant
+  // Parameters
+  // - size of the alphabet
+  // - phrase length
+  // - number of phrases in the sequence
+  // - number of optimal phrases
+  // - reward for optimal phrases
+  // - number of decoy (sub-optimal) phrases
+  // - reward for decoy phrases (must be smaller than reward for optimal phrases)
+  // - phrasesAsSets: a switch to determine wether symbols in a phrase can be shuffled (sets) or if the ordering is relevant (non-sets)
+
+  // this problem should be similar to symbolic regression and should be easier for approaches using a state esimation value and the canoncial state 
+  // when phrases are symbol sets instead of sequences then value-estimation routines should be better (TD)
+  public class FindPhrasesProblem : IProblem {
+
+    private readonly IGrammar grammar;
+    private readonly int numPhrases;
+    private readonly int phraseLen;
+    private readonly double correctReward;
+    private readonly double decoyReward;
+    private readonly bool phrasesAsSets;
+    private readonly SortedSet<string> optimalPhrases;
+    private readonly SortedSet<string> decoyPhrases;
+
+    public FindPhrasesProblem(Random rand, int alphabetSize, int numPhrases, int phraseLen, int numOptimalPhrases, int numDecoyPhrases = 1,
+      double correctReward = 1.0, double decoyReward = 0.0, bool phrasesAsSets = false) {
+      if (alphabetSize <= 0 || alphabetSize > 26) throw new ArgumentException();
+      if (numPhrases <= 0) throw new ArgumentException();
+      if (phraseLen < 1) throw new ArgumentException();
+      if (numOptimalPhrases < numPhrases) throw new ArgumentException();
+      if (numDecoyPhrases < 0) throw new ArgumentException();
+      if (correctReward <= decoyReward) throw new ArgumentException();
+
+      this.numPhrases = numPhrases;
+      this.phraseLen = phraseLen;
+      this.correctReward = correctReward;
+      this.decoyReward = decoyReward;
+      this.phrasesAsSets = phrasesAsSets;
+
+      // create grammar
+      var sentenceSymbol = 'S';
+      var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray();
+      var nonTerminalSymbols = new char[] { 'S' };
+      var rules = terminalSymbols.Select(t => Tuple.Create('S', t.ToString()))
+        .Concat(terminalSymbols.Select(t => Tuple.Create('S', t + "S")));
+
+      this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
+
+      // generate optimal phrases
+      optimalPhrases = new SortedSet<string>();
+      while (optimalPhrases.Count < numOptimalPhrases) {
+        string phrase = "";
+        for (int l = 0; l < phraseLen; l++) {
+          phrase += terminalSymbols.SelectRandom(rand);
+        }
+        phrase = CanonicalPhrase(phrase);
+
+        // don't allow dups
+        if (!optimalPhrases.Contains(phrase)) optimalPhrases.Add(phrase);
+      }
+
+      // generate decoy phrases
+      decoyPhrases = new SortedSet<string>();
+      while (decoyPhrases.Count < numDecoyPhrases) {
+        string phrase = "";
+        for (int l = 0; l < phraseLen; l++) {
+          phrase += terminalSymbols.SelectRandom(rand);
+        }
+        phrase = CanonicalPhrase(phrase);
+
+        // don't allow dups
+        if (!optimalPhrases.Contains(phrase) && !decoyPhrases.Contains(phrase)) decoyPhrases.Add(phrase);
+      }
+
+      Debug.Assert(Evaluate(BestKnownSolution) / BestKnownQuality(phraseLen * numPhrases) == 1.0);
+    }
+
+    public double BestKnownQuality(int maxLen) {
+      return Math.Min(maxLen / phraseLen, numPhrases) * correctReward; // integer division
+    }
+
+    public string BestKnownSolution {
+      get { return string.Join("", optimalPhrases.Take(numPhrases)); }
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
+      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
+
+
+      // split the sentence in phrases
+      // phrases must not overlap in the sentence, multiple occurences of a phrase are not counted
+      // the order of phrases is not relevant
+      var numPhrases = sentence.Length / phraseLen;
+      var phrases = new SortedSet<string>();
+      for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
+        var sentenceIdx = phraseIdx * phraseLen;
+        var phrase = sentence.Substring(sentenceIdx, phraseLen);
+        phrase = CanonicalPhrase(phrase);
+        if (!phrases.Contains(phrase)) phrases.Add(phrase);
+      }
+
+      // add reward for each correct phrase that occurs in the sentence 
+      // add reward for each decoy phrase that occurs in the sentence
+      var reward = phrases.Intersect(optimalPhrases).Count() * correctReward
+               + phrases.Intersect(decoyPhrases).Count() * decoyReward;
+
+      return reward;
+    }
+
+    // TODO: cache canonical phrases in most-recently used dictionary for increased performance (see symbolicregressionpoly10problem)
+    private string CanonicalPhrase(string phrase) {
+      if (phrasesAsSets) return string.Join("", phrase.OrderBy(ch => (byte)ch));
+      else return phrase;
+    }
+
+    public string CanonicalRepresentation(string terminalPhrase) {
+      // as the ordering of phrases does not matter we can reorder the phrases
+      // and remove duplicates
+      var numPhrases = terminalPhrase.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 remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
+      remainder = CanonicalPhrase(remainder);
+      if (!phrases.Contains(remainder)) phrases.Add(remainder);
+
+      return string.Join("", phrases);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs	(revision 11803)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs	(revision 11803)
@@ -0,0 +1,45 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class HardPalindromeProblem : IProblem {
+    // length of the longest palindrome in the sentence + number of different symbols occurring in the palindrome
+    private const string grammarString = @"
+G(S):
+S -> T | TS
+T -> a .. z
+";
+
+    private readonly IGrammar grammar;
+    public HardPalindromeProblem() {
+      this.grammar = new Grammar(grammarString);
+    }
+
+    public double BestKnownQuality(int maxLen) {
+      // the whole sentence is a palindrome + each symbol occurs only once or twice
+      // for odd total length the number of different characters can be larger than len/2 (aba)
+      // the second part is limited to 26 different characters
+      return maxLen + Math.Min(26, (maxLen + 1) / 2);
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      var palindrome = PalindromeProblem.LongestPalindromicSubstring(sentence);
+      var palindromeBytes = ASCIIEncoding.ASCII.GetBytes(palindrome);
+      var chrCount = new int[256];
+      foreach (var b in palindromeBytes) {
+        chrCount[b]++;
+      }
+      return palindrome.Length + chrCount.Count(c => c > 0);
+    }
+
+    public string CanonicalRepresentation(string terminalPhrase) {
+      return terminalPhrase;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs	(revision 11803)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs	(revision 11803)
@@ -0,0 +1,86 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class PalindromeProblem : IProblem {
+    // length of the longest palindrome in the sentence
+    private const string grammarString = @"
+G(S):
+S -> T | TS
+T -> a .. z
+";
+
+    private readonly IGrammar grammar;
+    public PalindromeProblem() {
+      this.grammar = new Grammar(grammarString);
+    }
+
+    public double BestKnownQuality(int maxLen) {
+      // the whole sentence is a palindrome
+      return maxLen;
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      return LongestPalindromicSubstring(sentence).Length;
+    }
+
+
+    private static string Preprocess(string s) {
+      var t = new char[2 * s.Length + 3];
+      t[0] = '$';
+      t[t.Length - 2] = '#';
+      t[t.Length - 1] = '@';
+      for (int i = 0; i < s.Length; i++) {
+        t[2 * (i) + 1] = '#';
+        t[2 * i + 2] = s[i];
+      }
+
+      return new string(t);
+    }
+
+    public static string LongestPalindromicSubstring(string str) {
+      var tLen = 2 * str.Length + 3;
+      var p = new int[tLen];
+      var t = Preprocess(str);
+
+      var center = 0;
+      var right = 0;
+      for (int i = 1; i < t.Length - 1; i++) {
+        var mirror = 2 * center - i;
+        if (right > i) p[i] = Math.Min(right - i, p[mirror]);
+        while (t[i + (1 + p[i])] == t[i - (1 + p[i])]) {
+          p[i]++;
+        }
+        if (i + p[i] > right) {
+          center = i;
+          right = i + p[i];
+        }
+      }
+      var len = 0;
+      center = 0;
+      for (int i = 0; i < t.Length - 1; i++) {
+        if (p[i] > len) {
+          center = i;
+          len = p[i];
+        }
+      }
+
+      var start = (center - 1 - len) / 2;
+      var result = new StringBuilder();
+      for (int i = 0; i < len; i++) {
+        result.Append(str[start + i]);
+      }
+      return result.ToString();
+    }
+
+    public string CanonicalRepresentation(string terminalPhrase) {
+      return terminalPhrase;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs	(revision 11803)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs	(revision 11803)
@@ -0,0 +1,42 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Text.RegularExpressions;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  // counts the number of times a pair of symbols occurs in a sentence
+  public class RoyalPairProblem : IProblem {
+    private const string grammarString = @"
+G(S):
+S -> a | aS | b | bS
+";
+
+    private readonly IGrammar grammar;
+    public RoyalPairProblem() {
+      this.grammar = new Grammar(grammarString);
+      // TODO: allow configuration of the number of symbols
+    }
+
+    public double BestKnownQuality(int maxLen) {
+      return maxLen - 1;
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    private Regex regex = new Regex("(?=ab)|(?=ba)"); // count the number of "ab" and "ba" pairs
+    public double Evaluate(string sentence) {
+      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
+      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
+      return regex.Matches(sentence).Count;
+    }
+
+    public string CanonicalRepresentation(string terminalPhrase) {
+      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 11803)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs	(revision 11803)
@@ -0,0 +1,135 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Text.RegularExpressions;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  // must find one of numCorrectPhrases*sequenceLen sequences where the quality of a sequence is the length of the subsequence containing only correct _phrases_ (of length phraseLen) and starting at the first position
+  // compared to the RoyalSequence problem this problem is harder because the number of different phrases starting at a position is much larger than the number of symbols (grows exponentially with the phrase-length)
+  // if phraseLen = 1 this is the same as the RoyalSequence problem
+  // parameters
+  // - alphabetSize: number of different symbols (max=26)
+  // - phraseLen: the length of a phrase in number of symbols
+  // - sequenceLen: the number of phrases in the correct subsequence (total sequence length is n * phraseLen
+  // - numCorrectPhrases: the number of correct phrases starting at each position
+  // - phrasesAsSets: switch to determine if the ordering of symbols within a phrase is relevant
+  // 
+  // this problem should be hard for GP and easy for MCTS (TD should not have an advantage compared to MCTS)
+  // for phraseLen > 1 this should be harder than RoyalSymbolProblem
+  // when phrases are symbol sets instead of sequences then value-estimation routines should be better (TD)
+  public class RoyalPhraseSequenceProblem : IProblem {
+
+    private readonly IGrammar grammar;
+    private readonly double correctReward;
+    private readonly double incorrectReward;
+    private readonly int sequenceLen;
+    private readonly int phraseLen;
+    private readonly bool phrasesAsSets;
+    private readonly SortedSet<string>[] optimalPhrasesForPos;
+
+    public RoyalPhraseSequenceProblem(Random rand, int alphabetSize, int sequenceLen, int phraseLen = 1, int numCorrectPhrases = 1, double correctReward = 1.0, double incorrectReward = 0.0, bool phrasesAsSets = false) {
+      if (alphabetSize <= 0 || alphabetSize > 26) throw new ArgumentException();
+      if (sequenceLen <= 0) throw new ArgumentException();
+      if (numCorrectPhrases < 1 || numCorrectPhrases > alphabetSize) throw new ArgumentException();
+      if (phraseLen < 1) throw new ArgumentException();
+      if (correctReward <= incorrectReward) throw new ArgumentException();
+
+      this.sequenceLen = sequenceLen;
+      this.phraseLen = phraseLen;
+      this.correctReward = correctReward;
+      this.incorrectReward = incorrectReward;
+      this.phrasesAsSets = phrasesAsSets;
+      var sentenceSymbol = 'S';
+      var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray();
+      var nonTerminalSymbols = new char[] { 'S' };
+      var rules = terminalSymbols.Select(t => Tuple.Create('S', t.ToString()))
+        .Concat(terminalSymbols.Select(t => Tuple.Create('S', t + "S")));
+
+      this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
+
+      this.optimalPhrasesForPos = new SortedSet<string>[sequenceLen];
+      for (int i = 0; i < sequenceLen; i++) {
+        optimalPhrasesForPos[i] = new SortedSet<string>();
+        for (int j = 0; j < numCorrectPhrases; j++) {
+          string phrase = "";
+          do {
+            for (int l = 0; l < phraseLen; l++) {
+              phrase += terminalSymbols.SelectRandom(rand);
+            }
+            phrase = CanonicalPhrase(phrase);
+          } while (optimalPhrasesForPos[i].Contains(phrase)); // don't allow duplicate phrases
+          optimalPhrasesForPos[i].Add(phrase);
+        }
+      }
+
+      Debug.Assert(Evaluate(BestKnownSolution) / BestKnownQuality(phraseLen * sequenceLen) == 1.0);
+    }
+
+    public double BestKnownQuality(int maxLen) {
+      return Math.Min(maxLen / phraseLen, sequenceLen) * correctReward; // integer division
+    }
+
+    public string BestKnownSolution {
+      get {
+        string solution = "";
+        for (int i = 0; i < sequenceLen; i++) {
+          solution += optimalPhrasesForPos[i].First();
+        }
+        return solution;
+      }
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
+      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
+      // as long as only correct symbols are found we increase the reward by +1
+      // on the first incorrect symbol we return
+      var reward = 0.0;
+      for (int i = 0; i < Math.Min(sentence.Length / phraseLen, sequenceLen); i++) {
+        var canonicalPhrase = CanonicalPhrase(sentence.Substring(i * phraseLen, phraseLen));
+        if (optimalPhrasesForPos[i].Contains(canonicalPhrase)) {
+          reward += correctReward;
+        } else {
+          // alternatively reduce reward by number of remaining phrases
+          return Math.Max(0.0, reward + incorrectReward * (sentence.Length / phraseLen - i));
+          // stop on first incorrect symbol and return reward
+          //return reward;
+        }
+      }
+      return reward;
+    }
+
+    // TODO: cache canonical phrases in most-recently used dictionary for increased performance (see symbolicregressionpoly10problem)
+    private string CanonicalPhrase(string phrase) {
+      if (phrasesAsSets) return string.Join("", phrase.OrderBy(ch => (byte)ch));
+      else return phrase;
+    }
+
+    public string CanonicalRepresentation(string terminalPhrase) {
+      if (phrasesAsSets) {
+        var phrases = new List<string>();
+        var numPhrases = terminalPhrase.Length / phraseLen;
+        for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
+          var sentenceIdx = phraseIdx * phraseLen;
+          var phrase = terminalPhrase.Substring(sentenceIdx, phraseLen);
+          phrase = CanonicalPhrase(phrase);
+          phrases.Add(phrase);
+        }
+
+        var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
+        remainder = CanonicalPhrase(remainder);
+        phrases.Add(remainder);
+
+        return string.Join("", phrases);
+      } else
+        return terminalPhrase;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalRoadProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalRoadProblem.cs	(revision 11803)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalRoadProblem.cs	(revision 11803)
@@ -0,0 +1,36 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class RoyalRoadProblem : IProblem {
+    // inspired by Mitchell, Forrest, Holland: "The Royal Road for Genetic Algorithms: Fitness Landscapes and GA Performance", 1992
+    private const string grammarString = @"
+G(S):
+S -> 1 | 0 | 1S | 0S
+";
+
+    private readonly IGrammar grammar;
+    public RoyalRoadProblem() {
+      this.grammar = new Grammar(grammarString);
+    }
+
+    public double BestKnownQuality(int maxLen) {
+      // for now only an upper bound is returned, ideally all fitness cases are predicted correctly
+      throw new NotImplementedException();
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      throw new NotImplementedException();
+    }
+    public string CanonicalRepresentation(string terminalPhrase) {
+      return terminalPhrase;
+    }
+
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs	(revision 11803)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs	(revision 11803)
@@ -0,0 +1,91 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Text.RegularExpressions;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  // must find one of k*sequenceLen sequences where the quality of a sequence is the length of the subsequence containing only correct symbols and starting at the first symbol
+  // parameters
+  // - alphabetSize: number of different symbols (max=26)
+  // - sequenceLen: length of the correct subsequence
+  // - k: the number of correct symbols at each position
+  // 
+  // this problem should be hard for GP and easy for MCTS (TD should not have an advantage compared to MCTS)
+  public class RoyalSequenceProblem : IProblem {
+
+    private readonly IGrammar grammar;
+    private readonly double correctReward;
+    private readonly double incorrectReward;
+    private readonly int sequenceLen;
+    private readonly SortedSet<char>[] optimalSymbolsForPos;
+
+    public RoyalSequenceProblem(Random rand, int alphabetSize, int sequenceLen, int k = 1, double correctReward = 1.0, double incorrectReward = 0.0) {
+      if (alphabetSize <= 0 || alphabetSize > 26) throw new ArgumentException();
+      if (sequenceLen <= 0) throw new ArgumentException();
+      if (k < 1 || k > alphabetSize) throw new ArgumentException();
+      if (correctReward <= incorrectReward) throw new ArgumentException();
+      this.sequenceLen = sequenceLen;
+      this.correctReward = correctReward;
+      this.incorrectReward = incorrectReward;
+      const char sentenceSymbol = 'S';
+      var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray();
+      var nonTerminalSymbols = new char[] { sentenceSymbol };
+      var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
+        .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString())));
+      //var rules = terminalSymbols.Select(t => Tuple.Create('S', t + "S"))
+      //  .Concat(terminalSymbols.Select(t => Tuple.Create('S', t.ToString())));
+      this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
+
+      this.optimalSymbolsForPos = new SortedSet<char>[sequenceLen];
+      for (int i = 0; i < sequenceLen; i++) {
+        optimalSymbolsForPos[i] = new SortedSet<char>();
+        for (int j = 0; j < k; j++) {
+          char ch;
+          do {
+            ch = terminalSymbols.SelectRandom(rand);
+          } while (optimalSymbolsForPos[i].Contains(ch));
+          optimalSymbolsForPos[i].Add(ch);
+        }
+      }
+    }
+
+    public double BestKnownQuality(int maxLen) {
+      return Math.Min(maxLen, sequenceLen) * correctReward;
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
+      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
+      var reward = 0.0;
+      for (int i = 0; i < Math.Min(sentence.Length, sequenceLen); i++) {
+        if (optimalSymbolsForPos[i].Contains(sentence[i])) {
+          reward += correctReward;
+        } else {
+          //  reduce reward by number of remaining symbols
+          return Math.Max(0.0, reward + incorrectReward * (sentence.Length - i));
+        }
+      }
+      return reward;
+    }
+
+    // in each position there could be multiple correct and incorrect symbols
+    public string CanonicalRepresentation(string terminalPhrase) {
+      var sb = new StringBuilder();
+      for (int i = 0; i < terminalPhrase.Length; i++) {
+        if (optimalSymbolsForPos[i].Contains(terminalPhrase[i])) {
+          sb.Append(optimalSymbolsForPos[i].First()); // all symbols in the set are equivalent
+        } else {
+          sb.Append(terminalPhrase[i]);
+        }
+      }
+      return sb.ToString();
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs	(revision 11803)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs	(revision 11803)
@@ -0,0 +1,42 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text.RegularExpressions;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  // counts the number of times a symbol occurs in a sentence
+  public class RoyalSymbolProblem : IProblem {
+    private const string grammarString = @"
+G(S):
+S -> a | aS | b | bS
+";
+    // Obj(s \in L(G(S))) = Anzahl "a"-Symbole in s
+
+    private readonly IGrammar grammar;
+    public RoyalSymbolProblem() {
+      this.grammar = new Grammar(grammarString);
+      //TODO: allow configuration of the number of symbols
+    }
+
+    public double BestKnownQuality(int maxLen) {
+      return maxLen;
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    private Regex regex = new Regex("a"); // count the number of "a"s
+    public double Evaluate(string sentence) {
+      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
+      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
+      return regex.Matches(sentence.ToString()).Count;
+    }
+    public string CanonicalRepresentation(string terminalPhrase) {
+      throw new NotImplementedException();
+      return terminalPhrase;
+    }
+
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs	(revision 11803)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs	(revision 11803)
@@ -0,0 +1,37 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class RoyalTreeProblem : IProblem {
+    // Punch: "How Effective Are Multiple Populations in Genetic Programming", 1998
+    private const string grammarString = @"
+G(S):
+S -> 0 
+";
+
+    private readonly IGrammar grammar;
+    public RoyalTreeProblem() {
+      this.grammar = new Grammar(grammarString);
+    }
+
+    public double BestKnownQuality(int maxLen) {
+      // for now only an upper bound is returned, ideally all fitness cases are predicted correctly
+      throw new NotImplementedException();
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      throw new NotImplementedException();
+    }
+    public string CanonicalRepresentation(string terminalPhrase) {
+      throw new NotImplementedException();
+      return terminalPhrase;
+    }
+
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs	(revision 11803)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs	(revision 11803)
@@ -0,0 +1,226 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Runtime.InteropServices;
+using System.Runtime.Remoting.Messaging;
+using System.Text;
+using System.Text.RegularExpressions;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class SantaFeAntProblem : IProblem {
+    private const string grammarString = @"
+G(A):
+A -> l | r | m | ?(A)(A) | lA | rA | mA 
+";
+
+
+    // original koza grammar
+    // Ant -> left | right | move | if-food-ahead Ant Ant | Ant Ant | Ant Ant Ant
+    // 
+    // here we use a modified grammar which has only one syntax tree for each sentence
+
+
+    private readonly IGrammar grammar;
+
+    public SantaFeAntProblem() {
+      this.grammar = new Grammar(grammarString);
+    }
+
+    public double BestKnownQuality(int maxLen) {
+      // for now only an upper bound is returned, ideally all food pellets are discovered
+      return 89;
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      var ant = new Ant();
+      int p = 0;
+      Run(ant, sentence, ref p);
+      return ant.FoodEaten;
+    }
+
+    private void Run(Ant ant, string sentence, ref int p) {
+      while (!ant.Done()) {
+        if (p >= sentence.Length) p = 0; // restart
+        switch (sentence[p]) {
+          case 'r': {
+              ant.TurnRight();
+              p++;
+              break;
+            }
+          case 'l': {
+              ant.TurnLeft();
+              p++;
+              break;
+            }
+          case 'm': {
+              ant.Move();
+              p++;
+              break;
+            }
+          case '?': {
+              p++; // skip p
+              if (ant.IsFoodAhead()) {
+                if (sentence[p] != '(') throw new ArgumentException();
+                p++;
+                Run(ant, sentence, ref p);      // it cannot happen that we run over the the end of the sentence here
+                if (ant.Done()) return;
+                if (sentence[p] != '(') throw new ArgumentException();
+                p++;
+                Skip(sentence, ref p);
+              } else {
+                if (sentence[p] != '(') throw new ArgumentException();
+                p++;
+                Skip(sentence, ref p);
+                if (sentence[p] != '(') throw new ArgumentException();
+                p++;
+                Run(ant, sentence, ref p);    // it cannot happen that we run over the the end of the sentence here
+              }
+              break;
+            }
+          case ')': {
+              p++; // skip
+              return;     // caller must continue processing
+            }
+          default: {
+              throw new ArgumentException();
+            }
+        }
+      }
+    }
+
+    private void Skip(string sentence, ref int p) {
+      int openCount = 1;
+      while (openCount > 0) {
+        if (sentence[p] == '(') openCount++;
+        else if (sentence[p] == ')') openCount--;
+        p++;
+      }
+    }
+
+    public string CanonicalRepresentation(string terminalPhrase) {
+      var sb = new StringBuilder(terminalPhrase);
+      string canonicalPhrase = terminalPhrase;
+      string oldPhrase;
+      do {
+        oldPhrase = canonicalPhrase;
+        sb.Replace("ll", "rr").Replace("rl", "lr").Replace("lr", "").Replace("lll", "r").Replace("rrr", "l");
+        canonicalPhrase = sb.ToString();
+      } while (canonicalPhrase != oldPhrase);
+      sb.Append(terminalPhrase.Length - canonicalPhrase.Length);
+      return sb.ToString();
+    }
+  }
+
+  public class Ant {
+    private const int maxSteps = 600;
+    public enum HeadingEnum { North, East, South, West };
+    public int FoodEaten { get; private set; }
+    private readonly char[][] world = new char[32][];
+    private int posX;
+    private int posY;
+    private int steps;
+    private HeadingEnum heading;
+
+
+
+    public Ant() {
+      world[00] = " ###                            ".ToCharArray();
+      world[01] = "   #                            ".ToCharArray();
+      world[02] = "   #                    .###..  ".ToCharArray();
+      world[03] = "   #                    #    #  ".ToCharArray();
+      world[04] = "   #                    #    #  ".ToCharArray();
+      world[05] = "   ####.#####       .##..    .  ".ToCharArray();
+      world[06] = "            #       .        #  ".ToCharArray();
+      world[07] = "            #       #        .  ".ToCharArray();
+      world[08] = "            #       #        .  ".ToCharArray();
+      world[09] = "            #       #        #  ".ToCharArray();
+      world[10] = "            .       #        .  ".ToCharArray();
+      world[11] = "            #       .        .  ".ToCharArray();
+      world[12] = "            #       .        #  ".ToCharArray();
+      world[13] = "            #       #        .  ".ToCharArray();
+      world[14] = "            #       #  ...###.  ".ToCharArray();
+      world[15] = "            .   .#...  #        ".ToCharArray();
+      world[16] = "            .   .      .        ".ToCharArray();
+      world[17] = "            #   .      .        ".ToCharArray();
+      world[18] = "            #   #      .#...    ".ToCharArray();
+      world[19] = "            #   #          #    ".ToCharArray();
+      world[20] = "            #   #          .    ".ToCharArray();
+      world[21] = "            #   #          .    ".ToCharArray();
+      world[22] = "            #   .      ...#.    ".ToCharArray();
+      world[23] = "            #   .      #        ".ToCharArray();
+      world[24] = " ..##..#####.   #               ".ToCharArray();
+      world[25] = " #              #               ".ToCharArray();
+      world[26] = " #              #               ".ToCharArray();
+      world[27] = " #     .#######..               ".ToCharArray();
+      world[28] = " #     #                        ".ToCharArray();
+      world[29] = " .     #                        ".ToCharArray();
+      world[30] = " .####..                        ".ToCharArray();
+      world[31] = "                                ".ToCharArray();
+
+      posX = 0;
+      posY = 0;
+      heading = HeadingEnum.East;
+      FoodEaten = 0;
+      steps = 0;
+    }
+
+    public bool Done() {
+      return steps > maxSteps;
+    }
+
+    public void TurnRight() {
+      if (steps <= maxSteps) {
+        steps++;
+        if (heading == HeadingEnum.West) heading = HeadingEnum.North;
+        else heading++;
+      }
+    }
+
+    public void TurnLeft() {
+      if (steps <= maxSteps) {
+        steps++;
+        if (heading == HeadingEnum.North) heading = HeadingEnum.West;
+        else heading--;
+      }
+    }
+
+    public void Move() {
+      if (steps <= maxSteps) {
+        steps++;
+        MoveInternal(ref posX, ref posY);
+        if (world[posY][posX] == '#') {
+          FoodEaten++;
+          world[posY][posX] = '.';
+        }
+      }
+    }
+
+    private void MoveInternal(ref int posX, ref int posY) {
+      switch (heading) {
+        case HeadingEnum.North:
+          posY = (posY + 31) % 32;
+          break;
+        case HeadingEnum.East:
+          posX = (posX + 1) % 32;
+          break;
+        case HeadingEnum.South:
+          posY = (posY + 1) % 32;
+          break;
+        case HeadingEnum.West:
+          posX = (posX + 31) % 32;
+          break;
+      }
+    }
+
+    public bool IsFoodAhead() {
+      int nextPosX = posX;
+      int nextPosY = posY;
+      MoveInternal(ref nextPosX, ref nextPosY);
+      return world[nextPosY][nextPosX] == '#';
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs	(revision 11803)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs	(revision 11803)
@@ -0,0 +1,120 @@
+﻿using System;
+using System.Collections.Concurrent;
+using System.Collections.Generic;
+using System.Collections.Specialized;
+using System.Linq;
+using System.Net;
+using System.Security;
+using System.Security.AccessControl;
+using System.Text;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class SymbolicRegressionPoly10Problem : IProblem {
+    //    private const string grammarString = @"
+    //    G(E):
+    //    E -> V | V+E | V-E | V*E | (E)
+    //    V -> a .. j 
+    //    ";
+    private const string grammarString = @"
+    G(E):
+    E -> a | b | c | d | e | f | g | h | i | j | a+E | b+E | c+E | d+E | e+E | f+E | g+E | h+E | i+E | j+E | a*E | b*E | c*E | d*E | e*E | f*E | g*E | h*E | i*E | j*E 
+    ";
+
+
+    private readonly IGrammar grammar;
+
+    private readonly int N;
+    private readonly double[][] x;
+    private readonly double[] y;
+
+    public SymbolicRegressionPoly10Problem() {
+      this.grammar = new Grammar(grammarString);
+
+      this.N = 500;
+      this.x = new double[N][];
+      this.y = new double[N];
+
+      GenerateData();
+    }
+
+    private void GenerateData() {
+      // generate data with fixed seed to make sure that data is always the same
+      var rand = new Random(31415);
+      for (int i = 0; i < N; i++) {
+        x[i] = new double[10];
+        for (int j = 0; j < 10; j++) {
+          x[i][j] = rand.NextDouble() * 2 - 1;
+        }
+        // poly-10 no noise
+        /* a*b + c*d + e*f + a*g*i + c*f*j */
+        y[i] = x[i][0] * x[i][1] +
+               x[i][2] * x[i][3] +
+               x[i][4] * x[i][5] +
+               x[i][0] * x[i][6] * x[i][8] +
+               x[i][2] * x[i][5] * x[i][9];
+      }
+    }
+
+    public double BestKnownQuality(int maxLen) {
+      // for now only an upper bound is returned, ideally we have an R² of 1.0
+      // the optimal R² can only be reached for sentences of at least 23 symbols
+      return 1.0;
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      var interpreter = new ExpressionInterpreter();
+      return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])).ToArray());
+    }
+
+
+
+    // most-recently-used caching (with limited capacity) for canonical representations
+    MostRecentlyUsedCache<string, string> canonicalPhraseCache = new MostRecentlyUsedCache<string, string>(100000);
+    // right now only + and * is supported
+    public string CanonicalRepresentation(string phrase) {
+      string canonicalPhrase;
+      if (!canonicalPhraseCache.TryGetValue(phrase, out canonicalPhrase)) {
+        var terms = phrase.Split('+');
+        var canonicalTerms = new SortedSet<string>();
+        // only the last term might contain a NT-symbol. make sure this term is added at the end
+        for (int i = 0; i < terms.Length - 1; i++) {
+          canonicalTerms.Add(CanonicalTerm(terms[i]));
+        }
+
+        var sb = new StringBuilder(phrase.Length);
+        foreach (var t in canonicalTerms)
+          sb.Append(t).Append('+');
+
+        sb.Append(CanonicalTerm(terms[terms.Length - 1]));
+        sb.Append(phrase.Length - sb.Length);
+        canonicalPhrase = sb.ToString();
+        canonicalPhraseCache.Add(phrase, canonicalPhrase);
+      }
+      return canonicalPhrase;
+    }
+
+    // cache the canonical form of terms for performance reasons
+    private Dictionary<string, string> canonicalTermDictionary = new Dictionary<string, string>();
+    private string CanonicalTerm(string term) {
+      string canonicalTerm;
+      if (!canonicalTermDictionary.TryGetValue(term, out canonicalTerm)) {
+        // add
+        var chars = term.ToCharArray();
+        Array.Sort(chars);
+        var sb = new StringBuilder(chars.Length);
+        // we want to have the up-case characters last
+        for (int i = chars.Length - 1; i >= 0; i--) {
+          if (chars[i] != '*') sb.Append(chars[i]);
+        }
+        canonicalTerm = sb.ToString();
+        canonicalTermDictionary.Add(term, canonicalTerm);
+      }
+      return canonicalTerm;
+    }
+  }
+}
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPairProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPairProblem.cs	(revision 11802)
+++ 	(revision )
@@ -1,42 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Diagnostics;
-using System.Linq;
-using System.Text;
-using System.Text.RegularExpressions;
-
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  // counts the number of times a pair of symbols occurs in a sentence
-  public class RoyalPairProblem : IProblem {
-    private const string grammarString = @"
-G(S):
-S -> a | aS | b | bS
-";
-
-    private readonly IGrammar grammar;
-    public RoyalPairProblem() {
-      this.grammar = new Grammar(grammarString);
-      // TODO: allow configuration of the number of symbols
-    }
-
-    public double BestKnownQuality(int maxLen) {
-      return maxLen - 1;
-    }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    private Regex regex = new Regex("(?=ab)|(?=ba)"); // count the number of "ab" and "ba" pairs
-    public double Evaluate(string sentence) {
-      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
-      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
-      return regex.Matches(sentence).Count;
-    }
-
-    public string CanonicalRepresentation(string terminalPhrase) {
-      throw new NotImplementedException();
-      return terminalPhrase;
-    }
-  }
-}
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPhraseSequenceProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPhraseSequenceProblem.cs	(revision 11802)
+++ 	(revision )
@@ -1,135 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Diagnostics;
-using System.Linq;
-using System.Text;
-using System.Text.RegularExpressions;
-using HeuristicLab.Common;
-
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  // must find one of numCorrectPhrases*sequenceLen sequences where the quality of a sequence is the length of the subsequence containing only correct _phrases_ (of length phraseLen) and starting at the first position
-  // compared to the RoyalSequence problem this problem is harder because the number of different phrases starting at a position is much larger than the number of symbols (grows exponentially with the phrase-length)
-  // if phraseLen = 1 this is the same as the RoyalSequence problem
-  // parameters
-  // - alphabetSize: number of different symbols (max=26)
-  // - phraseLen: the length of a phrase in number of symbols
-  // - sequenceLen: the number of phrases in the correct subsequence (total sequence length is n * phraseLen
-  // - numCorrectPhrases: the number of correct phrases starting at each position
-  // - phrasesAsSets: switch to determine if the ordering of symbols within a phrase is relevant
-  // 
-  // this problem should be hard for GP and easy for MCTS (TD should not have an advantage compared to MCTS)
-  // for phraseLen > 1 this should be harder than RoyalSymbolProblem
-  // when phrases are symbol sets instead of sequences then value-estimation routines should be better (TD)
-  public class RoyalPhraseSequenceProblem : IProblem {
-
-    private readonly IGrammar grammar;
-    private readonly double correctReward;
-    private readonly double incorrectReward;
-    private readonly int sequenceLen;
-    private readonly int phraseLen;
-    private readonly bool phrasesAsSets;
-    private readonly SortedSet<string>[] optimalPhrasesForPos;
-
-    public RoyalPhraseSequenceProblem(Random rand, int alphabetSize, int sequenceLen, int phraseLen = 1, int numCorrectPhrases = 1, double correctReward = 1.0, double incorrectReward = 0.0, bool phrasesAsSets = false) {
-      if (alphabetSize <= 0 || alphabetSize > 26) throw new ArgumentException();
-      if (sequenceLen <= 0) throw new ArgumentException();
-      if (numCorrectPhrases < 1 || numCorrectPhrases > alphabetSize) throw new ArgumentException();
-      if (phraseLen < 1) throw new ArgumentException();
-      if (correctReward <= incorrectReward) throw new ArgumentException();
-
-      this.sequenceLen = sequenceLen;
-      this.phraseLen = phraseLen;
-      this.correctReward = correctReward;
-      this.incorrectReward = incorrectReward;
-      this.phrasesAsSets = phrasesAsSets;
-      var sentenceSymbol = 'S';
-      var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray();
-      var nonTerminalSymbols = new char[] { 'S' };
-      var rules = terminalSymbols.Select(t => Tuple.Create('S', t.ToString()))
-        .Concat(terminalSymbols.Select(t => Tuple.Create('S', t + "S")));
-
-      this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
-
-      this.optimalPhrasesForPos = new SortedSet<string>[sequenceLen];
-      for (int i = 0; i < sequenceLen; i++) {
-        optimalPhrasesForPos[i] = new SortedSet<string>();
-        for (int j = 0; j < numCorrectPhrases; j++) {
-          string phrase = "";
-          do {
-            for (int l = 0; l < phraseLen; l++) {
-              phrase += terminalSymbols.SelectRandom(rand);
-            }
-            phrase = CanonicalPhrase(phrase);
-          } while (optimalPhrasesForPos[i].Contains(phrase)); // don't allow duplicate phrases
-          optimalPhrasesForPos[i].Add(phrase);
-        }
-      }
-
-      Debug.Assert(Evaluate(BestKnownSolution) / BestKnownQuality(phraseLen * sequenceLen) == 1.0);
-    }
-
-    public double BestKnownQuality(int maxLen) {
-      return Math.Min(maxLen / phraseLen, sequenceLen) * correctReward; // integer division
-    }
-
-    public string BestKnownSolution {
-      get {
-        string solution = "";
-        for (int i = 0; i < sequenceLen; i++) {
-          solution += optimalPhrasesForPos[i].First();
-        }
-        return solution;
-      }
-    }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    public double Evaluate(string sentence) {
-      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
-      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
-      // as long as only correct symbols are found we increase the reward by +1
-      // on the first incorrect symbol we return
-      var reward = 0.0;
-      for (int i = 0; i < Math.Min(sentence.Length / phraseLen, sequenceLen); i++) {
-        var canonicalPhrase = CanonicalPhrase(sentence.Substring(i * phraseLen, phraseLen));
-        if (optimalPhrasesForPos[i].Contains(canonicalPhrase)) {
-          reward += correctReward;
-        } else {
-          // alternatively reduce reward by number of remaining phrases
-          return Math.Max(0.0, reward + incorrectReward * (sentence.Length / phraseLen - i));
-          // stop on first incorrect symbol and return reward
-          //return reward;
-        }
-      }
-      return reward;
-    }
-
-    // TODO: cache canonical phrases in most-recently used dictionary for increased performance (see symbolicregressionpoly10problem)
-    private string CanonicalPhrase(string phrase) {
-      if (phrasesAsSets) return string.Join("", phrase.OrderBy(ch => (byte)ch));
-      else return phrase;
-    }
-
-    public string CanonicalRepresentation(string terminalPhrase) {
-      if (phrasesAsSets) {
-        var phrases = new List<string>();
-        var numPhrases = terminalPhrase.Length / phraseLen;
-        for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
-          var sentenceIdx = phraseIdx * phraseLen;
-          var phrase = terminalPhrase.Substring(sentenceIdx, phraseLen);
-          phrase = CanonicalPhrase(phrase);
-          phrases.Add(phrase);
-        }
-
-        var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
-        remainder = CanonicalPhrase(remainder);
-        phrases.Add(remainder);
-
-        return string.Join("", phrases);
-      } else
-        return terminalPhrase;
-    }
-  }
-}
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalRoadProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalRoadProblem.cs	(revision 11802)
+++ 	(revision )
@@ -1,36 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  public class RoyalRoadProblem : IProblem {
-    // inspired by Mitchell, Forrest, Holland: "The Royal Road for Genetic Algorithms: Fitness Landscapes and GA Performance", 1992
-    private const string grammarString = @"
-G(S):
-S -> 1 | 0 | 1S | 0S
-";
-
-    private readonly IGrammar grammar;
-    public RoyalRoadProblem() {
-      this.grammar = new Grammar(grammarString);
-    }
-
-    public double BestKnownQuality(int maxLen) {
-      // for now only an upper bound is returned, ideally all fitness cases are predicted correctly
-      throw new NotImplementedException();
-    }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    public double Evaluate(string sentence) {
-      throw new NotImplementedException();
-    }
-    public string CanonicalRepresentation(string terminalPhrase) {
-      return terminalPhrase;
-    }
-
-  }
-}
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSequenceProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSequenceProblem.cs	(revision 11802)
+++ 	(revision )
@@ -1,91 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Diagnostics;
-using System.Linq;
-using System.Text;
-using System.Text.RegularExpressions;
-using HeuristicLab.Common;
-
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  // must find one of k*sequenceLen sequences where the quality of a sequence is the length of the subsequence containing only correct symbols and starting at the first symbol
-  // parameters
-  // - alphabetSize: number of different symbols (max=26)
-  // - sequenceLen: length of the correct subsequence
-  // - k: the number of correct symbols at each position
-  // 
-  // this problem should be hard for GP and easy for MCTS (TD should not have an advantage compared to MCTS)
-  public class RoyalSequenceProblem : IProblem {
-
-    private readonly IGrammar grammar;
-    private readonly double correctReward;
-    private readonly double incorrectReward;
-    private readonly int sequenceLen;
-    private readonly SortedSet<char>[] optimalSymbolsForPos;
-
-    public RoyalSequenceProblem(Random rand, int alphabetSize, int sequenceLen, int k = 1, double correctReward = 1.0, double incorrectReward = 0.0) {
-      if (alphabetSize <= 0 || alphabetSize > 26) throw new ArgumentException();
-      if (sequenceLen <= 0) throw new ArgumentException();
-      if (k < 1 || k > alphabetSize) throw new ArgumentException();
-      if (correctReward <= incorrectReward) throw new ArgumentException();
-      this.sequenceLen = sequenceLen;
-      this.correctReward = correctReward;
-      this.incorrectReward = incorrectReward;
-      const char sentenceSymbol = 'S';
-      var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray();
-      var nonTerminalSymbols = new char[] { sentenceSymbol };
-      var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
-        .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString())));
-      //var rules = terminalSymbols.Select(t => Tuple.Create('S', t + "S"))
-      //  .Concat(terminalSymbols.Select(t => Tuple.Create('S', t.ToString())));
-      this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
-
-      this.optimalSymbolsForPos = new SortedSet<char>[sequenceLen];
-      for (int i = 0; i < sequenceLen; i++) {
-        optimalSymbolsForPos[i] = new SortedSet<char>();
-        for (int j = 0; j < k; j++) {
-          char ch;
-          do {
-            ch = terminalSymbols.SelectRandom(rand);
-          } while (optimalSymbolsForPos[i].Contains(ch));
-          optimalSymbolsForPos[i].Add(ch);
-        }
-      }
-    }
-
-    public double BestKnownQuality(int maxLen) {
-      return Math.Min(maxLen, sequenceLen) * correctReward;
-    }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    public double Evaluate(string sentence) {
-      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
-      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
-      var reward = 0.0;
-      for (int i = 0; i < Math.Min(sentence.Length, sequenceLen); i++) {
-        if (optimalSymbolsForPos[i].Contains(sentence[i])) {
-          reward += correctReward;
-        } else {
-          //  reduce reward by number of remaining symbols
-          return Math.Max(0.0, reward + incorrectReward * (sentence.Length - i));
-        }
-      }
-      return reward;
-    }
-
-    // in each position there could be multiple correct and incorrect symbols
-    public string CanonicalRepresentation(string terminalPhrase) {
-      var sb = new StringBuilder();
-      for (int i = 0; i < terminalPhrase.Length; i++) {
-        if (optimalSymbolsForPos[i].Contains(terminalPhrase[i])) {
-          sb.Append(optimalSymbolsForPos[i].First()); // all symbols in the set are equivalent
-        } else {
-          sb.Append(terminalPhrase[i]);
-        }
-      }
-      return sb.ToString();
-    }
-  }
-}
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSymbolProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSymbolProblem.cs	(revision 11802)
+++ 	(revision )
@@ -1,42 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Diagnostics;
-using System.Linq;
-using System.Text.RegularExpressions;
-
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  // counts the number of times a symbol occurs in a sentence
-  public class RoyalSymbolProblem : IProblem {
-    private const string grammarString = @"
-G(S):
-S -> a | aS | b | bS
-";
-    // Obj(s \in L(G(S))) = Anzahl "a"-Symbole in s
-
-    private readonly IGrammar grammar;
-    public RoyalSymbolProblem() {
-      this.grammar = new Grammar(grammarString);
-      //TODO: allow configuration of the number of symbols
-    }
-
-    public double BestKnownQuality(int maxLen) {
-      return maxLen;
-    }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    private Regex regex = new Regex("a"); // count the number of "a"s
-    public double Evaluate(string sentence) {
-      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
-      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
-      return regex.Matches(sentence.ToString()).Count;
-    }
-    public string CanonicalRepresentation(string terminalPhrase) {
-      throw new NotImplementedException();
-      return terminalPhrase;
-    }
-
-  }
-}
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalTreeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalTreeProblem.cs	(revision 11802)
+++ 	(revision )
@@ -1,37 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  public class RoyalTreeProblem : IProblem {
-    // Punch: "How Effective Are Multiple Populations in Genetic Programming", 1998
-    private const string grammarString = @"
-G(S):
-S -> 0 
-";
-
-    private readonly IGrammar grammar;
-    public RoyalTreeProblem() {
-      this.grammar = new Grammar(grammarString);
-    }
-
-    public double BestKnownQuality(int maxLen) {
-      // for now only an upper bound is returned, ideally all fitness cases are predicted correctly
-      throw new NotImplementedException();
-    }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    public double Evaluate(string sentence) {
-      throw new NotImplementedException();
-    }
-    public string CanonicalRepresentation(string terminalPhrase) {
-      throw new NotImplementedException();
-      return terminalPhrase;
-    }
-
-  }
-}
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs	(revision 11802)
+++ 	(revision )
@@ -1,226 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Runtime.InteropServices;
-using System.Runtime.Remoting.Messaging;
-using System.Text;
-using System.Text.RegularExpressions;
-
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  public class SantaFeAntProblem : IProblem {
-    private const string grammarString = @"
-G(A):
-A -> l | r | m | ?(A)(A) | lA | rA | mA 
-";
-
-
-    // original koza grammar
-    // Ant -> left | right | move | if-food-ahead Ant Ant | Ant Ant | Ant Ant Ant
-    // 
-    // here we use a modified grammar which has only one syntax tree for each sentence
-
-
-    private readonly IGrammar grammar;
-
-    public SantaFeAntProblem() {
-      this.grammar = new Grammar(grammarString);
-    }
-
-    public double BestKnownQuality(int maxLen) {
-      // for now only an upper bound is returned, ideally all food pellets are discovered
-      return 89;
-    }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    public double Evaluate(string sentence) {
-      var ant = new Ant();
-      int p = 0;
-      Run(ant, sentence, ref p);
-      return ant.FoodEaten;
-    }
-
-    private void Run(Ant ant, string sentence, ref int p) {
-      while (!ant.Done()) {
-        if (p >= sentence.Length) p = 0; // restart
-        switch (sentence[p]) {
-          case 'r': {
-              ant.TurnRight();
-              p++;
-              break;
-            }
-          case 'l': {
-              ant.TurnLeft();
-              p++;
-              break;
-            }
-          case 'm': {
-              ant.Move();
-              p++;
-              break;
-            }
-          case '?': {
-              p++; // skip p
-              if (ant.IsFoodAhead()) {
-                if (sentence[p] != '(') throw new ArgumentException();
-                p++;
-                Run(ant, sentence, ref p);      // it cannot happen that we run over the the end of the sentence here
-                if (ant.Done()) return;
-                if (sentence[p] != '(') throw new ArgumentException();
-                p++;
-                Skip(sentence, ref p);
-              } else {
-                if (sentence[p] != '(') throw new ArgumentException();
-                p++;
-                Skip(sentence, ref p);
-                if (sentence[p] != '(') throw new ArgumentException();
-                p++;
-                Run(ant, sentence, ref p);    // it cannot happen that we run over the the end of the sentence here
-              }
-              break;
-            }
-          case ')': {
-              p++; // skip
-              return;     // caller must continue processing
-            }
-          default: {
-              throw new ArgumentException();
-            }
-        }
-      }
-    }
-
-    private void Skip(string sentence, ref int p) {
-      int openCount = 1;
-      while (openCount > 0) {
-        if (sentence[p] == '(') openCount++;
-        else if (sentence[p] == ')') openCount--;
-        p++;
-      }
-    }
-
-    public string CanonicalRepresentation(string terminalPhrase) {
-      var sb = new StringBuilder(terminalPhrase);
-      string canonicalPhrase = terminalPhrase;
-      string oldPhrase;
-      do {
-        oldPhrase = canonicalPhrase;
-        sb.Replace("ll", "rr").Replace("rl", "lr").Replace("lr", "").Replace("lll", "r").Replace("rrr", "l");
-        canonicalPhrase = sb.ToString();
-      } while (canonicalPhrase != oldPhrase);
-      sb.Append(terminalPhrase.Length - canonicalPhrase.Length);
-      return sb.ToString();
-    }
-  }
-
-  public class Ant {
-    private const int maxSteps = 600;
-    public enum HeadingEnum { North, East, South, West };
-    public int FoodEaten { get; private set; }
-    private readonly char[][] world = new char[32][];
-    private int posX;
-    private int posY;
-    private int steps;
-    private HeadingEnum heading;
-
-
-
-    public Ant() {
-      world[00] = " ###                            ".ToCharArray();
-      world[01] = "   #                            ".ToCharArray();
-      world[02] = "   #                    .###..  ".ToCharArray();
-      world[03] = "   #                    #    #  ".ToCharArray();
-      world[04] = "   #                    #    #  ".ToCharArray();
-      world[05] = "   ####.#####       .##..    .  ".ToCharArray();
-      world[06] = "            #       .        #  ".ToCharArray();
-      world[07] = "            #       #        .  ".ToCharArray();
-      world[08] = "            #       #        .  ".ToCharArray();
-      world[09] = "            #       #        #  ".ToCharArray();
-      world[10] = "            .       #        .  ".ToCharArray();
-      world[11] = "            #       .        .  ".ToCharArray();
-      world[12] = "            #       .        #  ".ToCharArray();
-      world[13] = "            #       #        .  ".ToCharArray();
-      world[14] = "            #       #  ...###.  ".ToCharArray();
-      world[15] = "            .   .#...  #        ".ToCharArray();
-      world[16] = "            .   .      .        ".ToCharArray();
-      world[17] = "            #   .      .        ".ToCharArray();
-      world[18] = "            #   #      .#...    ".ToCharArray();
-      world[19] = "            #   #          #    ".ToCharArray();
-      world[20] = "            #   #          .    ".ToCharArray();
-      world[21] = "            #   #          .    ".ToCharArray();
-      world[22] = "            #   .      ...#.    ".ToCharArray();
-      world[23] = "            #   .      #        ".ToCharArray();
-      world[24] = " ..##..#####.   #               ".ToCharArray();
-      world[25] = " #              #               ".ToCharArray();
-      world[26] = " #              #               ".ToCharArray();
-      world[27] = " #     .#######..               ".ToCharArray();
-      world[28] = " #     #                        ".ToCharArray();
-      world[29] = " .     #                        ".ToCharArray();
-      world[30] = " .####..                        ".ToCharArray();
-      world[31] = "                                ".ToCharArray();
-
-      posX = 0;
-      posY = 0;
-      heading = HeadingEnum.East;
-      FoodEaten = 0;
-      steps = 0;
-    }
-
-    public bool Done() {
-      return steps > maxSteps;
-    }
-
-    public void TurnRight() {
-      if (steps <= maxSteps) {
-        steps++;
-        if (heading == HeadingEnum.West) heading = HeadingEnum.North;
-        else heading++;
-      }
-    }
-
-    public void TurnLeft() {
-      if (steps <= maxSteps) {
-        steps++;
-        if (heading == HeadingEnum.North) heading = HeadingEnum.West;
-        else heading--;
-      }
-    }
-
-    public void Move() {
-      if (steps <= maxSteps) {
-        steps++;
-        MoveInternal(ref posX, ref posY);
-        if (world[posY][posX] == '#') {
-          FoodEaten++;
-          world[posY][posX] = '.';
-        }
-      }
-    }
-
-    private void MoveInternal(ref int posX, ref int posY) {
-      switch (heading) {
-        case HeadingEnum.North:
-          posY = (posY + 31) % 32;
-          break;
-        case HeadingEnum.East:
-          posX = (posX + 1) % 32;
-          break;
-        case HeadingEnum.South:
-          posY = (posY + 1) % 32;
-          break;
-        case HeadingEnum.West:
-          posX = (posX + 31) % 32;
-          break;
-      }
-    }
-
-    public bool IsFoodAhead() {
-      int nextPosX = posX;
-      int nextPosY = posY;
-      MoveInternal(ref nextPosX, ref nextPosY);
-      return world[nextPosY][nextPosX] == '#';
-    }
-  }
-}
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs	(revision 11802)
+++ 	(revision )
@@ -1,120 +1,0 @@
-﻿using System;
-using System.Collections.Concurrent;
-using System.Collections.Generic;
-using System.Collections.Specialized;
-using System.Linq;
-using System.Net;
-using System.Security;
-using System.Security.AccessControl;
-using System.Text;
-using HeuristicLab.Common;
-
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  public class SymbolicRegressionPoly10Problem : IProblem {
-    //    private const string grammarString = @"
-    //    G(E):
-    //    E -> V | V+E | V-E | V*E | (E)
-    //    V -> a .. j 
-    //    ";
-    private const string grammarString = @"
-    G(E):
-    E -> a | b | c | d | e | f | g | h | i | j | a+E | b+E | c+E | d+E | e+E | f+E | g+E | h+E | i+E | j+E | a*E | b*E | c*E | d*E | e*E | f*E | g*E | h*E | i*E | j*E 
-    ";
-
-
-    private readonly IGrammar grammar;
-
-    private readonly int N;
-    private readonly double[][] x;
-    private readonly double[] y;
-
-    public SymbolicRegressionPoly10Problem() {
-      this.grammar = new Grammar(grammarString);
-
-      this.N = 500;
-      this.x = new double[N][];
-      this.y = new double[N];
-
-      GenerateData();
-    }
-
-    private void GenerateData() {
-      // generate data with fixed seed to make sure that data is always the same
-      var rand = new Random(31415);
-      for (int i = 0; i < N; i++) {
-        x[i] = new double[10];
-        for (int j = 0; j < 10; j++) {
-          x[i][j] = rand.NextDouble() * 2 - 1;
-        }
-        // poly-10 no noise
-        /* a*b + c*d + e*f + a*g*i + c*f*j */
-        y[i] = x[i][0] * x[i][1] +
-               x[i][2] * x[i][3] +
-               x[i][4] * x[i][5] +
-               x[i][0] * x[i][6] * x[i][8] +
-               x[i][2] * x[i][5] * x[i][9];
-      }
-    }
-
-    public double BestKnownQuality(int maxLen) {
-      // for now only an upper bound is returned, ideally we have an R² of 1.0
-      // the optimal R² can only be reached for sentences of at least 23 symbols
-      return 1.0;
-    }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    public double Evaluate(string sentence) {
-      var interpreter = new ExpressionInterpreter();
-      return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])).ToArray());
-    }
-
-
-
-    // most-recently-used caching (with limited capacity) for canonical representations
-    MostRecentlyUsedCache<string, string> canonicalPhraseCache = new MostRecentlyUsedCache<string, string>(100000);
-    // right now only + and * is supported
-    public string CanonicalRepresentation(string phrase) {
-      string canonicalPhrase;
-      if (!canonicalPhraseCache.TryGetValue(phrase, out canonicalPhrase)) {
-        var terms = phrase.Split('+');
-        var canonicalTerms = new SortedSet<string>();
-        // only the last term might contain a NT-symbol. make sure this term is added at the end
-        for (int i = 0; i < terms.Length - 1; i++) {
-          canonicalTerms.Add(CanonicalTerm(terms[i]));
-        }
-
-        var sb = new StringBuilder(phrase.Length);
-        foreach (var t in canonicalTerms)
-          sb.Append(t).Append('+');
-
-        sb.Append(CanonicalTerm(terms[terms.Length - 1]));
-        sb.Append(phrase.Length - sb.Length);
-        canonicalPhrase = sb.ToString();
-        canonicalPhraseCache.Add(phrase, canonicalPhrase);
-      }
-      return canonicalPhrase;
-    }
-
-    // cache the canonical form of terms for performance reasons
-    private Dictionary<string, string> canonicalTermDictionary = new Dictionary<string, string>();
-    private string CanonicalTerm(string term) {
-      string canonicalTerm;
-      if (!canonicalTermDictionary.TryGetValue(term, out canonicalTerm)) {
-        // add
-        var chars = term.ToCharArray();
-        Array.Sort(chars);
-        var sb = new StringBuilder(chars.Length);
-        // we want to have the up-case characters last
-        for (int i = chars.Length - 1; i >= 0; i--) {
-          if (chars[i] != '*') sb.Append(chars[i]);
-        }
-        canonicalTerm = sb.ToString();
-        canonicalTermDictionary.Add(term, canonicalTerm);
-      }
-      return canonicalTerm;
-    }
-  }
-}
