Changeset 10080 for branches/HeuristicLab.Problems.GPDL/CodeGenerator

Timestamp:

10/22/13 20:39:15 (11 years ago)

Author:

gkronber

Message:

#2026 implemented a code generator for random search solvers for GPDL problems

Location:

branches/HeuristicLab.Problems.GPDL/CodeGenerator

Files:

• BruteForceCodeGen.cs (modified) (2 diffs)
• CodeGenerator.csproj (modified) (1 diff)
• RandomSearchCodeGen.cs (copied) (copied from branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs) (9 diffs)

branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs

@@ -5 +5 @@
 using System.Linq;
 using System.Text;
-using System.Threading.Tasks;
 using HeuristicLab.Grammars;
 using Attribute = HeuristicLab.Grammars.Attribute;
@@ -254 +253 @@
 
 
-      // find formal parameters of root node
+      // get formal parameters of start symbol
       var attr = grammar.StartSymbol.Attributes;
 

branches/HeuristicLab.Problems.GPDL/CodeGenerator/CodeGenerator.csproj

@@ -38 +38 @@
     <Compile Include="BruteForceCodeGen.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="RandomSearchCodeGen.cs" />
   </ItemGroup>
   <ItemGroup>

branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs

@@ -5 +5 @@
 using System.Linq;
 using System.Text;
-using System.Threading.Tasks;
 using HeuristicLab.Grammars;
 using Attribute = HeuristicLab.Grammars.Attribute;
 
 namespace CodeGenerator {
-  public class BruteForceCodeGen {
+  public class RandomSearchCodeGen {
 
     private string usings = @"
@@ -39 +38 @@
     }
 
-    private class SearchTree {
-      private SearchTree[] subTrees;
-      public bool Done { get; private set; }
-      private int nextAlternative;
-
-      public SearchTree() {
-        Done = false;
-      }
-
-      public SearchTree GetSubtree(int i) {
-        // if (subTrees[i] == null) subTrees[i] = new SearchTree();
-        return subTrees[i];
-      }
-
-      public int GetNextAlternative() {
-        System.Diagnostics.Debug.Assert(IsAlternativeNode);
-        return nextAlternative;
-      }
-
-      public bool IsUninitialized {
-        get { return subTrees == null; }
-      }
-
-      public void SetNumberOfSubtrees(int n) {
-        this.subTrees = new SearchTree[n]; 
-        for(int i=0;i<n;i++) this.subTrees[i] = new SearchTree();
-        nextAlternative = 0;
-      }
-
-      public void UpdatePath() {
-        System.Diagnostics.Debug.Assert(!Done);
-        if (IsUninitialized) { return; }
-        Count++;
-        if (subTrees.Length == 0) {
-          Done = true;
-        }
-        if (IsAlternativeNode) {
-          // update only the active alternative and calculate a new alternative
-          subTrees[nextAlternative].UpdatePath();
-
-          do {
-            nextAlternative = (nextAlternative + 1) % subTrees.Length;
-          } while (subTrees[nextAlternative] != null && subTrees[nextAlternative].Done);
-
-          // from the nodes which are not done take the first with minimum count
-          //nextAlternative = (from i in Enumerable.Range(0, subTrees.Length)
-          //                   where subTrees[i] == null || !subTrees[i].Done
-          //                   orderby subTrees[i]==null?0:subTrees[i].Count ascending
-          //                   select i).FirstOrDefault(); // possibly there are no children left that can be tried
-        } else {
-          // for sequenceNodes update all sub-trees
-          foreach (var t in subTrees) t.UpdatePath();
-        }
-        // set node to done if all nodes are non-null and done
-        this.Done = true;
-        foreach(var t in subTrees) {
-          if(t == null || !t.Done) 
-            { this.Done = false; break; }
-        }        
-      }
-
-      public bool IsAlternativeNode { get; set; }
-      public bool IsSequenceNode { get; set; }
-      public int Count { get; private set; }
-    }
-
-    private SearchTree tree;
+
+    private Random seedRandom;
+    private int currentSeed;
     private void Start() {
-      // start with empty tree
-      tree = new SearchTree();
+      seedRandom = new Random();
       var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
       int n = 0;
       var sw = new System.Diagnostics.Stopwatch();
       sw.Start();
-      while (!tree.Done) {
-
+      while (true) {
+
+        // must make sure that calling the start-symbol multiple times in the fitness function always leads to the same path through the grammar
+        // so we use a PRNG for generating seeds for a separate PRNG that is reset each time the start symbol is called
+        currentSeed = seedRandom.Next();
         var f = Calculate();
-        // do one more run through the tree to update the path
-        tree.UpdatePath();
 
         n++;
@@ -243 +178 @@
           sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine();
         } else if (c.Type == ConstraintNodeType.Set) {
-          sb.AppendFormat("public {0}[] GetAllowed{1}_{2}() {{ return {3}.ToArray(); }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
-        }
-        sb.AppendFormat("public {0} Get{1}_{2}Element(int i) {{ return GetAllowed{1}_{2}()[i]; }}", fieldType, t.Ident, c.Ident);
+          sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3} }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
+        }
       }
       return sb.ToString();
@@ -252 +186 @@
     private string GenerateInterpreterSource(AttributedGrammar grammar) {
       var sb = new StringBuilder();
-
-
-      // find formal parameters of root node
-      var attr = grammar.StartSymbol.Attributes;
-
-      var formalParameter = grammar.StartSymbol.GetAttributeString();
-      // actual parameter are the same as formalparameter only without type identifier
-      string actualParameter;
-      if (attr.Any())
-        actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
-      else
-        actualParameter = string.Empty;
-
-      // generate entry method for evaluation. This is called from the min/max function
-      // e.g.: ProgramRoot(ref int a0) { ProgramRoot(rootNode , ref a0); }
-      sb.AppendFormat("void {0}({1}) {{", grammar.StartSymbol.Name, formalParameter).AppendLine();
-      sb.AppendFormat("{0}(tree, {1});", grammar.StartSymbol.Name, actualParameter).AppendLine();
-      sb.AppendLine("}");
 
       // generate methods for all nonterminals and terminals using the grammar instance
@@ -285 +201 @@
       // if the terminal symbol has attributes then we must create values for these attributes
       if (!s.Attributes.Any())
-        sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
+        sb.AppendFormat("private void {0}(Random random) {{", s.Name);
       else
-        sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());
-
-      sb.AppendFormat("if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", s.Attributes.Count());
+        sb.AppendFormat("private void {0}(Random random, {1}) {{", s.Name, s.GetAttributeString());
+
       // each field must match a formal parameter, assign a value for each parameter
-      int i = 0;
       foreach (var element in s.Attributes) {
-        // read next symbol
-        sb.AppendLine("throw new NotImplementedException(); // this is not yet supported ");
-        sb.AppendFormat("{0} = Get{1}_{0}Element(tree.GetSubTree({2}).GetAlternative())", element.Name, s.Name, i++).AppendLine(";");
+        // only works for "IN SET"-Constraints
+        sb.AppendFormat("{{ var tmp = GetAllowed{1}_{0}().ToArray(); {0} = tmp[random.Next(tmp.Length)]; }} ", element.Name, s.Name);
       }
       sb.AppendLine("}");
@@ -303 +216 @@
     private string GenerateInterpreterMethod(AttributedGrammar g, ISymbol s) {
       var sb = new StringBuilder();
+      // if this is the start symbol we additionally have to create the method which can be called from the fitness function
+
+      if (g.StartSymbol.Equals(s)) {
+        if (!s.Attributes.Any())
+          sb.AppendFormat("private void {0}() {{", s.Name);
+        else
+          sb.AppendFormat("private void {0}({1}) {{", s.Name, s.GetAttributeString());
+
+        // get formal parameters of start symbol
+        var attr = g.StartSymbol.Attributes;
+
+        // actual parameter are the same as formalparameter only without type identifier
+        string actualParameter;
+        if (attr.Any())
+          actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
+        else
+          actualParameter = string.Empty;
+
+        sb.AppendFormat("{0}(new Random(currentSeed), {1});", g.StartSymbol.Name, actualParameter).AppendLine();
+        sb.AppendLine("}");
+      }
+
       if (!s.Attributes.Any())
-        sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
+        sb.AppendFormat("private void {0}(Random random) {{", s.Name);
       else
-        sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());
+        sb.AppendFormat("private void {0}(Random random, {1}) {{", s.Name, s.GetAttributeString());
 
       // generate local definitions
@@ -312 +247 @@
 
 
-
-      // make sure we first descent into terminal alternatives -> we just order by number of non-terminals in the alternative
-      var altsWithSemActions = g.GetAlternativesWithSemanticActions(s).OrderBy(alt => alt.Count(symb => g.IsNonTerminal(symb))).ToArray();
+      var altsWithSemActions = g.GetAlternativesWithSemanticActions(s).ToArray();
+      var terminalAlts = altsWithSemActions.Where(alt => alt.Count(g.IsNonTerminal) == 0);
+      var nonTerminalAlts = altsWithSemActions.Where(alt => alt.Count(g.IsNonTerminal) > 0);
+      bool hasTerminalAlts = terminalAlts.Count() > 0;
+      bool hasNonTerminalAlts = nonTerminalAlts.Count() > 0;
 
       if (altsWithSemActions.Length > 1) {
-        sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsAlternativeNode = true; }}", altsWithSemActions.Length);
-
-        int i = 0;
-        sb.AppendLine("switch(tree.GetNextAlternative()) {");
-        // generate a case for each alternative
-        foreach (var alt in altsWithSemActions) {
-          sb.AppendFormat("case {0}: {{ ", i).AppendLine();
-          sb.AppendLine("SearchTree subtree = null; ");
-
-          // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
-          // handling multiple non-terminals here would require a change in the structure of the search tree
-          // another way to handle this is through grammar transformation (the examplary grammars all have the correct from)
-          Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
-          foreach (var altSymb in alt) {
-            if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", i);
-            sb.AppendLine(GenerateSourceForAction(altSymb));
-          }
-          i++;
-          sb.AppendLine("break;").AppendLine("}");
-        }
-        sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
+        // here we need to bias the selection of alternatives (non-terminal vs terminal alternatives) to make sure that
+        // terminals are selected with a certain probability to make sure that:
+        // 1) we don't create the same small trees all the time (terminals have high probability to be selected)
+        // 2) we don't create very big trees by recursing to deep (leads to stack-overflow) (terminals have a low probability to be selected)
+        // so we first decide if we want to generate a terminal or non-terminal (50%, 50%) and then choose a symbol in the class randomly
+        // the probability of choosing terminals should depend on the depth of the tree (small likelihood to choose terminals for small depths, large likelihood for large depths)
+        if (hasTerminalAlts && hasNonTerminalAlts) {
+          sb.AppendLine("if(random.NextDouble() < 0.5) {");
+          // terminals
+          sb.AppendLine("// terminals ");
+          GenerateSwitchStatement(sb, terminalAlts);
+          sb.AppendLine("} else {");
+          // non-terminals
+          sb.AppendLine("// non-terminals ");
+          GenerateSwitchStatement(sb, nonTerminalAlts);
+          sb.AppendLine("}");
+        } else if (hasTerminalAlts) {
+          sb.AppendLine("// terminals ");
+          GenerateSwitchStatement(sb, terminalAlts);
+        } else if (hasNonTerminalAlts) {
+          sb.AppendLine("// non-terminals ");
+          GenerateSwitchStatement(sb, nonTerminalAlts);
+        }
       } else {
-        sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", altsWithSemActions.Single().Count(symb => !(symb is SemanticSymbol)));
-        int j = 0;
-        sb.AppendLine("SearchTree subtree = null; ");
         foreach (var altSymb in altsWithSemActions.Single()) {
-          if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", j++);
           sb.AppendLine(GenerateSourceForAction(altSymb));
         }
@@ -349 +284 @@
       sb.AppendLine("}");
       return sb.ToString();
+    }
+
+    private void GenerateSwitchStatement(StringBuilder sb, IEnumerable<Sequence> alts) {
+      sb.AppendFormat("switch(random.Next({0})) {{", alts.Count());
+      // generate a case for each alternative
+      int i = 0;
+      foreach (var alt in alts) {
+        sb.AppendFormat("case {0}: {{ ", i).AppendLine();
+
+        // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
+        // a way to handle this is through grammar transformation (the examplary grammars all have the correct from)
+        Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
+        foreach (var altSymb in alt) {
+          sb.AppendLine(GenerateSourceForAction(altSymb));
+        }
+        i++;
+        sb.AppendLine("break;").AppendLine("}");
+      }
+      sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
+
     }
 
@@ -358 +313 @@
       } else {
         if (!s.Attributes.Any())
-          return string.Format("{0}(subtree);", s.Name);
+          return string.Format("{0}(random);", s.Name);
         else
-          return string.Format("{0}(subtree, {1});", s.Name, s.GetAttributeString());
+          return string.Format("{0}(random, {1});", s.Name, s.GetAttributeString());
       }
     }