1 | using System;
|
---|
2 | using System.Collections.Generic;
|
---|
3 | using System.Globalization;
|
---|
4 | using HeuristicLab.Algorithms.Bandits;
|
---|
5 | using HeuristicLab.Algorithms.Bandits.BanditPolicies;
|
---|
6 | using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
|
---|
7 | using HeuristicLab.Algorithms.Bandits.Models;
|
---|
8 | using HeuristicLab.Algorithms.GrammaticalOptimization;
|
---|
9 | using Microsoft.VisualStudio.TestTools.UnitTesting;
|
---|
10 | using RandomPolicy = HeuristicLab.Algorithms.Bandits.BanditPolicies.RandomPolicy;
|
---|
11 |
|
---|
12 | namespace 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 | }
|
---|