Changeset 15438 for branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionStatic.cs

Timestamp:

10/28/17 19:56:51 (6 years ago)

Author:

gkronber

Message:

#2796 refactoring to simplify the code

File:

• branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionStatic.cs (modified) (23 diffs)

branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionStatic.cs

@@ -26 +26 @@
 using System.Linq;
 using System.Text;
-using HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression.Policies;
 using HeuristicLab.Core;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
@@ -99 +98 @@
       internal readonly Tree tree;
       internal readonly Func<byte[], int, double> evalFun;
-      internal readonly IPolicy treePolicy;
       // MCTS might get stuck. Track statistics on the number of effective rollouts
       internal int totalRollouts;
@@ -145 +143 @@
       public State(IRegressionProblemData problemData, uint randSeed, int maxVariables, bool scaleVariables,
         int constOptIterations, double lambda,
-        IPolicy treePolicy = null,
         bool collectParetoOptimalModels = false,
         double lowerEstimationLimit = double.MinValue, double upperEstimationLimit = double.MaxValue,
@@ -187 +184 @@
         this.testEvaluator = new ExpressionEvaluator(testY.Length, lowerEstimationLimit, upperEstimationLimit);
 
-        this.automaton = new Automaton(x, new SimpleConstraintHandler(maxVariables), allowProdOfVars, allowExp, allowLog, allowInv, allowMultipleTerms);
-        this.treePolicy = treePolicy ?? new EpsilonGreedy();
+        this.automaton = new Automaton(x, allowProdOfVars, allowExp, allowLog, allowInv, allowMultipleTerms, maxVariables);
         this.tree = new Tree() {
           state = automaton.CurrentState,
-          actionStatistics = treePolicy.CreateActionStatistics(),
           expr = "",
           level = 0
@@ -469 +464 @@
     public static IState CreateState(IRegressionProblemData problemData, uint randSeed, int maxVariables = 3,
       bool scaleVariables = true, int constOptIterations = -1, double lambda = 0.0,
-      IPolicy policy = null,
       bool collectParameterOptimalModels = false,
       double lowerEstimationLimit = double.MinValue, double upperEstimationLimit = double.MaxValue,
@@ -479 +473 @@
       ) {
       return new State(problemData, randSeed, maxVariables, scaleVariables, constOptIterations, lambda,
-        policy, collectParameterOptimalModels,
+        collectParameterOptimalModels,
         lowerEstimationLimit, upperEstimationLimit,
         allowProdOfVars, allowExp, allowLog, allowInv, allowMultipleTerms);
@@ -499 +493 @@
       var eval = mctsState.evalFun;
       var rand = mctsState.random;
-      var treePolicy = mctsState.treePolicy;
       double q = 0;
       bool success = false;
@@ -505 +498 @@
 
         automaton.Reset();
-        success = TryTreeSearchRec2(rand, tree, automaton, eval, treePolicy, mctsState, out q);
+        success = TryTreeSearchRec2(rand, tree, automaton, eval, mctsState, out q);
         mctsState.totalRollouts++;
       } while (!success && !tree.Done);
@@ -517 +510 @@
 
     // search forward
-    private static bool TryTreeSearchRec2(IRandom rand, Tree tree, Automaton automaton, Func<byte[], int, double> eval, IPolicy treePolicy,
+    private static bool TryTreeSearchRec2(IRandom rand, Tree tree, Automaton automaton, 
+      Func<byte[], int, double> eval,
       State state,
       out double q) {
@@ -545 +539 @@
           int selectedIdx = 0;
           if (state.children[tree].Count > 1) {
-            selectedIdx = treePolicy.Select(state.children[tree].Select(ch => ch.actionStatistics), rand);
+            selectedIdx = SelectInternal(state.children[tree], rand);
           }
 
@@ -579 +573 @@
               if (!state.nodes.TryGetValue(hc, out child)) {
                 child = new Tree() {
-                  children = null,
                   state = possibleFollowStates[i],
-                  actionStatistics = treePolicy.CreateActionStatistics(),
                   expr = actionString + automaton.GetActionString(automaton.CurrentState, possibleFollowStates[i]),
                   level = tree.level + 1
@@ -591 +583 @@
                 // whenever we join paths we need to propagate back the statistics of the existing node through the newly created link
                 // to all parents 
-                BackpropagateStatistics(child.actionStatistics, tree, state);
+                BackpropagateStatistics(tree, state, child.visits);
               } else {
                 // prevent cycles
@@ -599 +591 @@
             } else {
               child = new Tree() {
-                children = null,
                 state = possibleFollowStates[i],
-                actionStatistics = treePolicy.CreateActionStatistics(),
                 expr = actionString + automaton.GetActionString(automaton.CurrentState, possibleFollowStates[i]),
                 level = tree.level + 1
@@ -639 +629 @@
         automaton.GetCode(out code, out nParams);
         q = eval(code, nParams);
-        // Console.WriteLine("{0:N4}\t{1}", q*q, tree.expr);
         success = true;
-        BackpropagateQuality(tree, q, treePolicy, state);
+        BackpropagateQuality(tree, q, state); 
       } else {
         // we got stuck in roll-out (not evaluation necessary!)
-        // Console.WriteLine("\t" + ExprStr(automaton) + " STOP");
         q = 0.0;
         success = false;
@@ -659 +647 @@
     }
 
+    private static int SelectInternal(List<Tree> list, IRandom rand) {
+      // choose a random node.
+      Debug.Assert(list.Any(t => !t.Done));
+
+      var idx = rand.Next(list.Count);
+      while(list[idx].Done) { idx = rand.Next(list.Count); }
+      return idx;
+    }
+
     // backpropagate existing statistics to all parents
-    private static void BackpropagateStatistics(IActionStatistics stats, Tree tree, State state) {
-      tree.actionStatistics.Add(stats);
+    private static void BackpropagateStatistics(Tree tree, State state, int numVisits) {
+      tree.visits += numVisits;
+
       if (state.parents.ContainsKey(tree)) {
         foreach (var parent in state.parents[tree]) {
-          BackpropagateStatistics(stats, parent, state);
+          BackpropagateStatistics(parent, state, numVisits);
         }
       }
@@ -676 +674 @@
     }
 
-    private static void BackpropagateQuality(Tree tree, double q, IPolicy policy, State state) {
-      policy.Update(tree.actionStatistics, q);
+    private static void BackpropagateQuality(Tree tree, double q, State state) {
+      tree.visits++;
+      // TODO: q is ignored for now
 
       if (state.parents.ContainsKey(tree)) {
         foreach (var parent in state.parents[tree]) {
-          BackpropagateQuality(parent, q, policy, state);
+          BackpropagateQuality(parent, q, state);
         }
       }
@@ -718 +717 @@
       }
       return children[selectedChildIdx];
-    }
-
-    // tree search might fail because of constraints for expressions
-    // in this case we get stuck we just restart
-    // see ConstraintHandler.cs for more info
-    private static bool TryTreeSearchRec(IRandom rand, Tree tree, Automaton automaton, Func<byte[], int, double> eval, IPolicy treePolicy,
-      out double q) {
-      Tree selectedChild = null;
-      Contract.Assert(tree.state == automaton.CurrentState);
-      Contract.Assert(!tree.Done);
-      if (tree.children == null) {
-        if (automaton.IsFinalState(tree.state)) {
-          // final state
-          tree.Done = true;
-
-          // EVALUATE
-          byte[] code; int nParams;
-          automaton.GetCode(out code, out nParams);
-          q = eval(code, nParams);
-
-          treePolicy.Update(tree.actionStatistics, q);
-          return true; // we reached a final state
-        } else {
-          // EXPAND 
-          int[] possibleFollowStates = new int[1000];
-          int nFs;
-          automaton.FollowStates(automaton.CurrentState, ref possibleFollowStates, out nFs);
-          if (nFs == 0) {
-            // stuck in a dead end (no final state and no allowed follow states)
-            q = 0;
-            tree.Done = true;
-            tree.children = null;
-            return false;
-          }
-          tree.children = new Tree[nFs];
-          for (int i = 0; i < tree.children.Length; i++)
-            tree.children[i] = new Tree() {
-              children = null,
-              state = possibleFollowStates[i],
-              actionStatistics = treePolicy.CreateActionStatistics()
-            };
-
-          selectedChild = nFs > 1 ? SelectFinalOrRandom(automaton, tree, rand) : tree.children[0];
-        }
-      } else {
-        // tree.children != null
-        // UCT selection within tree
-        int selectedIdx = 0;
-        if (tree.children.Length > 1) {
-          selectedIdx = treePolicy.Select(tree.children.Select(ch => ch.actionStatistics), rand);
-        }
-        selectedChild = tree.children[selectedIdx];
-      }
-      // make selected step and recurse
-      automaton.Goto(selectedChild.state);
-      var success = TryTreeSearchRec(rand, selectedChild, automaton, eval, treePolicy, out q);
-      if (success) {
-        // only update if successful
-        treePolicy.Update(tree.actionStatistics, q);
-      }
-
-      tree.Done = tree.children.All(ch => ch.Done);
-      if (tree.Done) {
-        tree.children = null; // cut off the sub-branch if it has been fully explored
-      }
-      return success;
-    }
-
-    private static Tree SelectFinalOrRandom(Automaton automaton, Tree tree, IRandom rand) {
-      // if one of the new children leads to a final state then go there
-      // otherwise choose a random child
-      int selectedChildIdx = -1;
-      // find first final state if there is one
-      for (int i = 0; i < tree.children.Length; i++) {
-        if (automaton.IsFinalState(tree.children[i].state)) {
-          selectedChildIdx = i;
-          break;
-        }
-      }
-      // no final state -> select a the first child
-      if (selectedChildIdx == -1) {
-        selectedChildIdx = 0;
-      }
-      return tree.children[selectedChildIdx];
-    }
+    }                                            
 
     // scales data and extracts values from dataset into arrays
@@ -869 +784 @@
       automaton.GetCode(out code, out nParams);
       return Disassembler.CodeToString(code);
-    }
-
-
-    private static string WriteStatistics(Tree tree, State state) {
-      var sb = new System.IO.StringWriter();
-      sb.Write("{0}\t{1:N5}\t", tree.actionStatistics.Tries, tree.actionStatistics.AverageQuality);
-      if (state.children.ContainsKey(tree)) {
-        foreach (var ch in state.children[tree]) {
-          sb.Write("{0}\t{1:N5}\t", ch.actionStatistics.Tries, ch.actionStatistics.AverageQuality);
-        }
-      }
-      sb.WriteLine();
-      return sb.ToString();
     }
 
@@ -899 +801 @@
 
     private static void TraceTreeRec(Tree tree, int parentId, StringBuilder sb, ref int nextId, State state) {
-      var avgNodeQ = tree.actionStatistics.AverageQuality;
-      var tries = tree.actionStatistics.Tries;
-      if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
-      var hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
-      hue = 0.0;
-
-      sb.AppendFormat("{0} [label=\"{1:E3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", parentId, avgNodeQ, tries, hue).AppendLine();
+      var tries = tree.visits;
+
+      sb.AppendFormat("{0} [label=\"{1}\"]; ", parentId, tries).AppendLine();
 
       var list = new List<Tuple<int, int, Tree>>();
@@ -911 +809 @@
         foreach (var ch in state.children[tree]) {
           nextId++;
-          avgNodeQ = ch.actionStatistics.AverageQuality;
-          tries = ch.actionStatistics.Tries;
-          if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
-          hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
-          hue = 0.0;
-          sb.AppendFormat("{0} [label=\"{1:E3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", nextId, avgNodeQ, tries, hue).AppendLine();
-          sb.AppendFormat("{0} -> {1} [label=\"{3}\"]", parentId, nextId, avgNodeQ, ch.expr).AppendLine();
+          tries = ch.visits;
+          sb.AppendFormat("{0} [label=\"{1}\"]; ", nextId, tries).AppendLine();
+          sb.AppendFormat("{0} -> {1} [label=\"{2}\"]", parentId, nextId, ch.expr).AppendLine();
           list.Add(Tuple.Create(tries, nextId, ch));
         }
@@ -927 +821 @@
             var chch = state.children[ch].First();
             nextId++;
-            avgNodeQ = chch.actionStatistics.AverageQuality;
-            tries = chch.actionStatistics.Tries;
-            if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
-            hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
-            hue = 0.0;
-            sb.AppendFormat("{0} [label=\"{1:E3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", nextId, avgNodeQ, tries, hue).AppendLine();
-            sb.AppendFormat("{0} -> {1} [label=\"{3}\"]", chId, nextId, avgNodeQ, chch.expr).AppendLine();
+            tries = chch.visits;
+            sb.AppendFormat("{0} [label=\"{1}\"]; ", nextId, tries).AppendLine();
+            sb.AppendFormat("{0} -> {1} [label=\"{2}\"]", chId, nextId, chch.expr).AppendLine();
           }
         }
@@ -957 +847 @@
         if (!nodeIds.TryGetValue(parent, out parentId)) {
           parentId = nodeIds.Count + 1;
-          var avgNodeQ = parent.actionStatistics.AverageQuality;
-          var tries = parent.actionStatistics.Tries;
-          if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
-          var hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
-          hue = 0.0;
-          if (parent.actionStatistics.Tries > threshold)
-            sb.Write("{0} [label=\"{1:E3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", parentId, avgNodeQ, tries, hue);
+          var tries = parent.visits;
+          if (tries > threshold)
+            sb.Write("{0} [label=\"{1}\"]; ", parentId, tries);
           nodeIds.Add(parent, parentId);
         }
@@ -972 +858 @@
             nodeIds.Add(child, childId);
           }
-          var avgNodeQ = child.actionStatistics.AverageQuality;
-          var tries = child.actionStatistics.Tries;
+          var tries = child.visits;
           if (tries < 1) continue;
-          if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
-          var hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
-          hue = 0.0;
           if (tries > threshold) {
-            sb.Write("{0} [label=\"{1:E3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", childId, avgNodeQ, tries, hue);
+            sb.Write("{0} [label=\"{1}\"]; ", childId, tries);
             var edgeLabel = child.expr;
             // if (parent.expr.Length > 0) edgeLabel = edgeLabel.Replace(parent.expr, "");
-            sb.Write("{0} -> {1} [label=\"{3}\"]", parentId, childId, avgNodeQ, edgeLabel);
+            sb.Write("{0} -> {1} [label=\"{2}\"]", parentId, childId, edgeLabel);
           }
         }