Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
01/24/14 17:54:35 (10 years ago)
Author:
gkronber
Message:

#2026 implemented brute force searcher

File:
1 edited

Legend:

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

    r10388 r10392  
    1010
    1111    private string solverTemplate = @"
     12
    1213namespace ?PROBLEMNAME? {
    1314  public sealed class ?IDENT?Solver {
    14     public class SearchTreeNode {
    15       public bool ready = false;
    16       public SearchTreeNode[] children;
    17       public int state;
    18       public int nextAltIdx;
    1915
    20       public SearchTreeNode(int state) {
    21         // do not initialize children yet to save mem
    22         nextAltIdx = 0;
     16    private readonly ?IDENT?Problem problem;
     17    private readonly Random random;
     18
     19    private IEnumerable<Tree> GenerateTrees(int parentState, int depth) {
     20      if(depth<=1) {
     21        if(Grammar.subtreeCount[parentState] == 0)
     22          foreach(var terminal in CreateTerminalNodes(parentState, problem))
     23            yield return terminal;
     24      } else if(Grammar.subtreeCount[parentState] == 1) {
     25        for(int altIdx = 0; altIdx < Grammar.transition[parentState].Length; altIdx++) {
     26          var targetState = Grammar.transition[parentState][altIdx];
     27          foreach(var subtree in GenerateTrees(targetState, depth - 1)) {
     28            var solution = new Tree(altIdx, new Tree[1] {subtree});
     29            yield return solution;
     30          }
     31        }
     32      } else if(Grammar.subtreeCount[parentState] > 1) {
     33        var trees = new IEnumerable<Tree>[Grammar.subtreeCount[parentState]];
     34        for(int subtreeIdx = 0; subtreeIdx < Grammar.subtreeCount[parentState]; subtreeIdx++) {
     35          trees[subtreeIdx] = GenerateTrees(Grammar.transition[parentState][subtreeIdx], depth - 1);
     36        }
     37        foreach(var e in CartesianProduct(trees)) {
     38          yield return new Tree(-1, e.ToArray()); // altIdx is ignored
     39        }
     40      }
     41    }
     42
     43    public IEnumerable<IEnumerable<Tree>> CartesianProduct(IEnumerable<IEnumerable<Tree>> sets) {
     44      if(sets.Count() == 1) {
     45        foreach(var e in sets.First()) {
     46          yield return new Tree[] {e};
     47        }
    2348      }
    24       public SearchTreeNode GetNextNode() {
    25         if(children == null) {
    26           int nChildren = Grammar.subtreeCount[state] == 1 ? Grammar.transitions[state].Length : Grammar.subtreeCount[state];
    27           children = new SearchTreeNode[nChildren];
    28         }
    29         if(children[nextAltIdx] == null) {
    30           children[nextAltIdx] =
     49      else {
     50        var firstSet = sets.First();
     51        foreach(var e in firstSet) {
     52          foreach(var p in CartesianProduct(sets.Skip(1))) {
     53            yield return new Tree[] {e}.Concat(p);
     54          }
    3155        }
    3256      }
    3357    }
    3458
    35 
    36     private readonly ?IDENT?Problem problem;
    37     private readonly Random random;
    38     private SearchTreeNode searchTree = null;
    39 
    40     private IEnumerable<Tree> GenerateTrees(int maxDepth) {
    41       if(searchTree==null) searchTree = new SearchTreeNode(0);
    42      
    43     }
    44 
    45     private Tree GenerateTree(SearchTreeNode node) {
    46       curDepth += 1;
    47       steps += 1;
    48       depth = Math.Max(depth, curDepth);
    49       Tree t = null;
    50 
    51       // terminals
    52       if(Grammar.subtreeCount[state] == 0) {
    53         t = CreateTerminalNode(state, random, problem);
    54       } else {
    55         // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case)
    56         if(Grammar.subtreeCount[state] == 1) {
    57           var targetStates = Grammar.transition[state];
    58           var altIdx = SampleAlternative(random, state, curDepth);
    59           var alternative = SampleTree(targetStates[altIdx], ref steps, ref curDepth, ref depth);
    60           t = new Tree(altIdx, new Tree[] { alternative });
    61         } else {
    62           // if the symbol contains only one sequence we must use create sub-trees for each symbol in the sequence
    63           Tree[] subtrees = new Tree[Grammar.subtreeCount[state]];
    64           for(int i = 0; i < Grammar.subtreeCount[state]; i++) {
    65             subtrees[i] = SampleTree(Grammar.transition[state][i], ref steps, ref curDepth, ref depth);
    66           }
    67           t = new Tree(-1, subtrees); // alternative index is ignored
    68         }
    69       }
    70       curDepth -=1;
    71       return t;
    72     }
    73 
    74     private static Tree CreateTerminalNode(int state, Random random, ?IDENT?Problem problem) {
     59    private static IEnumerable<Tree> CreateTerminalNodes(int state, ?IDENT?Problem problem) {
    7560      switch(state) {
    7661        ?CREATETERMINALNODECODE?
    7762        default: { throw new ArgumentException(""Unknown state index"" + state); }
    7863      }
    79     }
    80 
    81     private int NextAlternative(SearchTreeNode node) {
    82 ?RETURNNEXTALTERNATIVECODE?
    8364    }
    8465
     
    9576
    9677    private void Start() {
     78      const int MAX_SECONDS = 100000;
    9779      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
    9880      int n = 0;
     
    10082      long sumSize = 0;
    10183      var sumF = 0.0;
     84      var terminationTimer = new Stopwatch();
    10285      var sw = new System.Diagnostics.Stopwatch();
    10386      sw.Start();
    104       for(int d = 1; d < 20; d++) {
    105         foreach(var t in GenerateTrees(d)) {
     87      terminationTimer.Start();
     88      for(int depth = 1; terminationTimer.Elapsed.TotalSeconds < MAX_SECONDS; depth ++) {
     89        Console.WriteLine(""Depth {0}:"", depth);
     90        foreach(var t in GenerateTrees(0, depth)) {
    10691          var f = problem.Evaluate(t);
    107          
     92          //t.PrintTree(0); Console.WriteLine();
     93          var size = t.GetSize();
     94          sumSize += size;
     95          sumDepth += depth;
    10896          n++;   
    10997          sumF += f;
    11098          if (problem.IsBetter(f, bestF)) {
    11199            bestF = f;
    112             Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, 0, 0);
     100            Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, size, depth);
    113101          }
    114102          if (n % 1000 == 0) {
    115103            sw.Stop();
    116             Console.WriteLine(""{0}\tbest: {1:0.000}\t(avg: {2:0.000})\t(avg size: {3:0.0})\t(avg. depth: {4:0.0})\t({5:0.00} sols/ms)"", n, bestF, sumF/1000.0, sumSize/1000.0, sumDepth/1000.0, 1000.0 / sw.ElapsedMilliseconds);
     104            Console.WriteLine(""{6,5:0.0s}: {0}\tbest: {1:0.000}\t(avg: {2:0.000})\t(avg size: {3:0.0})\t(avg. depth: {4:0.0})\t({5:0.00} sols/ms)"",
     105                              n, bestF, sumF/1000.0, sumSize/1000.0, sumDepth/1000.0, 1000.0 / sw.ElapsedMilliseconds, terminationTimer.Elapsed.TotalSeconds);
    117106            sumSize = 0;
    118107            sumDepth = 0;
    119108            sumF = 0.0;
    120109            sw.Restart();
     110            if(terminationTimer.Elapsed.TotalSeconds >= MAX_SECONDS) break;
    121111          }
    122112        }
     
    130120      solverSourceCode.Append(solverTemplate)
    131121        .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
    132         .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar))
    133122        .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar, terminals))
    134123      ;
    135124
    136125      problemSourceCode.Append(solverSourceCode.ToString());
    137     }
    138 
    139 
    140 
    141     private string GenerateSampleAlternativeSource(IGrammar grammar) {
    142       Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
    143       var sb = new SourceBuilder();
    144       int stateCount = 0;
    145       foreach (var s in grammar.Symbols) {
    146         sb.AppendFormat("case {0}: ", stateCount++);
    147         if (grammar.IsTerminal(s)) {
    148           // ignore
    149         } else {
    150           var terminalAltIndexes = grammar.GetAlternatives(s)
    151             .Select((alt, idx) => new { alt, idx })
    152             .Where((p) => p.alt.All(symb => grammar.IsTerminal(symb)))
    153             .Select(p => p.idx);
    154           var nonTerminalAltIndexes = grammar.GetAlternatives(s)
    155             .Select((alt, idx) => new { alt, idx })
    156             .Where((p) => p.alt.Any(symb => grammar.IsNonTerminal(symb)))
    157             .Select(p => p.idx);
    158           var hasTerminalAlts = terminalAltIndexes.Any();
    159           var hasNonTerminalAlts = nonTerminalAltIndexes.Any();
    160           if (hasTerminalAlts && hasNonTerminalAlts) {
    161             sb.Append("if(random.NextDouble() < TerminalProbForDepth(depth)) {").BeginBlock();
    162             GenerateReturnStatement(terminalAltIndexes, sb);
    163             sb.Append("} else {");
    164             GenerateReturnStatement(nonTerminalAltIndexes, sb);
    165             sb.Append("}").EndBlock();
    166           } else {
    167             GenerateReturnStatement(grammar.NumberOfAlternatives(s), sb);
    168           }
    169         }
    170       }
    171       return sb.ToString();
    172126    }
    173127
     
    179133        if (grammar.IsTerminal(s)) {
    180134          sb.AppendFormat("case {0}: {{", allSymbols.IndexOf(s)).BeginBlock();
    181           sb.AppendFormat("var t = new {0}Tree();", s.Name).AppendLine();
    182135          var terminal = terminals.Single(t => t.Ident == s.Name);
     136          if (terminal.Constraints.Any(c => c.Type == ConstraintNodeType.Range)) {
     137            throw new NotSupportedException("Sorry the brute force solver does not support RANGE constraints");
     138          }
     139          sb.AppendFormat("{0}Tree t = null;", terminal.Ident).AppendLine();
     140          // create nested loop to produce all combinations of values (only set constraints)
    183141          foreach (var constr in terminal.Constraints) {
    184             if (constr.Type == ConstraintNodeType.Set) {
    185               sb.Append("{").BeginBlock();
    186               sb.AppendLine("throw new NotImplementedException(\"Enumeration of terminal values is not implemented.\");");
    187               sb.AppendFormat("//var elements = problem.GetAllowed{0}_{1}().ToArray();", terminal.Ident, constr.Ident).AppendLine();
    188               sb.AppendFormat("//t.{0} = elements[random.Next(elements.Length)]; ", constr.Ident).EndBlock();
    189               sb.AppendLine("}");
    190             } else {
    191               sb.Append("{").BeginBlock();
    192               sb.AppendLine("throw new NotSupportedException(\"The brute force solver does not support RANGE constraints\");");
    193               sb.AppendLine("}");
    194             }
     142            sb.AppendFormat("foreach(var {1} in problem.GetAllowed{0}_{1}()) {{;", terminal.Ident, constr.Ident).BeginBlock();
    195143          }
    196           sb.AppendLine("return t;").EndBlock();
    197           sb.Append("}");
     144          sb.AppendFormat("t = new {0}Tree();", terminal.Ident).AppendLine();
     145
     146          foreach (var constr in terminal.Constraints.Reverse()) {
     147            sb.AppendFormat("t.{0} = {0};", constr.Ident).EndBlock();
     148            sb.AppendLine("}");
     149          }
     150
     151          sb.AppendLine("yield return t; ").EndBlock();
     152
     153          sb.AppendLine(" break; }");
    198154        }
    199155      }
    200156      return sb.ToString();
    201157    }
    202 
    203     private void GenerateReturnStatement(IEnumerable<int> idxs, SourceBuilder sb) {
    204       if (idxs.Count() == 1) {
    205         sb.AppendFormat("return {0};", idxs.Single()).AppendLine();
    206       } else {
    207         var idxStr = idxs.Aggregate(string.Empty, (str, idx) => str + idx + ", ");
    208         sb.AppendFormat("return new int[] {{ {0} }}[random.Next({1})]; ", idxStr, idxs.Count()).AppendLine();
    209       }
    210     }
    211 
    212     private void GenerateReturnStatement(int nAlts, SourceBuilder sb) {
    213       if (nAlts > 1) {
    214         sb.AppendFormat("return random.Next({0});", nAlts).AppendLine();
    215       } else if (nAlts == 1) {
    216         sb.AppendLine("return 0; ");
    217       } else {
    218         sb.AppendLine("throw new InvalidProgramException();");
    219       }
    220     }
    221158  }
    222159}
Note: See TracChangeset for help on using the changeset viewer.