Changeset 10415

Timestamp:

01/28/14 19:23:46 (11 years ago)

Author:

gkronber

Message:

#2026 implemented prevention of resampling of known nodes.

Location:

branches/HeuristicLab.Problems.GPDL

Files:

• CodeGenerator/MonteCarloTreeSearchCodeGen.cs (modified) (10 diffs)
• CodeGenerator/ProblemCodeGen.cs (modified) (1 diff)
• Examples/OneMaxBinary.txt (added)
• Examples/OneMaxTernary.txt (added)
• HeuristicLab.Problems.GPDL.sln (modified) (1 diff)

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

@@ -15 +15 @@
     public double sumQuality = 0.0;
     public double bestQuality = double.NegativeInfinity;
-    public bool ready;
+    public bool done;
     public SearchTreeNode[] children;
-
+    public double[] Ucb {
+      get {
+        return (from c in children
+                select ?IDENT?Solver.UCB(this, c)
+               ).ToArray();
+      }
+    }
     public SearchTreeNode() {
     }
@@ -37 +43 @@
 
     private void SampleTree(SearchTreeNode searchTree, Stack<Tuple<Tree, int, int>> extensionPoints) {
-      const int RANDOM_TRIES = 100;
-      if(extensionPoints.Count == 0) return; // nothing to do
+      const int RANDOM_TRIES = 1000;
+      if(extensionPoints.Count == 0) {
+        searchTree.done = true;
+        return; // nothing to do
+      }
       var extensionPoint = extensionPoints.Pop();
       Tree parent = extensionPoint.Item1;
@@ -44 +53 @@
       int subtreeIdx = extensionPoint.Item3;
       Tree t = null;
-      
       if(searchTree.tries < RANDOM_TRIES || Grammar.subtreeCount[state] == 0) {
         t = SampleTreeRandom(state);
@@ -53 +61 @@
             searchTree.children = new SearchTreeNode[] { new SearchTreeNode() } ;
           SampleTree(searchTree.children[0], extensionPoints);
+          if(searchTree.children[0].done) searchTree.done = true;
         } else {
           // fill up all remaining slots randomly
@@ -81 +90 @@
             extensionPoints.Push(Tuple.Create(t, Grammar.transition[state][i], i));
           }
-          SampleTree(searchTree, extensionPoints);
-        }
-      }
+          SampleTree(searchTree, extensionPoints);          
+        }
+      }      
       Debug.Assert(parent.subtrees[subtreeIdx] == null);
       parent.subtrees[subtreeIdx] = t;
@@ -95 +104 @@
         return altIdx;
       } else {
+        altIdx = Array.FindIndex(searchTree.children, (e) => !e.done && e.tries < 1000);
+        if(altIdx >= 0) return altIdx;
         // 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].done && searchTree.children[idx].tries < minSamples) {
+        //    minSamples = searchTree.children[idx].tries;
+        //    altIdx = idx;
+        //  }
+        //}
+        // select the alternative with the largest average
         altIdx = 0;
-        int minSamples = searchTree.children[altIdx].tries;
+        double bestAverage = UCB(searchTree, searchTree.children[altIdx]);
         for(int idx = 1; idx < searchTree.children.Length; idx++) {
-          if(searchTree.children[idx].tries < minSamples) {
-            minSamples = searchTree.children[idx].tries;
+          if (!searchTree.children[idx].done && UCB(searchTree, searchTree.children[idx]) > UCB(searchTree, searchTree.children[altIdx])) {
             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;
-        //   }
-        // }
+
+        searchTree.done = searchTree.children.All(c=>c.done);
         return altIdx;
       }
     }
 
-    private double UCB(SearchTreeNode parent, SearchTreeNode n) {
+    public static double UCB(SearchTreeNode parent, SearchTreeNode n) {
       Debug.Assert(parent.tries >= n.tries);
       Debug.Assert(n.tries > 0);
-      return n.sumQuality / n.tries + Math.Sqrt((2 * Math.Log(parent.tries)) / n.tries ); // constant is dependent fitness function values
+      return n.sumQuality / n.tries + Math.Sqrt((10 * Math.Log(parent.tries)) / n.tries ); // constant is dependent fitness function values
     }
 
@@ -144 +157 @@
         if(t.subtrees != null) { 
           Debug.Assert(t.subtrees.Length == 1);
-          if(searchTree.children!=null) {
+          if(searchTree.children != null) {
             trees.Push(t.subtrees[0]);
             UpdateSearchTree(searchTree.children[t.altIdx], trees, quality);
           }
         } else {
-          if(searchTree.children!=null) {
+          if(searchTree.children != null) {
             Debug.Assert(searchTree.children.Length == 1);
             UpdateSearchTree(searchTree.children[0], trees, quality);
@@ -225 +238 @@
       var sw = new System.Diagnostics.Stopwatch();
       sw.Start();
-      while (true) {
+      while (!searchTree.done) {
 
         int steps, depth;
@@ -297 +310 @@
             GenerateReturnStatement(terminalAltIndexes, sb);
             sb.Append("} else {");
-            GenerateReturnStatement(nonTerminalAltIndexes, sb);
+            GenerateReturnStatement(nonTerminalAltIndexes.Concat(terminalAltIndexes), sb);
             sb.Append("}").EndBlock();
           } else {
@@ -317 +330 @@
           foreach (var constr in terminal.Constraints) {
             if (constr.Type == ConstraintNodeType.Set) {
-              sb.Append("{").BeginBlock();
-              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("}");
+              throw new NotImplementedException("Support for terminal symbols with attributes is not yet implemented.");
+              // sb.Append("{").BeginBlock();
+              // 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 {
               throw new NotSupportedException("The MTCS solver does not support RANGE constraints.");

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

@@ -151 +151 @@
       // var randomSearchCodeGen = new RandomSearchCodeGen();
       // randomSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
-      //var bruteForceSearchCodeGen = new BruteForceCodeGen();
-      //bruteForceSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
+      // var bruteForceSearchCodeGen = new BruteForceCodeGen();
+      // bruteForceSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
       var mctsCodeGen = new MonteCarloTreeSearchCodeGen();
       mctsCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);

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

@@ -43 +43 @@
     Examples\multi-output-multiplier.txt = Examples\multi-output-multiplier.txt
     Examples\Multiplexer.txt = Examples\Multiplexer.txt
+    Examples\OneMaxBinary.txt = Examples\OneMaxBinary.txt
     Examples\OnlyTerminals.txt = Examples\OnlyTerminals.txt
     Examples\Rastrigin.txt = Examples\Rastrigin.txt