Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs @ 12391

Last change on this file since 12391 was 12391, checked in by gkronber, 9 years ago

#2283: added shuffling of terminal symbols to the royal pair problem to make sure that there is no bias from order of terminal symbols.

File size: 3.3 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4using System.Linq;
5using System.Text;
6using System.Text.RegularExpressions;
7using HeuristicLab.Common;
8using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
9using HeuristicLab.Random;
10
11namespace HeuristicLab.Problems.GrammaticalOptimization {
12  // counts the number of times a pair of symbols occurs in a sentence
13  public class RoyalPairProblem : ISymbolicExpressionTreeProblem {
14
15    private readonly IGrammar grammar;
16    private readonly int numTerminals;
17    public string Name { get { return string.Format("RoyalPair({0})", numTerminals); } }
18
19    public RoyalPairProblem(int numTerminals = 2) {
20      this.numTerminals = numTerminals;
21
22      var sentenceSymbol = 'S';
23      var terminalSymbols = Enumerable.Range(0, numTerminals).Select(off => (char)((byte)'a' + off)).ToList();
24      terminalSymbols.ShuffleInPlace(new MersenneTwister(31415));
25
26      var nonTerminalSymbols = new char[] { sentenceSymbol };
27
28      {
29        // create grammar
30        // S -> a..z | aS .. zS
31        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
32          .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString())));
33
34        this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
35      }
36      {
37        // create grammar for tree-based GP
38        // S -> a..z | SS
39        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
40          .Concat(new Tuple<char, string>[] { Tuple.Create(sentenceSymbol, sentenceSymbol.ToString() + sentenceSymbol) });
41
42        this.TreeBasedGPGrammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
43      }
44
45
46    }
47
48    public double BestKnownQuality(int maxLen) {
49      return maxLen - 1;
50    }
51
52    public IGrammar Grammar {
53      get { return grammar; }
54    }
55
56    private Regex regex = new Regex("(?=ab)|(?=ba)"); // count the number of "ab" and "ba" pairs
57    public double Evaluate(string sentence) {
58      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
59      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
60      return regex.Matches(sentence).Count;
61    }
62
63    public string CanonicalRepresentation(string phrase) {
64      return phrase;
65    }
66
67    public IEnumerable<Feature> GetFeatures(string phrase) {
68      if (phrase.Length <= 1)
69        yield return new Feature("$$", 1.0);
70      else if (phrase.Length == 2)
71        yield return new Feature(phrase, 1.0);
72      else if (phrase.EndsWith("S")) // second to last symbol
73        yield return new Feature(phrase.Substring(phrase.Length - 3, 2), 1.0);
74      else // last symbol
75        yield return new Feature(phrase.Substring(phrase.Length - 2, 2), 1.0);
76
77    }
78
79    public IGrammar TreeBasedGPGrammar { get; private set; }
80    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
81      var sb = new StringBuilder();
82      foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) {
83        if (s.Symbol.Name == "S") continue;
84        sb.Append(s.Symbol.Name);
85      }
86      return sb.ToString();
87    }
88  }
89}
Note: See TracBrowser for help on using the repository browser.