Changeset 10384

Timestamp:

01/22/14 18:09:44 (11 years ago)

Author:

gkronber

Message:

#2026 fixed random search code generation

Location:

branches/HeuristicLab.Problems.GPDL/CodeGenerator

Files:

• CodeGenerator.csproj (modified) (1 diff)
• ProblemCodeGen.cs (modified) (10 diffs)
• RandomSearchCodeGen.cs (modified) (9 diffs)

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

@@ -36 +36 @@
   </ItemGroup>
   <ItemGroup>
-    <Compile Include="BruteForceCodeGen.cs" />
     <Compile Include="ProblemCodeGen.cs" />
     <Compile Include="SourceBuilder.cs" />

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

@@ -33 +33 @@
 
   // generic interface for communication from problem interpretation to solver
-  public interface ISolverState {
-    void Reset();
-    int PeekNextAlternative(); // in alternative nodes returns the index of the alternative that should be followed
-    void Follow(int idx); // next: derive the NT symbol with index=idx;
-    void Unwind(); // finished with deriving the NT symbol
-  }
+  // public interface ISolverState {
+  //   void Reset();
+  //   int PeekNextAlternative(); // in alternative nodes returns the index of the alternative that should be followed
+  //   void Follow(int idx); // next: derive the NT symbol with index=idx;
+  //   void Unwind(); // finished with deriving the NT symbol
+  // }
 
   public sealed class ?IDENT?Problem {
@@ -53 +53 @@
     }
 
-    private ISolverState _state;
-    public double Evaluate(ISolverState _state) {
-      this._state = _state;
+    private Tree _t;
+    public double Evaluate(Tree _t) {
+      this._t = _t;
 #region objective function (MINIMIZE / MAXIMIZE section)
 ?FITNESSFUNCTION?
@@ -216 +216 @@
       sb.AppendFormat("public class {0}Tree : Tree {{", terminal.Ident).BeginBlock();
       foreach (var att in terminal.FieldDefinitions) {
-        sb.AppendFormat("{0} {1};", att.Type, att.Identifier).AppendLine();
+        sb.AppendFormat("public {0} {1};", att.Type, att.Identifier).AppendLine();
       }
       sb.AppendFormat(" public {0}Tree(Random random, ?IDENT?Problem problem) : base() {{", terminal.Ident).BeginBlock();
@@ -222 +222 @@
         if (constr.Type == ConstraintNodeType.Set) {
           sb.AppendLine("{").BeginBlock();
-          sb.AppendFormat(" var elements = problem.GetAllowed{0}_{1}().ToArray();", terminal.Ident, constr.Ident).AppendLine();
+          sb.AppendFormat("var elements = problem.GetAllowed{0}_{1}().ToArray();", terminal.Ident, constr.Ident).AppendLine();
           sb.AppendFormat("{0} = elements[random.Next(elements.Length)]; ", constr.Ident).AppendLine();
           sb.AppendLine("}").EndBlock();
@@ -229 +229 @@
           sb.AppendFormat(" var max = problem.GetMax{0}_{1}();", terminal.Ident, constr.Ident).AppendLine();
           sb.AppendFormat(" var min = problem.GetMin{0}_{1}();", terminal.Ident, constr.Ident).AppendLine();
-          sb.AppendFormat("{0} = random.NextDouble() * (max - min) + min ", constr.Ident).AppendLine();
+          sb.AppendFormat("{0} = random.NextDouble() * (max - min) + min;", constr.Ident).AppendLine();
           sb.AppendLine("}").EndBlock();
         }
@@ -268 +268 @@
       else
         actualParameter = string.Empty;
-      sb.AppendLine("_state.Reset();");
-      sb.AppendFormat("{0}(_state, {1});", s.Name, actualParameter).AppendLine();
+      sb.AppendFormat("{0}(_t, {1});", s.Name, actualParameter).AppendLine();
       sb.AppendLine("}").EndBlock();
     }
@@ -275 +274 @@
     private void GenerateInterpreterMethod(AttributedGrammar g, ISymbol s, SourceBuilder sb) {
       if (!s.Attributes.Any())
-        sb.AppendFormat("private void {0}(ISolverState _state) {{", s.Name).BeginBlock();
+        sb.AppendFormat("private void {0}(Tree _t) {{", s.Name).BeginBlock();
       else
-        sb.AppendFormat("private void {0}(ISolverState _state, {1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
+        sb.AppendFormat("private void {0}(Tree _t, {1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
 
       // generate local definitions
@@ -297 +296 @@
 
     private void GenerateSwitchStatement(IEnumerable<Sequence> alts, SourceBuilder sb) {
-      sb.Append("switch(_state.PeekNextAlternative()) {").BeginBlock();
+      sb.Append("switch(_t.altIdx) {").BeginBlock();
       // generate a case for each alternative
       int i = 0;
@@ -321 +320 @@
         sb.Append(action.Code + ";");
       else if (!s.Attributes.Any())
-        sb.AppendFormat("_state.Follow({0}); {1}(_state); _state.Unwind();", idx, s.Name);
-      else sb.AppendFormat("_state.Follow({0}); {1}(_state, {2}); _state.Unwind();", idx, s.Name, s.GetAttributeString());
+        sb.AppendFormat("{1}(_t.subtrees[{0}]);", idx, s.Name);
+      else sb.AppendFormat("{1}(_t.subtrees[{0}], {2}); ", idx, s.Name, s.GetAttributeString());
       sb.AppendLine();
     }
@@ -329 +328 @@
       // if the terminal symbol has attributes then we must samples values for these attributes
       if (!s.Attributes.Any())
-        sb.AppendFormat("private void {0}(ISolverState _state) {{", s.Name).BeginBlock();
+        sb.AppendFormat("private void {0}(Tree _t) {{", s.Name).BeginBlock();
       else
-        sb.AppendFormat("private void {0}(ISolverState _state, {1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
+        sb.AppendFormat("private void {0}(Tree _t, {1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
 
       // each field must match a formal parameter, assign a value for each parameter
       int i = 0;
       foreach (var element in s.Attributes) {
-        sb.AppendFormat("_state.Follow({0});", i++).AppendLine();
-        sb.AppendFormat("{0} = Get{1}_{0}(_state);", element.Name, s.Name).AppendLine();
-        sb.AppendFormat("_state.Unwind();").AppendLine();
+        sb.AppendFormat("{0} = (_t as {1}Tree).{0};", element.Name, s.Name).AppendLine();
       }
       sb.Append("}").EndBlock();

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

@@ -25 +25 @@
 
     
-    public sealed class SolverState : ISolverState {
+    public sealed class SolverState  {
       public int curDepth;
       public int steps;
       public int depth;
-      private readonly Stack<Tree> nodes;
+      // private readonly Stack<Tree> nodes;
       private readonly ?IDENT?Problem problem;
+      private Random random;
 
       public SolverState(?IDENT?Problem problem, int seed) {
         this.problem = problem;
-        this.nodes = new Stack<Tree>();
+        // this.nodes = new Stack<Tree>();
         
-        // create a random tree
-        var tree = SampleTree(new Random(seed), 0, -1);  // state 0 is the state for the start symbol
-        nodes.Push(tree);
-      }
-
-      public void Reset() {
-        // stack must contain only the root of the tree
-        System.Diagnostics.Debug.Assert(nodes.Count == 1);
-      }
-
-      private Tree SampleTree(Random random, int state, int altIdx) {
-        // Console.Write(state + "" "");        
+        this.random = new Random(seed);
+        // nodes.Push(tree);
+      }
+
+      // public void Reset() {
+      //   // stack must contain only the root of the tree
+      //   System.Diagnostics.Debug.Assert(nodes.Count == 1);
+      // }
+
+      public Tree SampleTree() {
+        return SampleTree(0);
+      }
+
+      private Tree SampleTree(int state) {
+        // Console.Write(state + "" "" );
         curDepth += 1;
         steps += 1;
         depth = Math.Max(depth, curDepth);
-        var t = new Tree(state, altIdx, subtreeCount[state]);
-
-        // t.symbol = symb.Length > state ? symb[state] : ""TERM"";
-        // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case)
-        if(subtreeCount[state] == 1) {
-          var targetStates = transition[state];
-          var i = SampleAlternative(random, state);
-          if(targetStates.Length == 0) {
-            //terminal
-            t.subtrees.Add(SampleTree(random, -1, i));
+        Tree t = null;
+
+        // terminals
+        if(subtreeCount[state] == 0) {
+          t = CreateTerminalNode(state);
+        } else {
+          
+          t = new Tree(state, -1, subtreeCount[state]);
+          if(subtreeCount[state] < 1) throw new ArgumentException();
+          // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case)
+          if(subtreeCount[state] == 1) {
+            var targetStates = transition[state];
+            var i = SampleAlternative(random, state);
+            t.altIdx = i;
+            t.subtrees.Add(SampleTree(targetStates[i]));
           } else {
-            t.subtrees.Add(SampleTree(random, targetStates[i], i));
-          }
-        } else {
-          // if the symbol contains only one sequence we must use create sub-trees for each symbol in the sequence
-          for(int i = 0; i < subtreeCount[state]; i++) {
-            t.subtrees.Add(SampleTree(random, transition[state][i], i));
+            // if the symbol contains only one sequence we must use create sub-trees for each symbol in the sequence
+            for(int i = 0; i < subtreeCount[state]; i++) {
+              t.subtrees.Add(SampleTree(transition[state][i]));
+            }
           }
         }
@@ -74 +81 @@
       }
 
-      public int PeekNextAlternative() {
-        // this must only be called nodes that contain alternatives and therefore must only have single-symbols alternatives
-        System.Diagnostics.Debug.Assert(nodes.Peek().subtrees.Count == 1);
-        return nodes.Peek().subtrees[0].altIdx;
-      }
-
-      public void Follow(int idx) {
-        nodes.Push(nodes.Peek().subtrees[idx]);
-      }
-
-      public void Unwind() {
-        nodes.Pop();
-      }
+      private Tree CreateTerminalNode(int state) {
+        switch(state) {
+          ?CREATETERMINALNODECODE?
+          default: { throw new ArgumentException(""Unknown state index"" + state); }
+        }
+      }
+
+      // public int PeekNextAlternative() {
+      //   // this must only be called nodes that contain alternatives and therefore must only have single-symbols alternatives
+      //   System.Diagnostics.Debug.Assert(nodes.Peek().subtrees.Count == 1);
+      //   return nodes.Peek().subtrees[0].altIdx;
+      // }
+      // 
+      // public void Follow(int idx) {
+      //   nodes.Push(nodes.Peek().subtrees[idx]);
+      // }
+      // 
+      // public void Unwind() {
+      //   nodes.Pop();
+      // }
 
       private int SampleAlternative(Random random, int state) {
@@ -155 +169 @@
       while (true) {
 
-        // must make sure that calling the start-symbol multiple times in the fitness function always leads to the same path through the grammar
-        // so we use a PRNG for generating seeds for a separate PRNG that is reset each time the start symbol is called
-        
         var _state = new SolverState(problem, seedRandom.Next());
-
-        var f = problem.Evaluate(_state);
+        var _t = _state.SampleTree();
+        var f = problem.Evaluate(_t);
  
-        n++;
-        sumSize += _state.steps;
-        sumDepth += _state.depth;
+        n++;    
+        // sumSize += _state.steps;
+        // sumDepth += _state.depth;
         sumF += f;
         if (IsBetter(f, bestF)) {
           bestF = f;
-          Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, _state.steps, _state.depth);
+          Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, 0, 0 /* _state.steps, _state.depth */);
         }
         if (n % 1000 == 0) {
@@ -196 +207 @@
         .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", "))
         .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar))
+        .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar))
         .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
         .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar))
-//        .Replace("?SAMPLETERMINALCODE?", GenerateSampleTerminalSource(grammar))
+        //        .Replace("?SAMPLETERMINALCODE?", GenerateSampleTerminalSource(grammar))
       ;
 
@@ -217 +229 @@
     //  return sb.ToString();
     //}
-
+    private string GenerateCreateTerminalCode(IGrammar grammar) {
+      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
+      var sb = new SourceBuilder();
+      var allSymbols = grammar.Symbols.ToList();
+      foreach (var s in grammar.Symbols) {
+        if (grammar.IsTerminal(s)) {
+          sb.AppendFormat("case {0}: {{ return new {1}Tree(random, problem); }}", allSymbols.IndexOf(s), s.Name).AppendLine();
+        }
+      }
+      return sb.ToString();
+    }
 
     private string GenerateTransitionTable(IGrammar grammar) {
@@ -225 +247 @@
       // state idx = idx of the corresponding symbol in the grammar
       var allSymbols = grammar.Symbols.ToList();
-      var attributes = new List<string>();
       foreach (var s in grammar.Symbols) {
         var targetStates = new List<int>();
         if (grammar.IsTerminal(s)) {
-          foreach (var att in s.Attributes) {
-            targetStates.Add(allSymbols.Count + attributes.Count);
-            attributes.Add(s.Name + "_" + att);
-          }
         } else {
           if (grammar.NumberOfAlternatives(s) > 1) {
@@ -253 +270 @@
         sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine();
       }
-      for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
-        sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();
-        sb.AppendFormat("{{ {0} , new int[] {{ }} }},", attIdx + allSymbols.Count).AppendLine();
-      }
       return sb.ToString();
     }
@@ -265 +278 @@
       // state idx = idx of the corresponding symbol in the grammar
       var allSymbols = grammar.Symbols.ToList();
-      var attributes = new List<string>();
       foreach (var s in grammar.Symbols) {
-        int subtreeCount;
+        int subtreeCount = 0;
         if (grammar.IsTerminal(s)) {
-          subtreeCount = s.Attributes.Count();
-          attributes.AddRange(s.Attributes.Select(att => s.Name + "_" + att.Name));
         } else {
           if (grammar.NumberOfAlternatives(s) > 1) {
@@ -284 +294 @@
       }
 
-      for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
-        sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();
-        sb.AppendFormat("{{ {0} , 1 }},", attIdx + allSymbols.Count).AppendLine();
-      }
       return sb.ToString();
     }