Changeset 10424

Timestamp:

01/29/14 16:17:20 (11 years ago)

Author:

gkronber

Message:

#2026 maximal depth limit for random search

Location:

branches/HeuristicLab.Problems.GPDL

Files:

• CodeGenerator/ProblemCodeGen.cs (modified) (4 diffs)
• CodeGenerator/RandomSearchCodeGen.cs (modified) (13 diffs)
• Examples/OneMaxBinary.txt (modified) (3 diffs)

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

@@ -101 +101 @@
        { -1, 0 }, // terminals
 ?SUBTREECOUNTTABLE?
+    };
+    public static readonly Dictionary<int, int> minDepth = new Dictionary<int, int>() {
+?MINDEPTHTABLE?
     };
     public static readonly string[] symb = new string[] { ?SYMBOLNAMES? };
@@ -144 +147 @@
         .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar))
         .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
+        .Replace("?MINDEPTHTABLE?", GenerateMinDepthTable(grammar))
        ;
     }
@@ -149 +153 @@
     private void GenerateSolvers(GPDefNode ast, SourceBuilder solverSourceCode) {
       var grammar = CreateGrammarFromAst(ast);
-      // var randomSearchCodeGen = new RandomSearchCodeGen();
-      // randomSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
+      var randomSearchCodeGen = new RandomSearchCodeGen();
+      randomSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
       // var bruteForceSearchCodeGen = new BruteForceCodeGen();
       // bruteForceSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
-      var mctsCodeGen = new MonteCarloTreeSearchCodeGen();
-      mctsCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
+      // var mctsCodeGen = new MonteCarloTreeSearchCodeGen();
+      // mctsCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
     }
 
@@ -428 +432 @@
       return sb.ToString();
     }
-
+    private string GenerateMinDepthTable(IGrammar grammar) {
+      var sb = new SourceBuilder();
+      var minDepth = new Dictionary<ISymbol, int>();
+      foreach (var s in grammar.TerminalSymbols) {
+        minDepth[s] = 1;
+      }
+      while (minDepth.Count < grammar.Symbols.Count()) {
+        foreach (var s in grammar.NonTerminalSymbols) {
+          if (grammar.NumberOfAlternatives(s) > 1) {
+            // alternatives
+            if (grammar.GetAlternatives(s).Any(alt => minDepth.ContainsKey(alt.Single()))) {
+              minDepth[s] = (grammar.GetAlternatives(s)
+                .Where(alt => minDepth.ContainsKey(alt.Single()))
+                .Select(alt => minDepth[alt.Single()]))
+                .Min() + 1;
+            }
+          } else {
+            // sequences
+            if (grammar.GetAlternatives(s).Single().All(c => minDepth.ContainsKey(c))) {
+              minDepth[s] = (grammar.GetAlternatives(s).Single().Select(c => minDepth[c])).Max() + 1;
+            }
+          }
+        }
+      }
+      var allSymbols = grammar.Symbols.ToList();
+      foreach (var s in grammar.Symbols) {
+        sb.AppendFormat("// {0}", s).AppendLine();
+        sb.AppendFormat("{{ {0}, {1} }}, ", allSymbols.IndexOf(s), minDepth[s]).AppendLine();
+      }
+      return sb.ToString();
+    }
   }
 }

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

@@ -14 +14 @@
     private static double baseTerminalProbability = 0.05; // 5% of all samples are only a terminal node
     private static double terminalProbabilityInc = 0.05; // for each level the probability to sample a terminal grows by 5%
+    private static int maxDepth = 20;
 
     private readonly ?IDENT?Problem problem;
     private readonly Random random;
 
-    private Tree SampleTree(out int steps, out int depth) {
+    private Tree SampleTree(int maxDepth, out int steps, out int depth) {
       steps = 0;
       depth = 0;
       int curDepth = 0;
-      return SampleTree(0, ref steps, ref curDepth, ref depth);
-    }
-
-    private Tree SampleTree(int state, ref int steps, ref int curDepth, ref int depth) {
+      return SampleTree(0, maxDepth, ref steps, ref curDepth, ref depth);
+    }
+
+    private Tree SampleTree(int state, int maxDepth, ref int steps, ref int curDepth, ref int depth) {
       curDepth += 1;
+      Debug.Assert(maxDepth > 0);
       steps += 1;
       depth = Math.Max(depth, curDepth);
@@ -38 +40 @@
         if(Grammar.subtreeCount[state] == 1) {
           var targetStates = Grammar.transition[state];
-          var altIdx = SampleAlternative(random, state, curDepth);
-          var alternative = SampleTree(targetStates[altIdx], ref steps, ref curDepth, ref depth);
+          var altIdx = SampleAlternative(random, maxDepth - 1, state, curDepth);
+          var alternative = SampleTree(targetStates[altIdx], maxDepth - 1, ref steps, ref curDepth, ref depth);
           t = new Tree(altIdx, new Tree[] { alternative });
         } else {
@@ -45 +47 @@
           Tree[] subtrees = new Tree[Grammar.subtreeCount[state]];
           for(int i = 0; i < Grammar.subtreeCount[state]; i++) {
-            subtrees[i] = SampleTree(Grammar.transition[state][i], ref steps, ref curDepth, ref depth);
+            subtrees[i] = SampleTree(Grammar.transition[state][i], maxDepth - 1, ref steps, ref curDepth, ref depth);
           }
           t = new Tree(-1, subtrees); // alternative index is ignored
@@ -57 +59 @@
       switch(state) {
         ?CREATETERMINALNODECODE?
-        default: { throw new ArgumentException(""Unknown state index"" + state); }
-      }
-    }
-
-    private int SampleAlternative(Random random, int state, int depth) {
+        default: { throw new ArgumentException(""Unknown state index "" + state); }
+      }
+    }
+
+    private int SampleAlternative(Random random, int maxDepth, int state, int depth) {
       switch(state) {
 
@@ -71 +73 @@
 
     private double TerminalProbForDepth(int depth) {
+      if(depth>=maxDepth) return 1.0;
       return baseTerminalProbability + depth * terminalProbabilityInc;
     }
@@ -84 +87 @@
       var baseTerminalProbabilityRegex = new Regex(@""--terminalProbBase=(?<prob>.+)"");
       var terminalProbabilityIncRegex = new Regex(@""--terminalProbInc=(?<prob>.+)"");
+      var maxDepthRegex = new Regex(@""--maxDepth=(?<d>.+)"");
+
       var helpRegex = new Regex(@""--help|/\?"");
       
@@ -89 +94 @@
         var baseTerminalProbabilityMatch = baseTerminalProbabilityRegex.Match(arg);
         var terminalProbabilityIncMatch = terminalProbabilityIncRegex.Match(arg);
+        var maxDepthMatch = maxDepthRegex.Match(arg);
         var helpMatch = helpRegex.Match(arg);
         if(helpMatch.Success) { PrintUsage(); Environment.Exit(0); }
@@ -97 +103 @@
            terminalProbabilityInc = double.Parse(terminalProbabilityIncMatch.Groups[""prob""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture);
            if(terminalProbabilityInc < 0.0 || terminalProbabilityInc > 1.0) throw new ArgumentException(""terminal probability increment must lie in range [0.0 ... 1.0]"");
+        } else if(maxDepthMatch.Success) {
+           maxDepth = int.Parse(maxDepthMatch.Groups[""d""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture);
+           if(maxDepth < 1 || maxDepth > 100) throw new ArgumentException(""max depth must lie in range [1 ... 100]"");
         } else {
            Console.WriteLine(""Unknown switch {0}"", arg); PrintUsage(); Environment.Exit(0); 
@@ -106 +115 @@
       Console.WriteLine();
       Console.WriteLine(""Parameters:"");
+      Console.WriteLine(""\t--maxDepth=<depth>\tSets the maximal depth of sampled trees [Default: 20]"");
       Console.WriteLine(""\t--terminalProbBase=<prob>\tSets the probability of sampling a terminal alternative in a rule [Default: 0.05]"");
       Console.WriteLine(""\t--terminalProbInc=<prob>\tSets the increment for the probability of sampling a terminal alternative for each level in the syntax tree [Default: 0.05]"");
@@ -127 +137 @@
 
         int steps, depth;
-        var _t = SampleTree(out steps, out depth);
+        var _t = SampleTree(maxDepth, out steps, out depth);
+        Debug.Assert(depth <= maxDepth);
+        // _t.PrintTree(0); Console.WriteLine();
         var f = problem.Evaluate(_t);
  
@@ -185 +197 @@
           var hasNonTerminalAlts = nonTerminalAltIndexes.Any();
           if (hasTerminalAlts && hasNonTerminalAlts) {
-            sb.Append("if(random.NextDouble() < TerminalProbForDepth(depth)) {").BeginBlock();
-            GenerateReturnStatement(terminalAltIndexes, sb);
+            sb.Append("if(maxDepth <= 1 || random.NextDouble() < TerminalProbForDepth(depth)) {").BeginBlock();
+            GenerateSampleTerminalAlternativesStatement(terminalAltIndexes, sb);
             sb.Append("} else {");
-            GenerateReturnStatement(nonTerminalAltIndexes, sb);
+            GenerateSampleNonterminalAlternativesStatement(nonTerminalAltIndexes, sb);
             sb.Append("}").EndBlock();
           } else {
@@ -226 +238 @@
       return sb.ToString();
     }
-    private void GenerateReturnStatement(IEnumerable<int> idxs, SourceBuilder sb) {
+    private void GenerateSampleTerminalAlternativesStatement(IEnumerable<int> idxs, SourceBuilder sb) {
       if (idxs.Count() == 1) {
         sb.AppendFormat("return {0};", idxs.Single()).AppendLine();
@@ -234 +246 @@
       }
     }
+    private void GenerateSampleNonterminalAlternativesStatement(IEnumerable<int> idxs, SourceBuilder sb) {
+      if (idxs.Count() == 1) {
+        sb.AppendFormat("return {0};", idxs.Single()).AppendLine();
+      } else {
+        var idxStr = idxs.Aggregate(string.Empty, (str, idx) => str + idx + ", ");
+        sb.AppendLine("{");
+        sb.AppendFormat("var allIdx = new int[] {{ {0} }}; ", idxStr).AppendLine();
+        sb.AppendFormat(
+          "var allowedIdx = (from idx in allIdx let targetState = Grammar.transition[state][idx] where Grammar.minDepth[targetState] <= maxDepth select idx).ToArray();")
+          .AppendLine();
+        sb.AppendLine(
+          "if(allowedIdx.Length==0) { allowedIdx = Enumerable.Range(0, Grammar.transition[state].Length).Except(allIdx).ToArray(); } ")
+          .AppendLine();
+        sb.AppendLine("return allowedIdx[random.Next(allowedIdx.Length)];");
+        sb.AppendLine("}");
+      }
+    }
 
     private void GenerateReturnStatement(int nAlts, SourceBuilder sb) {
-      if (nAlts > 1) {
-        sb.AppendFormat("return random.Next({0});", nAlts).AppendLine();
+      if (nAlts > 1)
+      {
+        sb.AppendLine("{");
+        sb.AppendFormat(
+          "var allowedIdx = (from idx in Enumerable.Range(0, {0}) let targetState = Grammar.transition[state][idx] where Grammar.minDepth[targetState] <= maxDepth select idx).ToArray();", nAlts)
+          .AppendLine();
+        sb.AppendLine("return allowedIdx[random.Next(allowedIdx.Length)];");
+        sb.AppendLine("}");
       } else if (nAlts == 1) {
         sb.AppendLine("return 0; ");

branches/HeuristicLab.Problems.GPDL/Examples/OneMaxBinary.txt

@@ -31 +31 @@
 NONTERMINALS
   E<<out int n>>.
-  T<<out int n>>.
   N<<out int n>>.
 
@@ -40 +39 @@
 RULES
   E<<out int n>> = 
-    T<<out n>>
+    A                                             SEM << n = 0; >>
+    | B                                           SEM << n = 1; >>
     | N<<out n>>
   .
@@ -48 +48 @@
   .
   
-  T<<out int n>> = 
-    A                                             SEM << n = 0; >>
-    | B                                           SEM << n = 1; >>
-  .
-
 MAXIMIZE
   <<