Changeset 10392

Timestamp:

01/24/14 17:54:35 (11 years ago)

Author:

gkronber

Message:

#2026 implemented brute force searcher

Location:

branches/HeuristicLab.Problems.GPDL

Files:

• CodeGenerator/BruteForceCodeGen.cs (modified) (5 diffs)
• CodeGenerator/ProblemCodeGen.cs (modified) (4 diffs)
• Examples/symbreg Koza.txt (modified) (1 diff)
• HeuristicLab.Problems.GPDL.sln (modified) (3 diffs)
• TestExamples.bat (modified) (2 diffs)

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

@@ -10 +10 @@
 
     private string solverTemplate = @"
+
 namespace ?PROBLEMNAME? {
   public sealed class ?IDENT?Solver {
-    public class SearchTreeNode {
-      public bool ready = false;
-      public SearchTreeNode[] children;
-      public int state;
-      public int nextAltIdx;
 
-      public SearchTreeNode(int state) {
-        // do not initialize children yet to save mem
-        nextAltIdx = 0;
+    private readonly ?IDENT?Problem problem;
+    private readonly Random random;
+
+    private IEnumerable<Tree> GenerateTrees(int parentState, int depth) {
+      if(depth<=1) {
+        if(Grammar.subtreeCount[parentState] == 0) 
+          foreach(var terminal in CreateTerminalNodes(parentState, problem)) 
+            yield return terminal;
+      } else if(Grammar.subtreeCount[parentState] == 1) {
+        for(int altIdx = 0; altIdx < Grammar.transition[parentState].Length; altIdx++) {
+          var targetState = Grammar.transition[parentState][altIdx];
+          foreach(var subtree in GenerateTrees(targetState, depth - 1)) {
+            var solution = new Tree(altIdx, new Tree[1] {subtree});
+            yield return solution;
+          }
+        }
+      } else if(Grammar.subtreeCount[parentState] > 1) {
+        var trees = new IEnumerable<Tree>[Grammar.subtreeCount[parentState]];
+        for(int subtreeIdx = 0; subtreeIdx < Grammar.subtreeCount[parentState]; subtreeIdx++) {
+          trees[subtreeIdx] = GenerateTrees(Grammar.transition[parentState][subtreeIdx], depth - 1);
+        }
+        foreach(var e in CartesianProduct(trees)) {
+          yield return new Tree(-1, e.ToArray()); // altIdx is ignored
+        }
+      } 
+    }
+
+    public IEnumerable<IEnumerable<Tree>> CartesianProduct(IEnumerable<IEnumerable<Tree>> sets) {
+      if(sets.Count() == 1) { 
+        foreach(var e in sets.First()) {
+          yield return new Tree[] {e};
+        }
       }
-      public SearchTreeNode GetNextNode() {
-        if(children == null) {
-          int nChildren = Grammar.subtreeCount[state] == 1 ? Grammar.transitions[state].Length : Grammar.subtreeCount[state];
-          children = new SearchTreeNode[nChildren];
-        }
-        if(children[nextAltIdx] == null) {
-          children[nextAltIdx] = 
+      else {
+        var firstSet = sets.First();
+        foreach(var e in firstSet) {
+          foreach(var p in CartesianProduct(sets.Skip(1))) {
+            yield return new Tree[] {e}.Concat(p);
+          }
         }
       }
     }
 
-
-    private readonly ?IDENT?Problem problem;
-    private readonly Random random;
-    private SearchTreeNode searchTree = null;
-
-    private IEnumerable<Tree> GenerateTrees(int maxDepth) {
-      if(searchTree==null) searchTree = new SearchTreeNode(0);
-      
-    }
-
-    private Tree GenerateTree(SearchTreeNode node) {
-      curDepth += 1;
-      steps += 1;
-      depth = Math.Max(depth, curDepth);
-      Tree t = null;
-
-      // terminals
-      if(Grammar.subtreeCount[state] == 0) {
-        t = CreateTerminalNode(state, random, problem);
-      } else {
-        // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case)
-        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);
-          t = new Tree(altIdx, new Tree[] { alternative });
-        } else {
-          // if the symbol contains only one sequence we must use create sub-trees for each symbol in the sequence
-          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);
-          }
-          t = new Tree(-1, subtrees); // alternative index is ignored
-        }
-      }
-      curDepth -=1;
-      return t;
-    }
-
-    private static Tree CreateTerminalNode(int state, Random random, ?IDENT?Problem problem) {
+    private static IEnumerable<Tree> CreateTerminalNodes(int state, ?IDENT?Problem problem) {
       switch(state) {
         ?CREATETERMINALNODECODE?
         default: { throw new ArgumentException(""Unknown state index"" + state); }
       }
-    }
-
-    private int NextAlternative(SearchTreeNode node) {
-?RETURNNEXTALTERNATIVECODE?
     }
 
@@ -95 +76 @@
 
     private void Start() {
+      const int MAX_SECONDS = 100000;
       var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
       int n = 0;
@@ -100 +82 @@
       long sumSize = 0;
       var sumF = 0.0;
+      var terminationTimer = new Stopwatch();
       var sw = new System.Diagnostics.Stopwatch();
       sw.Start();
-      for(int d = 1; d < 20; d++) {
-        foreach(var t in GenerateTrees(d)) {
+      terminationTimer.Start();
+      for(int depth = 1; terminationTimer.Elapsed.TotalSeconds < MAX_SECONDS; depth ++) {
+        Console.WriteLine(""Depth {0}:"", depth);
+        foreach(var t in GenerateTrees(0, depth)) {
           var f = problem.Evaluate(t);
-          
+          //t.PrintTree(0); Console.WriteLine();
+          var size = t.GetSize();
+          sumSize += size;
+          sumDepth += depth;
           n++;    
           sumF += f;
           if (problem.IsBetter(f, bestF)) {
             bestF = f;
-            Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, 0, 0);
+            Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, size, depth);
           }
           if (n % 1000 == 0) {
             sw.Stop();
-            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);
+            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)"",
+                              n, bestF, sumF/1000.0, sumSize/1000.0, sumDepth/1000.0, 1000.0 / sw.ElapsedMilliseconds, terminationTimer.Elapsed.TotalSeconds);
             sumSize = 0;
             sumDepth = 0;
             sumF = 0.0;
             sw.Restart();
+            if(terminationTimer.Elapsed.TotalSeconds >= MAX_SECONDS) break;
           }
         }
@@ -130 +120 @@
       solverSourceCode.Append(solverTemplate)
         .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
-        .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar))
         .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar, terminals))
       ;
 
       problemSourceCode.Append(solverSourceCode.ToString());
-    }
-
-
-
-    private string GenerateSampleAlternativeSource(IGrammar grammar) {
-      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
-      var sb = new SourceBuilder();
-      int stateCount = 0;
-      foreach (var s in grammar.Symbols) {
-        sb.AppendFormat("case {0}: ", stateCount++);
-        if (grammar.IsTerminal(s)) {
-          // ignore
-        } else {
-          var terminalAltIndexes = grammar.GetAlternatives(s)
-            .Select((alt, idx) => new { alt, idx })
-            .Where((p) => p.alt.All(symb => grammar.IsTerminal(symb)))
-            .Select(p => p.idx);
-          var nonTerminalAltIndexes = grammar.GetAlternatives(s)
-            .Select((alt, idx) => new { alt, idx })
-            .Where((p) => p.alt.Any(symb => grammar.IsNonTerminal(symb)))
-            .Select(p => p.idx);
-          var hasTerminalAlts = terminalAltIndexes.Any();
-          var hasNonTerminalAlts = nonTerminalAltIndexes.Any();
-          if (hasTerminalAlts && hasNonTerminalAlts) {
-            sb.Append("if(random.NextDouble() < TerminalProbForDepth(depth)) {").BeginBlock();
-            GenerateReturnStatement(terminalAltIndexes, sb);
-            sb.Append("} else {");
-            GenerateReturnStatement(nonTerminalAltIndexes, sb);
-            sb.Append("}").EndBlock();
-          } else {
-            GenerateReturnStatement(grammar.NumberOfAlternatives(s), sb);
-          }
-        }
-      }
-      return sb.ToString();
     }
 
@@ -179 +133 @@
         if (grammar.IsTerminal(s)) {
           sb.AppendFormat("case {0}: {{", allSymbols.IndexOf(s)).BeginBlock();
-          sb.AppendFormat("var t = new {0}Tree();", s.Name).AppendLine();
           var terminal = terminals.Single(t => t.Ident == s.Name);
+          if (terminal.Constraints.Any(c => c.Type == ConstraintNodeType.Range)) {
+            throw new NotSupportedException("Sorry the brute force solver does not support RANGE constraints");
+          }
+          sb.AppendFormat("{0}Tree t = null;", terminal.Ident).AppendLine();
+          // create nested loop to produce all combinations of values (only set constraints)
           foreach (var constr in terminal.Constraints) {
-            if (constr.Type == ConstraintNodeType.Set) {
-              sb.Append("{").BeginBlock();
-              sb.AppendLine("throw new NotImplementedException(\"Enumeration of terminal values is not implemented.\");");
-              sb.AppendFormat("//var elements = problem.GetAllowed{0}_{1}().ToArray();", terminal.Ident, constr.Ident).AppendLine();
-              sb.AppendFormat("//t.{0} = elements[random.Next(elements.Length)]; ", constr.Ident).EndBlock();
-              sb.AppendLine("}");
-            } else {
-              sb.Append("{").BeginBlock();
-              sb.AppendLine("throw new NotSupportedException(\"The brute force solver does not support RANGE constraints\");");
-              sb.AppendLine("}");
-            }
+            sb.AppendFormat("foreach(var {1} in problem.GetAllowed{0}_{1}()) {{;", terminal.Ident, constr.Ident).BeginBlock();
           }
-          sb.AppendLine("return t;").EndBlock();
-          sb.Append("}");
+          sb.AppendFormat("t = new {0}Tree();", terminal.Ident).AppendLine();
+
+          foreach (var constr in terminal.Constraints.Reverse()) {
+            sb.AppendFormat("t.{0} = {0};", constr.Ident).EndBlock();
+            sb.AppendLine("}");
+          }
+
+          sb.AppendLine("yield return t; ").EndBlock();
+
+          sb.AppendLine(" break; }");
         }
       }
       return sb.ToString();
     }
-
-    private void GenerateReturnStatement(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.AppendFormat("return new int[] {{ {0} }}[random.Next({1})]; ", idxStr, idxs.Count()).AppendLine();
-      }
-    }
-
-    private void GenerateReturnStatement(int nAlts, SourceBuilder sb) {
-      if (nAlts > 1) {
-        sb.AppendFormat("return random.Next({0});", nAlts).AppendLine();
-      } else if (nAlts == 1) {
-        sb.AppendLine("return 0; ");
-      } else {
-        sb.AppendLine("throw new InvalidProgramException();");
-      }
-    }
   }
 }

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

@@ -14 +14 @@
 using System;
 using System.Text.RegularExpressions;
+using System.Diagnostics;
 ";
 
@@ -63 +64 @@
       // leave subtrees uninitialized
     }
-    public Tree(int altIdx, Tree[] subtrees) {
+    public Tree(int altIdx, Tree[] subtrees = null) {
       this.altIdx = altIdx;
       this.subtrees = subtrees;
+    }
+    public int GetSize() {
+      if(subtrees==null) return 1;
+      else return 1 + subtrees.Sum(t=>t.GetSize());
+    }
+    public int GetDepth() {
+      if(subtrees==null) return 1;
+      else return 1 + subtrees.Max(t=>t.GetDepth());
+    }
+    public void PrintTree(int curState) {
+      Console.Write(""{0} "", Grammar.symb[curState]);
+      if(subtrees != null) {
+        if(subtrees.Length==1) {
+          subtrees[0].PrintTree(Grammar.transition[curState][altIdx]);
+        } else {
+          for(int i=0;i<subtrees.Length;i++) {
+            subtrees[i].PrintTree(Grammar.transition[curState][i]);
+          }
+        }
+      }
     }
   }
@@ -294 +315 @@
     }
 
-    private void GenerateSwitchStatement(IEnumerable<Sequence> alts, SourceBuilder sb)
-    {
+    private void GenerateSwitchStatement(IEnumerable<Sequence> alts, SourceBuilder sb) {
       sb.Append("switch(_t.altIdx) {").BeginBlock();
       // generate a case for each alternative
@@ -340 +360 @@
     }
 
-    
+
 
     private string GenerateTransitionTable(IGrammar grammar) {

branches/HeuristicLab.Problems.GPDL/Examples/symbreg Koza.txt

@@ -106 +106 @@
     | Multiplication<<row, out val>>
     | Var<<out varName>>                                   SEM << val = GetValue(x, varName, row); >>
-    | ERC<<out val>> 
+    /* | ERC<<out val>>  */
   .
 

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Problems.GPDL.sln

@@ -1 +1 @@
 
 Microsoft Visual Studio Solution File, Format Version 12.00
-# Visual Studio 2013
-VisualStudioVersion = 12.0.21005.1
-MinimumVisualStudioVersion = 10.0.40219.1
+# Visual Studio 2012
 Project("{2150E333-8FDC-42A3-9474-1A3956D46DE8}") = "Solution Items", "Solution Items", "{3768D612-38EB-47D8-9E79-75D8E5AB00A8}"
   ProjectSection(SolutionItems) = preProject
@@ -9 +7 @@
     Performance1.psess = Performance1.psess
     PreBuildEvent.cmd = PreBuildEvent.cmd
+    TestAnt.bat = TestAnt.bat
     TestExamples.bat = TestExamples.bat
   EndProjectSection
@@ -117 +116 @@
     {E2060931-6700-464B-9E82-50846D7AE4E9} = {3768D612-38EB-47D8-9E79-75D8E5AB00A8}
   EndGlobalSection
+  GlobalSection(Performance) = preSolution
+    HasPerformanceSessions = true
+  EndGlobalSection
 EndGlobal

branches/HeuristicLab.Problems.GPDL/TestExamples.bat

@@ +1 @@
+del *.exe
+del *.cs
+
 for /f "delims=" %%i in ('dir /b /s Examples\*.txt') do (
   GpdlCompiler\bin\Debug\GpdlCompiler.exe "%%i"
@@ -4 +7 @@
 
 for /f "delims=" %%i in ('dir /b *.cs') do (
-  csc /optimize+ "%%i"
+  csc /optimize+ /debug- "%%i"
 )