Free cookie consent management tool by TermsFeed Policy Generator

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

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

optimal artificial ant solutions
File size: 11.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      // all possible minimal solutions to the artificial ant problem
146      Assert.AreEqual(89, p.Evaluate("?(m)(ll?(m)(r))mr"));
147      Assert.AreEqual(89, p.Evaluate("?(m)(rr?(m)(l))ml"));
148      Assert.AreEqual(89, p.Evaluate("r?(m)(ll?(m)(r))m"));
149      Assert.AreEqual(89, p.Evaluate("l?(m)(rr?(m)(l))m"));
150      Assert.AreEqual(89, p.Evaluate("mr?(m)(ll?(m)(r))"));
151      Assert.AreEqual(89, p.Evaluate("ml?(m)(rr?(m)(l))"));
152      Assert.AreEqual(89, p.Evaluate("?(m)(ll?(m)(l))ml"));
153      Assert.AreEqual(89, p.Evaluate("?(m)(rr?(m)(r))mr"));
154      Assert.AreEqual(89, p.Evaluate("l?(m)(ll?(m)(l))m"));
155      Assert.AreEqual(89, p.Evaluate("r?(m)(rr?(m)(r))m"));
156      Assert.AreEqual(89, p.Evaluate("ml?(m)(ll?(m)(l))"));
157      Assert.AreEqual(89, p.Evaluate("mr?(m)(rr?(m)(r))"));
158    }
159
160    [TestMethod]
161    public void TestRoyalRoadProblem() {
162      var p = new RoyalRoadProblem();
163      Console.WriteLine(p.Grammar);
164
165    }
166    [TestMethod]
167    public void TestPalindromeProblem() {
168      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("aba"));
169      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("aaba"));
170      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("abaa"));
171      Assert.AreEqual("aabaa", PalindromeProblem.LongestPalindromicSubstring("aaaabaa"));
172      Assert.AreEqual("aabaa", PalindromeProblem.LongestPalindromicSubstring("aabaaaa"));
173      Assert.AreEqual("baaaab", PalindromeProblem.LongestPalindromicSubstring("aabaaaab"));
174
175
176      var p = new PalindromeProblem();
177      Console.WriteLine(p.Grammar);
178
179      Assert.AreEqual(1, p.Evaluate("a"));
180      Assert.AreEqual(2, p.Evaluate("aa"));
181      Assert.AreEqual(3, p.Evaluate("aaa"));
182      Assert.AreEqual(3, p.Evaluate("aba"));
183      Assert.AreEqual(3, p.Evaluate("baba"));
184      Assert.AreEqual(3, p.Evaluate("abab"));
185      Assert.AreEqual(5, p.Evaluate("babab"));
186    }
187    [TestMethod]
188    public void TestHardPalindromeProblem() {
189      var p = new HardPalindromeProblem();
190      Console.WriteLine(p.Grammar);
191
192      Assert.AreEqual(1 + 1, p.Evaluate("a"));
193      Assert.AreEqual(2 + 1, p.Evaluate("aa"));
194      Assert.AreEqual(3 + 1, p.Evaluate("aaa"));
195      Assert.AreEqual(3 + 2, p.Evaluate("aba"));
196      Assert.AreEqual(3 + 2, p.Evaluate("baba"));
197      Assert.AreEqual(3 + 2, p.Evaluate("abab"));
198      Assert.AreEqual(5 + 2, p.Evaluate("babab"));
199      Assert.AreEqual(5 + 3, p.Evaluate("bacab"));
200    }
201
202    [TestMethod]
203    public void TestEvenParityProblem() {
204      var p = new EvenParityProblem();
205      Console.WriteLine(p.Grammar);
206
207      // a | b | c | d | res
208      // 0 | 0 | 0 | 0 | 1
209      // 0 | 0 | 0 | 1 | 0
210      // 0 | 0 | 1 | 0 | 0
211      // 0 | 0 | 1 | 1 | 1
212      // 0 | 1 | 0 | 0 | 0
213      // 0 | 1 | 0 | 1 | 1
214      // 0 | 1 | 1 | 0 | 1
215      // 0 | 1 | 1 | 1 | 0
216      // 1 | 0 | 0 | 0 | 0
217      // 1 | 0 | 0 | 1 | 1
218      // 1 | 0 | 1 | 0 | 1
219      // 1 | 0 | 1 | 1 | 0
220      // 1 | 1 | 0 | 0 | 1
221      // 1 | 1 | 0 | 1 | 0
222      // 1 | 1 | 1 | 0 | 0
223      // 1 | 1 | 1 | 1 | 1
224
225
226      Assert.AreEqual(8, p.Evaluate("a"));
227      Assert.AreEqual(8, p.Evaluate("b"));
228      Assert.AreEqual(8, p.Evaluate("c"));
229      Assert.AreEqual(8, p.Evaluate("d"));
230
231      Assert.AreEqual(8, p.Evaluate("a*b")); // a and b
232      Assert.AreEqual(8, p.Evaluate("a+b")); // a or b
233      Assert.AreEqual(8, p.Evaluate("!a*b+a*!b")); // a xor b
234      Assert.AreEqual(8, p.Evaluate("!(a*b)+(a*!b)")); // a xor b
235      Assert.AreEqual(16, p.Evaluate("a^b^c^d")); // a xor b
236    }
237
238    [TestMethod]
239    public void TestSymbolicRegressionPoly10Problem() {
240      var p = new SymbolicRegressionPoly10Problem();
241      Console.WriteLine(p.Grammar);
242
243      Assert.AreEqual(0.00319925877644673, p.Evaluate("a"), 1.0E-7);
244      Assert.AreEqual(0.00632775454329686, p.Evaluate("b"), 1.0E-7);
245      Assert.AreEqual(0.00569030954291292, p.Evaluate("c"), 1.0E-7);
246      Assert.AreEqual(3.32317092313123E-05, p.Evaluate("d"), 1.0E-7);
247      Assert.AreEqual(0.000562538829174826, p.Evaluate("e"), 1.0E-7);
248      Assert.AreEqual(3.29458942533772E-06, p.Evaluate("f"), 1.0E-7);
249      Assert.AreEqual(0.000193866006166768, p.Evaluate("g"), 1.0E-7);
250      Assert.AreEqual(2.83339004096246E-05, p.Evaluate("h"), 1.0E-7);
251      Assert.AreEqual(0.00291584574914239, p.Evaluate("i"), 1.0E-7);
252      Assert.AreEqual(0.00504038616701691, p.Evaluate("j"), 1.0E-7);
253
254      Assert.AreEqual(0.252718466940018, p.Evaluate("a*b"), 1.0E-7);
255      Assert.AreEqual(0.290635611728845, p.Evaluate("c*d"), 1.0E-7);
256      Assert.AreEqual(0.25737325167716, p.Evaluate("e*f"), 1.0E-7);
257
258      Assert.AreEqual(0.00173739472363473, p.Evaluate("b*c"), 1.0E-7);
259      Assert.AreEqual(3.15450564064128E-05, p.Evaluate("d*e"), 1.0E-7);
260
261      Assert.AreEqual(0.0943358163760454, p.Evaluate("a*g*i"), 1.0E-7);
262      Assert.AreEqual(0.116199534934045, p.Evaluate("c*f*j"), 1.0E-7);
263
264      Assert.AreEqual(0.824522210419616, p.Evaluate("a*b+c*d+e*f"), 1E-7);
265
266
267      Assert.AreEqual(1.0, p.Evaluate("a*b+c*d+e*f+a*g*i+c*f*j"), 1.0E-7);
268    }
269
270    [TestMethod]
271    public void TestRoyalTreeProblem() {
272      var p = new RoyalTreeProblem(7);
273      Console.WriteLine(p.Grammar);
274
275      // examples from The Royal Tree Problem, a Benchmark for Single and Multi-population Genetic Programming (Punch, Zongker, Goodman)
276      Assert.AreEqual(4, p.Evaluate("ax"), 1.0E-7);
277      Assert.AreEqual(384.0, p.Evaluate("cbaxaxbaxaxbaxax"), 1.0E-7);
278      Assert.AreEqual(128.66, p.Evaluate("cbaxaxbaxaxbxx"), 1.0E-7);
279      Assert.AreEqual(64.66, p.Evaluate("cbaxaxxx"), 1.0E-7);
280
281    }
282  }
283}
Note: See TracBrowser for help on using the repository browser.