# source:branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSolvers.cs@11895

Last change on this file since 11895 was 11895, checked in by gkronber, 7 years ago

#2283: constant opt, expressioncompiler, autodiff, fixes in GP solvers

File size: 5.2 KB
Line
1using System;
2using HeuristicLab.Algorithms.GeneticProgramming;
3using HeuristicLab.Algorithms.GrammaticalOptimization;
4using HeuristicLab.Problems.GrammaticalOptimization.SymbReg;
5using Microsoft.VisualStudio.TestTools.UnitTesting;
6
7namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
8  [TestClass]
9  public class TestSolvers {
10    [TestMethod]
11    public void TestExhaustiveBFS() {
12      {
13        // G(A): A -> l | r | m | ?(A)(A) | lA | rA | mA
14        var prob = new SantaFeAntProblem();
15        var comb = 3;
16        TestBFS(prob, 1, comb);
17
18        comb = comb * 3 + 3;
19        TestBFS(prob, 2, comb);
20
21        comb = comb * 3 + 3;
22        TestBFS(prob, 3, comb);
23
24        comb = comb * 3 + 3;
25        TestBFS(prob, 4, comb);
26
27        comb = comb * 3 + 3;
28        TestBFS(prob, 5, comb);
29
30        comb = comb * 3 + 3;
31        TestBFS(prob, 6, comb);
32
33        comb = comb * 3 + 3 + (3 * 3); // additionally for ?(A)(A)
34        TestBFS(prob, 7, comb);
35      }
36      {
37        // G(E):
38        // E -> V | V+E | V-E | V*E | V/E | (E)
39        // V -> a .. j
40        /* grammar has been change ... unit test not yet adapted
41        var prob = new SymbolicRegressionPoly10Problem();
42        var comb = 10;
43        TestDFS(prob, 1, comb);
44        TestDFS(prob, 2, comb);
45
46        comb = comb + 10 * 4 * comb + comb;
47        TestDFS(prob, 3, comb);
48        TestDFS(prob, 4, comb);
49
50        comb = comb + 10 * 4 * comb + 10; // ((E))
51        TestDFS(prob, 5, comb);
52        TestDFS(prob, 6, comb);
53
54        comb = comb + 10 * 4 * comb + 10; // (((E)))  */
55        // takes too long
56        //TestDFS(prob, 7, comb);
57        //TestDFS(prob, 8, comb);
58      }
59    }
60
61    private void TestBFS(IProblem prob, int len, int numExpectedSols) {
62      var solver = new ExhaustiveBreadthFirstSearch(prob, len);
63      int numSols = 0;
64
65      solver.SolutionEvaluated += (s, d) => { numSols++; };
66
67      solver.Run(int.MaxValue);
68      Assert.AreEqual(numExpectedSols, numSols);
69    }
70
71    [TestMethod]
72    public void TestExhaustiveDFS() {
73      {
74        // G(A): A -> l | r | m | ?(A)(A) | lA | rA | mA
75        var prob = new SantaFeAntProblem();
76        var comb = 3;
77        TestDFS(prob, 1, comb);
78
79        comb = comb * 3 + 3;
80        TestDFS(prob, 2, comb);
81
82        comb = comb * 3 + 3;
83        TestDFS(prob, 3, comb);
84
85        comb = comb * 3 + 3;
86        TestDFS(prob, 4, comb);
87
88        comb = comb * 3 + 3;
89        TestDFS(prob, 5, comb);
90
91        comb = comb * 3 + 3;
92        TestDFS(prob, 6, comb);
93
94        comb = comb * 3 + 3 + (3 * 3); // additionally for ?(A)(A)
95        TestDFS(prob, 7, comb);
96      }
97      {
98        // G(E):
99        // E -> V | V+E | V-E | V*E | V/E | (E)
100        // V -> a .. j
101        /* grammar has been change ... unit test not yet adapted
102        var prob = new SymbolicRegressionPoly10Problem();
103        var comb = 10;
104        TestDFS(prob, 1, comb);
105        TestDFS(prob, 2, comb);
106
107        comb = comb + 10 * 4 * comb + comb;
108        TestDFS(prob, 3, comb);
109        TestDFS(prob, 4, comb);
110
111        comb = comb + 10 * 4 * comb + 10; // ((E))
112        TestDFS(prob, 5, comb);
113        TestDFS(prob, 6, comb);
114
115        comb = comb + 10 * 4 * comb + 10; // (((E))) */
116        // takes too long
117        //TestDFS(prob, 7, comb);
118        //TestDFS(prob, 8, comb);
119      }
120    }
121
122    private void TestDFS(IProblem prob, int len, int numExpectedSols) {
123      var solver = new ExhaustiveDepthFirstSearch(prob, len);
124      int numSols = 0;
125
126      solver.SolutionEvaluated += (s, d) => { numSols++; Console.WriteLine(s); };
127
128      solver.Run(int.MaxValue);
129      Assert.AreEqual(numExpectedSols, numSols);
130    }
131
132    [TestMethod]
133    public void TestStandardGP() {
134      var prob = new SymbolicRegressionPoly10Problem();
135      var rand = new Random(31415);
136      var sgp = new StandardGP(prob, rand);
137      sgp.PopulationSize = 10000;
138      sgp.MaxSolutionSize = 50;
139      sgp.MaxSolutionDepth = 20;
140
141      string bestSentence = string.Empty;
142      double bestQuality = double.NegativeInfinity;
143
144      sgp.FoundNewBestSolution += (sentence, quality) => {
145        Assert.Inconclusive(string.Format("{0:N3} {1}", quality, sentence));
146        bestSentence = sentence;
147        bestQuality = quality;
148      };
149
150      sgp.Run(100000);
151
152      Assert.AreEqual(1.0, bestQuality, 1E-6);
153      Assert.AreEqual("", bestSentence);
154    }
155
156    [TestMethod]
157    public void TestOSGP()
158    {
159      const int seed = 31415;
160      var prob = new SymbolicRegressionProblem(new Random(seed), "Tower");
161      var rand = new Random(31415);
162      var osgp = new OffspringSelectionGP(prob, rand);
163      osgp.PopulationSize = 500;
164      osgp.MaxSolutionSize = 100;
165      osgp.MaxSolutionDepth = 20;
166
167      string bestSentence = string.Empty;
168      double bestQuality = double.NegativeInfinity;
169
170      osgp.FoundNewBestSolution += (sentence, quality) => {
171        // Assert.Inconclusive(string.Format("{0:N3} {1}", quality, sentence));
172        bestSentence = sentence;
173        bestQuality = quality;
174      };
175
176      osgp.Run(100000);
177
178      Assert.AreEqual(1.0, bestQuality, 1E-6);
179      Assert.AreEqual("", bestSentence);
180    }
181  }
182}
Note: See TracBrowser for help on using the repository browser.