Changeset 10386 for branches/HeuristicLab.Problems.GPDL/CodeGenerator
- Timestamp:
- 01/22/14 19:27:04 (11 years ago)
- Location:
- branches/HeuristicLab.Problems.GPDL/CodeGenerator
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.Problems.GPDL/CodeGenerator/ProblemCodeGen.cs
r10385 r10386 18 18 private const string problemTemplate = @" 19 19 namespace ?PROBLEMNAME? { 20 #region class definitions for tree21 public class Tree {22 public int altIdx;23 public List<Tree> subtrees;24 protected Tree() {25 // leave subtrees uninitialized26 }27 public Tree(int state, int altIdx, int numSubTrees) {28 subtrees = new List<Tree>();29 this.altIdx = altIdx;30 }31 }32 33 ?TERMINALNODECLASSDEFINITIONS?34 #endregion35 36 20 public sealed class ?IDENT?Problem { 37 21 … … 54 38 #endregion 55 39 } 40 public bool IsBetter(double a, double b) { 41 return ?MAXIMIZATION? ? a > b : a < b; 42 } 56 43 57 44 // additional code from the problem definition (CODE section) … … 68 55 #endregion 69 56 } 57 58 #region class definitions for tree 59 public class Tree { 60 public int altIdx; 61 public Tree[] subtrees; 62 protected Tree() { 63 // leave subtrees uninitialized 64 } 65 public Tree(int altIdx, Tree[] subtrees) { 66 this.altIdx = altIdx; 67 this.subtrees = subtrees; 68 } 69 } 70 71 ?TERMINALNODECLASSDEFINITIONS? 72 #endregion 73 74 #region helper class for the grammar representation 75 public class Grammar { 76 public static readonly Dictionary<int, int[]> transition = new Dictionary<int, int[]>() { 77 ?TRANSITIONTABLE? 78 }; 79 public static readonly Dictionary<int, int> subtreeCount = new Dictionary<int, int>() { 80 { -1, 0 }, // terminals 81 ?SUBTREECOUNTTABLE? 82 }; 83 public static readonly string[] symb = new string[] { ?SYMBOLNAMES? }; 84 85 public static Tree CreateTerminalNode(int state, Random random, ?IDENT?Problem problem) { 86 switch(state) { 87 ?CREATETERMINALNODECODE? 88 default: { throw new ArgumentException(""Unknown state index"" + state); } 89 } 90 } 91 } 92 #endregion 70 93 }"; 71 94 … … 97 120 .AppendLine(problemTemplate) 98 121 .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode) 122 .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant()) 99 123 .Replace("?INITSOURCE?", ast.InitCodeNode.SrcCode) 100 124 .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode) … … 102 126 .Replace("?CONSTRAINTSSOURCE?", GenerateConstraintMethods(ast.Terminals)) 103 127 .Replace("?TERMINALNODECLASSDEFINITIONS?", GenerateTerminalNodeClassDefinitions(ast.Terminals.OfType<TerminalNode>())) 128 .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", ")) 129 .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar)) 130 .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar)) 131 .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar)) 104 132 ; 105 133 } … … 190 218 sb.AppendFormat("public {0} GetMax{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMaxExpression).AppendLine(); 191 219 sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine(); 192 //sb.AppendFormat("public {0} Get{1}_{2}(ISolverState _state) {{ _state. }}", fieldType, t.Ident, c.Ident, )193 220 } else if (c.Type == ConstraintNodeType.Set) { 194 221 sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine(); … … 289 316 } 290 317 291 private void GenerateSwitchStatement(IEnumerable<Sequence> alts, SourceBuilder sb) { 318 private void GenerateSwitchStatement(IEnumerable<Sequence> alts, SourceBuilder sb) 319 { 292 320 sb.Append("switch(_t.altIdx) {").BeginBlock(); 293 321 // generate a case for each alternative 294 int i= 0;322 int altIdx = 0; 295 323 foreach (var alt in alts) { 296 sb.AppendFormat("case {0}: {{ ", i).BeginBlock();324 sb.AppendFormat("case {0}: {{ ", altIdx).BeginBlock(); 297 325 298 326 // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols)! … … 302 330 GenerateSourceForAction(0, altSymb, sb); // index is always 0 because of the assertion above 303 331 } 304 i++;332 altIdx++; 305 333 sb.AppendLine("break;").Append("}").EndBlock(); 306 334 } … … 333 361 sb.Append("}").EndBlock(); 334 362 } 363 364 private string GenerateCreateTerminalCode(IGrammar grammar) { 365 Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol)); 366 var sb = new SourceBuilder(); 367 var allSymbols = grammar.Symbols.ToList(); 368 foreach (var s in grammar.Symbols) { 369 if (grammar.IsTerminal(s)) { 370 sb.AppendFormat("case {0}: {{ return new {1}Tree(random, problem); }}", allSymbols.IndexOf(s), s.Name).AppendLine(); 371 } 372 } 373 return sb.ToString(); 374 } 375 376 private string GenerateTransitionTable(IGrammar grammar) { 377 Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol)); 378 var sb = new SourceBuilder(); 379 380 // state idx = idx of the corresponding symbol in the grammar 381 var allSymbols = grammar.Symbols.ToList(); 382 foreach (var s in grammar.Symbols) { 383 var targetStates = new List<int>(); 384 if (grammar.IsTerminal(s)) { 385 } else { 386 if (grammar.NumberOfAlternatives(s) > 1) { 387 foreach (var alt in grammar.GetAlternatives(s)) { 388 // only single-symbol alternatives are supported 389 Debug.Assert(alt.Count() == 1); 390 targetStates.Add(allSymbols.IndexOf(alt.Single())); 391 } 392 } else { 393 // rule is a sequence of symbols 394 var seq = grammar.GetAlternatives(s).Single(); 395 targetStates.AddRange(seq.Select(symb => allSymbols.IndexOf(symb))); 396 } 397 } 398 399 var targetStateString = targetStates.Aggregate(string.Empty, (str, state) => str + state + ", "); 400 401 var idxOfSourceState = allSymbols.IndexOf(s); 402 sb.AppendFormat("// {0}", s).AppendLine(); 403 sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine(); 404 } 405 return sb.ToString(); 406 } 407 private string GenerateSubtreeCountTable(IGrammar grammar) { 408 Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol)); 409 var sb = new SourceBuilder(); 410 411 // state idx = idx of the corresponding symbol in the grammar 412 var allSymbols = grammar.Symbols.ToList(); 413 foreach (var s in grammar.Symbols) { 414 int subtreeCount = 0; 415 if (grammar.IsTerminal(s)) { 416 } else { 417 if (grammar.NumberOfAlternatives(s) > 1) { 418 Debug.Assert(grammar.GetAlternatives(s).All(alt => alt.Count() == 1)); 419 subtreeCount = 1; 420 } else { 421 subtreeCount = grammar.GetAlternative(s, 0).Count(); 422 } 423 } 424 425 sb.AppendFormat("// {0}", s).AppendLine(); 426 sb.AppendFormat("{{ {0} , {1} }},", allSymbols.IndexOf(s), subtreeCount).AppendLine(); 427 } 428 429 return sb.ToString(); 430 } 431 335 432 } 336 433 } -
branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs
r10385 r10386 15 15 private static double terminalProbabilityInc = 0.05; // for each level the probability to sample a terminal grows by 5% 16 16 17 private static Dictionary<int, int[]> transition = new Dictionary<int, int[]>() { 18 ?TRANSITIONTABLE? 19 }; 20 private static Dictionary<int, int> subtreeCount = new Dictionary<int, int>() { 21 { -1, 0 }, // terminals 22 ?SUBTREECOUNTTABLE? 23 }; 24 private static string[] symb = new string[] { ?SYMBOLNAMES? }; 25 26 27 public sealed class SolverState { 28 public int curDepth; 29 public int steps; 30 public int depth; 31 private readonly ?IDENT?Problem problem; 32 private Random random; 33 34 public SolverState(?IDENT?Problem problem, int seed) { 35 this.problem = problem; 36 this.random = new Random(seed); 37 } 38 39 public Tree SampleTree() { 40 return SampleTree(0); 41 } 42 43 private Tree SampleTree(int state) { 44 // Console.Write(state + "" "" ); 45 curDepth += 1; 46 steps += 1; 47 depth = Math.Max(depth, curDepth); 48 Tree t = null; 49 50 // terminals 51 if(subtreeCount[state] == 0) { 52 t = CreateTerminalNode(state); 17 private readonly ?IDENT?Problem problem; 18 private readonly Random random; 19 20 public Tree SampleTree(out int steps, out int depth) { 21 steps = 0; 22 depth = 0; 23 int curDepth = 0; 24 return SampleTree(0, ref steps, ref curDepth, ref depth); 25 } 26 27 private Tree SampleTree(int state, ref int steps, ref int curDepth, ref int depth) { 28 curDepth += 1; 29 steps += 1; 30 depth = Math.Max(depth, curDepth); 31 Tree t = null; 32 33 // terminals 34 if(Grammar.subtreeCount[state] == 0) { 35 t = Grammar.CreateTerminalNode(state, random, problem); 36 } else { 37 // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case) 38 if(Grammar.subtreeCount[state] == 1) { 39 var targetStates = Grammar.transition[state]; 40 var altIdx = SampleAlternative(random, state, curDepth); 41 var alternative = SampleTree(targetStates[altIdx], ref steps, ref curDepth, ref depth); 42 t = new Tree(altIdx, new Tree[] { alternative }); 53 43 } else { 54 55 t = new Tree(state, -1, subtreeCount[state]); 56 if(subtreeCount[state] < 1) throw new ArgumentException(); 57 // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case) 58 if(subtreeCount[state] == 1) { 59 var targetStates = transition[state]; 60 var i = SampleAlternative(random, state); 61 t.altIdx = i; 62 t.subtrees.Add(SampleTree(targetStates[i])); 63 } else { 64 // if the symbol contains only one sequence we must use create sub-trees for each symbol in the sequence 65 for(int i = 0; i < subtreeCount[state]; i++) { 66 t.subtrees.Add(SampleTree(transition[state][i])); 67 } 44 // if the symbol contains only one sequence we must use create sub-trees for each symbol in the sequence 45 Tree[] subtrees = new Tree[Grammar.subtreeCount[state]]; 46 for(int i = 0; i < Grammar.subtreeCount[state]; i++) { 47 subtrees[i] = SampleTree(Grammar.transition[state][i], ref steps, ref curDepth, ref depth); 68 48 } 69 } 70 curDepth -=1; 71 return t; 72 } 73 74 private Tree CreateTerminalNode(int state) { 75 switch(state) { 76 ?CREATETERMINALNODECODE? 77 default: { throw new ArgumentException(""Unknown state index"" + state); } 78 } 79 } 80 81 private int SampleAlternative(Random random, int state) { 82 switch(state) { 49 t = new Tree(-1, subtrees); // alternative index is ignored 50 } 51 } 52 curDepth -=1; 53 return t; 54 } 55 56 private int SampleAlternative(Random random, int state, int depth) { 57 switch(state) { 83 58 84 59 ?SAMPLEALTERNATIVECODE? 85 60 86 default: throw new InvalidOperationException(); 87 } 88 } 89 90 private double TerminalProbForDepth(int depth) { 91 return baseTerminalProbability + depth * terminalProbabilityInc; 92 } 61 default: throw new InvalidOperationException(); 62 } 63 } 64 65 private double TerminalProbForDepth(int depth) { 66 return baseTerminalProbability + depth * terminalProbabilityInc; 93 67 } 94 68 … … 130 104 131 105 132 private readonly ?IDENT?Problem problem;133 106 public ?IDENT?Solver(?IDENT?Problem problem) { 134 107 this.problem = problem; 108 this.random = new Random(); 135 109 } 136 110 137 111 private void Start() { 138 var seedRandom = new Random();139 112 var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity; 140 113 int n = 0; … … 146 119 while (n <= 10000) { 147 120 148 var _state = new SolverState(problem, seedRandom.Next());149 var _t = _state.SampleTree();121 int steps, depth; 122 var _t = SampleTree(out steps, out depth); 150 123 var f = problem.Evaluate(_t); 151 124 152 125 n++; 153 // sumSize += _state.steps;154 // sumDepth += _state.depth;126 sumSize += steps; 127 sumDepth += depth; 155 128 sumF += f; 156 if ( IsBetter(f, bestF)) {129 if (problem.IsBetter(f, bestF)) { 157 130 bestF = f; 158 Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, 0, 0 /* _state.steps, _state.depth */);131 Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, steps, depth); 159 132 } 160 133 if (n % 1000 == 0) { … … 168 141 } 169 142 } 170 171 private bool IsBetter(double a, double b) {172 return ?MAXIMIZATION? ? a > b : a < b;173 }174 143 } 175 144 }"; … … 179 148 solverSourceCode.Append(solverTemplate) 180 149 .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant()) 181 .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", "))182 .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar))183 .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar))184 .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))185 150 .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar)) 186 151 ; … … 190 155 191 156 192 private string GenerateCreateTerminalCode(IGrammar grammar) {193 Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));194 var sb = new SourceBuilder();195 var allSymbols = grammar.Symbols.ToList();196 foreach (var s in grammar.Symbols) {197 if (grammar.IsTerminal(s)) {198 sb.AppendFormat("case {0}: {{ return new {1}Tree(random, problem); }}", allSymbols.IndexOf(s), s.Name).AppendLine();199 }200 }201 return sb.ToString();202 }203 204 private string GenerateTransitionTable(IGrammar grammar) {205 Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));206 var sb = new SourceBuilder();207 208 // state idx = idx of the corresponding symbol in the grammar209 var allSymbols = grammar.Symbols.ToList();210 foreach (var s in grammar.Symbols) {211 var targetStates = new List<int>();212 if (grammar.IsTerminal(s)) {213 } else {214 if (grammar.NumberOfAlternatives(s) > 1) {215 foreach (var alt in grammar.GetAlternatives(s)) {216 // only single-symbol alternatives are supported217 Debug.Assert(alt.Count() == 1);218 targetStates.Add(allSymbols.IndexOf(alt.Single()));219 }220 } else {221 // rule is a sequence of symbols222 var seq = grammar.GetAlternatives(s).Single();223 targetStates.AddRange(seq.Select(symb => allSymbols.IndexOf(symb)));224 }225 }226 227 var targetStateString = targetStates.Aggregate(string.Empty, (str, state) => str + state + ", ");228 229 var idxOfSourceState = allSymbols.IndexOf(s);230 sb.AppendFormat("// {0}", s).AppendLine();231 sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine();232 }233 return sb.ToString();234 }235 private string GenerateSubtreeCountTable(IGrammar grammar) {236 Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));237 var sb = new SourceBuilder();238 239 // state idx = idx of the corresponding symbol in the grammar240 var allSymbols = grammar.Symbols.ToList();241 foreach (var s in grammar.Symbols) {242 int subtreeCount = 0;243 if (grammar.IsTerminal(s)) {244 } else {245 if (grammar.NumberOfAlternatives(s) > 1) {246 Debug.Assert(grammar.GetAlternatives(s).All(alt => alt.Count() == 1));247 subtreeCount = 1;248 } else {249 subtreeCount = grammar.GetAlternative(s, 0).Count();250 }251 }252 253 sb.AppendFormat("// {0}", s).AppendLine();254 sb.AppendFormat("{{ {0} , {1} }},", allSymbols.IndexOf(s), subtreeCount).AppendLine();255 }256 257 return sb.ToString();258 }259 157 260 158 private string GenerateSampleAlternativeSource(IGrammar grammar) {
Note: See TracChangeset
for help on using the changeset viewer.