Free cookie consent management tool by TermsFeed Policy Generator

Changeset 10388


Ignore:
Timestamp:
01/23/14 09:20:15 (11 years ago)
Author:
gkronber
Message:

#2026 worked on code generator for brute force solver

Location:
branches/HeuristicLab.Problems.GPDL/CodeGenerator
Files:
4 edited

Legend:

Unmodified
Added
Removed

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

    r10335 r10388  
    33using System.Diagnostics;
    44using System.Linq;
     5using System.Text;
    56using HeuristicLab.Grammars;
    67
    78namespace CodeGenerator {
    89  public class BruteForceCodeGen {
     10
    911    private string solverTemplate = @"
    1012namespace ?PROBLEMNAME? {
    1113  public sealed class ?IDENT?Solver {
    12 
    13     private static Dictionary<int, int[]> transition = new Dictionary<int, int[]>() {
    14 ?TRANSITIONTABLE?
    15     };
    16     private static Dictionary<int, int> subtreeCount = new Dictionary<int, int>() {
    17        { -1, 0 }, // terminals
    18 ?SUBTREECOUNTTABLE?
    19     };
    20 
    21     private static string[] symb = new string[] { ?SYMBOLNAMES? };
    22     private static bool[] isTerminal = new bool[] { ?TERMINALTABLE? };
    23     private static bool[] hasAlternatives = new bool[] {?HASALTERNATIVESTABLE? };
    24 
    25    
    26     public sealed class SolverState : ISolverState {
    27       private class Node {
    28         public int state;
    29         public int count;
    30         public List<Node> nodes;
    31         public bool done;
    32         private int nextAlt;
    33         public Node(int state) {
    34           this.state = state;
    35           nodes = new List<Node>(transition[state].Length);
    36           if (!hasAlternatives[state]) {
    37             foreach (var t in transition[state]) { nodes.Add(new Node(t)); }
    38           }
    39         }
    40 
    41         public int GetNextAlternative() {
    42           System.Diagnostics.Debug.Assert(hasAlternatives[state]);
    43           if(nodes.Count == 0 && !isTerminal[state]) {
    44             foreach(var targetState in transition[state]) nodes.Add(new Node(targetState));
    45             nextAlt = 0;
    46             // begin with a terminal if possible
    47             if(!isTerminal[nodes[nextAlt].state])
    48               do { nextAlt = (nextAlt + 1) % nodes.Count; } while(nextAlt != 0 /* full circle*/ && !isTerminal[nodes[nextAlt].state]);
    49           }
    50 
    51           throw new NotImplementedException(); // TODO: handle terminal classes correctly
    52           return nextAlt;
    53         }
    54 
    55         public void Update() {
    56           count++;
    57           if(hasAlternatives[state] && !isTerminal[state]) {
    58             nodes[GetNextAlternative()].Update();
    59             // check if all nodes done and set this node to done
    60             if(nodes.All(n=>n.done)) {
    61               this.done = true;
    62             } else {
    63               // must not walk nodes that are done
    64               do { nextAlt = (nextAlt + 1) % nodes.Count; } while (nodes[nextAlt].done);
    65             }
    66           } else {
    67             if(isTerminal[state]) {
    68               throw new NotImplementedException(); // TODO: handle terminal classes correctly
    69               done = (nextAlt + 1) >= GetAlternativesCount(symb[state]);
    70             } else {
    71               // update the smallest count. this basically means keeping all sub-trees the same and only altering the updated one
    72               Node minNode = nodes.First();
    73               foreach(var node in nodes.Skip(1)) {
    74                 if(node.count < minNode.count) {
    75                   minNode = node;
    76                 }
    77               }
    78               minNode.Update();
    79               if(nodes.All(n=>n.done)) this.done = true;
    80             }
    81           }
    82         }
    83       }
    84 
    85 
    86       ?ALTERNATIVESCOUNTMETHOD?
    87 
    88 
    89       public int curDepth;
    90       public int steps;
    91       public int depth;
    92       private readonly Stack<Node> nodes;
    93       private readonly IGpdlProblem problem;
    94       private readonly Node searchTree;
    95 
    96       public SolverState(IGpdlProblem problem) {
    97         this.problem = problem;
    98         nodes = new Stack<Node>();
    99         searchTree = new Node(0);
    100         nodes.Push(searchTree);
    101       }
    102 
    103       public void Reset() {
    104         System.Diagnostics.Debug.Assert(nodes.Count == 1);
    105         steps = 0;
    106         depth = 0;
    107         curDepth = 0;
    108       }
    109 
    110       public int PeekNextAlternative() {
    111         var curNode = nodes.Peek();
    112         System.Diagnostics.Debug.Assert(hasAlternatives[curNode.state]);
    113         return curNode.GetNextAlternative();
    114       }
    115 
    116       public void Follow(int idx) {
    117         steps++;
    118         curDepth++;
    119         depth = Math.Max(depth, curDepth);
    120         var curNode = nodes.Peek();
    121         if(hasAlternatives[curNode.state]) {
    122           nodes.Push(curNode.nodes[curNode.GetNextAlternative()]);
     14    public class SearchTreeNode {
     15      public bool ready = false;
     16      public SearchTreeNode[] children;
     17      public int state;
     18      public int nextAltIdx;
     19
     20      public SearchTreeNode(int state) {
     21        // do not initialize children yet to save mem
     22        nextAltIdx = 0;
     23      }
     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] =
     31        }
     32      }
     33    }
     34
     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 });
    12361        } else {
    124           nodes.Push(curNode.nodes[idx]);
    125         }
    126       }
    127 
    128       public void Unwind() {
    129         nodes.Pop();
    130         curDepth--;
    131       }
    132 
    133       public void Update() {
    134         searchTree.Update();
    135       }
     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) {
     75      switch(state) {
     76        ?CREATETERMINALNODECODE?
     77        default: { throw new ArgumentException(""Unknown state index"" + state); }
     78      }
     79    }
     80
     81    private int NextAlternative(SearchTreeNode node) {
     82?RETURNNEXTALTERNATIVECODE?
    13683    }
    13784
    … …  
    14188      solver.Start();
    14289    }
    143    
    144     private readonly ?IDENT?Problem problem;
     90
    14591    public ?IDENT?Solver(?IDENT?Problem problem) {
    14692      this.problem = problem;
     93      this.random = new Random();
    14794    }
    14895
    … …  
    155102      var sw = new System.Diagnostics.Stopwatch();
    156103      sw.Start();
    157       var _state = new SolverState(problem);
    158       while (true) {
    159 
    160         var f = problem.Evaluate(_state);
    161         _state.Update();
    162 
    163         n++;
    164         sumSize += _state.steps;
    165         sumDepth += _state.depth;
    166         sumF += f;
    167         if (IsBetter(f, bestF)) {
    168           // evaluate again with tracing to console
    169           // problem.Evaluate(new SolverState(_state.seed, true));
    170           bestF = f;
    171           Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, _state.steps, _state.depth);
    172         }
    173         if (n % 1000 == 0) {
    174           sw.Stop();
    175           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);
    176           sw.Reset();
    177           sumSize = 0;
    178           sumDepth = 0;
    179           sumF = 0.0;
    180           sw.Start();
    181         }
    182       }
    183     }
    184 
    185     private bool IsBetter(double a, double b) {
    186       return ?MAXIMIZATION? ? a > b : a < b;
     104      for(int d = 1; d < 20; d++) {
     105        foreach(var t in GenerateTrees(d)) {
     106          var f = problem.Evaluate(t);
     107         
     108          n++;   
     109          sumF += f;
     110          if (problem.IsBetter(f, bestF)) {
     111            bestF = f;
     112            Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, 0, 0);
     113          }
     114          if (n % 1000 == 0) {
     115            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);
     117            sumSize = 0;
     118            sumDepth = 0;
     119            sumF = 0.0;
     120            sw.Restart();
     121          }
     122        }
     123      }
    187124    }
    188125  }
    189126}";
    190127
    191 
    192     public void Generate(IGrammar grammar, bool maximization, SourceBuilder problemSourceCode) {
     128    public void Generate(IGrammar grammar, IEnumerable<TerminalNode> terminals, bool maximization, SourceBuilder problemSourceCode) {
    193129      var solverSourceCode = new SourceBuilder();
    194130      solverSourceCode.Append(solverTemplate)
    195131        .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
    196         .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", "))
    197         .Replace("?TERMINALTABLE?", grammar.Symbols.Select(grammar.IsTerminal).Aggregate(string.Empty, (str, b) => str + b.ToString().ToLowerInvariant() + ", "))
    198         .Replace("?HASALTERNATIVESTABLE?", grammar.Symbols.Select(s => grammar.IsNonTerminal(s) && (grammar.NumberOfAlternatives(s) > 1)).Aggregate(string.Empty, (str, b) => str + b.ToString().ToLowerInvariant() + ", "))
    199         .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar))
    200         .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
    201         .Replace("?ALTERNATIVESCOUNTMETHOD?", GenerateAlternativesCountMethod(grammar))
     132        .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar))
     133        .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar, terminals))
    202134      ;
    203135
    … …  
    205137    }
    206138
    207     #region same as random search
    208     private string GenerateTransitionTable(IGrammar grammar) {
     139
     140
     141    private string GenerateSampleAlternativeSource(IGrammar grammar) {
    209142      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
    210143      var sb = new SourceBuilder();
    211 
    212       // state idx = idx of the corresponding symbol in the grammar
    213       var allSymbols = grammar.Symbols.ToList();
    214       var attributes = new List<string>();
     144      int stateCount = 0;
    215145      foreach (var s in grammar.Symbols) {
    216         var targetStates = new List<int>();
     146        sb.AppendFormat("case {0}: ", stateCount++);
    217147        if (grammar.IsTerminal(s)) {
    218           foreach (var att in s.Attributes) {
    219             targetStates.Add(allSymbols.Count + attributes.Count);
    220             attributes.Add(s.Name + "_" + att);
    221           }
     148          // ignore
    222149        } else {
    223           if (grammar.NumberOfAlternatives(s) > 1) {
    224             foreach (var alt in grammar.GetAlternatives(s)) {
    225               // only single-symbol alternatives are supported
    226               Debug.Assert(alt.Count() == 1);
    227               targetStates.Add(allSymbols.IndexOf(alt.Single()));
    228             }
     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();
    229166          } else {
    230             // rule is a sequence of symbols
    231             var seq = grammar.GetAlternatives(s).Single();
    232             targetStates.AddRange(seq.Select(symb => allSymbols.IndexOf(symb)));
    233           }
    234         }
    235 
    236         var targetStateString = targetStates.Aggregate(string.Empty, (str, state) => str + state + ", ");
    237 
    238         var idxOfSourceState = allSymbols.IndexOf(s);
    239         sb.AppendFormat("// {0}", s).AppendLine();
    240         sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine();
    241       }
    242       for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
    243         sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();
    244         sb.AppendFormat("{{ {0} , new int[] {{ }} }},", attIdx + allSymbols.Count).AppendLine();
     167            GenerateReturnStatement(grammar.NumberOfAlternatives(s), sb);
     168          }
     169        }
    245170      }
    246171      return sb.ToString();
    247172    }
    248     private string GenerateSubtreeCountTable(IGrammar grammar) {
     173
     174    private string GenerateCreateTerminalCode(IGrammar grammar, IEnumerable<TerminalNode> terminals) {
    249175      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
    250176      var sb = new SourceBuilder();
    251 
    252       // state idx = idx of the corresponding symbol in the grammar
    253177      var allSymbols = grammar.Symbols.ToList();
    254       var attributes = new List<string>();
    255178      foreach (var s in grammar.Symbols) {
    256         int subtreeCount;
    257179        if (grammar.IsTerminal(s)) {
    258           subtreeCount = s.Attributes.Count();
    259           attributes.AddRange(s.Attributes.Select(att => s.Name + "_" + att.Name));
    260         } else {
    261           if (grammar.NumberOfAlternatives(s) > 1) {
    262             Debug.Assert(grammar.GetAlternatives(s).All(alt => alt.Count() == 1));
    263             subtreeCount = 1;
    264           } else {
    265             subtreeCount = grammar.GetAlternative(s, 0).Count();
    266           }
    267         }
    268 
    269         sb.AppendFormat("// {0}", s).AppendLine();
    270         sb.AppendFormat("{{ {0} , {1} }},", allSymbols.IndexOf(s), subtreeCount).AppendLine();
    271       }
    272 
    273       for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
    274         sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();
    275         sb.AppendFormat("{{ {0} , 1 }},", attIdx + allSymbols.Count).AppendLine();
     180          sb.AppendFormat("case {0}: {{", allSymbols.IndexOf(s)).BeginBlock();
     181          sb.AppendFormat("var t = new {0}Tree();", s.Name).AppendLine();
     182          var terminal = terminals.Single(t => t.Ident == s.Name);
     183          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            }
     195          }
     196          sb.AppendLine("return t;").EndBlock();
     197          sb.Append("}");
     198        }
    276199      }
    277200      return sb.ToString();
    278201    }
    279     #endregion
    280     private string GenerateAlternativesCountMethod(IGrammar grammar) {
    281       Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
    282       var sb = new SourceBuilder();
    283       sb.Append("public int GetAlternativesCount(string symbol, string attribute = null) {").BeginBlock();
    284       sb.AppendLine("switch(symbol) {");
    285       foreach (var s in grammar.Symbols) {
    286         sb.AppendFormat("case \"{0}\":", s.Name).AppendLine();
    287         int altCount;
    288         if (grammar.IsTerminal(s)) {
    289           if (s.Attributes.Any()) {
    290             sb.Append("switch(attribute) {").BeginBlock();
    291             foreach (var att in s.Attributes) {
    292               sb.AppendFormat("case \"{1}\": return problem.GetCardinality(\"{0}\", \"{1}\");", s.Name, att.Name).AppendLine();
    293             }
    294             sb.Append("} // switch").EndBlock();
    295           } else {
    296             sb.AppendLine("return 0;");
    297           }
    298         } else {
    299           sb.AppendFormat("return {0};", grammar.NumberOfAlternatives(s)).AppendLine();
    300         }
    301 
    302 
    303       }
    304       sb.AppendLine("} // switch");
    305       sb.Append("}").EndBlock();
    306       return sb.ToString();
     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      }
    307220    }
    308221  }

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

    r10384 r10388  
    3636  </ItemGroup>
    3737  <ItemGroup>
     38    <Compile Include="BruteForceCodeGen.cs" />
    3839    <Compile Include="ProblemCodeGen.cs" />
    3940    <Compile Include="SourceBuilder.cs" />

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

    r10387 r10388  
    128128    private void GenerateSolvers(GPDefNode ast, SourceBuilder solverSourceCode) {
    129129      var grammar = CreateGrammarFromAst(ast);
    130       var randomSearchCodeGen = new RandomSearchCodeGen();
    131       randomSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
    132       //var bruteForceSearchCodeGen = new BruteForceCodeGen();
    133       //bruteForceSearchCodeGen.Generate(grammar, ast.FitnessFunctionNode.Maximization, solverSourceCode);
     130      // var randomSearchCodeGen = new RandomSearchCodeGen();
     131      // randomSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
     132      var bruteForceSearchCodeGen = new BruteForceCodeGen();
     133      bruteForceSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
    134134    }
    135135

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

    r10387 r10388  
    1818    private readonly Random random;
    1919
    20     public Tree SampleTree(out int steps, out int depth) {
     20    private Tree SampleTree(out int steps, out int depth) {
    2121      steps = 0;
    2222      depth = 0;
    … …  
    5454    }
    5555
    56     public static Tree CreateTerminalNode(int state, Random random, ?IDENT?Problem problem) {
     56    private static Tree CreateTerminalNode(int state, Random random, ?IDENT?Problem problem) {
    5757      switch(state) {
    5858        ?CREATETERMINALNODECODE?
Note: See TracChangeset for help on using the changeset viewer.