Changeset 10424


Ignore:
Timestamp:
01/29/14 16:17:20 (6 years ago)
Author:
gkronber
Message:

#2026 maximal depth limit for random search

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

Legend:

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

    r10415 r10424  
    101101       { -1, 0 }, // terminals
    102102?SUBTREECOUNTTABLE?
     103    };
     104    public static readonly Dictionary<int, int> minDepth = new Dictionary<int, int>() {
     105?MINDEPTHTABLE?
    103106    };
    104107    public static readonly string[] symb = new string[] { ?SYMBOLNAMES? };
     
    144147        .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar))
    145148        .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
     149        .Replace("?MINDEPTHTABLE?", GenerateMinDepthTable(grammar))
    146150       ;
    147151    }
     
    149153    private void GenerateSolvers(GPDefNode ast, SourceBuilder solverSourceCode) {
    150154      var grammar = CreateGrammarFromAst(ast);
    151       // var randomSearchCodeGen = new RandomSearchCodeGen();
    152       // randomSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
     155      var randomSearchCodeGen = new RandomSearchCodeGen();
     156      randomSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
    153157      // var bruteForceSearchCodeGen = new BruteForceCodeGen();
    154158      // bruteForceSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
    155       var mctsCodeGen = new MonteCarloTreeSearchCodeGen();
    156       mctsCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
     159      // var mctsCodeGen = new MonteCarloTreeSearchCodeGen();
     160      // mctsCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
    157161    }
    158162
     
    428432      return sb.ToString();
    429433    }
    430 
     434    private string GenerateMinDepthTable(IGrammar grammar) {
     435      var sb = new SourceBuilder();
     436      var minDepth = new Dictionary<ISymbol, int>();
     437      foreach (var s in grammar.TerminalSymbols) {
     438        minDepth[s] = 1;
     439      }
     440      while (minDepth.Count < grammar.Symbols.Count()) {
     441        foreach (var s in grammar.NonTerminalSymbols) {
     442          if (grammar.NumberOfAlternatives(s) > 1) {
     443            // alternatives
     444            if (grammar.GetAlternatives(s).Any(alt => minDepth.ContainsKey(alt.Single()))) {
     445              minDepth[s] = (grammar.GetAlternatives(s)
     446                .Where(alt => minDepth.ContainsKey(alt.Single()))
     447                .Select(alt => minDepth[alt.Single()]))
     448                .Min() + 1;
     449            }
     450          } else {
     451            // sequences
     452            if (grammar.GetAlternatives(s).Single().All(c => minDepth.ContainsKey(c))) {
     453              minDepth[s] = (grammar.GetAlternatives(s).Single().Select(c => minDepth[c])).Max() + 1;
     454            }
     455          }
     456        }
     457      }
     458      var allSymbols = grammar.Symbols.ToList();
     459      foreach (var s in grammar.Symbols) {
     460        sb.AppendFormat("// {0}", s).AppendLine();
     461        sb.AppendFormat("{{ {0}, {1} }}, ", allSymbols.IndexOf(s), minDepth[s]).AppendLine();
     462      }
     463      return sb.ToString();
     464    }
    431465  }
    432466}
  • branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs

    r10400 r10424  
    1414    private static double baseTerminalProbability = 0.05; // 5% of all samples are only a terminal node
    1515    private static double terminalProbabilityInc = 0.05; // for each level the probability to sample a terminal grows by 5%
     16    private static int maxDepth = 20;
    1617
    1718    private readonly ?IDENT?Problem problem;
    1819    private readonly Random random;
    1920
    20     private Tree SampleTree(out int steps, out int depth) {
     21    private Tree SampleTree(int maxDepth, out int steps, out int depth) {
    2122      steps = 0;
    2223      depth = 0;
    2324      int curDepth = 0;
    24       return SampleTree(0, ref steps, ref curDepth, ref depth);
    25     }
    26 
    27     private Tree SampleTree(int state, ref int steps, ref int curDepth, ref int depth) {
     25      return SampleTree(0, maxDepth, ref steps, ref curDepth, ref depth);
     26    }
     27
     28    private Tree SampleTree(int state, int maxDepth, ref int steps, ref int curDepth, ref int depth) {
    2829      curDepth += 1;
     30      Debug.Assert(maxDepth > 0);
    2931      steps += 1;
    3032      depth = Math.Max(depth, curDepth);
     
    3840        if(Grammar.subtreeCount[state] == 1) {
    3941          var targetStates = Grammar.transition[state];
    40           var altIdx = SampleAlternative(random, state, curDepth);
    41           var alternative = SampleTree(targetStates[altIdx], ref steps, ref curDepth, ref depth);
     42          var altIdx = SampleAlternative(random, maxDepth - 1, state, curDepth);
     43          var alternative = SampleTree(targetStates[altIdx], maxDepth - 1, ref steps, ref curDepth, ref depth);
    4244          t = new Tree(altIdx, new Tree[] { alternative });
    4345        } else {
     
    4547          Tree[] subtrees = new Tree[Grammar.subtreeCount[state]];
    4648          for(int i = 0; i < Grammar.subtreeCount[state]; i++) {
    47             subtrees[i] = SampleTree(Grammar.transition[state][i], ref steps, ref curDepth, ref depth);
     49            subtrees[i] = SampleTree(Grammar.transition[state][i], maxDepth - 1, ref steps, ref curDepth, ref depth);
    4850          }
    4951          t = new Tree(-1, subtrees); // alternative index is ignored
     
    5759      switch(state) {
    5860        ?CREATETERMINALNODECODE?
    59         default: { throw new ArgumentException(""Unknown state index"" + state); }
    60       }
    61     }
    62 
    63     private int SampleAlternative(Random random, int state, int depth) {
     61        default: { throw new ArgumentException(""Unknown state index "" + state); }
     62      }
     63    }
     64
     65    private int SampleAlternative(Random random, int maxDepth, int state, int depth) {
    6466      switch(state) {
    6567
     
    7173
    7274    private double TerminalProbForDepth(int depth) {
     75      if(depth>=maxDepth) return 1.0;
    7376      return baseTerminalProbability + depth * terminalProbabilityInc;
    7477    }
     
    8487      var baseTerminalProbabilityRegex = new Regex(@""--terminalProbBase=(?<prob>.+)"");
    8588      var terminalProbabilityIncRegex = new Regex(@""--terminalProbInc=(?<prob>.+)"");
     89      var maxDepthRegex = new Regex(@""--maxDepth=(?<d>.+)"");
     90
    8691      var helpRegex = new Regex(@""--help|/\?"");
    8792     
     
    8994        var baseTerminalProbabilityMatch = baseTerminalProbabilityRegex.Match(arg);
    9095        var terminalProbabilityIncMatch = terminalProbabilityIncRegex.Match(arg);
     96        var maxDepthMatch = maxDepthRegex.Match(arg);
    9197        var helpMatch = helpRegex.Match(arg);
    9298        if(helpMatch.Success) { PrintUsage(); Environment.Exit(0); }
     
    97103           terminalProbabilityInc = double.Parse(terminalProbabilityIncMatch.Groups[""prob""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture);
    98104           if(terminalProbabilityInc < 0.0 || terminalProbabilityInc > 1.0) throw new ArgumentException(""terminal probability increment must lie in range [0.0 ... 1.0]"");
     105        } else if(maxDepthMatch.Success) {
     106           maxDepth = int.Parse(maxDepthMatch.Groups[""d""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture);
     107           if(maxDepth < 1 || maxDepth > 100) throw new ArgumentException(""max depth must lie in range [1 ... 100]"");
    99108        } else {
    100109           Console.WriteLine(""Unknown switch {0}"", arg); PrintUsage(); Environment.Exit(0);
     
    106115      Console.WriteLine();
    107116      Console.WriteLine(""Parameters:"");
     117      Console.WriteLine(""\t--maxDepth=<depth>\tSets the maximal depth of sampled trees [Default: 20]"");
    108118      Console.WriteLine(""\t--terminalProbBase=<prob>\tSets the probability of sampling a terminal alternative in a rule [Default: 0.05]"");
    109119      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]"");
     
    127137
    128138        int steps, depth;
    129         var _t = SampleTree(out steps, out depth);
     139        var _t = SampleTree(maxDepth, out steps, out depth);
     140        Debug.Assert(depth <= maxDepth);
     141        // _t.PrintTree(0); Console.WriteLine();
    130142        var f = problem.Evaluate(_t);
    131143 
     
    185197          var hasNonTerminalAlts = nonTerminalAltIndexes.Any();
    186198          if (hasTerminalAlts && hasNonTerminalAlts) {
    187             sb.Append("if(random.NextDouble() < TerminalProbForDepth(depth)) {").BeginBlock();
    188             GenerateReturnStatement(terminalAltIndexes, sb);
     199            sb.Append("if(maxDepth <= 1 || random.NextDouble() < TerminalProbForDepth(depth)) {").BeginBlock();
     200            GenerateSampleTerminalAlternativesStatement(terminalAltIndexes, sb);
    189201            sb.Append("} else {");
    190             GenerateReturnStatement(nonTerminalAltIndexes, sb);
     202            GenerateSampleNonterminalAlternativesStatement(nonTerminalAltIndexes, sb);
    191203            sb.Append("}").EndBlock();
    192204          } else {
     
    226238      return sb.ToString();
    227239    }
    228     private void GenerateReturnStatement(IEnumerable<int> idxs, SourceBuilder sb) {
     240    private void GenerateSampleTerminalAlternativesStatement(IEnumerable<int> idxs, SourceBuilder sb) {
    229241      if (idxs.Count() == 1) {
    230242        sb.AppendFormat("return {0};", idxs.Single()).AppendLine();
     
    234246      }
    235247    }
     248    private void GenerateSampleNonterminalAlternativesStatement(IEnumerable<int> idxs, SourceBuilder sb) {
     249      if (idxs.Count() == 1) {
     250        sb.AppendFormat("return {0};", idxs.Single()).AppendLine();
     251      } else {
     252        var idxStr = idxs.Aggregate(string.Empty, (str, idx) => str + idx + ", ");
     253        sb.AppendLine("{");
     254        sb.AppendFormat("var allIdx = new int[] {{ {0} }}; ", idxStr).AppendLine();
     255        sb.AppendFormat(
     256          "var allowedIdx = (from idx in allIdx let targetState = Grammar.transition[state][idx] where Grammar.minDepth[targetState] <= maxDepth select idx).ToArray();")
     257          .AppendLine();
     258        sb.AppendLine(
     259          "if(allowedIdx.Length==0) { allowedIdx = Enumerable.Range(0, Grammar.transition[state].Length).Except(allIdx).ToArray(); } ")
     260          .AppendLine();
     261        sb.AppendLine("return allowedIdx[random.Next(allowedIdx.Length)];");
     262        sb.AppendLine("}");
     263      }
     264    }
    236265
    237266    private void GenerateReturnStatement(int nAlts, SourceBuilder sb) {
    238       if (nAlts > 1) {
    239         sb.AppendFormat("return random.Next({0});", nAlts).AppendLine();
     267      if (nAlts > 1)
     268      {
     269        sb.AppendLine("{");
     270        sb.AppendFormat(
     271          "var allowedIdx = (from idx in Enumerable.Range(0, {0}) let targetState = Grammar.transition[state][idx] where Grammar.minDepth[targetState] <= maxDepth select idx).ToArray();", nAlts)
     272          .AppendLine();
     273        sb.AppendLine("return allowedIdx[random.Next(allowedIdx.Length)];");
     274        sb.AppendLine("}");
    240275      } else if (nAlts == 1) {
    241276        sb.AppendLine("return 0; ");
  • branches/HeuristicLab.Problems.GPDL/Examples/OneMaxBinary.txt

    r10423 r10424  
    3131NONTERMINALS
    3232  E<<out int n>>.
    33   T<<out int n>>.
    3433  N<<out int n>>.
    3534
     
    4039RULES
    4140  E<<out int n>> =
    42     T<<out n>>
     41    A                                             SEM << n = 0; >>
     42    | B                                           SEM << n = 1; >>
    4343    | N<<out n>>
    4444  .
     
    4848  .
    4949 
    50   T<<out int n>> =
    51     A                                             SEM << n = 0; >>
    52     | B                                           SEM << n = 1; >>
    53   .
    54 
    5550MAXIMIZE
    5651  <<
Note: See TracChangeset for help on using the changeset viewer.