Changeset 15441

Timestamp:

10/29/17 22:22:38 (22 months ago)

Author:

gkronber

Message:

#2796 more bug fixing

Location:

branches/MCTS-SymbReg-2796

Files:

• HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Automaton.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionStatic.cs (modified) (4 diffs)
• Tests/HeuristicLab.Algorithms.DataAnalysis-3.4/MctsSymbolicRegressionTest.cs (modified) (1 diff)

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

@@ -440 +440 @@
       int storedPC = codeGenerator.ProgramCounter;
 
-      if (!IsFinalState(CurrentState)) {
+      if (CurrentState != StateExprEnd) {
         // save state and code,
         storedState = CurrentState;
@@ -446 +446 @@
 
         // take shortest route to final state (smaller state values are closer to the final state)
-        while (!IsFinalState(CurrentState)) {
+        while (CurrentState != StateExprEnd) {
           Debug.Assert(followStates[CurrentState][0] == followStates[CurrentState].Min());
           var nextState = followStates[CurrentState][0];

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

@@ -61 +61 @@
     // TODO: Solve Poly-10
     // TODO: rename everything as this is not MCTS anymore
-    // TODO: After state unification the recursive backpropagation of results takes a lot of time. How can this be improved?
+    // TODO: when a path to an expression is explored first (e.g. x1 + x2)
+    //       and later we find the a longer form x1 + x1 + x2 where the number of variable references
+    //       exceeds the maximum in the automaton this leads to an error (see unit tests) 
+    // ~~obsolete TODO: After state unification the recursive backpropagation of results takes a lot of time. How can this be improved?
     // ~~obsolete TODO: Why is the algorithm so slow for rather greedy policies (e.g. low C value in UCB)?
     // ~~obsolete TODO: check if we can use a quality measure with range [-1..1] in policies
@@ -72 +75 @@
     // TODO: is it OK to initialize all constants to 1 (Obj 2)?
     // TODO: improve memory usage
+    // TODO: analyze / improve perf of ExprHashing (canonical form for expressions)
     // TODO: support empty test partition
     // TODO: the algorithm should be invariant to linear transformations of the space (y = f(x') = f( Ax ) ) for invertible transformations A --> unit tests
@@ -561 +565 @@
           tree = state.children[tree][selectedIdx];
 
-          // move the automaton forward until reaching the state
           // all steps where no alternatives could be taken immediately (without expanding the tree)
           // TODO: simplification of the automaton 
@@ -669 +672 @@
 
     private static int SelectInternal(List<Tree> list, IRandom rand) {
+      Debug.Assert(list.Any(t => !t.Done));
+      
+      // check if there is any node which has not been visited
+      for(int i=0;i<list.Count;i++) {
+        if (!list[i].Done && list[i].visits == 0) return i;
+      }
+
       // 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); }

branches/MCTS-SymbReg-2796/Tests/HeuristicLab.Algorithms.DataAnalysis-3.4/MctsSymbolicRegressionTest.cs

@@ -1442 +1442 @@
       // some Keijzer problem instances have very large test partitions (here we are not concerened about test performance)
       if (regProblem.TestPartition.End - regProblem.TestPartition.Start > 1000) regProblem.TestPartition.End = regProblem.TestPartition.Start + 1000;
-      TestMcts(regProblem, maxVariableReferences: 20, allowExp: false, allowLog: false, allowInv: true);
+      TestMcts(regProblem, maxVariableReferences: 10, allowExp: false, allowLog: false, allowInv: true);
     }