Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Test/RunMctsExperiments.cs @ 12391

Last change on this file since 12391 was 12391, checked in by gkronber, 10 years ago

#2283: added shuffling of terminal symbols to the royal pair problem to make sure that there is no bias from order of terminal symbols.

File size: 13.4 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Globalization;
4using HeuristicLab.Algorithms.Bandits;
5using HeuristicLab.Algorithms.Bandits.BanditPolicies;
6using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
7using HeuristicLab.Algorithms.Bandits.Models;
8using HeuristicLab.Algorithms.GrammaticalOptimization;
9using Microsoft.VisualStudio.TestTools.UnitTesting;
10using RandomPolicy = HeuristicLab.Algorithms.Bandits.BanditPolicies.RandomPolicy;
11
12namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
13
14  [TestClass]
15  public class RunMctsExperiments {
16    private readonly static int randSeed = 31415;
17
18    internal class Configuration {
19      public ISymbolicExpressionTreeProblem Problem;
20      public IBanditPolicy Policy;
21      public int MaxSize;
22      public int RandSeed;
23
24      public override string ToString() {
25        return string.Format("{0} {1} {2} {3}", RandSeed, Problem, Policy, MaxSize);
26      }
27    }
28
29    private Func<IBanditPolicy>[] policyFactories = new Func<IBanditPolicy>[]
30    {
31          () => new RandomPolicy(),
32          () => new ActiveLearningPolicy(), 
33         () => new GaussianThompsonSamplingPolicy(true),
34         () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1)),
35         () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1, 1)),
36         () => new GenericThompsonSamplingPolicy(new BernoulliModel(1, 1)),
37         () => new EpsGreedyPolicy(0.01),
38         () => new EpsGreedyPolicy(0.05),
39         () => new EpsGreedyPolicy(0.1),
40         () => new EpsGreedyPolicy(0.2),
41         () => new EpsGreedyPolicy(0.5),
42         () => new UCTPolicy(0.01),
43         () => new UCTPolicy(0.05),
44         () => new UCTPolicy(0.1),
45         () => new UCTPolicy(0.5),
46         () => new UCTPolicy(1),
47         () => new UCTPolicy(2),
48         () => new UCTPolicy( 5),
49         () => new UCTPolicy( 10),
50         () => new ModifiedUCTPolicy(0.01),
51         () => new ModifiedUCTPolicy(0.05),
52         () => new ModifiedUCTPolicy(0.1),
53         () => new ModifiedUCTPolicy(0.5),
54         () => new ModifiedUCTPolicy(1),
55         () => new ModifiedUCTPolicy(2),
56         () => new ModifiedUCTPolicy( 5),
57         () => new ModifiedUCTPolicy( 10),
58         () => new UCB1Policy(),
59         () => new UCB1TunedPolicy(),
60         () => new UCBNormalPolicy(),
61         () => new BoltzmannExplorationPolicy(1),
62         () => new BoltzmannExplorationPolicy(10),
63         () => new BoltzmannExplorationPolicy(20),
64         () => new BoltzmannExplorationPolicy(100),
65         () => new BoltzmannExplorationPolicy(200),
66         () => new BoltzmannExplorationPolicy(500),
67          () => new ChernoffIntervalEstimationPolicy( 0.01),
68          () => new ChernoffIntervalEstimationPolicy( 0.05),
69          () => new ChernoffIntervalEstimationPolicy( 0.1),
70          () => new ChernoffIntervalEstimationPolicy( 0.2),
71         () => new ThresholdAscentPolicy(5, 0.01),
72         () => new ThresholdAscentPolicy(5, 0.05),
73         () => new ThresholdAscentPolicy(5, 0.1),
74         () => new ThresholdAscentPolicy(5, 0.2),
75         () => new ThresholdAscentPolicy(10, 0.01),
76         () => new ThresholdAscentPolicy(10, 0.05),
77         () => new ThresholdAscentPolicy(10, 0.1),
78         () => new ThresholdAscentPolicy(10, 0.2),
79         () => new ThresholdAscentPolicy(50, 0.01),
80         () => new ThresholdAscentPolicy(50, 0.05),
81         () => new ThresholdAscentPolicy(50, 0.1),
82         () => new ThresholdAscentPolicy(50, 0.2),
83         () => new ThresholdAscentPolicy(100, 0.01),
84         () => new ThresholdAscentPolicy(100, 0.05),
85         () => new ThresholdAscentPolicy(100, 0.1),
86         () => new ThresholdAscentPolicy(100, 0.2),
87         () => new ThresholdAscentPolicy(500, 0.01),
88         () => new ThresholdAscentPolicy(500, 0.05),
89         () => new ThresholdAscentPolicy(500, 0.1),
90         () => new ThresholdAscentPolicy(500, 0.2),
91         () => new ThresholdAscentPolicy(5000, 0.01),
92         () => new ThresholdAscentPolicy(10000, 0.01), 
93    };
94
95    #region artificial ant
96    [TestMethod]
97    [Timeout(1000 * 60 * 60 * 72)] // 72 hours
98    public void RunMctsArtificialAntProblem() {
99      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
100
101      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
102      {
103        (randSeed) => (ISymbolicExpressionTreeProblem) new SantaFeAntProblem(),
104      };
105
106      var maxSizes = new int[] { 17 }; // size of sequential representation is 17
107      int nReps = 30;
108      int maxIterations = 100000; // randomsearch finds the optimum almost always for 100000 evals
109      foreach (var instanceFactory in instanceFactories) {
110        foreach (var policyFactory in policyFactories) {
111          foreach (var conf in GenerateConfigurations(instanceFactory, policyFactory, nReps, maxSizes)) {
112            RunMctsForProblem(conf.RandSeed, conf.Problem, conf.Policy, maxIterations, conf.MaxSize);
113          }
114        }
115      }
116    }
117
118    #endregion
119
120    #region symb-reg-poly-10
121    [TestMethod]
122    [Timeout(1000 * 60 * 60 * 120)] // 120 hours
123    public void RunMctsPoly10Problem() {
124      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
125
126      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
127      {
128        (randSeed) => (ISymbolicExpressionTreeProblem) new SymbolicRegressionPoly10Problem(),
129      };
130
131      var maxSizes = new int[] { 23 }; // size of sequential representation is 23
132      int nReps = 30;
133      int maxIterations = 100000; // sequentialsearch should find the optimum within 100000 evals
134      foreach (var instanceFactory in instanceFactories) {
135        foreach (var policyFactory in policyFactories) {
136          foreach (var conf in GenerateConfigurations(instanceFactory, policyFactory, nReps, maxSizes)) {
137            RunMctsForProblem(conf.RandSeed, conf.Problem, conf.Policy, maxIterations, conf.MaxSize);
138          }
139        }
140      }
141    }
142    #endregion
143
144    #region hardpalindrome
145    [TestMethod]
146    [Timeout(1000 * 60 * 60 * 120)] // 120 hours
147    public void RunMctsPalindromeProblem() {
148      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
149
150      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
151      {
152        (randSeed) => (ISymbolicExpressionTreeProblem) new HardPalindromeProblem(),
153      };
154
155      var maxSizes = new int[] { 10, 20, 30, 40, 50 };
156      int nReps = 30;
157      int maxIterations = 30000;
158      foreach (var instanceFactory in instanceFactories) {
159        foreach (var policyFactory in policyFactories) {
160          foreach (var conf in GenerateConfigurations(instanceFactory, policyFactory, nReps, maxSizes)) {
161            RunMctsForProblem(conf.RandSeed, conf.Problem, conf.Policy, maxIterations, conf.MaxSize);
162          }
163        }
164      }
165    }
166    #endregion
167
168    #region royalpair
169    [TestMethod]
170    [Timeout(1000 * 60 * 60 * 120)] // 120 hours
171    public void RunMctsRoyalPairProblem() {
172      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
173
174      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
175      {
176        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalPairProblem(2),
177        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalPairProblem(4),
178        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalPairProblem(8),
179        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalPairProblem(16),
180      };
181
182      var maxSizes = new int[] { /*10, 20, 30, 40,*/ 25, 50 };
183      int nReps = 30;
184      int maxIterations = 20000;
185      foreach (var instanceFactory in instanceFactories) {
186        foreach (var policyFactory in policyFactories) {
187          foreach (var conf in GenerateConfigurations(instanceFactory, policyFactory, nReps, maxSizes)) {
188            RunMctsForProblem(conf.RandSeed, conf.Problem, conf.Policy, maxIterations, conf.MaxSize);
189          }
190        }
191      }
192    }
193    #endregion
194
195    #region royalseq
196    [TestMethod]
197    [Timeout(1000 * 60 * 60 * 120)] // 120 hours
198    public void RunMctsRoyalSequenceProblem() {
199      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
200
201      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
202      {
203        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalSequenceProblem(new Random(randSeed), 3, 50),
204        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalSequenceProblem(new Random(randSeed), 5, 50),
205        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalSequenceProblem(new Random(randSeed), 10, 50),
206        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalSequenceProblem(new Random(randSeed), 20, 50),
207      };
208
209      var maxSizes = new int[] { 10, 20, 30, 40, 50 };
210      int nReps = 30;
211      int maxIterations = 30000;
212      foreach (var instanceFactory in instanceFactories) {
213        foreach (var policyFactory in policyFactories) {
214          foreach (var conf in GenerateConfigurations(instanceFactory, policyFactory, nReps, maxSizes)) {
215            RunMctsForProblem(conf.RandSeed, conf.Problem, conf.Policy, maxIterations, conf.MaxSize);
216          }
217        }
218      }
219    }
220    #endregion
221
222    #region royaltree
223    [TestMethod]
224    [Timeout(1000 * 60 * 60 * 120)] // 120 hours
225    public void RunMctsRoyalTreeProblem() {
226      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
227
228      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
229      {
230        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalTreeProblem(3),
231        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalTreeProblem(4),
232        // (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalTreeProblem(5),
233        // (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalTreeProblem(6),
234      };
235
236      var maxSizes = new int[] { 30, 100, 200 };
237      int nReps = 30;
238      int maxIterations = 30000;
239      foreach (var instanceFactory in instanceFactories) {
240        foreach (var policyFactory in policyFactories) {
241          foreach (var conf in GenerateConfigurations(instanceFactory, policyFactory, nReps, maxSizes)) {
242            RunMctsForProblem(conf.RandSeed, conf.Problem, conf.Policy, maxIterations, conf.MaxSize);
243          }
244        }
245      }
246    }
247    #endregion
248
249    #region findphrases
250    [TestMethod]
251    [Timeout(1000 * 60 * 60 * 120)] // 120 hours
252    public void RunMctsFindPhrasesProblem() {
253      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
254
255      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
256      {
257        (randSeed) => (ISymbolicExpressionTreeProblem) new FindPhrasesProblem(new Random(randSeed), 10, 10, 3, 10, 0, 1.0, 0.0, true),
258      };
259
260      var maxSizes = new int[] { 9, 12, 15, 21, 30 };
261      int nReps = 30;
262      int maxIterations = 30000;
263      foreach (var instanceFactory in instanceFactories) {
264        foreach (var policyFactory in policyFactories) {
265          foreach (var conf in GenerateConfigurations(instanceFactory, policyFactory, nReps, maxSizes)) {
266            RunMctsForProblem(conf.RandSeed, conf.Problem, conf.Policy, maxIterations, conf.MaxSize);
267          }
268        }
269      }
270    }
271    #endregion
272   
273    #region helpers
274    private IEnumerable<Configuration> GenerateConfigurations(
275      Func<int, ISymbolicExpressionTreeProblem> problemFactory,
276      Func<IBanditPolicy> policyFactory,
277      int nReps,
278      IEnumerable<int> maxSizes
279      ) {
280      var seedRand = new Random(randSeed);
281      // the problem seed is the same for all configuratons
282      // this guarantees that we solve the _same_ problem each time
283      // with different solvers and multiple repetitions
284      var problemSeed = randSeed;
285      for (int i = 0; i < nReps; i++) {
286        // in each repetition use the same random seed for all solver configuratons
287        // do nReps with different seeds for each configuration
288        var solverSeed = seedRand.Next();
289        foreach (var maxSize in maxSizes) {
290          yield return new Configuration {
291            MaxSize = maxSize,
292            Problem = problemFactory(problemSeed),
293            Policy = policyFactory(),
294            RandSeed = solverSeed
295          };
296        }
297      }
298    }
299
300    private static void RunMctsForProblem(
301      int randSeed,
302      IProblem problem,
303      IBanditPolicy policy,
304      int maxIters,
305      int maxSize
306      ) {
307      var solver = new SequentialSearch(problem, maxSize, new Random(randSeed), 0,
308        new GenericGrammarPolicy(problem, policy, false));
309      var problemName = problem.Name;
310      RunSolver(solver, problemName, policy.ToString(), maxIters, maxSize);
311    }
312
313    private static void RunSolver(ISolver solver, string problemName, string policyName, int maxIters, int maxSize) {
314      int iterations = 0;
315      var globalStatistics = new SentenceSetStatistics(1.0);
316      var solverName = solver.GetType().Name;
317      solver.SolutionEvaluated += (sentence, quality) => {
318        iterations++;
319        globalStatistics.AddSentence(sentence, quality);
320
321        if (iterations % 1000 == 0) {
322          Console.WriteLine("\"{0,25}\" {1} \"{2,25}\" \"{3}\" {4}", solverName, maxSize, problemName, policyName, globalStatistics);
323        }
324      };
325
326      solver.Run(maxIters);
327    }
328    #endregion
329  }
330}
Note: See TracBrowser for help on using the repository browser.