1 | using System;
|
---|
2 | using System.Collections.Generic;
|
---|
3 | using System.Globalization;
|
---|
4 | using System.Linq;
|
---|
5 | using System.Text;
|
---|
6 | using System.Threading.Tasks;
|
---|
7 | using HeuristicLab.Algorithms.Bandits;
|
---|
8 | using HeuristicLab.Algorithms.Bandits.BanditPolicies;
|
---|
9 | using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
|
---|
10 | using HeuristicLab.Algorithms.Bandits.Models;
|
---|
11 | using HeuristicLab.Algorithms.GrammaticalOptimization;
|
---|
12 | using HeuristicLab.Common;
|
---|
13 | using HeuristicLab.Problems.GrammaticalOptimization.SymbReg;
|
---|
14 | using Microsoft.VisualStudio.TestTools.UnitTesting;
|
---|
15 | using RandomPolicy = HeuristicLab.Algorithms.Bandits.BanditPolicies.RandomPolicy;
|
---|
16 |
|
---|
17 | namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
|
---|
18 | [TestClass]
|
---|
19 | public class TestTunedSettings {
|
---|
20 | private const int randSeed = 31415;
|
---|
21 | internal class Configuration {
|
---|
22 | public IProblem Problem;
|
---|
23 | public int MaxSize;
|
---|
24 | public int RandSeed;
|
---|
25 |
|
---|
26 | public override string ToString() {
|
---|
27 | return string.Format("{0} {1} {2}", RandSeed, Problem, MaxSize);
|
---|
28 | }
|
---|
29 | }
|
---|
30 | [TestMethod]
|
---|
31 | [Timeout(1000 * 60 * 60 * 12)] // 12 hours
|
---|
32 | // this configuration worked especially well in the experiments
|
---|
33 | public void TestAllPoliciesArtificialAnt() {
|
---|
34 | CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
|
---|
35 |
|
---|
36 | var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
|
---|
37 | {
|
---|
38 | (randSeed) => (ISymbolicExpressionTreeProblem)new SantaFeAntProblem(),
|
---|
39 | };
|
---|
40 |
|
---|
41 | var policyFactories = new Func<IBanditPolicy>[]
|
---|
42 | {
|
---|
43 | () => new RandomPolicy(),
|
---|
44 | () => new ActiveLearningPolicy(),
|
---|
45 | () => new EpsGreedyPolicy(0.01, (aInfo)=> aInfo.MaxReward, "max"),
|
---|
46 | () => new EpsGreedyPolicy(0.05, (aInfo)=> aInfo.MaxReward, "max"),
|
---|
47 | () => new EpsGreedyPolicy(0.1, (aInfo)=> aInfo.MaxReward, "max"),
|
---|
48 | () => new EpsGreedyPolicy(0.2, (aInfo)=> aInfo.MaxReward, "max"),
|
---|
49 | //() => new GaussianThompsonSamplingPolicy(),
|
---|
50 | () => new GaussianThompsonSamplingPolicy(true),
|
---|
51 | () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1)),
|
---|
52 | () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1, 1)),
|
---|
53 | //() => new BernoulliThompsonSamplingPolicy(),
|
---|
54 | () => new GenericThompsonSamplingPolicy(new BernoulliModel(1, 1)),
|
---|
55 | () => new EpsGreedyPolicy(0.01),
|
---|
56 | () => new EpsGreedyPolicy(0.05),
|
---|
57 | () => new EpsGreedyPolicy(0.1),
|
---|
58 | () => new EpsGreedyPolicy(0.2),
|
---|
59 | () => new EpsGreedyPolicy(0.5),
|
---|
60 | () => new UCTPolicy(0.01),
|
---|
61 | () => new UCTPolicy(0.05),
|
---|
62 | () => new UCTPolicy(0.1),
|
---|
63 | () => new UCTPolicy(0.5),
|
---|
64 | () => new UCTPolicy(1),
|
---|
65 | () => new UCTPolicy(2),
|
---|
66 | () => new UCTPolicy( 5),
|
---|
67 | () => new UCTPolicy( 10),
|
---|
68 | () => new ModifiedUCTPolicy(0.01),
|
---|
69 | () => new ModifiedUCTPolicy(0.05),
|
---|
70 | () => new ModifiedUCTPolicy(0.1),
|
---|
71 | () => new ModifiedUCTPolicy(0.5),
|
---|
72 | () => new ModifiedUCTPolicy(1),
|
---|
73 | () => new ModifiedUCTPolicy(2),
|
---|
74 | () => new ModifiedUCTPolicy( 5),
|
---|
75 | () => new ModifiedUCTPolicy( 10),
|
---|
76 | () => new UCB1Policy(),
|
---|
77 | () => new UCB1TunedPolicy(),
|
---|
78 | () => new UCBNormalPolicy(),
|
---|
79 | () => new BoltzmannExplorationPolicy(1),
|
---|
80 | () => new BoltzmannExplorationPolicy(10),
|
---|
81 | () => new BoltzmannExplorationPolicy(20),
|
---|
82 | () => new BoltzmannExplorationPolicy(100),
|
---|
83 | () => new BoltzmannExplorationPolicy(200),
|
---|
84 | () => new BoltzmannExplorationPolicy(500),
|
---|
85 | () => new ChernoffIntervalEstimationPolicy( 0.01),
|
---|
86 | () => new ChernoffIntervalEstimationPolicy( 0.05),
|
---|
87 | () => new ChernoffIntervalEstimationPolicy( 0.1),
|
---|
88 | () => new ChernoffIntervalEstimationPolicy( 0.2),
|
---|
89 | () => new ThresholdAscentPolicy(5, 0.01),
|
---|
90 | () => new ThresholdAscentPolicy(5, 0.05),
|
---|
91 | () => new ThresholdAscentPolicy(5, 0.1),
|
---|
92 | () => new ThresholdAscentPolicy(5, 0.2),
|
---|
93 | () => new ThresholdAscentPolicy(10, 0.01),
|
---|
94 | () => new ThresholdAscentPolicy(10, 0.05),
|
---|
95 | () => new ThresholdAscentPolicy(10, 0.1),
|
---|
96 | () => new ThresholdAscentPolicy(10, 0.2),
|
---|
97 | () => new ThresholdAscentPolicy(50, 0.01),
|
---|
98 | () => new ThresholdAscentPolicy(50, 0.05),
|
---|
99 | () => new ThresholdAscentPolicy(50, 0.1),
|
---|
100 | () => new ThresholdAscentPolicy(50, 0.2),
|
---|
101 | () => new ThresholdAscentPolicy(100, 0.01),
|
---|
102 | () => new ThresholdAscentPolicy(100, 0.05),
|
---|
103 | () => new ThresholdAscentPolicy(100, 0.1),
|
---|
104 | () => new ThresholdAscentPolicy(100, 0.2),
|
---|
105 | () => new ThresholdAscentPolicy(500, 0.01),
|
---|
106 | () => new ThresholdAscentPolicy(500, 0.05),
|
---|
107 | () => new ThresholdAscentPolicy(500, 0.1),
|
---|
108 | () => new ThresholdAscentPolicy(500, 0.2),
|
---|
109 | () => new ThresholdAscentPolicy(5000, 0.01),
|
---|
110 | () => new ThresholdAscentPolicy(10000, 0.01),
|
---|
111 | };
|
---|
112 | var maxSizes = new int[] { 17 }; // necessary size for ant programm
|
---|
113 | int nReps = 20;
|
---|
114 | int maxIterations = 100000;
|
---|
115 | foreach (var instanceFactory in instanceFactories) {
|
---|
116 | var sumBestQ = 0.0;
|
---|
117 | var sumItersToBest = 0;
|
---|
118 | double fractionSolved = 0.0;
|
---|
119 | foreach (var conf in GenerateConfigurations(instanceFactory, nReps, maxSizes)) {
|
---|
120 | foreach (var policy in policyFactories) {
|
---|
121 | var prob = conf.Problem;
|
---|
122 | var maxLen = conf.MaxSize;
|
---|
123 | var rand = new Random(conf.RandSeed);
|
---|
124 |
|
---|
125 | var solver = new SequentialSearch(prob, maxLen, rand, 0, new GenericGrammarPolicy(prob, policy(), true));
|
---|
126 | var problemName = prob.GetType().Name;
|
---|
127 | var policyName = policy().ToString();
|
---|
128 | double bestQ; int itersToBest;
|
---|
129 | RunSolver(solver, problemName, policyName, 1.0, maxIterations, maxLen, out bestQ, out itersToBest);
|
---|
130 | sumBestQ += bestQ;
|
---|
131 | sumItersToBest += itersToBest;
|
---|
132 | if (bestQ.IsAlmost(1.0)) fractionSolved += 1.0 / nReps;
|
---|
133 | }
|
---|
134 | }
|
---|
135 | // Assert.AreEqual(0.85, fractionSolved, 1E-6);
|
---|
136 | // Assert.AreEqual(0.99438202247191, sumBestQ / nReps, 1E-6);
|
---|
137 | // Assert.AreEqual(5461.7, sumItersToBest / (double)nReps, 1E-6);
|
---|
138 | }
|
---|
139 | }
|
---|
140 |
|
---|
141 |
|
---|
142 | [TestMethod]
|
---|
143 | [Timeout(1000 * 60 * 60 * 12)] // 12 hours
|
---|
144 | // this configuration worked especially well in the experiments
|
---|
145 | public void TestPoly10WithOutConstantOpt() {
|
---|
146 | CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
|
---|
147 |
|
---|
148 | var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
|
---|
149 | {
|
---|
150 | (randSeed) => (ISymbolicExpressionTreeProblem)new SymbolicRegressionPoly10Problem(),
|
---|
151 | };
|
---|
152 |
|
---|
153 | var maxSizes = new int[] { 23 };
|
---|
154 | int nReps = 20;
|
---|
155 | int maxIterations = 100000;
|
---|
156 | foreach (var instanceFactory in instanceFactories) {
|
---|
157 | var sumBestQ = 0.0;
|
---|
158 | var sumItersToBest = 0;
|
---|
159 | double fractionSolved = 0.0;
|
---|
160 | foreach (var conf in GenerateConfigurations(instanceFactory, nReps, maxSizes)) {
|
---|
161 | var prob = conf.Problem;
|
---|
162 | var maxLen = conf.MaxSize;
|
---|
163 | var rand = new Random(conf.RandSeed);
|
---|
164 |
|
---|
165 | var solver = new SequentialSearch(prob, maxLen, rand, 0,
|
---|
166 | new GenericFunctionApproximationGrammarPolicy(prob, true));
|
---|
167 |
|
---|
168 | var problemName = prob.GetType().Name;
|
---|
169 | double bestQ; int itersToBest;
|
---|
170 | RunSolver(solver, problemName, string.Empty, 1.0, maxIterations, maxLen, out bestQ, out itersToBest);
|
---|
171 | sumBestQ += bestQ;
|
---|
172 | sumItersToBest += itersToBest;
|
---|
173 | if (bestQ.IsAlmost(1.0)) fractionSolved += 1.0 / nReps;
|
---|
174 | }
|
---|
175 | // Assert.AreEqual(0.85, fractionSolved, 1E-6);
|
---|
176 | // Assert.AreEqual(0.99438202247191, sumBestQ / nReps, 1E-6);
|
---|
177 | // Assert.AreEqual(5461.7, sumItersToBest / (double)nReps, 1E-6);
|
---|
178 | }
|
---|
179 | }
|
---|
180 |
|
---|
181 | [TestMethod]
|
---|
182 | [Timeout(1000 * 60 * 60 * 12)] // 12 hours
|
---|
183 | // this configuration worked especially well in the experiments
|
---|
184 | public void TestPoly10WithConstantOpt() {
|
---|
185 | CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
|
---|
186 |
|
---|
187 | var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
|
---|
188 | {
|
---|
189 | (randSeed) => (ISymbolicExpressionTreeProblem)new SymbolicRegressionProblem(new Random(randSeed), "Poly-10", true ),
|
---|
190 | };
|
---|
191 |
|
---|
192 | var maxSizes = new int[] { 23 };
|
---|
193 | int nReps = 20;
|
---|
194 | int maxIterations = 100000;
|
---|
195 | foreach (var instanceFactory in instanceFactories) {
|
---|
196 | var sumBestQ = 0.0;
|
---|
197 | var sumItersToBest = 0;
|
---|
198 | double fractionSolved = 0.0;
|
---|
199 | foreach (var conf in GenerateConfigurations(instanceFactory, nReps, maxSizes)) {
|
---|
200 | var prob = conf.Problem;
|
---|
201 | var maxLen = conf.MaxSize;
|
---|
202 | var rand = new Random(conf.RandSeed);
|
---|
203 |
|
---|
204 | var solver = new SequentialSearch(prob, maxLen, rand, 0,
|
---|
205 | new GenericFunctionApproximationGrammarPolicy(prob, true));
|
---|
206 |
|
---|
207 | var problemName = prob.GetType().Name;
|
---|
208 | double bestQ; int itersToBest;
|
---|
209 | RunSolver(solver, problemName, string.Empty, 1.0, maxIterations, maxLen, out bestQ, out itersToBest);
|
---|
210 | sumBestQ += bestQ;
|
---|
211 | sumItersToBest += itersToBest;
|
---|
212 | if (bestQ.IsAlmost(1.0)) fractionSolved += 1.0 / nReps;
|
---|
213 | }
|
---|
214 | // Assert.AreEqual(0.85, fractionSolved, 1E-6);
|
---|
215 | // Assert.AreEqual(0.99438202247191, sumBestQ / nReps, 1E-6);
|
---|
216 | // Assert.AreEqual(5461.7, sumItersToBest / (double)nReps, 1E-6);
|
---|
217 | }
|
---|
218 | }
|
---|
219 |
|
---|
220 | private IEnumerable<Configuration> GenerateConfigurations(Func<int, ISymbolicExpressionTreeProblem> problemFactory,
|
---|
221 | int nReps,
|
---|
222 | IEnumerable<int> maxSizes
|
---|
223 | ) {
|
---|
224 | var seedRand = new Random(randSeed);
|
---|
225 | // the problem seed is the same for all configuratons
|
---|
226 | // this guarantees that we solve the _same_ problem each time
|
---|
227 | // with different solvers and multiple repetitions
|
---|
228 | var problemSeed = randSeed;
|
---|
229 | for (int i = 0; i < nReps; i++) {
|
---|
230 | // in each repetition use the same random seed for all solver configuratons
|
---|
231 | // do nReps with different seeds for each configuration
|
---|
232 | var solverSeed = seedRand.Next();
|
---|
233 | foreach (var maxSize in maxSizes) {
|
---|
234 | yield return new Configuration {
|
---|
235 | MaxSize = maxSize,
|
---|
236 | Problem = problemFactory(problemSeed),
|
---|
237 | RandSeed = solverSeed
|
---|
238 | };
|
---|
239 | }
|
---|
240 | }
|
---|
241 | }
|
---|
242 |
|
---|
243 |
|
---|
244 |
|
---|
245 |
|
---|
246 | private static void RunSolver(ISolver solver, string problemName, string policyName, double bestKnownQuality, int maxIters, int maxSize,
|
---|
247 | out double bestQ, out int itersToBest) {
|
---|
248 | int iterations = 0;
|
---|
249 | var globalStatistics = new SentenceSetStatistics(bestKnownQuality);
|
---|
250 | var solverName = solver.GetType().Name;
|
---|
251 | double bestQuality = double.NegativeInfinity;
|
---|
252 | int iterationsToBest = -1;
|
---|
253 | solver.SolutionEvaluated += (sentence, quality) => {
|
---|
254 | iterations++;
|
---|
255 | globalStatistics.AddSentence(sentence, quality);
|
---|
256 | if (quality > bestQuality) {
|
---|
257 | bestQuality = quality;
|
---|
258 | iterationsToBest = iterations;
|
---|
259 | }
|
---|
260 | if (iterations % 1000 == 0) {
|
---|
261 | Console.WriteLine("\"{0,25}\" \"{1,25}\" {2} \"{3,25}\" {4}", solverName, policyName, maxSize, problemName, globalStatistics);
|
---|
262 | }
|
---|
263 | };
|
---|
264 |
|
---|
265 |
|
---|
266 | solver.Run(maxIters);
|
---|
267 |
|
---|
268 | bestQ = bestQuality;
|
---|
269 | itersToBest = iterationsToBest;
|
---|
270 | }
|
---|
271 | }
|
---|
272 | }
|
---|