- Timestamp:
- 10/20/13 21:31:41 (11 years ago)
- Location:
- branches/HeuristicLab.Problems.GPDL
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs
r10067 r10074 20 20 private string solverTemplate = @" 21 21 namespace ?PROBLEMNAME? { 22 internal static class Grammar {23 ?GRAMMARCLASSCODE?24 }25 internal sealed class PartiallyProcessedSeq {26 private IEnumerable<string> remaining;27 private IEnumerable<int> path;28 public PartiallyProcessedSeq(IEnumerable<string> remaining) : this (Enumerable.Empty<int>(), remaining) {29 }30 public PartiallyProcessedSeq(IEnumerable<int> path, IEnumerable<string> remaining) {31 this.path = path;32 this.remaining = remaining;33 }34 35 public bool MoveNext() {36 if(!remaining.Any()) return false;37 else remaining = remaining.Skip(1);38 return true;39 }40 41 public string Current {42 get {43 return remaining.FirstOrDefault();44 }45 }46 public IEnumerable<int> Path {47 get {48 return path;49 }50 }51 public IEnumerable<string> Remaining {52 get {53 return remaining;54 }55 }56 public override string ToString() {57 return path.Aggregate("""", (str, p) => str + "" "" + p) + "" >> "" +58 remaining.Aggregate("""", (str, r) => str + "" "" + r);59 }60 61 }62 22 public sealed class ?IDENT?Solver { 63 23 … … 79 39 } 80 40 81 #region path generator (BFS in the grammar to generate solutions) 82 ?PATHGENERATORCODE? 83 #endregion 84 85 private IEnumerable<IEnumerable<int>> GeneratePaths() { 86 var queue = new Queue<PartiallyProcessedSeq>(); 87 queue.Enqueue(new PartiallyProcessedSeq(new string[] { Grammar.RootSymbol })); 88 89 while (queue.Count > 0) { 90 var e = queue.Dequeue(); 91 var symb = e.Current; // the next symbol to generate paths for 92 // Console.WriteLine(""Out: "" + e); 93 94 var lastSymbol = !e.MoveNext(); 95 96 if (Grammar.IsTerminal(symb)) { 97 // generate all paths for the terminal 98 if (lastSymbol) { 99 var pathsForSymb = GeneratePathsFor(symb); 100 if (pathsForSymb.Any()) { 101 foreach (var path in GeneratePathsFor(symb)) { 102 yield return e.Path.Concat(path); 103 } 104 } else { 105 yield return e.Path; 106 } 107 } else { 108 var paths = GeneratePathsFor(symb); 109 if(!paths.Any() || paths.Count() == 1) { 110 yield return e.Path; 111 } else { 112 foreach (var path in paths) { 113 var eAlt = new PartiallyProcessedSeq(e.Path.Concat(path), e.Remaining); 114 queue.Enqueue(eAlt); 115 // Console.WriteLine(""In: "" + eAlt); 116 } 117 } 118 } 41 private class SearchTree { 42 private SearchTree[] subTrees; 43 public bool Done { get; private set; } 44 private int nextAlternative; 45 46 public SearchTree() { 47 Done = false; 48 } 49 50 public SearchTree GetSubtree(int i) { 51 // if (subTrees[i] == null) subTrees[i] = new SearchTree(); 52 return subTrees[i]; 53 } 54 55 public int GetNextAlternative() { 56 System.Diagnostics.Debug.Assert(IsAlternativeNode); 57 return nextAlternative; 58 } 59 60 public bool IsUninitialized { 61 get { return subTrees == null; } 62 } 63 64 public void SetNumberOfSubtrees(int n) { 65 this.subTrees = new SearchTree[n]; 66 for(int i=0;i<n;i++) this.subTrees[i] = new SearchTree(); 67 nextAlternative = 0; 68 } 69 70 public void UpdatePath() { 71 System.Diagnostics.Debug.Assert(!Done); 72 if (IsUninitialized) { return; } 73 Count++; 74 if (subTrees.Length == 0) { 75 Done = true; 76 } 77 if (IsAlternativeNode) { 78 // update only the active alternative and calculate a new alternative 79 subTrees[nextAlternative].UpdatePath(); 80 81 do { 82 nextAlternative = (nextAlternative + 1) % subTrees.Length; 83 } while (subTrees[nextAlternative] != null && subTrees[nextAlternative].Done); 84 85 // from the nodes which are not done take the first with minimum count 86 //nextAlternative = (from i in Enumerable.Range(0, subTrees.Length) 87 // where subTrees[i] == null || !subTrees[i].Done 88 // orderby subTrees[i]==null?0:subTrees[i].Count ascending 89 // select i).FirstOrDefault(); // possibly there are no children left that can be tried 119 90 } else { 120 // non-terminal -> generate alternatives if necessary 121 var alts = Grammar.GetAlternatives(symb); 122 if (alts.Count() == 1) { 123 var eAlt = new PartiallyProcessedSeq(e.Path, alts.Single().Concat(e.Remaining)); 124 queue.Enqueue(eAlt); 125 // Console.WriteLine(""In: "" + eAlt); 126 } else { 127 int i = 0; 128 foreach (var alt in alts) { 129 var eAlt = new PartiallyProcessedSeq(e.Path.Concat(new int[] { i++ }), alt.Concat(e.Remaining)); 130 queue.Enqueue(eAlt); 131 // Console.WriteLine(""In: "" + eAlt); 132 } 133 } 134 } 135 } 136 } 137 91 // for sequenceNodes update all sub-trees 92 foreach (var t in subTrees) t.UpdatePath(); 93 } 94 // set node to done if all nodes are non-null and done 95 this.Done = true; 96 foreach(var t in subTrees) { 97 if(t == null || !t.Done) 98 { this.Done = false; break; } 99 } 100 } 101 102 public bool IsAlternativeNode { get; set; } 103 public bool IsSequenceNode { get; set; } 104 public int Count { get; private set; } 105 } 106 107 private SearchTree tree; 138 108 private void Start() { 139 // generate possible paths through the grammar and evaluate each of them 109 // start with empty tree 110 tree = new SearchTree(); 140 111 var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity; 141 112 int n = 0; 142 foreach(var path in GeneratePaths()) { 143 var length = path.Count(); 144 currentPath = path; 113 var sw = new System.Diagnostics.Stopwatch(); 114 sw.Start(); 115 while (!tree.Done) { 116 145 117 var f = Calculate(); 118 // do one more run through the tree to update the path 119 tree.UpdatePath(); 120 146 121 n++; 147 if(IsBetter(f, bestF)) bestF = f; 148 if (n%1000 == 0) Console.WriteLine(""{0}\t{1}\t{2}\t{3}"",n, length, bestF, f); 149 } 150 } 151 152 private IEnumerable<int> currentPath; 122 if (IsBetter(f, bestF)) bestF = f; 123 if (n % 100 == 0) { 124 sw.Stop(); 125 Console.WriteLine(""{0}\t{1}\t{2}\t({3:0.00} sols/ms)"", n, bestF, f, 100.0 / sw.ElapsedMilliseconds); 126 sw.Reset(); 127 sw.Start(); 128 } 129 } 130 } 153 131 154 132 public double Calculate() { … … 188 166 solverTemplate 189 167 .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant()) 190 .Replace("?GRAMMARCLASSCODE?", GenerateGrammarClassCode(grammar))191 168 .Replace("?IDENT?", ast.Name) 192 169 .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode) … … 195 172 .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode) 196 173 .Replace("?CONSTRAINTSSOURCE?", GenerateConstraintMethods(ast.Terminals)) 197 .Replace("?PATHGENERATORCODE?", GeneratePathGeneratorCode(ast))198 174 ; 199 175 … … 248 224 } 249 225 250 251 private string GenerateGrammarClassCode(IGrammar grammar) {252 var sb = new StringBuilder();253 // RootSymbol254 sb.AppendFormat("public static string RootSymbol {{ get {{ return \"{0}\"; }} }}", grammar.StartSymbol.Name).AppendLine();255 sb.AppendLine("public static HashSet<string> terminalSymbols = new HashSet<string>() {");256 sb.AppendFormat("{0}", grammar.TerminalSymbols.Aggregate("", (str, symb) => str + "\"" + symb.Name + "\", "));257 sb.AppendLine("};");258 // GetAlternatives259 sb.AppendFormat("public static IEnumerable<IEnumerable<string>> GetAlternatives(string symbol) {{");260 sb.AppendFormat("switch(symbol) {{ ").AppendLine();261 foreach (var ntSymbol in grammar.NonTerminalSymbols) {262 sb.AppendFormat("case \"{0}\": {{ ", ntSymbol.Name).AppendLine();263 sb.Append("return new string[][] { ").AppendLine();264 foreach (var alt in grammar.GetAlternatives(ntSymbol)) {265 sb.Append("new string[] { ")266 .Append(alt.Skip(1).Aggregate("\"" + alt.First().Name + "\"", (str, symb) => str + ", \"" + symb.Name + "\""))267 .AppendLine("},");268 }269 sb.Append("};");270 sb.AppendLine("}");271 }272 sb.AppendLine(" default: { throw new InvalidOperationException(\"Unkown symbol: \"+symbol); }");273 sb.AppendLine("}");274 sb.AppendLine("}");275 276 sb.AppendLine("public static bool IsTerminal(string symbol) {");277 sb.AppendFormat("return terminalSymbols.Contains(symbol);");278 sb.AppendLine("}");279 // NumberOfAlternatives280 sb.AppendLine(281 "public static int NumberOfAlternatives(string symbol) { return GetAlternatives(symbol).Count(); }");282 return sb.ToString();283 }284 285 286 226 // produces helper methods for the attributes of all terminal nodes 287 227 private string GenerateConstraintMethods(List<SymbolNode> symbols) { … … 310 250 } 311 251 312 313 // generates code for a breath-first-search generating all possible paths through the grammar314 private string GeneratePathGeneratorCode(GPDefNode ast) {315 var sb = new StringBuilder();316 foreach (var s in ast.NonTerminals.OfType<NonTerminalNode>()) {317 sb.Append(GeneratePathGeneratorCode(s));318 }319 320 sb.Append(GeneratePathGeneratorCode(ast.Terminals.OfType<TerminalNode>()));321 return sb.ToString();322 }323 324 private string GeneratePathGeneratorCode(NonTerminalNode s) {325 var sb = new StringBuilder();326 327 return sb.ToString();328 }329 330 // generates a method for the terminal that returns all an IEnumerable of int[] representing each possible combination of values for that terminal331 private string GeneratePathGeneratorCode(IEnumerable<TerminalNode> terminals) {332 var sb = new StringBuilder();333 sb.AppendLine("private IEnumerable<IEnumerable<int>> GeneratePathsFor(string tSymbol) {");334 sb.AppendLine("switch(tSymbol) {");335 foreach (var t in terminals) {336 sb.AppendFormat("case \"{0}\": {{", t.Ident).AppendLine();337 if (t.FieldDefinitions.Any()) {338 int i = 0;339 // open for loop for each field340 foreach (var f in t.FieldDefinitions) {341 sb.AppendFormat("for(int i{0}=0; i{0} < GetAllowed{1}_{2}().Length; i{0}++) {{", i++, t.Ident, f.Identifier)342 .343 AppendLine();344 }345 sb.AppendFormat("yield return new int[] {{ {0} }};",346 Enumerable.Range(0, i).Select(ii => "i" + ii + ", ").Aggregate((str, e) => str + e));347 // close braces348 while (i-- > 0) {349 sb.AppendLine("}");350 }351 sb.AppendLine("break;");352 } else {353 sb.AppendLine("yield return Enumerable.Empty<int>();");354 sb.AppendLine("break;");355 }356 sb.AppendLine("}");357 }358 sb.AppendLine("} }");359 return sb.ToString();360 }361 362 252 private string GenerateInterpreterSource(AttributedGrammar grammar) { 363 253 var sb = new StringBuilder(); … … 378 268 // e.g.: ProgramRoot(ref int a0) { ProgramRoot(rootNode , ref a0); } 379 269 sb.AppendFormat("void {0}({1}) {{", grammar.StartSymbol.Name, formalParameter).AppendLine(); 380 sb.AppendLine(" var path = currentPath.GetEnumerator();"); 381 sb.AppendFormat("{0}(path, {1});", grammar.StartSymbol.Name, actualParameter).AppendLine(); 382 sb.AppendLine("if(path.MoveNext()) throw new InvalidOperationException(); // assert that the full path has been processed"); 270 sb.AppendFormat("{0}(tree, {1});", grammar.StartSymbol.Name, actualParameter).AppendLine(); 383 271 sb.AppendLine("}"); 384 272 … … 397 285 // if the terminal symbol has attributes then we must create values for these attributes 398 286 if (!s.Attributes.Any()) 399 sb.AppendFormat("private void {0}( IEnumerator<int> path) {{", s.Name);287 sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name); 400 288 else 401 sb.AppendFormat("private void {0}(IEnumerator<int> path, {1}) {{", s.Name, s.GetAttributeString()); 402 289 sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString()); 290 291 sb.AppendFormat("if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", s.Attributes.Count()); 403 292 // each field must match a formal parameter, assign a value for each parameter 293 int i = 0; 404 294 foreach (var element in s.Attributes) { 405 295 // read next symbol 406 sb.AppendLine(" path.MoveNext();");407 sb.AppendFormat("{0} = Get{1}_{0}Element( path.Current)", element.Name, s.Name).AppendLine(";");296 sb.AppendLine("throw new NotImplementedException(); // this is not yet supported "); 297 sb.AppendFormat("{0} = Get{1}_{0}Element(tree.GetSubTree({2}).GetAlternative())", element.Name, s.Name, i++).AppendLine(";"); 408 298 } 409 299 sb.AppendLine("}"); … … 414 304 var sb = new StringBuilder(); 415 305 if (!s.Attributes.Any()) 416 sb.AppendFormat("private void {0}( IEnumerator<int> path) {{", s.Name);306 sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name); 417 307 else 418 sb.AppendFormat("private void {0}(IEnumerator<int> path, {1}) {{", s.Name, s.GetAttributeString()); 308 sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString()); 309 419 310 // generate local definitions 420 311 sb.AppendLine(g.GetLocalDefinitions(s)); 421 312 422 313 423 // if there are alternatives for this symbol -> choose alternative based on the path 424 var alts = g.GetAlternatives(s); 425 if (alts.Count() > 1) { 426 // read next symbol 427 sb.AppendLine("path.MoveNext();"); 314 315 // make sure we first descent into terminal alternatives -> we just order by number of non-terminals in the alternative 316 var altsWithSemActions = g.GetAlternativesWithSemanticActions(s).OrderBy(alt => alt.Count(symb => g.IsNonTerminal(symb))).ToArray(); 317 318 if (altsWithSemActions.Length > 1) { 319 sb.AppendFormat(" if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsAlternativeNode = true; }}", altsWithSemActions.Length); 320 428 321 int i = 0; 429 sb.AppendLine("switch( path.Current) {");322 sb.AppendLine("switch(tree.GetNextAlternative()) {"); 430 323 // generate a case for each alternative 431 foreach (var l in alts) {324 foreach (var alt in altsWithSemActions) { 432 325 sb.AppendFormat("case {0}: {{ ", i).AppendLine(); 433 foreach (var altS in g.GetAlternativeWithSemanticActions(s, i++)) { 434 sb.AppendLine(GenerateSourceForAction(altS)); 326 sb.AppendLine("SearchTree subtree = null; "); 327 328 // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far! 329 // handling multiple non-terminals here would require a change in the structure of the search tree 330 // another way to handle this is through grammar transformation (the examplary grammars all have the correct from) 331 Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1); 332 foreach (var altSymb in alt) { 333 if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", i); 334 sb.AppendLine(GenerateSourceForAction(altSymb)); 435 335 } 336 i++; 436 337 sb.AppendLine("break;").AppendLine("}"); 437 338 } 438 339 sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}"); 439 340 } else { 440 foreach (var altS in g.GetAlternativeWithSemanticActions(s, 0)) { 441 sb.AppendLine(GenerateSourceForAction(altS)); 341 sb.AppendFormat(" if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", altsWithSemActions.Single().Count(symb => !(symb is SemanticSymbol))); 342 int j = 0; 343 sb.AppendLine("SearchTree subtree = null; "); 344 foreach (var altSymb in altsWithSemActions.Single()) { 345 if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", j++); 346 sb.AppendLine(GenerateSourceForAction(altSymb)); 442 347 } 443 348 } … … 453 358 } else { 454 359 if (!s.Attributes.Any()) 455 return string.Format("{0}( path);", s.Name);360 return string.Format("{0}(subtree);", s.Name); 456 361 else 457 return string.Format("{0}( path, {1});", s.Name, s.GetAttributeString());362 return string.Format("{0}(subtree, {1});", s.Name, s.GetAttributeString()); 458 363 } 459 364 } -
branches/HeuristicLab.Problems.GPDL/Examples/Artificial Ant.txt
r10061 r10074 86 86 87 87 public void Reset() { 88 world = LosAltosTrail.Select(l=>l.ToArray()).ToArray(); 88 for(int row = 0; row<world.Length;row++) 89 for(int col = 0; col < world[row].Length; col++) { 90 world[row][col] = LosAltosTrail[row][col]; 91 } 89 92 } 90 93 … … 209 212 . 210 213 211 Prog2<<World world, AntState state>> = 214 Prog2<<World world, AntState state>> = 212 215 Ant<<world, state>> Ant<<world, state>> 213 216 .
Note: See TracChangeset
for help on using the changeset viewer.