Changeset 11865 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization

Timestamp:

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

Author:

gkronber

Message:

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

Location:

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

Files:

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

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;
     }