Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestInstances.cs @ 11842

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

#2283: implemented test problems for MCTS

File size: 10.0 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    [TestMethod]
149    public void TestRoyalTreeProblem() {
150      var p = new RoyalTreeProblem();
151      Console.WriteLine(p.Grammar);
152
153    }
154    [TestMethod]
155    public void TestRoyalRoadProblem() {
156      var p = new RoyalRoadProblem();
157      Console.WriteLine(p.Grammar);
158
159    }
160    [TestMethod]
161    public void TestPalindromeProblem() {
162      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("aba"));
163      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("aaba"));
164      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("abaa"));
165      Assert.AreEqual("aabaa", PalindromeProblem.LongestPalindromicSubstring("aaaabaa"));
166      Assert.AreEqual("aabaa", PalindromeProblem.LongestPalindromicSubstring("aabaaaa"));
167      Assert.AreEqual("baaaab", PalindromeProblem.LongestPalindromicSubstring("aabaaaab"));
168
169
170      var p = new PalindromeProblem();
171      Console.WriteLine(p.Grammar);
172
173      Assert.AreEqual(1, p.Evaluate("a"));
174      Assert.AreEqual(2, p.Evaluate("aa"));
175      Assert.AreEqual(3, p.Evaluate("aaa"));
176      Assert.AreEqual(3, p.Evaluate("aba"));
177      Assert.AreEqual(3, p.Evaluate("baba"));
178      Assert.AreEqual(3, p.Evaluate("abab"));
179      Assert.AreEqual(5, p.Evaluate("babab"));
180    }
181    [TestMethod]
182    public void TestHardPalindromeProblem() {
183      var p = new HardPalindromeProblem();
184      Console.WriteLine(p.Grammar);
185
186      Assert.AreEqual(1 + 1, p.Evaluate("a"));
187      Assert.AreEqual(2 + 1, p.Evaluate("aa"));
188      Assert.AreEqual(3 + 1, p.Evaluate("aaa"));
189      Assert.AreEqual(3 + 2, p.Evaluate("aba"));
190      Assert.AreEqual(3 + 2, p.Evaluate("baba"));
191      Assert.AreEqual(3 + 2, p.Evaluate("abab"));
192      Assert.AreEqual(5 + 2, p.Evaluate("babab"));
193      Assert.AreEqual(5 + 3, p.Evaluate("bacab"));
194    }
195
196    [TestMethod]
197    public void TestEvenParityProblem() {
198      var p = new EvenParityProblem();
199      Console.WriteLine(p.Grammar);
200
201      // a | b | c | d | res
202      // 0 | 0 | 0 | 0 | 1
203      // 0 | 0 | 0 | 1 | 0
204      // 0 | 0 | 1 | 0 | 0
205      // 0 | 0 | 1 | 1 | 1
206      // 0 | 1 | 0 | 0 | 0
207      // 0 | 1 | 0 | 1 | 1
208      // 0 | 1 | 1 | 0 | 1
209      // 0 | 1 | 1 | 1 | 0
210      // 1 | 0 | 0 | 0 | 0
211      // 1 | 0 | 0 | 1 | 1
212      // 1 | 0 | 1 | 0 | 1
213      // 1 | 0 | 1 | 1 | 0
214      // 1 | 1 | 0 | 0 | 1
215      // 1 | 1 | 0 | 1 | 0
216      // 1 | 1 | 1 | 0 | 0
217      // 1 | 1 | 1 | 1 | 1
218
219
220      Assert.AreEqual(8, p.Evaluate("a"));
221      Assert.AreEqual(8, p.Evaluate("b"));
222      Assert.AreEqual(8, p.Evaluate("c"));
223      Assert.AreEqual(8, p.Evaluate("d"));
224
225      Assert.AreEqual(8, p.Evaluate("a*b")); // a and b
226      Assert.AreEqual(8, p.Evaluate("a+b")); // a or b
227      Assert.AreEqual(8, p.Evaluate("!a*b+a*!b")); // a xor b
228      Assert.AreEqual(8, p.Evaluate("!(a*b)+(a*!b)")); // a xor b
229      Assert.AreEqual(16, p.Evaluate("a^b^c^d")); // a xor b
230    }
231
232    [TestMethod]
233    public void TestSymbolicRegressionPoly10Problem() {
234      var p = new SymbolicRegressionPoly10Problem();
235      Console.WriteLine(p.Grammar);
236
237      Assert.AreEqual(0.00319925877644673, p.Evaluate("a"), 1.0E-7);
238      Assert.AreEqual(0.00632775454329686, p.Evaluate("b"), 1.0E-7);
239      Assert.AreEqual(0.00569030954291292, p.Evaluate("c"), 1.0E-7);
240      Assert.AreEqual(3.32317092313123E-05, p.Evaluate("d"), 1.0E-7);
241      Assert.AreEqual(0.000562538829174826, p.Evaluate("e"), 1.0E-7);
242      Assert.AreEqual(3.29458942533772E-06, p.Evaluate("f"), 1.0E-7);
243      Assert.AreEqual(0.000193866006166768, p.Evaluate("g"), 1.0E-7);
244      Assert.AreEqual(2.83339004096246E-05, p.Evaluate("h"), 1.0E-7);
245      Assert.AreEqual(0.00291584574914239, p.Evaluate("i"), 1.0E-7);
246      Assert.AreEqual(0.00504038616701691, p.Evaluate("j"), 1.0E-7);
247
248      Assert.AreEqual(0.252718466940018, p.Evaluate("a*b"), 1.0E-7);
249      Assert.AreEqual(0.290635611728845, p.Evaluate("c*d"), 1.0E-7);
250      Assert.AreEqual(0.25737325167716, p.Evaluate("e*f"), 1.0E-7);
251
252      Assert.AreEqual(0.00173739472363473, p.Evaluate("b*c"), 1.0E-7);
253      Assert.AreEqual(3.15450564064128E-05, p.Evaluate("d*e"), 1.0E-7);
254
255      Assert.AreEqual(0.0943358163760454, p.Evaluate("a*g*i"), 1.0E-7);
256      Assert.AreEqual(0.116199534934045, p.Evaluate("c*f*j"), 1.0E-7);
257
258      Assert.AreEqual(0.824522210419616, p.Evaluate("a*b+c*d+e*f"), 1E-7);
259
260
261      Assert.AreEqual(1.0, p.Evaluate("a*b+c*d+e*f+a*g*i+c*f*j"), 1.0E-7);
262    }
263  }
264}
Note: See TracBrowser for help on using the repository browser.