Free cookie consent management tool by TermsFeed Policy Generator

Changeset 10074


Ignore:
Timestamp:
10/20/13 21:31:41 (9 years ago)
Author:
gkronber
Message:

#2026: finished tree searcher for artifical ant, multiplexer and even parity examples. (+ performance tweak in Artificial Ant.txt)

Location:
branches/HeuristicLab.Problems.GPDL
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs

    r10067 r10074  
    2020    private string solverTemplate = @"
    2121namespace ?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   }
    6222  public sealed class ?IDENT?Solver {
    6323
     
    7939    }
    8040
    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
    11990        } 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;
    138108    private void Start() {
    139       // generate possible paths through the grammar and evaluate each of them   
     109      // start with empty tree
     110      tree = new SearchTree();
    140111      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
    141112      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
    145117        var f = Calculate();
     118        // do one more run through the tree to update the path
     119        tree.UpdatePath();
     120
    146121        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    }
    153131
    154132    public double Calculate() {
     
    188166        solverTemplate
    189167          .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant())
    190           .Replace("?GRAMMARCLASSCODE?", GenerateGrammarClassCode(grammar))
    191168          .Replace("?IDENT?", ast.Name)
    192169          .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
     
    195172          .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
    196173          .Replace("?CONSTRAINTSSOURCE?", GenerateConstraintMethods(ast.Terminals))
    197           .Replace("?PATHGENERATORCODE?", GeneratePathGeneratorCode(ast))
    198174          ;
    199175
     
    248224    }
    249225
    250 
    251     private string GenerateGrammarClassCode(IGrammar grammar) {
    252       var sb = new StringBuilder();
    253       // RootSymbol
    254       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       // GetAlternatives
    259       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       // NumberOfAlternatives
    280       sb.AppendLine(
    281         "public static int NumberOfAlternatives(string symbol) { return GetAlternatives(symbol).Count(); }");
    282       return sb.ToString();
    283     }
    284 
    285 
    286226    // produces helper methods for the attributes of all terminal nodes
    287227    private string GenerateConstraintMethods(List<SymbolNode> symbols) {
     
    310250    }
    311251
    312 
    313     // generates code for a breath-first-search generating all possible paths through the grammar
    314     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 terminal
    331     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 field
    340           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 braces
    348           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 
    362252    private string GenerateInterpreterSource(AttributedGrammar grammar) {
    363253      var sb = new StringBuilder();
     
    378268      // e.g.: ProgramRoot(ref int a0) { ProgramRoot(rootNode , ref a0); }
    379269      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();
    383271      sb.AppendLine("}");
    384272
     
    397285      // if the terminal symbol has attributes then we must create values for these attributes
    398286      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);
    400288      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());
    403292      // each field must match a formal parameter, assign a value for each parameter
     293      int i = 0;
    404294      foreach (var element in s.Attributes) {
    405295        // 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(";");
    408298      }
    409299      sb.AppendLine("}");
     
    414304      var sb = new StringBuilder();
    415305      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);
    417307      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
    419310      // generate local definitions
    420311      sb.AppendLine(g.GetLocalDefinitions(s));
    421312
    422313
    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
    428321        int i = 0;
    429         sb.AppendLine("switch(path.Current) {");
     322        sb.AppendLine("switch(tree.GetNextAlternative()) {");
    430323        // generate a case for each alternative
    431         foreach (var l in alts) {
     324        foreach (var alt in altsWithSemActions) {
    432325          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));
    435335          }
     336          i++;
    436337          sb.AppendLine("break;").AppendLine("}");
    437338        }
    438339        sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
    439340      } 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));
    442347        }
    443348      }
     
    453358      } else {
    454359        if (!s.Attributes.Any())
    455           return string.Format("{0}(path);", s.Name);
     360          return string.Format("{0}(subtree);", s.Name);
    456361        else
    457           return string.Format("{0}(path, {1});", s.Name, s.GetAttributeString());
     362          return string.Format("{0}(subtree, {1});", s.Name, s.GetAttributeString());
    458363      }
    459364    }
  • branches/HeuristicLab.Problems.GPDL/Examples/Artificial Ant.txt

    r10061 r10074  
    8686 
    8787  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      }
    8992  }
    9093 
     
    209212  .
    210213
    211   Prog2<<World world, AntState state>> = 
     214  Prog2<<World world, AntState state>> =
    212215    Ant<<world, state>> Ant<<world, state>>
    213216  .
Note: See TracChangeset for help on using the changeset viewer.