Changeset 10409


Ignore:
Timestamp:
01/28/14 16:25:36 (6 years ago)
Author:
gkronber
Message:

#2026 prepare for inclusion of terminals into the search tree

Location:
branches/HeuristicLab.Problems.GPDL
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.GPDL/CodeGenerator/MonteCarloTreeSearchCodeGen.cs

    r10408 r10409  
    7474          Debug.Assert(searchTree.children.Length == Grammar.transition[state].Length);
    7575          Debug.Assert(searchTree.tries - RANDOM_TRIES - 1 == searchTree.children.Where(c=>c!=null).Sum(c=>c.tries));
    76           // check if there is an unchecked alternative
    77           var altIdx = Array.FindIndex(searchTree.children, (e) => e == null);
    78           if(altIdx != -1) {
    79             Debug.Assert(searchTree.children[altIdx] == null);
    80             searchTree.children[altIdx] = new SearchTreeNode();
    81             t = new Tree(altIdx, new Tree[1]);
    82             extensionPoints.Push(Tuple.Create(t, Grammar.transition[state][altIdx], 0));
    83             SampleTree(searchTree.children[altIdx], extensionPoints);
    84           } else {
    85             // select the least sampled alternative
    86             //altIdx = 0;
    87             //int minSamples = searchTree.children[altIdx].tries;
    88             //for(int idx = 1; idx < searchTree.children.Length; idx++) {
    89             //  if(searchTree.children[idx].tries < minSamples) {
    90             //    minSamples = searchTree.children[idx].tries;
    91             //    altIdx = idx;
    92             //  }
    93             //}
    94             // select the alternative with the largest average
    95             altIdx = 0;
    96             double bestAverage = UCB(searchTree, searchTree.children[altIdx]);
    97             for(int idx = 1; idx < searchTree.children.Length; idx++) {
    98               if (UCB(searchTree, searchTree.children[idx]) > UCB(searchTree, searchTree.children[altIdx])) {
    99                 altIdx = idx;
    100               }
    101             }
    102             t = new Tree(altIdx, new Tree[1]);
    103             extensionPoints.Push(Tuple.Create(t, Grammar.transition[state][altIdx], 0));
    104             SampleTree(searchTree.children[altIdx], extensionPoints);
    105           }
     76          var altIdx = SelectAlternative(searchTree);
     77          t = new Tree(altIdx, new Tree[1]);
     78          extensionPoints.Push(Tuple.Create(t, Grammar.transition[state][altIdx], 0));
     79          SampleTree(searchTree.children[altIdx], extensionPoints);
    10680        } else {
    10781          // multiple subtrees
     
    11690      Debug.Assert(parent.subtrees[subtreeIdx] == null);
    11791      parent.subtrees[subtreeIdx] = t;
     92    }
     93
     94    private int SelectAlternative(SearchTreeNode searchTree) {
     95      // any alternative not yet explored?
     96      var altIdx = Array.FindIndex(searchTree.children, (e) => e == null);
     97      if(altIdx >= 0) {
     98        searchTree.children[altIdx] = new SearchTreeNode();
     99        return altIdx;
     100      } else {
     101        // select the least sampled alternative
     102        altIdx = 0;
     103        int minSamples = searchTree.children[altIdx].tries;
     104        for(int idx = 1; idx < searchTree.children.Length; idx++) {
     105          if(searchTree.children[idx].tries < minSamples) {
     106            minSamples = searchTree.children[idx].tries;
     107            altIdx = idx;
     108          }
     109        }
     110        // select the alternative with the largest average
     111        // altIdx = 0;
     112        // double bestAverage = UCB(searchTree, searchTree.children[altIdx]);
     113        // for(int idx = 1; idx < searchTree.children.Length; idx++) {
     114        //   if (UCB(searchTree, searchTree.children[idx]) > UCB(searchTree, searchTree.children[altIdx])) {
     115        //     altIdx = idx;
     116        //   }
     117        // }
     118        return altIdx;
     119      }
    118120    }
    119121
     
    349351              sb.AppendLine("}");
    350352            } else {
    351               sb.Append("{").BeginBlock();
    352               sb.AppendFormat(" var max = problem.GetMax{0}_{1}();", terminal.Ident, constr.Ident).AppendLine();
    353               sb.AppendFormat(" var min = problem.GetMin{0}_{1}();", terminal.Ident, constr.Ident).AppendLine();
    354               sb.AppendFormat("t.{0} = random.NextDouble() * (max - min) + min;", constr.Ident).EndBlock();
    355               sb.AppendLine("}");
     353              throw new NotSupportedException("The MTCS solver does not support RANGE constraints.");
    356354            }
    357355          }
  • branches/HeuristicLab.Problems.GPDL/Examples/symbreg Koza.txt

    r10395 r10409  
    9393    | Multiplication<<row, out val>>
    9494    | Var<<out variable>>                                  SEM << val = x[row, variable]; >>
    95     /* | ERC<<out val>>  */
     95    | ERC<<out val>>
    9696  .
    9797
Note: See TracChangeset for help on using the changeset viewer.