Changeset 11865 for branches

Timestamp:

02/02/15 20:41:11 (10 years ago)

Author:

gkronber

Message:

#2283: implemented royal tree problem and grid test for tree-based gp variants

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization

Files:

• GrammaticalOptimization.sln (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj (modified) (2 diffs)
• HeuristicLab.Problems.GrammaticalOptimization/Interfaces/ISymbolicExpressionTreeProblem.cs (copied) (copied from branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/TreeRepresentation/ISymbolicExpressionTreeProblem.cs)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs (modified) (5 diffs)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs (modified) (4 diffs)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs (modified) (4 diffs)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs (modified) (3 diffs)
• HeuristicLab.Problems.GrammaticalOptimization/SentenceSetStatistics.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/TreeRepresentation (deleted)
• Main/Program.cs (modified) (4 diffs)
• Test/TestInstances.cs (modified) (2 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln

@@ -72 +72 @@
     HideSolutionNode = FALSE
   EndGlobalSection
-  GlobalSection(Performance) = preSolution
-    HasPerformanceSessions = true
-  EndGlobalSection
 EndGlobal

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

@@ -78 +78 @@
     <Compile Include="Interfaces\IGrammar.cs" />
     <Compile Include="Interfaces\IProblem.cs" />
+    <Compile Include="Interfaces\ISymbolicExpressionTreeProblem.cs" />
     <Compile Include="Problems\EvenParityProblem.cs" />
     <Compile Include="Problems\FindPhrasesProblem.cs" />
@@ -95 +96 @@
     <Compile Include="Sequence.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
-    <Compile Include="TreeRepresentation\ISymbolicExpressionTreeProblem.cs" />
   </ItemGroup>
   <ItemGroup>

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs

@@ -3 +3 @@
 using System.Diagnostics;
 using System.Linq;
+using System.Text;
 using HeuristicLab.Common;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 
 namespace HeuristicLab.Problems.GrammaticalOptimization {
@@ -19 +21 @@
   // 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 {
+  public class FindPhrasesProblem : ISymbolicExpressionTreeProblem {
 
     private readonly IGrammar grammar;
@@ -45 +47 @@
       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")));
+      var nonTerminalSymbols = new char[] { sentenceSymbol };
 
-      this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
+      {
+        // create grammar
+        // S -> a..z | aS .. zS
+        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
+          .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString())));
+
+        this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
+      }
+      {
+        // create grammar for tree-based GP
+        // S -> a..z | SS
+        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
+          .Concat(new Tuple<char, string>[] { Tuple.Create(sentenceSymbol, sentenceSymbol.ToString() + sentenceSymbol) });
+
+        this.TreeBasedGPGrammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
+      }
 
       // generate optimal phrases
@@ -144 +158 @@
     }
 
-    public IEnumerable<Feature> GetFeatures(string phrase)
-    {
+    public IEnumerable<Feature> GetFeatures(string phrase) {
       throw new NotImplementedException();
     }
@@ -153 +166 @@
         optimalPhrases.Count, correctReward, decoyPhrases.Count, decoyReward, phrasesAsSets);
     }
+
+    public IGrammar TreeBasedGPGrammar { get; private set; }
+    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
+      var sb = new StringBuilder();
+      foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) {
+        if (s.Symbol.Name == "S") continue;
+        sb.Append(s.Symbol.Name);
+      }
+      return sb.ToString();
+    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs

@@ -6 +6 @@
 using System.Text.RegularExpressions;
 using HeuristicLab.Common;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 
 namespace HeuristicLab.Problems.GrammaticalOptimization {
@@ -21 +22 @@
   // 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 {
+  public class RoyalPhraseSequenceProblem : ISymbolicExpressionTreeProblem {
 
     private readonly IGrammar grammar;
@@ -43 +44 @@
       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")));
+      var nonTerminalSymbols = new char[] { sentenceSymbol };
 
-      this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
+      {
+        // create grammar
+        // S -> a..z | aS .. zS
+        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
+          .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString())));
+
+        this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
+      }
+      {
+        // create grammar for tree-based GP
+        // S -> a..z | SS
+        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
+          .Concat(new Tuple<char, string>[] { Tuple.Create(sentenceSymbol, sentenceSymbol.ToString() + sentenceSymbol) });
+
+        this.TreeBasedGPGrammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
+      }
 
       this.optimalPhrasesForPos = new SortedSet<string>[sequenceLen];
@@ -133 +148 @@
     }
 
-    public IEnumerable<Feature> GetFeatures(string phrase)
-    {
+    public IEnumerable<Feature> GetFeatures(string phrase) {
       throw new NotImplementedException();
+    }
+
+    public IGrammar TreeBasedGPGrammar { get; private set; }
+    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
+      var sb = new StringBuilder();
+      foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) {
+        if (s.Symbol.Name == "S") continue;
+        sb.Append(s.Symbol.Name);
+      }
+      return sb.ToString();
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs

@@ -6 +6 @@
 using System.Text.RegularExpressions;
 using HeuristicLab.Common;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 
 namespace HeuristicLab.Problems.GrammaticalOptimization {
@@ -15 +16 @@
   // 
   // this problem should be hard for GP and easy for MCTS (TD should not have an advantage compared to MCTS)
-  public class RoyalSequenceProblem : IProblem {
+  public class RoyalSequenceProblem : ISymbolicExpressionTreeProblem {
 
     private readonly IGrammar grammar;
@@ -31 +32 @@
       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);
+
+      {
+        // create grammar for sequential search
+        // S -> a..z | aS .. zS
+        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
+          .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString())));
+        this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
+      }
+      {
+        // create grammar for sequential search
+        // S -> a..z | SS
+        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
+          .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString())));
+        this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
+      }
 
       this.optimalSymbolsForPos = new SortedSet<char>[sequenceLen];
@@ -89 +101 @@
     }
 
-    public IEnumerable<Feature> GetFeatures(string phrase)
-    {
+    public IEnumerable<Feature> GetFeatures(string phrase) {
       throw new NotImplementedException();
+    }
+
+    public IGrammar TreeBasedGPGrammar { get; private set; }
+    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
+      var sb = new StringBuilder();
+      foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) {
+        if (s.Symbol.Name == "S") continue;
+        sb.Append(s.Symbol.Name);
+      }
+      return sb.ToString();
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 
 namespace HeuristicLab.Problems.GrammaticalOptimization {
-  public class RoyalTreeProblem : IProblem {
+  public class RoyalTreeProblem : ISymbolicExpressionTreeProblem {
     // Punch: "How Effective Are Multiple Populations in Genetic Programming", 1998
-    private const string grammarString = @"
-G(S):
-S -> 0 
-";
+    // In fact, for a new GP system it is dicult to judge whether it is performing
+    // as intended or not, since the programs it generates are not necessarily identical to
+    // those generated by other GP systems. This raised two questions: what constitutes
+    // a "standard" problem in GP, and how do we rate the performance of a system on
+    // such a problem.
+    // One of the goals of this research was to create a benchmark problem to test how
+    // well a particular GP configuration would perform as compared to other configurations.
+    // ...
+    // We were interested in addressing the same issues, showing how GP could address
+    // difficult problems as well as providing a tunable benchmark for comparing GP con-
+    // figurations. Furthermore, we were interested in creating and using this benchmark
+    // to test the effectiveness of coarse-grain parallel GP's as compared to single population
+    // GP's.
+    // ...
+    // A suitable benchmark problem which has only a single, unique tree as an answer can remove this obstruction.
 
     private readonly IGrammar grammar;
-    public RoyalTreeProblem() {
-      this.grammar = new Grammar(grammarString);
-    }
+    private readonly char targetRootSymbol;
+    // the number of levels determines the number of non-terminal symbols
+    // non-terminal A has only one argument, non-terminal B has two arguments ...
+    // optimal level-e tree has quality 122880, 
+    // level-a (a) tree has 
+    // level-f (6) tree "is extremely difficult"
+    // level-g (7) tree "never succeeded"
+    public RoyalTreeProblem(int levels) {
+      if (levels < 1 || levels > 7) throw new ArgumentException();
+      var sentenceSymbol = 'S';
+      var terminalSymbols = new char[] { 'x', 'y', 'z' };
+      // originally non-terminal-symbols (but for the sequential search grammar these are only alternatives
+      var nonTerminalSymbols = Enumerable.Range(0, levels).Select(lvl => (char)(lvl + (byte)'A')).ToArray(); // [A, B ... ]
+      var arities = Enumerable.Range(1, levels).ToArray(); // [1, 2, ... levels]
+      this.targetRootSymbol = char.ToLower(nonTerminalSymbols.Last());
+      {
+        // grammar for sequential search
+        // S -> x | y | z | aS | bSS | cSSS ...
+
+        var rules = new List<Tuple<char, string>>();
+        foreach (var symb in terminalSymbols) {
+          rules.Add(Tuple.Create('S', symb.ToString()));
+        }
+        for (int ntIdx = 0; ntIdx < nonTerminalSymbols.Length; ntIdx++) {
+          var opSymb = char.ToLower(nonTerminalSymbols[ntIdx]);
+          var remChain = string.Join("", Enumerable.Repeat('S', arities[ntIdx]));
+          rules.Add(Tuple.Create('S', opSymb + remChain));
+        }
+
+        this.grammar = new Grammar(sentenceSymbol, terminalSymbols.Concat(nonTerminalSymbols.Select(char.ToLower)), new char[] { 'S' }, rules);
+      }
+
+      {
+        // grammar for tree-based GP
+        // S -> x | y | z | A | B | C ...
+        // A -> S
+        // B -> SS
+        // C -> SSS
+        var rules = new List<Tuple<char, string>>();
+        foreach (var symb in terminalSymbols.Concat(nonTerminalSymbols)) {
+          rules.Add(Tuple.Create('S', symb.ToString()));
+        }
+
+        for (int ntIdx = 0; ntIdx < nonTerminalSymbols.Length; ntIdx++) {
+          var ntSymb = nonTerminalSymbols[ntIdx];
+          var alt = string.Join("", Enumerable.Repeat('S', arities[ntIdx]));
+          rules.Add(Tuple.Create(ntSymb, alt));
+        }
+        this.TreeBasedGPGrammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols.Concat(new char[] { 'S' }), rules);
+      }
+
+      maxSizeForLevel = new int[8];
+      optimalSentencesForLevel = new string[8];
+      optimalQualityForLevel = new double[8];
+      maxSizeForLevel[0] = 1; // lvl-0 (x | y)
+      maxSizeForLevel[1] = 2; // lvl-1 (e.g. ax)
+      optimalSentencesForLevel[0] = "x";
+      optimalQualityForLevel[0] = 1;
+      //optimalSentencesForLevel[1] = "ax";
+      //optimalQualityForLevel[1] = 4;
+
+      for (int i = 1; i < maxSizeForLevel.Length; i++) {
+        maxSizeForLevel[i] = i * maxSizeForLevel[i - 1] + 1; // e.g. lvl-2: baxax
+
+        var opSymb = char.ToLower(nonTerminalSymbols[i - 1]);
+        optimalSentencesForLevel[i] = opSymb +
+                                       string.Join("",
+                                         Enumerable.Repeat(optimalSentencesForLevel[i - 1], arities[i - 1]));
+
+        optimalQualityForLevel[i] = Evaluate(optimalSentencesForLevel[i]);
+      }
+
+      // from the paper
+      Debug.Assert(maxSizeForLevel[5] == 326);
+      Debug.Assert(maxSizeForLevel[6] == 1957);
+    }
+
+    private readonly string[] optimalSentencesForLevel;
+    private readonly double[] optimalQualityForLevel;
+    private readonly int[] maxSizeForLevel;
 
     public double BestKnownQuality(int maxLen) {
-      // for now only an upper bound is returned, ideally all fitness cases are predicted correctly
-      throw new NotImplementedException();
+      // search for corresponding level
+      int level = 0;
+      while (maxSizeForLevel[level + 1] < maxLen) level++;
+      // ASSERT: maxSizeForLevel[level + 1] >= maxLen
+      return optimalQualityForLevel[level];
     }
 
@@ -27 +120 @@
 
     public double Evaluate(string sentence) {
-      throw new NotImplementedException();
-    }
+      int pos = 0;
+      bool perfect;
+      return Evaluate(sentence, ref pos, out perfect);
+    }
+
+    private double Evaluate(string sentence, ref int pos, out bool perfect) {
+      const double completeBonus = 2.0;
+      double t = 0.0;
+      double weight = 0.0;
+      double sum = 0.0;
+      bool correctRoot = false;
+      bool allPerfect = true, tPerfect;
+      int arity;
+      switch (sentence[pos]) {
+        case 'a':
+          pos++;
+          correctRoot = (sentence[pos] == 'x');
+          t = Evaluate(sentence, ref pos, out tPerfect); // ignores the perfect flag (false for terminals)
+          weight = GetWeight(correctRoot, true);
+          sum = weight * t;
+          perfect = correctRoot;
+          if (correctRoot) sum *= completeBonus;
+          return sum;
+        case 'b': {
+            arity = 2;
+            pos++;
+            for (int i = 0; i < arity; i++) {
+              correctRoot = (sentence[pos] == 'a');
+              t = Evaluate(sentence, ref pos, out tPerfect);
+              weight = GetWeight(correctRoot, tPerfect);
+              allPerfect &= correctRoot & tPerfect;
+              sum += weight * t;
+            }
+            perfect = allPerfect;
+            if (allPerfect) sum *= completeBonus;
+            return sum;
+          }
+        case 'c': {
+            arity = 3;
+            sum = 0.0;
+            pos++;
+            for (int i = 0; i < arity; i++) {
+              correctRoot = (sentence[pos] == 'b');
+              t = Evaluate(sentence, ref pos, out tPerfect);
+              weight = GetWeight(correctRoot, tPerfect);
+              allPerfect &= correctRoot & tPerfect;
+              sum += weight * t;
+            }
+            perfect = allPerfect;
+            if (allPerfect) sum *= completeBonus;
+            return sum;
+          }
+        case 'd': {
+            arity = 4;
+            sum = 0.0;
+            pos++;
+            for (int i = 0; i < arity; i++) {
+              correctRoot = (sentence[pos] == 'c');
+              t = Evaluate(sentence, ref pos, out tPerfect);
+              weight = GetWeight(correctRoot, tPerfect);
+              allPerfect &= correctRoot & tPerfect;
+              sum += weight * t;
+            }
+            perfect = allPerfect;
+            if (allPerfect) sum *= completeBonus;
+            return sum;
+          }
+        case 'e': {
+            arity = 5;
+            sum = 0.0;
+            pos++;
+            for (int i = 0; i < arity; i++) {
+              correctRoot = (sentence[pos] == 'd');
+              t = Evaluate(sentence, ref pos, out tPerfect);
+              weight = GetWeight(correctRoot, tPerfect);
+              allPerfect &= correctRoot & tPerfect;
+              sum += weight * t;
+            }
+            perfect = allPerfect;
+            if (allPerfect) sum *= completeBonus;
+            return sum;
+          }
+        case 'f': {
+            arity = 6;
+            sum = 0.0;
+            pos++;
+            for (int i = 0; i < arity; i++) {
+              correctRoot = (sentence[pos] == 'e');
+              t = Evaluate(sentence, ref pos, out tPerfect);
+              weight = GetWeight(correctRoot, tPerfect);
+              allPerfect &= correctRoot & tPerfect;
+              sum += weight * t;
+            }
+            perfect = allPerfect;
+            if (allPerfect) sum *= completeBonus;
+            return sum;
+          }
+        case 'g': {
+            arity = 7;
+            sum = 0.0;
+            pos++;
+            for (int i = 0; i < arity; i++) {
+              correctRoot = (sentence[pos] == 'f');
+              t = Evaluate(sentence, ref pos, out tPerfect);
+              weight = GetWeight(correctRoot, tPerfect);
+              allPerfect &= correctRoot & tPerfect;
+              sum += weight * t;
+            }
+            perfect = allPerfect;
+            if (allPerfect) sum *= completeBonus;
+            return sum;
+          }
+        case 'x':
+          pos++;
+          perfect = false;
+          return 1.0;
+        case 'y':
+        case 'z':
+          pos++;
+          perfect = false;
+          return 0.0;
+        default: throw new ArgumentException();
+      }
+    }
+
+    private double GetWeight(bool correctRoot, bool perfect) {
+      const double fullBonus = 2.0;
+      const double partialBonus = 1.0;
+      const double penalty = 0.33;
+      if (correctRoot && perfect) return fullBonus;
+      else if (correctRoot) return partialBonus;
+      else return penalty;
+    }
+
     public string CanonicalRepresentation(string phrase) {
       throw new NotImplementedException();
@@ -34 +259 @@
     }
 
-    public IEnumerable<Feature> GetFeatures(string phrase)
-    {
+    public IEnumerable<Feature> GetFeatures(string phrase) {
       throw new NotImplementedException();
+    }
+
+    public IGrammar TreeBasedGPGrammar { get; private set; }
+    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
+      var sb = new StringBuilder();
+      foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) {
+        if (s.Symbol.Name == "S") continue;
+        sb.Append(s.Symbol.Name.ToLower());
+      }
+      return sb.ToString();
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SentenceSetStatistics.cs

@@ -23 +23 @@
     public SentenceSetStatistics(double bestKnownQuality = 1.0) {
       this.bestKnownQuality = bestKnownQuality;
+      BestSentenceQuality = double.NegativeInfinity;
+      BestSentence = string.Empty;
+      FirstSentence = string.Empty;
+      LastSentence = string.Empty;
     }
 

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

@@ -25 +25 @@
 
       //RunDemo();
-      RunGpDemo();
+      //RunGpDemo();
       // RunGridTest();
+      RunGpGridTest();
     }
 
@@ -174 +175 @@
 
     private static void RunDemo() {
-      // TODO: implement bridge to HL-GP 
       // TODO: unify MCTS, TD and ContextMCTS Solvers (stateInfos)
       // TODO: test with eps-greedy using max instead of average as value (seems to work well for symb-reg! explore further!)
       // TODO: separate value function from policy
-      // TODO: in contextual MCTS store a bandit info for each node in the _graph_ and also update all bandit infos of all parents
-      // TODO: exhaustive search with priority list
       // TODO: warum funktioniert die alte Implementierung von GaussianThompson besser fÃŒr SantaFe als neue? Siehe Vergleich: alte vs. neue implementierung GaussianThompsonSampling
       // TODO: why does GaussianThompsonSampling work so well with MCTS for the artificial ant problem?
       // TODO: research thompson sampling for max bandit?
-      // TODO: ausfÃŒhrlicher test von strategien fÃŒr numCorrectPhrases-armed max bandit
       // TODO: verify TA implementation using example from the original paper      
-      // TODO: separate policy from MCTS tree data structure to allow sharing of information over disconnected parts of the tree (semantic equivalence)
       // TODO: implement thompson sampling for gaussian mixture models
-      // TODO: implement inspection for MCTS (eventuell interactive command line fÃŒr statistiken aus dem baum anzeigen)
-      // TODO: implement ACO-style bandit policy
       // TODO: gleichzeitige modellierung von transformierter zielvariable (y, 1/y, log(y), exp(y), sqrt(y), ...)
       // TODO: vergleich bei complete-randomly möglichst kurze sÀtze generieren vs. einfach zufÀllig alternativen wÀhlen
@@ -299 +293 @@
 
     public static void RunGpDemo() {
-
       int iterations = 0;
+      const int seed = 31415;
       const int maxIterations = 100000;
+
+    }
+
+
+    private static void RunGpGridTest() {
+      const int nReps = 20;
       const int seed = 31415;
-      var globalStatistics = new SentenceSetStatistics(512);
-
-      var gp = new StandardGP(new HardPalindromeProblem(), new Random(seed));
-      gp.FoundNewBestSolution += (sentence, quality) => {
-        Console.WriteLine("{0}", globalStatistics);
-      };
+      const int maxIters = 100000;
+      var rand = new Random(seed);
+      var problemFactories = new Func<ISymbolicExpressionTreeProblem>[]
+      {
+        () => new SantaFeAntProblem(), 
+        () => new SymbolicRegressionPoly10Problem(), 
+      };
+      foreach (var popSize in new int[] { 50, 100, 250, 500, 1000, 2500, 5000 }) {
+        foreach (var mutationRate in new double[] {/* 0.05, 0.10, */ 0.15, /* 0.25, 0.3 */ }) {
+          foreach (var maxSize in new int[] { 30, 50, 100 }) {
+            foreach (var problemFactory in problemFactories)
+              for (int i = 0; i < nReps; i++) {
+                var solverSeed = rand.Next();
+                {
+                  var prob = problemFactory();
+                  RunStandardGP(prob, solverSeed, maxIters, popSize, mutationRate, maxSize);
+                }
+                {
+                  var prob = problemFactory();
+                  RunOSGP(prob, solverSeed, maxIters, popSize, mutationRate, maxSize);
+                }
+              }
+          }
+        }
+      }
+    }
+
+    private static void RunStandardGP(ISymbolicExpressionTreeProblem prob, int solverSeed, int maxIters, int popSize, double mutationRate, int maxSize) {
+      int iterations = 0;
+      var globalStatistics = new SentenceSetStatistics(prob.BestKnownQuality(maxSize));
+
+      var gp = new StandardGP(prob, new Random(solverSeed));
       gp.SolutionEvaluated += (sentence, quality) => {
         iterations++;
@@ -314 +340 @@
 
         if (iterations % 10000 == 0) {
-          Console.WriteLine("{0}", globalStatistics);
-        }
-      };
-
-      gp.PopulationSize = 1000;
-      gp.MaxSolutionSize = 31 + 2;
-      gp.MaxSolutionDepth = 20;
+          Console.WriteLine("\"{0,25}\" \"{1,25}\" {2}", gp, prob, globalStatistics);
+        }
+      };
+
+      gp.PopulationSize = popSize;
+      gp.MutationRate = mutationRate;
+      gp.MaxSolutionSize = maxSize + 2;
+      gp.MaxSolutionDepth = maxSize + 2;
 
       var sw = new Stopwatch();
 
       sw.Start();
-      gp.Run(maxIterations);
+      gp.Run(maxIters);
       sw.Stop();
 
-      Console.WriteLine(globalStatistics);
-      Console.WriteLine("{0:F2} sec {1,10:F1} sols/sec {2,10:F1} ns/sol",
-        sw.Elapsed.TotalSeconds,
-        maxIterations / (double)sw.Elapsed.TotalSeconds,
-        (double)sw.ElapsedMilliseconds * 1000 / maxIterations);
+      Console.WriteLine("\"{0,25}\" \"{1,25}\" {2}", gp, prob, globalStatistics);
+
+      // Console.WriteLine("{0:F2} sec {1,10:F1} sols/sec {2,10:F1} ns/sol",
+      //   sw.Elapsed.TotalSeconds,
+      //   maxIters / (double)sw.Elapsed.TotalSeconds,
+      //   (double)sw.ElapsedMilliseconds * 1000 / maxIters);
+    }
+
+    private static void RunOSGP(ISymbolicExpressionTreeProblem prob, int solverSeed, int maxIters, int popSize, double mutationRate, int maxSize) {
+      int iterations = 0;
+      var globalStatistics = new SentenceSetStatistics(prob.BestKnownQuality(maxSize));
+
+      var gp = new OffspringSelectionGP(prob, new Random(solverSeed));
+      gp.SolutionEvaluated += (sentence, quality) => {
+        iterations++;
+        globalStatistics.AddSentence(sentence, quality);
+
+        if (iterations % 10000 == 0) {
+          Console.WriteLine("\"{0,25}\" \"{1,25}\" {2}", gp, prob, globalStatistics);
+        }
+      };
+
+      gp.PopulationSize = popSize;
+      gp.MutationRate = mutationRate;
+      gp.MaxSolutionSize = maxSize + 2;
+      gp.MaxSolutionDepth = maxSize + 2;
+
+      var sw = new Stopwatch();
+
+      sw.Start();
+      gp.Run(maxIters);
+      sw.Stop();
+
+      Console.WriteLine("\"{0,25}\" \"{1,25}\" {2}", gp, prob, globalStatistics);
+
+      // Console.WriteLine("{0:F2} sec {1,10:F1} sols/sec {2,10:F1} ns/sol",
+      //   sw.Elapsed.TotalSeconds,
+      //   maxIters / (double)sw.Elapsed.TotalSeconds,
+      //   (double)sw.ElapsedMilliseconds * 1000 / maxIters);
     }
   }

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

@@ -146 +146 @@
       Assert.AreEqual(89, p.Evaluate("?(m)(ll?(m)(r))mr"));
     }
-    [TestMethod]
-    public void TestRoyalTreeProblem() {
-      var p = new RoyalTreeProblem();
-      Console.WriteLine(p.Grammar);
-
-    }
+
     [TestMethod]
     public void TestRoyalRoadProblem() {
@@ -261 +256 @@
       Assert.AreEqual(1.0, p.Evaluate("a*b+c*d+e*f+a*g*i+c*f*j"), 1.0E-7);
     }
+
+    [TestMethod]
+    public void TestRoyalTreeProblem() {
+      var p = new RoyalTreeProblem(7);
+      Console.WriteLine(p.Grammar);
+
+      // examples from The Royal Tree Problem, a Benchmark for Single and Multi-population Genetic Programming (Punch, Zongker, Goodman)
+      Assert.AreEqual(4, p.Evaluate("ax"), 1.0E-7);
+      Assert.AreEqual(384.0, p.Evaluate("cbaxaxbaxaxbaxax"), 1.0E-7);
+      Assert.AreEqual(128.66, p.Evaluate("cbaxaxbaxaxbxx"), 1.0E-7);
+      Assert.AreEqual(64.66, p.Evaluate("cbaxaxxx"), 1.0E-7);
+
+    }
   }
 }