Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Test/TestInstances.cs @ 13985

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

#2283: experiments on grammatical optimization algorithms (maxreward instead of avg reward, ...)
File size: 10.8 KB
Line 
1using System;
2using System.Diagnostics;
3using System.Linq;
4using Microsoft.VisualStudio.TestTools.UnitTesting;
5
6namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
7  [TestClass]
8  public class TestInstances {
9    [TestMethod]
10    public void TestGrammarFromString() {
11      {
12        var g = Grammar.FromString(@"
13
14G(S):
15  S -> aA | bB
16  A -> a | aA
17  B -> Bb | b
18");
19        Assert.AreEqual('S', g.SentenceSymbol);
20        Assert.AreEqual(2, g.TerminalSymbols.Count());
21        Assert.AreEqual(3, g.NonTerminalSymbols.Count());
22        Assert.IsTrue(g.TerminalSymbols.All(s => new char[] { 'a', 'b' }.Contains(s)));
23        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S', 'A', 'B' }.Contains(s)));
24
25        Assert.AreEqual(2, g.GetAlternatives('S').Count());
26        Assert.AreEqual(2, g.GetAlternatives('A').Count());
27        Assert.AreEqual(2, g.GetAlternatives('B').Count());
28
29        Assert.IsTrue(g.GetAlternatives('S').Any(s => s.ToString() == "aA"));
30        Assert.IsTrue(g.GetAlternatives('S').Any(s => s.ToString() == "bB"));
31        Assert.IsTrue(g.GetAlternatives('A').Any(s => s.ToString() == "aA"));
32        Assert.IsTrue(g.GetAlternatives('A').Any(s => s.ToString() == "a"));
33        Assert.IsTrue(g.GetAlternatives('B').Any(s => s.ToString() == "Bb"));
34        Assert.IsTrue(g.GetAlternatives('B').Any(s => s.ToString() == "b"));
35
36        Assert.AreEqual(2, g.MinPhraseLength(new Sequence("S")));
37        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength(new Sequence("S")));
38        Assert.AreEqual(1, g.MinPhraseLength(new Sequence("A")));
39        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength(new Sequence("A")));
40        Assert.AreEqual(1, g.MinPhraseLength(new Sequence("B")));
41        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength(new Sequence("B")));
42      }
43
44      {
45        var g = Grammar.FromString(@"
46
47G(S):
48  S -> sS
49");
50        Assert.AreEqual('S', g.SentenceSymbol);
51        Assert.AreEqual(1, g.TerminalSymbols.Count());
52        Assert.AreEqual(1, g.NonTerminalSymbols.Count());
53        Assert.IsTrue(g.TerminalSymbols.All(s => new char[] { 's' }.Contains(s)));
54        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S' }.Contains(s)));
55
56        Assert.AreEqual(1, g.GetAlternatives('S').Count());
57
58        Assert.IsTrue(g.GetAlternatives('S').Any(s => s.ToString() == "sS"));
59
60        Assert.AreEqual(short.MaxValue, g.MinPhraseLength(new Sequence("S")));
61        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength(new Sequence("S")));
62      }
63
64      {
65        var g = Grammar.FromString(@"
66
67G(S):
68S->sss|sS");
69        Assert.AreEqual('S', g.SentenceSymbol);
70        Assert.AreEqual(1, g.TerminalSymbols.Count());
71        Assert.AreEqual(1, g.NonTerminalSymbols.Count());
72        Assert.IsTrue(g.TerminalSymbols.All(s => new char[] { 's' }.Contains(s)));
73        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S' }.Contains(s)));
74
75        Assert.AreEqual(2, g.GetAlternatives('S').Count());
76
77        Assert.IsTrue(g.GetAlternatives('S').Any(s => s.ToString() == "sss"));
78        Assert.IsTrue(g.GetAlternatives('S').Any(s => s.ToString() == "sS"));
79
80        Assert.AreEqual(3, g.MinPhraseLength(new Sequence("S")));
81        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength(new Sequence("S")));
82        Assert.AreEqual(4, g.MinPhraseLength(new Sequence("sS")));
83        Assert.AreEqual(7, g.MinPhraseLength(new Sequence("sSS")));
84        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength(new Sequence("sSS")));
85        Assert.AreEqual(3, g.MaxPhraseLength(new Sequence("sss")));
86        Assert.AreEqual(3, g.MinPhraseLength(new Sequence("sss")));
87      }
88
89      {
90        var g = Grammar.FromString(@"
91
92G(S):
93S->T|TS
94T-> a..z
95");
96        Assert.AreEqual('S', g.SentenceSymbol);
97        Assert.AreEqual(26, g.TerminalSymbols.Count());
98        Assert.AreEqual(2, g.NonTerminalSymbols.Count());
99        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S', 'T' }.Contains(s)));
100
101        Assert.AreEqual(2, g.GetAlternatives('S').Count());
102
103        Assert.IsTrue(g.GetAlternatives('S').Any(s => s.ToString() == "T"));
104        Assert.IsTrue(g.GetAlternatives('S').Any(s => s.ToString() == "TS"));
105
106        Assert.AreEqual(1, g.MinPhraseLength(new Sequence("S")));
107        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength(new Sequence("S")));
108        Assert.AreEqual(1, g.MinPhraseLength(new Sequence("T")));
109        Assert.AreEqual(1, g.MaxPhraseLength(new Sequence("T")));
110      }
111
112    }
113
114    [TestMethod]
115    public void TestRoyalSymbolProblem() {
116      var p = new RoyalSymbolProblem();
117      Console.WriteLine(p.Grammar);
118
119      Assert.AreEqual(1, p.Evaluate("ab"));
120      Assert.AreEqual(0, p.Evaluate("bb"));
121      Assert.AreEqual(2, p.Evaluate("aa"));
122      Assert.AreEqual(3, p.Evaluate("aaa"));
123    }
124
125
126    [TestMethod]
127    public void TestRoyalPairProblem() {
128      var p = new RoyalPairProblem();
129      Console.WriteLine(p.Grammar);
130
131      Assert.AreEqual(1, p.Evaluate("ab"));
132      Assert.AreEqual(0, p.Evaluate("bb"));
133      Assert.AreEqual(0, p.Evaluate("aa"));
134      Assert.AreEqual(0, p.Evaluate("aaa"));
135      Assert.AreEqual(2, p.Evaluate("aba"));
136      Assert.AreEqual(2, p.Evaluate("abba"));
137      Assert.AreEqual(3, p.Evaluate("abab"));
138    }
139
140    [TestMethod]
141    public void TestSantaFeAntProblem() {
142      var p = new SantaFeAntProblem();
143      Console.WriteLine(p.Grammar);
144
145      // one possible optimal solution: if-food-ahead (move) ( left left if-food-ahead (move) (right)) move right
146      Assert.AreEqual(89, p.Evaluate("?(m)(ll?(m)(r))mr"));
147    }
148
149    [TestMethod]
150    public void TestRoyalRoadProblem() {
151      var p = new RoyalRoadProblem();
152      Console.WriteLine(p.Grammar);
153
154    }
155    [TestMethod]
156    public void TestPalindromeProblem() {
157      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("aba"));
158      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("aaba"));
159      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("abaa"));
160      Assert.AreEqual("aabaa", PalindromeProblem.LongestPalindromicSubstring("aaaabaa"));
161      Assert.AreEqual("aabaa", PalindromeProblem.LongestPalindromicSubstring("aabaaaa"));
162      Assert.AreEqual("baaaab", PalindromeProblem.LongestPalindromicSubstring("aabaaaab"));
163
164
165      var p = new PalindromeProblem();
166      Console.WriteLine(p.Grammar);
167
168      Assert.AreEqual(1, p.Evaluate("a"));
169      Assert.AreEqual(2, p.Evaluate("aa"));
170      Assert.AreEqual(3, p.Evaluate("aaa"));
171      Assert.AreEqual(3, p.Evaluate("aba"));
172      Assert.AreEqual(3, p.Evaluate("baba"));
173      Assert.AreEqual(3, p.Evaluate("abab"));
174      Assert.AreEqual(5, p.Evaluate("babab"));
175    }
176    [TestMethod]
177    public void TestHardPalindromeProblem() {
178      var p = new HardPalindromeProblem();
179      Console.WriteLine(p.Grammar);
180
181      Assert.AreEqual(1 + 1, p.Evaluate("a"));
182      Assert.AreEqual(2 + 1, p.Evaluate("aa"));
183      Assert.AreEqual(3 + 1, p.Evaluate("aaa"));
184      Assert.AreEqual(3 + 2, p.Evaluate("aba"));
185      Assert.AreEqual(3 + 2, p.Evaluate("baba"));
186      Assert.AreEqual(3 + 2, p.Evaluate("abab"));
187      Assert.AreEqual(5 + 2, p.Evaluate("babab"));
188      Assert.AreEqual(5 + 3, p.Evaluate("bacab"));
189    }
190
191    [TestMethod]
192    public void TestEvenParityProblem() {
193      var p = new EvenParityProblem();
194      Console.WriteLine(p.Grammar);
195
196      // a | b | c | d | res
197      // 0 | 0 | 0 | 0 | 1
198      // 0 | 0 | 0 | 1 | 0
199      // 0 | 0 | 1 | 0 | 0
200      // 0 | 0 | 1 | 1 | 1
201      // 0 | 1 | 0 | 0 | 0
202      // 0 | 1 | 0 | 1 | 1
203      // 0 | 1 | 1 | 0 | 1
204      // 0 | 1 | 1 | 1 | 0
205      // 1 | 0 | 0 | 0 | 0
206      // 1 | 0 | 0 | 1 | 1
207      // 1 | 0 | 1 | 0 | 1
208      // 1 | 0 | 1 | 1 | 0
209      // 1 | 1 | 0 | 0 | 1
210      // 1 | 1 | 0 | 1 | 0
211      // 1 | 1 | 1 | 0 | 0
212      // 1 | 1 | 1 | 1 | 1
213
214
215      Assert.AreEqual(8, p.Evaluate("a"));
216      Assert.AreEqual(8, p.Evaluate("b"));
217      Assert.AreEqual(8, p.Evaluate("c"));
218      Assert.AreEqual(8, p.Evaluate("d"));
219
220      Assert.AreEqual(8, p.Evaluate("a*b")); // a and b
221      Assert.AreEqual(8, p.Evaluate("a+b")); // a or b
222      Assert.AreEqual(8, p.Evaluate("!a*b+a*!b")); // a xor b
223      Assert.AreEqual(8, p.Evaluate("!(a*b)+(a*!b)")); // a xor b
224      Assert.AreEqual(16, p.Evaluate("a^b^c^d")); // a xor b
225    }
226
227    [TestMethod]
228    public void TestSymbolicRegressionPoly10Problem() {
229      var p = new SymbolicRegressionPoly10Problem();
230      Console.WriteLine(p.Grammar);
231
232      Assert.AreEqual(0.00319925877644673, p.Evaluate("a"), 1.0E-7);
233      Assert.AreEqual(0.00632775454329686, p.Evaluate("b"), 1.0E-7);
234      Assert.AreEqual(0.00569030954291292, p.Evaluate("c"), 1.0E-7);
235      Assert.AreEqual(3.32317092313123E-05, p.Evaluate("d"), 1.0E-7);
236      Assert.AreEqual(0.000562538829174826, p.Evaluate("e"), 1.0E-7);
237      Assert.AreEqual(3.29458942533772E-06, p.Evaluate("f"), 1.0E-7);
238      Assert.AreEqual(0.000193866006166768, p.Evaluate("g"), 1.0E-7);
239      Assert.AreEqual(2.83339004096246E-05, p.Evaluate("h"), 1.0E-7);
240      Assert.AreEqual(0.00291584574914239, p.Evaluate("i"), 1.0E-7);
241      Assert.AreEqual(0.00504038616701691, p.Evaluate("j"), 1.0E-7);
242
243      Assert.AreEqual(0.252718466940018, p.Evaluate("a*b"), 1.0E-7);
244      Assert.AreEqual(0.290635611728845, p.Evaluate("c*d"), 1.0E-7);
245      Assert.AreEqual(0.25737325167716, p.Evaluate("e*f"), 1.0E-7);
246
247      Assert.AreEqual(0.00173739472363473, p.Evaluate("b*c"), 1.0E-7);
248      Assert.AreEqual(3.15450564064128E-05, p.Evaluate("d*e"), 1.0E-7);
249
250      Assert.AreEqual(0.0943358163760454, p.Evaluate("a*g*i"), 1.0E-7);
251      Assert.AreEqual(0.116199534934045, p.Evaluate("c*f*j"), 1.0E-7);
252
253      Assert.AreEqual(0.824522210419616, p.Evaluate("a*b+c*d+e*f"), 1E-7);
254
255
256      Assert.AreEqual(1.0, p.Evaluate("a*b+c*d+e*f+a*g*i+c*f*j"), 1.0E-7);
257    }
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    }
271
272    //[TestMethod]
273    //public void GenerateDataForPoly10() {
274    //  var p = new SymbolicRegressionPoly10Problem();
275    //
276    //  // complete a sentence n times and observe rewards
277    //  var incompleteSequence = new ReadonlySequence("a*b+c*d+e*f+E");
278    //  var options =
279    //  int n = 100000;
280    //  for (int i = 0; i < n; i++) {
281    //    var s = new Sequence(incompleteSequence);
282    //  }
283    //}
284  }
285}
Note: See TracBrowser for help on using the repository browser.