Changeset 10409 for branches/HeuristicLab.Problems.GPDL

Timestamp:

01/28/14 16:25:36 (10 years ago)

Author:

gkronber

Message:

#2026 prepare for inclusion of terminals into the search tree

Location:

branches/HeuristicLab.Problems.GPDL

Files:

• CodeGenerator/MonteCarloTreeSearchCodeGen.cs (modified) (3 diffs)
• Examples/symbreg Koza.txt (modified) (1 diff)

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

@@ -74 +74 @@
           Debug.Assert(searchTree.children.Length == Grammar.transition[state].Length);
           Debug.Assert(searchTree.tries - RANDOM_TRIES - 1 == searchTree.children.Where(c=>c!=null).Sum(c=>c.tries));
-          // check if there is an unchecked alternative
-          var altIdx = Array.FindIndex(searchTree.children, (e) => e == null);
-          if(altIdx != -1) {
-            Debug.Assert(searchTree.children[altIdx] == null);
-            searchTree.children[altIdx] = new SearchTreeNode();
-            t = new Tree(altIdx, new Tree[1]);
-            extensionPoints.Push(Tuple.Create(t, Grammar.transition[state][altIdx], 0));
-            SampleTree(searchTree.children[altIdx], extensionPoints);
-          } else {
-            // select the least sampled alternative
-            //altIdx = 0;
-            //int minSamples = searchTree.children[altIdx].tries;
-            //for(int idx = 1; idx < searchTree.children.Length; idx++) {
-            //  if(searchTree.children[idx].tries < minSamples) {
-            //    minSamples = searchTree.children[idx].tries;
-            //    altIdx = idx;
-            //  }
-            //}
-            // select the alternative with the largest average
-            altIdx = 0;
-            double bestAverage = UCB(searchTree, searchTree.children[altIdx]);
-            for(int idx = 1; idx < searchTree.children.Length; idx++) {
-              if (UCB(searchTree, searchTree.children[idx]) > UCB(searchTree, searchTree.children[altIdx])) {
-                altIdx = idx;
-              }
-            }
-            t = new Tree(altIdx, new Tree[1]);
-            extensionPoints.Push(Tuple.Create(t, Grammar.transition[state][altIdx], 0));
-            SampleTree(searchTree.children[altIdx], extensionPoints);
-          }
+          var altIdx = SelectAlternative(searchTree);
+          t = new Tree(altIdx, new Tree[1]);
+          extensionPoints.Push(Tuple.Create(t, Grammar.transition[state][altIdx], 0));
+          SampleTree(searchTree.children[altIdx], extensionPoints);
         } else {
           // multiple subtrees
@@ -116 +90 @@
       Debug.Assert(parent.subtrees[subtreeIdx] == null);
       parent.subtrees[subtreeIdx] = t;
+    }
+
+    private int SelectAlternative(SearchTreeNode searchTree) {
+      // any alternative not yet explored?
+      var altIdx = Array.FindIndex(searchTree.children, (e) => e == null);
+      if(altIdx >= 0) {
+        searchTree.children[altIdx] = new SearchTreeNode();
+        return altIdx;
+      } else {
+        // select the least sampled alternative
+        altIdx = 0;
+        int minSamples = searchTree.children[altIdx].tries;
+        for(int idx = 1; idx < searchTree.children.Length; idx++) {
+          if(searchTree.children[idx].tries < minSamples) {
+            minSamples = searchTree.children[idx].tries;
+            altIdx = idx;
+          }
+        }
+        // select the alternative with the largest average
+        // altIdx = 0;
+        // double bestAverage = UCB(searchTree, searchTree.children[altIdx]);
+        // for(int idx = 1; idx < searchTree.children.Length; idx++) {
+        //   if (UCB(searchTree, searchTree.children[idx]) > UCB(searchTree, searchTree.children[altIdx])) {
+        //     altIdx = idx;
+        //   }
+        // }
+        return altIdx;
+      }
     }
 
@@ -349 +351 @@
               sb.AppendLine("}");
             } else {
-              sb.Append("{").BeginBlock();
-              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("t.{0} = random.NextDouble() * (max - min) + min;", constr.Ident).EndBlock();
-              sb.AppendLine("}");
+              throw new NotSupportedException("The MTCS solver does not support RANGE constraints.");
             }
           }

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

@@ -93 +93 @@
     | Multiplication<<row, out val>>
     | Var<<out variable>>                                  SEM << val = x[row, variable]; >>
-    /* | ERC<<out val>>  */
+    | ERC<<out val>> 
   .