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

Timestamp:

10/27/13 20:17:17 (11 years ago)

Author:

gkronber

Message:

#2026 worked on random search solver (now all examples are working)

Location:

branches/HeuristicLab.Problems.GPDL/CodeGenerator

Files:

• BruteForceCodeGen.cs (modified) (6 diffs)
• RandomSearchCodeGen.cs (modified) (15 diffs)

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

@@ -81 +81 @@
             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
@@ -177 +171 @@
 
     private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
+
+      var nonTerminals = ast.NonTerminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
+      var terminals = ast.Terminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
       string startSymbolName = ast.Rules.First().NtSymbol;
-      var startSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == startSymbolName);
+
       // create startSymbol
-      var g = new AttributedGrammar(new Symbol(startSymbolName, ParseSymbolAttributes(startSymbolNode.FormalParameters)));
+      var startSymbol = nonTerminals.Single(s => s.Name == startSymbolName);
+      var g = new AttributedGrammar(startSymbol, nonTerminals, terminals);
+
+      // add all production rules
       foreach (var rule in ast.Rules) {
-        // create nt-symbol
-        var ntSymbolName = rule.NtSymbol;
-        var ntSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == ntSymbolName);
-        var attributes = ParseSymbolAttributes(ntSymbolNode.FormalParameters);
-        var ntSymbol = new Symbol(ntSymbolName, attributes);
-        foreach (var alt in GetAlternatives(rule.Alternatives)) {
+        var ntSymbol = nonTerminals.Single(s => s.Name == rule.NtSymbol);
+        foreach (var alt in GetAlternatives(rule.Alternatives, nonTerminals.Concat(terminals))) {
           g.AddProductionRule(ntSymbol, alt);
         }
@@ -196 +192 @@
     }
 
-    private IEnumerable<IAttribute> ParseSymbolAttributes(string formalParameters) {
+    private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
       return (from fieldDef in Util.ExtractParameters(formalParameters)
               select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
@@ -202 +198 @@
     }
 
-    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode) {
+    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode, IEnumerable<ISymbol> allSymbols) {
       foreach (var alt in altNode.Alternatives) {
-        yield return GetSequence(alt.Sequence);
-      }
-    }
-
-    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence) {
+        yield return GetSequence(alt.Sequence, allSymbols);
+      }
+    }
+
+    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence, IEnumerable<ISymbol> allSymbols) {
       Debug.Assert(sequence.All(s => s is CallSymbolNode || s is RuleActionNode));
       var l = new List<ISymbol>();
@@ -215 +211 @@
         var actionNode = node as RuleActionNode;
         if (callSymbolNode != null) {
-          l.Add(new Symbol(callSymbolNode.Ident, ParseSymbolAttributes(callSymbolNode.ActualParameter)));
+          Debug.Assert(allSymbols.Any(s => s.Name == callSymbolNode.Ident));
+          // create a new symbol with actual parameters
+          l.Add(new Symbol(callSymbolNode.Ident, GetSymbolAttributes(callSymbolNode.ActualParameter)));
         } else if (actionNode != null) {
           l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
@@ -313 +311 @@
 
       // 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)
+        .OrderBy(alt => alt.Count(symb => g.IsNonTerminal(symb))).ToArray();
 
       if (altsWithSemActions.Length > 1) {

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

@@ -20 +20 @@
 namespace ?PROBLEMNAME? {
   public sealed class ?IDENT?Solver {
+    public sealed class SolverState {
+      private int currentSeed;
+      public Random random;
+      public int depth;
+      public int steps;
+      public int maxDepth;
+      public SolverState(int seed) {
+        this.currentSeed = seed;
+      }
+
+      public SolverState IncDepth() {
+        depth++;
+        if(depth>maxDepth) maxDepth = depth;
+        return this;
+      }
+      public SolverState Prepare() {
+        this.random = new Random(currentSeed);
+        depth = 0;
+        maxDepth = 0;
+        steps = 0;
+        return this;
+      }
+    }
 
     public static void Main(string[] args) {
@@ -38 +61 @@
     }
 
-
-    private Random seedRandom;
-    private int currentSeed;
+    private double TerminalProbForDepth(int depth) {
+      const double baseProb = 0.05;  // 5% of all samples are only a terminal node
+      const double probIncPerLevel = 0.05; // for each level the probability to sample a terminal grows by 5%
+      return baseProb + depth * probIncPerLevel;
+    }
+
+    private SolverState _state;
     private void Start() {
-      seedRandom = new Random();
+      var seedRandom = new Random();
       var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
       int n = 0;
@@ -51 +78 @@
         // 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();
+        
+        _state = new SolverState(seedRandom.Next());
+
         var f = Calculate();
 
         n++;
-        if (IsBetter(f, bestF)) bestF = f;
-        if (n % 100 == 0) {
+        if (IsBetter(f, bestF)) {
+          bestF = f;
+          Console.WriteLine(""{0}\t{1}\t(depth={2})"", n, bestF, _state.maxDepth);
+        }
+        if (n % 1000 == 0) {
           sw.Stop();
-          Console.WriteLine(""{0}\t{1}\t{2}\t({3:0.00} sols/ms)"", n, bestF, f, 100.0 / sw.ElapsedMilliseconds);
+          Console.WriteLine(""{0}\t{1}\t{2}\t({3:0.00} sols/ms)"", n, bestF, f, 1000.0 / sw.ElapsedMilliseconds);
           sw.Reset();
           sw.Start();
@@ -112 +144 @@
     }
 
+    #region create grammar instance from AST
     private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
+
+      var nonTerminals = ast.NonTerminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
+      var terminals = ast.Terminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
       string startSymbolName = ast.Rules.First().NtSymbol;
-      var startSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == startSymbolName);
+
       // create startSymbol
-      var g = new AttributedGrammar(new Symbol(startSymbolName, ParseSymbolAttributes(startSymbolNode.FormalParameters)));
+      var startSymbol = nonTerminals.Single(s => s.Name == startSymbolName);
+      var g = new AttributedGrammar(startSymbol, nonTerminals, terminals);
+
+      // add all production rules
       foreach (var rule in ast.Rules) {
-        // create nt-symbol
-        var ntSymbolName = rule.NtSymbol;
-        var ntSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == ntSymbolName);
-        var attributes = ParseSymbolAttributes(ntSymbolNode.FormalParameters);
-        var ntSymbol = new Symbol(ntSymbolName, attributes);
-        foreach (var alt in GetAlternatives(rule.Alternatives)) {
+        var ntSymbol = nonTerminals.Single(s => s.Name == rule.NtSymbol);
+        foreach (var alt in GetAlternatives(rule.Alternatives, nonTerminals.Concat(terminals))) {
           g.AddProductionRule(ntSymbol, alt);
         }
@@ -132 +167 @@
     }
 
-    private IEnumerable<IAttribute> ParseSymbolAttributes(string formalParameters) {
+    private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
       return (from fieldDef in Util.ExtractParameters(formalParameters)
               select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
@@ -138 +173 @@
     }
 
-    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode) {
+    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode, IEnumerable<ISymbol> allSymbols) {
       foreach (var alt in altNode.Alternatives) {
-        yield return GetSequence(alt.Sequence);
-      }
-    }
-
-    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence) {
+        yield return GetSequence(alt.Sequence, allSymbols);
+      }
+    }
+
+    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence, IEnumerable<ISymbol> allSymbols) {
       Debug.Assert(sequence.All(s => s is CallSymbolNode || s is RuleActionNode));
       var l = new List<ISymbol>();
@@ -151 +186 @@
         var actionNode = node as RuleActionNode;
         if (callSymbolNode != null) {
-          l.Add(new Symbol(callSymbolNode.Ident, ParseSymbolAttributes(callSymbolNode.ActualParameter)));
+          Debug.Assert(allSymbols.Any(s => s.Name == callSymbolNode.Ident));
+          // create a new symbol with actual parameters
+          l.Add(new Symbol(callSymbolNode.Ident, GetSymbolAttributes(callSymbolNode.ActualParameter)));
         } else if (actionNode != null) {
           l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
@@ -158 +195 @@
       return new Sequence(l);
     }
-
+    #endregion
+
+    #region helper methods for terminal symbols
     // produces helper methods for the attributes of all terminal nodes
     private string GenerateConstraintMethods(List<SymbolNode> symbols) {
@@ -177 +216 @@
           sb.AppendFormat("public {0} GetMax{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMaxExpression).AppendLine();
           sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine();
+          sb.AppendFormat("public {0} GetRandom{1}_{2}(SolverState _state) {{ return _state.random.NextDouble() * (GetMax{1}_{2}() - GetMin{1}_{2}()) + GetMin{1}_{2}(); }}", fieldType, t.Ident, c.Ident).AppendLine();
         } else if (c.Type == ConstraintNodeType.Set) {
-          sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3} }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
-        }
-      }
-      return sb.ToString();
-    }
+          sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
+          sb.AppendFormat("public {0} GetRandom{1}_{2}(SolverState _state) {{ var tmp = GetAllowed{1}_{2}().ToArray(); return tmp[_state.random.Next(tmp.Length)]; }}", fieldType, t.Ident, c.Ident).AppendLine();
+        }
+      }
+      return sb.ToString();
+    }
+    #endregion
 
     private string GenerateInterpreterSource(AttributedGrammar grammar) {
@@ -197 +239 @@
     }
 
-    private string GenerateTerminalInterpreterMethod(ISymbol s) {
-      var sb = new StringBuilder();
-      // if the terminal symbol has attributes then we must create values for these attributes
-      if (!s.Attributes.Any())
-        sb.AppendFormat("private void {0}(Random random) {{", s.Name);
-      else
-        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
-      foreach (var element in s.Attributes) {
-        // 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("}");
-      return sb.ToString();
-    }
-
     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())
@@ -234 +259 @@
           actualParameter = string.Empty;
 
-        sb.AppendFormat("{0}(new Random(currentSeed), {1});", g.StartSymbol.Name, actualParameter).AppendLine();
+        sb.AppendFormat("{0}(_state.Prepare(), {1});", g.StartSymbol.Name, actualParameter).AppendLine();
         sb.AppendLine("}");
       }
 
       if (!s.Attributes.Any())
-        sb.AppendFormat("private void {0}(Random random) {{", s.Name);
+        sb.AppendFormat("private void {0}(SolverState _state) {{", s.Name);
       else
-        sb.AppendFormat("private void {0}(Random random, {1}) {{", s.Name, s.GetAttributeString());
+        sb.AppendFormat("private void {0}(SolverState _state, {1}) {{", s.Name, s.GetAttributeString());
 
       // generate local definitions
@@ -250 +275 @@
       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;
+      bool hasTerminalAlts = terminalAlts.Any();
+      bool hasNonTerminalAlts = nonTerminalAlts.Any();
 
       if (altsWithSemActions.Length > 1) {
@@ -261 +286 @@
         // 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) {");
+          sb.AppendLine("if(_state.random.NextDouble() < TerminalProbForDepth(_state.depth)) {");
           // terminals
           sb.AppendLine("// terminals ");
@@ -287 +312 @@
 
     private void GenerateSwitchStatement(StringBuilder sb, IEnumerable<Sequence> alts) {
-      sb.AppendFormat("switch(random.Next({0})) {{", alts.Count());
+      sb.AppendFormat("switch(_state.random.Next({0})) {{", alts.Count());
       // generate a case for each alternative
       int i = 0;
@@ -313 +338 @@
       } else {
         if (!s.Attributes.Any())
-          return string.Format("{0}(random);", s.Name);
+          return string.Format("{0}(_state.IncDepth()); _state.depth--;", s.Name);
         else
-          return string.Format("{0}(random, {1});", s.Name, s.GetAttributeString());
-      }
+          return string.Format("{0}(_state.IncDepth(), {1}); _state.depth--;", s.Name, s.GetAttributeString());
+      }
+    }
+
+    private string GenerateTerminalInterpreterMethod(ISymbol s) {
+      var sb = new StringBuilder();
+      // if the terminal symbol has attributes then we must samples values for these attributes
+      if (!s.Attributes.Any())
+        sb.AppendFormat("private void {0}(SolverState _state) {{", s.Name);
+      else
+        sb.AppendFormat("private void {0}(SolverState _state, {1}) {{", s.Name, s.GetAttributeString());
+
+      // each field must match a formal parameter, assign a value for each parameter
+      foreach (var element in s.Attributes) {
+        sb.AppendFormat("{{ {0} = GetRandom{1}_{0}(_state); }} ", element.Name, s.Name);
+      }
+      sb.AppendLine("}");
+      return sb.ToString();
     }
   }