Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs @ 11846

Last change on this file since 11846 was 11846, checked in by gkronber, 8 years ago

#2283 implemented bridge to HL (solve grammatical optimization problem instances with StandardGP and OffspringSelectionGP)

File size: 6.7 KB
Line 
1using System;
2using System.Collections.Concurrent;
3using System.Collections.Generic;
4using System.Collections.Specialized;
5using System.Diagnostics;
6using System.Linq;
7using System.Net;
8using System.Security;
9using System.Security.AccessControl;
10using System.Text;
11using HeuristicLab.Common;
12using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
13
14namespace HeuristicLab.Problems.GrammaticalOptimization {
15  public class SymbolicRegressionPoly10Problem : ISymbolicExpressionTreeProblem {
16    //    private const string grammarString = @"
17    //    G(E):
18    //    E -> V | V+E | V-E | V*E | (E)
19    //    V -> a .. j
20    //    ";
21    private const string grammarString = @"
22    G(E):
23    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
24    ";
25
26    // for tree-based GP in HL we need a different grammar for the same language
27    // E = expr, S = sum, P = product
28    private const string hlGrammarString = @"
29    G(E):
30    E -> S | P | a | b | c | d | e | f | g | h | i | j
31    S -> EE | EEE
32    P -> EE | EEE
33    ";
34    // mininmal tree for the optimal expr (40 nodes)
35    // E S
36    //     E S
37    //         E P
38    //           E a E b
39    //         E P
40    //           E c E d
41    //         E P
42    //           E e E f
43    //     E S
44    //         E P
45    //           E a E g E i
46    //         E P
47    //           E c E f E j
48
49    private SymbolicExpressionGrammar symbExprGrammar;
50    public ISymbolicExpressionGrammar SymbolicExpressionGrammar {
51      get {
52        return symbExprGrammar;
53      }
54    }
55
56    private readonly IGrammar grammar;
57
58    private readonly int N;
59    private readonly double[][] x;
60    private readonly double[] y;
61
62    public SymbolicRegressionPoly10Problem() {
63      this.grammar = new Grammar(grammarString);
64      this.symbExprGrammar = new GenericSymbExprGrammar(new Grammar(hlGrammarString));
65
66      this.N = 500;
67      this.x = new double[N][];
68      this.y = new double[N];
69
70      GenerateData();
71    }
72
73    private void GenerateData() {
74      // generate data with fixed seed to make sure that data is always the same
75      var rand = new Random(31415);
76      for (int i = 0; i < N; i++) {
77        x[i] = new double[10];
78        for (int j = 0; j < 10; j++) {
79          x[i][j] = rand.NextDouble() * 2 - 1;
80        }
81        // poly-10 no noise
82        /* a*b + c*d + e*f + a*g*i + c*f*j */
83        y[i] = x[i][0] * x[i][1] +
84               x[i][2] * x[i][3] +
85               x[i][4] * x[i][5] +
86               x[i][0] * x[i][6] * x[i][8] +
87               x[i][2] * x[i][5] * x[i][9];
88      }
89    }
90
91    public double BestKnownQuality(int maxLen) {
92      // for now only an upper bound is returned, ideally we have an R² of 1.0
93      // the optimal R² can only be reached for sentences of at least 23 symbols
94      return 1.0;
95    }
96
97    public IGrammar Grammar {
98      get { return grammar; }
99    }
100
101    public double Evaluate(string sentence) {
102      var interpreter = new ExpressionInterpreter();
103      return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])).ToArray());
104    }
105
106
107    // most-recently-used caching (with limited capacity) for canonical representations
108    MostRecentlyUsedCache<string, string> canonicalPhraseCache = new MostRecentlyUsedCache<string, string>(100000);
109    // right now only + and * is supported
110    public string CanonicalRepresentation(string phrase) {
111      string canonicalPhrase;
112      if (!canonicalPhraseCache.TryGetValue(phrase, out canonicalPhrase)) {
113        var terms = phrase.Split('+');
114        var canonicalTerms = new SortedSet<string>();
115        // only the last term might contain a NT-symbol. make sure this term is added at the end
116        for (int i = 0; i < terms.Length - 1; i++) {
117          canonicalTerms.Add(CanonicalTerm(terms[i]));
118        }
119
120        var sb = new StringBuilder(phrase.Length);
121        foreach (var t in canonicalTerms)
122          sb.Append(t).Append('+');
123
124        sb.Append(CanonicalTerm(terms[terms.Length - 1]));
125        canonicalPhrase = sb.ToString();
126        canonicalPhraseCache.Add(phrase, canonicalPhrase);
127      }
128      return canonicalPhrase;
129    }
130
131    // cache the canonical form of terms for performance reasons
132    private Dictionary<string, string> canonicalTermDictionary = new Dictionary<string, string>();
133    private string CanonicalTerm(string term) {
134      string canonicalTerm;
135      if (!canonicalTermDictionary.TryGetValue(term, out canonicalTerm)) {
136        // add
137        var chars = term.ToCharArray();
138        Array.Sort(chars);
139        var sb = new StringBuilder(chars.Length);
140        // we want to have the up-case characters last
141        for (int i = chars.Length - 1; i > 0; i--) {
142          if (chars[i] != '*') {
143            sb.Append(chars[i]);
144            if (chars[i - 1] != '*') sb.Append('*');
145          }
146        }
147        if (chars[0] != '*') sb.Append(chars[0]); // last term
148        canonicalTerm = sb.ToString();
149        canonicalTermDictionary.Add(term, canonicalTerm);
150      }
151      return canonicalTerm;
152    }
153
154    // splits the phrase into terms and creates (sparse) term-occurrance features
155    public IEnumerable<Feature> GetFeatures(string phrase) {
156      var canonicalTerms = new HashSet<string>();
157      foreach (string t in phrase.Split('+')) {
158        canonicalTerms.Add(CanonicalTerm(t));
159      }
160      return canonicalTerms.Select(entry => new Feature(entry, 1.0)).Concat(new Feature[] { new Feature(CanonicalRepresentation(phrase), 1.0) });
161    }
162
163    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
164      var sb = new StringBuilder();
165
166      TreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
167
168      return sb.ToString();
169    }
170
171    private void TreeToSentence(ISymbolicExpressionTreeNode treeNode, StringBuilder sb) {
172      if (treeNode.SubtreeCount == 0) {
173        // terminal
174        sb.Append(treeNode.Symbol.Name);
175      } else {
176        string op = string.Empty;
177        switch (treeNode.Symbol.Name) {
178          case "S": op = "+"; break;
179          case "P": op = "*"; break;
180          default: {
181              Debug.Assert(treeNode.SubtreeCount == 1);
182              break;
183            }
184        }
185        // nonterminal
186        if (op == "+") sb.Append("(");
187        TreeToSentence(treeNode.Subtrees.First(), sb);
188        foreach (var subTree in treeNode.Subtrees.Skip(1)) {
189          sb.Append(op);
190          TreeToSentence(subTree, sb);
191        }
192        if (op == "+") sb.Append(")");
193      }
194    }
195  }
196}
Note: See TracBrowser for help on using the repository browser.