Changeset 11865


Ignore:
Timestamp:
02/02/15 20:41:11 (8 years ago)
Author:
gkronber
Message:

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

Location:
branches/HeuristicLab.Problems.GrammaticalOptimization
Files:
1 deleted
9 edited
1 copied

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln

    r11851 r11865  
    7272    HideSolutionNode = FALSE
    7373  EndGlobalSection
    74   GlobalSection(Performance) = preSolution
    75     HasPerformanceSessions = true
    76   EndGlobalSection
    7774EndGlobal
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj

    r11857 r11865  
    7878    <Compile Include="Interfaces\IGrammar.cs" />
    7979    <Compile Include="Interfaces\IProblem.cs" />
     80    <Compile Include="Interfaces\ISymbolicExpressionTreeProblem.cs" />
    8081    <Compile Include="Problems\EvenParityProblem.cs" />
    8182    <Compile Include="Problems\FindPhrasesProblem.cs" />
     
    9596    <Compile Include="Sequence.cs" />
    9697    <Compile Include="Properties\AssemblyInfo.cs" />
    97     <Compile Include="TreeRepresentation\ISymbolicExpressionTreeProblem.cs" />
    9898  </ItemGroup>
    9999  <ItemGroup>
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs

    r11851 r11865  
    33using System.Diagnostics;
    44using System.Linq;
     5using System.Text;
    56using HeuristicLab.Common;
     7using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    68
    79namespace HeuristicLab.Problems.GrammaticalOptimization {
     
    1921  // this problem should be similar to symbolic regression and should be easier for approaches using a state esimation value and the canoncial state
    2022  // when phrases are symbol sets instead of sequences then value-estimation routines should be better (TD)
    21   public class FindPhrasesProblem : IProblem {
     23  public class FindPhrasesProblem : ISymbolicExpressionTreeProblem {
    2224
    2325    private readonly IGrammar grammar;
     
    4547      this.phrasesAsSets = phrasesAsSets;
    4648
    47       // create grammar
    4849      var sentenceSymbol = 'S';
    4950      var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray();
    50       var nonTerminalSymbols = new char[] { 'S' };
    51       var rules = terminalSymbols.Select(t => Tuple.Create('S', t.ToString()))
    52         .Concat(terminalSymbols.Select(t => Tuple.Create('S', t + "S")));
     51      var nonTerminalSymbols = new char[] { sentenceSymbol };
    5352
    54       this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
     53      {
     54        // create grammar
     55        // S -> a..z | aS .. zS
     56        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
     57          .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString())));
     58
     59        this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
     60      }
     61      {
     62        // create grammar for tree-based GP
     63        // S -> a..z | SS
     64        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
     65          .Concat(new Tuple<char, string>[] { Tuple.Create(sentenceSymbol, sentenceSymbol.ToString() + sentenceSymbol) });
     66
     67        this.TreeBasedGPGrammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
     68      }
    5569
    5670      // generate optimal phrases
     
    144158    }
    145159
    146     public IEnumerable<Feature> GetFeatures(string phrase)
    147     {
     160    public IEnumerable<Feature> GetFeatures(string phrase) {
    148161      throw new NotImplementedException();
    149162    }
     
    153166        optimalPhrases.Count, correctReward, decoyPhrases.Count, decoyReward, phrasesAsSets);
    154167    }
     168
     169    public IGrammar TreeBasedGPGrammar { get; private set; }
     170    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
     171      var sb = new StringBuilder();
     172      foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) {
     173        if (s.Symbol.Name == "S") continue;
     174        sb.Append(s.Symbol.Name);
     175      }
     176      return sb.ToString();
     177    }
    155178  }
    156179}
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs

    r11832 r11865  
    66using System.Text.RegularExpressions;
    77using HeuristicLab.Common;
     8using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    89
    910namespace HeuristicLab.Problems.GrammaticalOptimization {
     
    2122  // for phraseLen > 1 this should be harder than RoyalSymbolProblem
    2223  // when phrases are symbol sets instead of sequences then value-estimation routines should be better (TD)
    23   public class RoyalPhraseSequenceProblem : IProblem {
     24  public class RoyalPhraseSequenceProblem : ISymbolicExpressionTreeProblem {
    2425
    2526    private readonly IGrammar grammar;
     
    4344      this.incorrectReward = incorrectReward;
    4445      this.phrasesAsSets = phrasesAsSets;
     46
    4547      var sentenceSymbol = 'S';
    4648      var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray();
    47       var nonTerminalSymbols = new char[] { 'S' };
    48       var rules = terminalSymbols.Select(t => Tuple.Create('S', t.ToString()))
    49         .Concat(terminalSymbols.Select(t => Tuple.Create('S', t + "S")));
     49      var nonTerminalSymbols = new char[] { sentenceSymbol };
    5050
    51       this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
     51      {
     52        // create grammar
     53        // S -> a..z | aS .. zS
     54        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
     55          .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString())));
     56
     57        this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
     58      }
     59      {
     60        // create grammar for tree-based GP
     61        // S -> a..z | SS
     62        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
     63          .Concat(new Tuple<char, string>[] { Tuple.Create(sentenceSymbol, sentenceSymbol.ToString() + sentenceSymbol) });
     64
     65        this.TreeBasedGPGrammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
     66      }
    5267
    5368      this.optimalPhrasesForPos = new SortedSet<string>[sequenceLen];
     
    133148    }
    134149
    135     public IEnumerable<Feature> GetFeatures(string phrase)
    136     {
     150    public IEnumerable<Feature> GetFeatures(string phrase) {
    137151      throw new NotImplementedException();
     152    }
     153
     154    public IGrammar TreeBasedGPGrammar { get; private set; }
     155    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
     156      var sb = new StringBuilder();
     157      foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) {
     158        if (s.Symbol.Name == "S") continue;
     159        sb.Append(s.Symbol.Name);
     160      }
     161      return sb.ToString();
    138162    }
    139163  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs

    r11832 r11865  
    66using System.Text.RegularExpressions;
    77using HeuristicLab.Common;
     8using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    89
    910namespace HeuristicLab.Problems.GrammaticalOptimization {
     
    1516  //
    1617  // this problem should be hard for GP and easy for MCTS (TD should not have an advantage compared to MCTS)
    17   public class RoyalSequenceProblem : IProblem {
     18  public class RoyalSequenceProblem : ISymbolicExpressionTreeProblem {
    1819
    1920    private readonly IGrammar grammar;
     
    3132      this.correctReward = correctReward;
    3233      this.incorrectReward = incorrectReward;
     34
    3335      const char sentenceSymbol = 'S';
    3436      var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray();
    3537      var nonTerminalSymbols = new char[] { sentenceSymbol };
    36       var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
    37         .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString())));
    38       //var rules = terminalSymbols.Select(t => Tuple.Create('S', t + "S"))
    39       //  .Concat(terminalSymbols.Select(t => Tuple.Create('S', t.ToString())));
    40       this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
     38
     39      {
     40        // create grammar for sequential search
     41        // S -> a..z | aS .. zS
     42        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
     43          .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString())));
     44        this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
     45      }
     46      {
     47        // create grammar for sequential search
     48        // S -> a..z | SS
     49        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
     50          .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString())));
     51        this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
     52      }
    4153
    4254      this.optimalSymbolsForPos = new SortedSet<char>[sequenceLen];
     
    89101    }
    90102
    91     public IEnumerable<Feature> GetFeatures(string phrase)
    92     {
     103    public IEnumerable<Feature> GetFeatures(string phrase) {
    93104      throw new NotImplementedException();
     105    }
     106
     107    public IGrammar TreeBasedGPGrammar { get; private set; }
     108    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
     109      var sb = new StringBuilder();
     110      foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) {
     111        if (s.Symbol.Name == "S") continue;
     112        sb.Append(s.Symbol.Name);
     113      }
     114      return sb.ToString();
    94115    }
    95116  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs

    r11832 r11865  
    11using System;
    22using System.Collections.Generic;
     3using System.Diagnostics;
    34using System.Linq;
    45using System.Text;
     6using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    57
    68namespace HeuristicLab.Problems.GrammaticalOptimization {
    7   public class RoyalTreeProblem : IProblem {
     9  public class RoyalTreeProblem : ISymbolicExpressionTreeProblem {
    810    // Punch: "How Effective Are Multiple Populations in Genetic Programming", 1998
    9     private const string grammarString = @"
    10 G(S):
    11 S -> 0
    12 ";
     11    // In fact, for a new GP system it is dicult to judge whether it is performing
     12    // as intended or not, since the programs it generates are not necessarily identical to
     13    // those generated by other GP systems. This raised two questions: what constitutes
     14    // a "standard" problem in GP, and how do we rate the performance of a system on
     15    // such a problem.
     16    // One of the goals of this research was to create a benchmark problem to test how
     17    // well a particular GP configuration would perform as compared to other configurations.
     18    // ...
     19    // We were interested in addressing the same issues, showing how GP could address
     20    // difficult problems as well as providing a tunable benchmark for comparing GP con-
     21    // figurations. Furthermore, we were interested in creating and using this benchmark
     22    // to test the effectiveness of coarse-grain parallel GP's as compared to single population
     23    // GP's.
     24    // ...
     25    // A suitable benchmark problem which has only a single, unique tree as an answer can remove this obstruction.
    1326
    1427    private readonly IGrammar grammar;
    15     public RoyalTreeProblem() {
    16       this.grammar = new Grammar(grammarString);
    17     }
     28    private readonly char targetRootSymbol;
     29    // the number of levels determines the number of non-terminal symbols
     30    // non-terminal A has only one argument, non-terminal B has two arguments ...
     31    // optimal level-e tree has quality 122880,
     32    // level-a (a) tree has
     33    // level-f (6) tree "is extremely difficult"
     34    // level-g (7) tree "never succeeded"
     35    public RoyalTreeProblem(int levels) {
     36      if (levels < 1 || levels > 7) throw new ArgumentException();
     37      var sentenceSymbol = 'S';
     38      var terminalSymbols = new char[] { 'x', 'y', 'z' };
     39      // originally non-terminal-symbols (but for the sequential search grammar these are only alternatives
     40      var nonTerminalSymbols = Enumerable.Range(0, levels).Select(lvl => (char)(lvl + (byte)'A')).ToArray(); // [A, B ... ]
     41      var arities = Enumerable.Range(1, levels).ToArray(); // [1, 2, ... levels]
     42      this.targetRootSymbol = char.ToLower(nonTerminalSymbols.Last());
     43      {
     44        // grammar for sequential search
     45        // S -> x | y | z | aS | bSS | cSSS ...
     46
     47        var rules = new List<Tuple<char, string>>();
     48        foreach (var symb in terminalSymbols) {
     49          rules.Add(Tuple.Create('S', symb.ToString()));
     50        }
     51        for (int ntIdx = 0; ntIdx < nonTerminalSymbols.Length; ntIdx++) {
     52          var opSymb = char.ToLower(nonTerminalSymbols[ntIdx]);
     53          var remChain = string.Join("", Enumerable.Repeat('S', arities[ntIdx]));
     54          rules.Add(Tuple.Create('S', opSymb + remChain));
     55        }
     56
     57        this.grammar = new Grammar(sentenceSymbol, terminalSymbols.Concat(nonTerminalSymbols.Select(char.ToLower)), new char[] { 'S' }, rules);
     58      }
     59
     60      {
     61        // grammar for tree-based GP
     62        // S -> x | y | z | A | B | C ...
     63        // A -> S
     64        // B -> SS
     65        // C -> SSS
     66        var rules = new List<Tuple<char, string>>();
     67        foreach (var symb in terminalSymbols.Concat(nonTerminalSymbols)) {
     68          rules.Add(Tuple.Create('S', symb.ToString()));
     69        }
     70
     71        for (int ntIdx = 0; ntIdx < nonTerminalSymbols.Length; ntIdx++) {
     72          var ntSymb = nonTerminalSymbols[ntIdx];
     73          var alt = string.Join("", Enumerable.Repeat('S', arities[ntIdx]));
     74          rules.Add(Tuple.Create(ntSymb, alt));
     75        }
     76        this.TreeBasedGPGrammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols.Concat(new char[] { 'S' }), rules);
     77      }
     78
     79      maxSizeForLevel = new int[8];
     80      optimalSentencesForLevel = new string[8];
     81      optimalQualityForLevel = new double[8];
     82      maxSizeForLevel[0] = 1; // lvl-0 (x | y)
     83      maxSizeForLevel[1] = 2; // lvl-1 (e.g. ax)
     84      optimalSentencesForLevel[0] = "x";
     85      optimalQualityForLevel[0] = 1;
     86      //optimalSentencesForLevel[1] = "ax";
     87      //optimalQualityForLevel[1] = 4;
     88
     89      for (int i = 1; i < maxSizeForLevel.Length; i++) {
     90        maxSizeForLevel[i] = i * maxSizeForLevel[i - 1] + 1; // e.g. lvl-2: baxax
     91
     92        var opSymb = char.ToLower(nonTerminalSymbols[i - 1]);
     93        optimalSentencesForLevel[i] = opSymb +
     94                                       string.Join("",
     95                                         Enumerable.Repeat(optimalSentencesForLevel[i - 1], arities[i - 1]));
     96
     97        optimalQualityForLevel[i] = Evaluate(optimalSentencesForLevel[i]);
     98      }
     99
     100      // from the paper
     101      Debug.Assert(maxSizeForLevel[5] == 326);
     102      Debug.Assert(maxSizeForLevel[6] == 1957);
     103    }
     104
     105    private readonly string[] optimalSentencesForLevel;
     106    private readonly double[] optimalQualityForLevel;
     107    private readonly int[] maxSizeForLevel;
    18108
    19109    public double BestKnownQuality(int maxLen) {
    20       // for now only an upper bound is returned, ideally all fitness cases are predicted correctly
    21       throw new NotImplementedException();
     110      // search for corresponding level
     111      int level = 0;
     112      while (maxSizeForLevel[level + 1] < maxLen) level++;
     113      // ASSERT: maxSizeForLevel[level + 1] >= maxLen
     114      return optimalQualityForLevel[level];
    22115    }
    23116
     
    27120
    28121    public double Evaluate(string sentence) {
    29       throw new NotImplementedException();
    30     }
     122      int pos = 0;
     123      bool perfect;
     124      return Evaluate(sentence, ref pos, out perfect);
     125    }
     126
     127    private double Evaluate(string sentence, ref int pos, out bool perfect) {
     128      const double completeBonus = 2.0;
     129      double t = 0.0;
     130      double weight = 0.0;
     131      double sum = 0.0;
     132      bool correctRoot = false;
     133      bool allPerfect = true, tPerfect;
     134      int arity;
     135      switch (sentence[pos]) {
     136        case 'a':
     137          pos++;
     138          correctRoot = (sentence[pos] == 'x');
     139          t = Evaluate(sentence, ref pos, out tPerfect); // ignores the perfect flag (false for terminals)
     140          weight = GetWeight(correctRoot, true);
     141          sum = weight * t;
     142          perfect = correctRoot;
     143          if (correctRoot) sum *= completeBonus;
     144          return sum;
     145        case 'b': {
     146            arity = 2;
     147            pos++;
     148            for (int i = 0; i < arity; i++) {
     149              correctRoot = (sentence[pos] == 'a');
     150              t = Evaluate(sentence, ref pos, out tPerfect);
     151              weight = GetWeight(correctRoot, tPerfect);
     152              allPerfect &= correctRoot & tPerfect;
     153              sum += weight * t;
     154            }
     155            perfect = allPerfect;
     156            if (allPerfect) sum *= completeBonus;
     157            return sum;
     158          }
     159        case 'c': {
     160            arity = 3;
     161            sum = 0.0;
     162            pos++;
     163            for (int i = 0; i < arity; i++) {
     164              correctRoot = (sentence[pos] == 'b');
     165              t = Evaluate(sentence, ref pos, out tPerfect);
     166              weight = GetWeight(correctRoot, tPerfect);
     167              allPerfect &= correctRoot & tPerfect;
     168              sum += weight * t;
     169            }
     170            perfect = allPerfect;
     171            if (allPerfect) sum *= completeBonus;
     172            return sum;
     173          }
     174        case 'd': {
     175            arity = 4;
     176            sum = 0.0;
     177            pos++;
     178            for (int i = 0; i < arity; i++) {
     179              correctRoot = (sentence[pos] == 'c');
     180              t = Evaluate(sentence, ref pos, out tPerfect);
     181              weight = GetWeight(correctRoot, tPerfect);
     182              allPerfect &= correctRoot & tPerfect;
     183              sum += weight * t;
     184            }
     185            perfect = allPerfect;
     186            if (allPerfect) sum *= completeBonus;
     187            return sum;
     188          }
     189        case 'e': {
     190            arity = 5;
     191            sum = 0.0;
     192            pos++;
     193            for (int i = 0; i < arity; i++) {
     194              correctRoot = (sentence[pos] == 'd');
     195              t = Evaluate(sentence, ref pos, out tPerfect);
     196              weight = GetWeight(correctRoot, tPerfect);
     197              allPerfect &= correctRoot & tPerfect;
     198              sum += weight * t;
     199            }
     200            perfect = allPerfect;
     201            if (allPerfect) sum *= completeBonus;
     202            return sum;
     203          }
     204        case 'f': {
     205            arity = 6;
     206            sum = 0.0;
     207            pos++;
     208            for (int i = 0; i < arity; i++) {
     209              correctRoot = (sentence[pos] == 'e');
     210              t = Evaluate(sentence, ref pos, out tPerfect);
     211              weight = GetWeight(correctRoot, tPerfect);
     212              allPerfect &= correctRoot & tPerfect;
     213              sum += weight * t;
     214            }
     215            perfect = allPerfect;
     216            if (allPerfect) sum *= completeBonus;
     217            return sum;
     218          }
     219        case 'g': {
     220            arity = 7;
     221            sum = 0.0;
     222            pos++;
     223            for (int i = 0; i < arity; i++) {
     224              correctRoot = (sentence[pos] == 'f');
     225              t = Evaluate(sentence, ref pos, out tPerfect);
     226              weight = GetWeight(correctRoot, tPerfect);
     227              allPerfect &= correctRoot & tPerfect;
     228              sum += weight * t;
     229            }
     230            perfect = allPerfect;
     231            if (allPerfect) sum *= completeBonus;
     232            return sum;
     233          }
     234        case 'x':
     235          pos++;
     236          perfect = false;
     237          return 1.0;
     238        case 'y':
     239        case 'z':
     240          pos++;
     241          perfect = false;
     242          return 0.0;
     243        default: throw new ArgumentException();
     244      }
     245    }
     246
     247    private double GetWeight(bool correctRoot, bool perfect) {
     248      const double fullBonus = 2.0;
     249      const double partialBonus = 1.0;
     250      const double penalty = 0.33;
     251      if (correctRoot && perfect) return fullBonus;
     252      else if (correctRoot) return partialBonus;
     253      else return penalty;
     254    }
     255
    31256    public string CanonicalRepresentation(string phrase) {
    32257      throw new NotImplementedException();
     
    34259    }
    35260
    36     public IEnumerable<Feature> GetFeatures(string phrase)
    37     {
     261    public IEnumerable<Feature> GetFeatures(string phrase) {
    38262      throw new NotImplementedException();
     263    }
     264
     265    public IGrammar TreeBasedGPGrammar { get; private set; }
     266    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
     267      var sb = new StringBuilder();
     268      foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) {
     269        if (s.Symbol.Name == "S") continue;
     270        sb.Append(s.Symbol.Name.ToLower());
     271      }
     272      return sb.ToString();
    39273    }
    40274  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SentenceSetStatistics.cs

    r11847 r11865  
    2323    public SentenceSetStatistics(double bestKnownQuality = 1.0) {
    2424      this.bestKnownQuality = bestKnownQuality;
     25      BestSentenceQuality = double.NegativeInfinity;
     26      BestSentence = string.Empty;
     27      FirstSentence = string.Empty;
     28      LastSentence = string.Empty;
    2529    }
    2630
  • branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs

    r11847 r11865  
    2525
    2626      //RunDemo();
    27       RunGpDemo();
     27      //RunGpDemo();
    2828      // RunGridTest();
     29      RunGpGridTest();
    2930    }
    3031
     
    174175
    175176    private static void RunDemo() {
    176       // TODO: implement bridge to HL-GP
    177177      // TODO: unify MCTS, TD and ContextMCTS Solvers (stateInfos)
    178178      // TODO: test with eps-greedy using max instead of average as value (seems to work well for symb-reg! explore further!)
    179179      // TODO: separate value function from policy
    180       // TODO: in contextual MCTS store a bandit info for each node in the _graph_ and also update all bandit infos of all parents
    181       // TODO: exhaustive search with priority list
    182180      // TODO: warum funktioniert die alte Implementierung von GaussianThompson besser fÃŒr SantaFe als neue? Siehe Vergleich: alte vs. neue implementierung GaussianThompsonSampling
    183181      // TODO: why does GaussianThompsonSampling work so well with MCTS for the artificial ant problem?
    184182      // TODO: research thompson sampling for max bandit?
    185       // TODO: ausfÃŒhrlicher test von strategien fÃŒr numCorrectPhrases-armed max bandit
    186183      // TODO: verify TA implementation using example from the original paper     
    187       // TODO: separate policy from MCTS tree data structure to allow sharing of information over disconnected parts of the tree (semantic equivalence)
    188184      // TODO: implement thompson sampling for gaussian mixture models
    189       // TODO: implement inspection for MCTS (eventuell interactive command line fÃŒr statistiken aus dem baum anzeigen)
    190       // TODO: implement ACO-style bandit policy
    191185      // TODO: gleichzeitige modellierung von transformierter zielvariable (y, 1/y, log(y), exp(y), sqrt(y), ...)
    192186      // TODO: vergleich bei complete-randomly möglichst kurze sÀtze generieren vs. einfach zufÀllig alternativen wÀhlen
     
    299293
    300294    public static void RunGpDemo() {
    301 
    302295      int iterations = 0;
     296      const int seed = 31415;
    303297      const int maxIterations = 100000;
     298
     299    }
     300
     301
     302    private static void RunGpGridTest() {
     303      const int nReps = 20;
    304304      const int seed = 31415;
    305       var globalStatistics = new SentenceSetStatistics(512);
    306 
    307       var gp = new StandardGP(new HardPalindromeProblem(), new Random(seed));
    308       gp.FoundNewBestSolution += (sentence, quality) => {
    309         Console.WriteLine("{0}", globalStatistics);
    310       };
     305      const int maxIters = 100000;
     306      var rand = new Random(seed);
     307      var problemFactories = new Func<ISymbolicExpressionTreeProblem>[]
     308      {
     309        () => new SantaFeAntProblem(),
     310        () => new SymbolicRegressionPoly10Problem(),
     311      };
     312      foreach (var popSize in new int[] { 50, 100, 250, 500, 1000, 2500, 5000 }) {
     313        foreach (var mutationRate in new double[] {/* 0.05, 0.10, */ 0.15, /* 0.25, 0.3 */ }) {
     314          foreach (var maxSize in new int[] { 30, 50, 100 }) {
     315            foreach (var problemFactory in problemFactories)
     316              for (int i = 0; i < nReps; i++) {
     317                var solverSeed = rand.Next();
     318                {
     319                  var prob = problemFactory();
     320                  RunStandardGP(prob, solverSeed, maxIters, popSize, mutationRate, maxSize);
     321                }
     322                {
     323                  var prob = problemFactory();
     324                  RunOSGP(prob, solverSeed, maxIters, popSize, mutationRate, maxSize);
     325                }
     326              }
     327          }
     328        }
     329      }
     330    }
     331
     332    private static void RunStandardGP(ISymbolicExpressionTreeProblem prob, int solverSeed, int maxIters, int popSize, double mutationRate, int maxSize) {
     333      int iterations = 0;
     334      var globalStatistics = new SentenceSetStatistics(prob.BestKnownQuality(maxSize));
     335
     336      var gp = new StandardGP(prob, new Random(solverSeed));
    311337      gp.SolutionEvaluated += (sentence, quality) => {
    312338        iterations++;
     
    314340
    315341        if (iterations % 10000 == 0) {
    316           Console.WriteLine("{0}", globalStatistics);
    317         }
    318       };
    319 
    320       gp.PopulationSize = 1000;
    321       gp.MaxSolutionSize = 31 + 2;
    322       gp.MaxSolutionDepth = 20;
     342          Console.WriteLine("\"{0,25}\" \"{1,25}\" {2}", gp, prob, globalStatistics);
     343        }
     344      };
     345
     346      gp.PopulationSize = popSize;
     347      gp.MutationRate = mutationRate;
     348      gp.MaxSolutionSize = maxSize + 2;
     349      gp.MaxSolutionDepth = maxSize + 2;
    323350
    324351      var sw = new Stopwatch();
    325352
    326353      sw.Start();
    327       gp.Run(maxIterations);
     354      gp.Run(maxIters);
    328355      sw.Stop();
    329356
    330       Console.WriteLine(globalStatistics);
    331       Console.WriteLine("{0:F2} sec {1,10:F1} sols/sec {2,10:F1} ns/sol",
    332         sw.Elapsed.TotalSeconds,
    333         maxIterations / (double)sw.Elapsed.TotalSeconds,
    334         (double)sw.ElapsedMilliseconds * 1000 / maxIterations);
     357      Console.WriteLine("\"{0,25}\" \"{1,25}\" {2}", gp, prob, globalStatistics);
     358
     359      // Console.WriteLine("{0:F2} sec {1,10:F1} sols/sec {2,10:F1} ns/sol",
     360      //   sw.Elapsed.TotalSeconds,
     361      //   maxIters / (double)sw.Elapsed.TotalSeconds,
     362      //   (double)sw.ElapsedMilliseconds * 1000 / maxIters);
     363    }
     364
     365    private static void RunOSGP(ISymbolicExpressionTreeProblem prob, int solverSeed, int maxIters, int popSize, double mutationRate, int maxSize) {
     366      int iterations = 0;
     367      var globalStatistics = new SentenceSetStatistics(prob.BestKnownQuality(maxSize));
     368
     369      var gp = new OffspringSelectionGP(prob, new Random(solverSeed));
     370      gp.SolutionEvaluated += (sentence, quality) => {
     371        iterations++;
     372        globalStatistics.AddSentence(sentence, quality);
     373
     374        if (iterations % 10000 == 0) {
     375          Console.WriteLine("\"{0,25}\" \"{1,25}\" {2}", gp, prob, globalStatistics);
     376        }
     377      };
     378
     379      gp.PopulationSize = popSize;
     380      gp.MutationRate = mutationRate;
     381      gp.MaxSolutionSize = maxSize + 2;
     382      gp.MaxSolutionDepth = maxSize + 2;
     383
     384      var sw = new Stopwatch();
     385
     386      sw.Start();
     387      gp.Run(maxIters);
     388      sw.Stop();
     389
     390      Console.WriteLine("\"{0,25}\" \"{1,25}\" {2}", gp, prob, globalStatistics);
     391
     392      // Console.WriteLine("{0:F2} sec {1,10:F1} sols/sec {2,10:F1} ns/sol",
     393      //   sw.Elapsed.TotalSeconds,
     394      //   maxIters / (double)sw.Elapsed.TotalSeconds,
     395      //   (double)sw.ElapsedMilliseconds * 1000 / maxIters);
    335396    }
    336397  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestInstances.cs

    r11747 r11865  
    146146      Assert.AreEqual(89, p.Evaluate("?(m)(ll?(m)(r))mr"));
    147147    }
    148     [TestMethod]
    149     public void TestRoyalTreeProblem() {
    150       var p = new RoyalTreeProblem();
    151       Console.WriteLine(p.Grammar);
    152 
    153     }
     148
    154149    [TestMethod]
    155150    public void TestRoyalRoadProblem() {
     
    261256      Assert.AreEqual(1.0, p.Evaluate("a*b+c*d+e*f+a*g*i+c*f*j"), 1.0E-7);
    262257    }
     258
     259    [TestMethod]
     260    public void TestRoyalTreeProblem() {
     261      var p = new RoyalTreeProblem(7);
     262      Console.WriteLine(p.Grammar);
     263
     264      // examples from The Royal Tree Problem, a Benchmark for Single and Multi-population Genetic Programming (Punch, Zongker, Goodman)
     265      Assert.AreEqual(4, p.Evaluate("ax"), 1.0E-7);
     266      Assert.AreEqual(384.0, p.Evaluate("cbaxaxbaxaxbaxax"), 1.0E-7);
     267      Assert.AreEqual(128.66, p.Evaluate("cbaxaxbaxaxbxx"), 1.0E-7);
     268      Assert.AreEqual(64.66, p.Evaluate("cbaxaxxx"), 1.0E-7);
     269
     270    }
    263271  }
    264272}
Note: See TracChangeset for help on using the changeset viewer.