Changeset 10437


Ignore:
Timestamp:
02/04/14 19:28:29 (7 years ago)
Author:
gkronber
Message:

#2026 implemented epsilon-greedy search policy

File:
1 edited

Legend:

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

    r10436 r10437  
    148148        // }
    149149        // Softmax selection
    150         double temperature = 1;
    151         var ms = searchTree.children.Select((c,i) => c == null || c.done || Grammar.minDepth[Grammar.transition[state][i]] > maxDepth ? 0.0 : Math.Exp((c.sumQuality / c.tries) / temperature)).ToArray();
    152         var msSum = ms.Sum();
    153         if(msSum == 0.0) {
    154           // uniform distribution
    155           ms = searchTree.children.Select((c,i) => c == null || c.done || Grammar.minDepth[Grammar.transition[state][i]] > maxDepth ? 0.0 : 1.0).ToArray(); 
    156           msSum = ms.Sum();
    157         }
    158         Debug.Assert(msSum > 0.0);
    159         var r = random.NextDouble() * msSum;
    160          
    161         altIdx = 0;
    162         var aggSum = 0.0;
    163         while(altIdx < searchTree.children.Length && aggSum <= r) {
    164           var c = searchTree.children[altIdx];
    165           aggSum += ms[altIdx++];
    166         }
    167         altIdx--;
     150        // double temperature = 1;
     151        // var ms = searchTree.children.Select((c,i) => c == null || c.done || Grammar.minDepth[Grammar.transition[state][i]] > maxDepth ? 0.0 : Math.Exp((c.sumQuality / c.tries) / temperature)).ToArray();
     152        // var msSum = ms.Sum();
     153        // if(msSum == 0.0) {
     154        //   // uniform distribution
     155        //   ms = searchTree.children.Select((c,i) => c == null || c.done || Grammar.minDepth[Grammar.transition[state][i]] > maxDepth ? 0.0 : 1.0).ToArray(); 
     156        //   msSum = ms.Sum();
     157        // }
     158        // Debug.Assert(msSum > 0.0);
     159        // var r = random.NextDouble() * msSum;
     160        // 
     161        // altIdx = 0;
     162        // var aggSum = 0.0;
     163        // while(altIdx < searchTree.children.Length && aggSum <= r) {
     164        //   var c = searchTree.children[altIdx];
     165        //   aggSum += ms[altIdx++];
     166        // }
     167        // altIdx--;
     168
     169        // epsilon-greedy selection
     170        double eps = 0.1;
     171        if(random.NextDouble() >= eps) {
     172          // select best
     173          altIdx = 0; while(searchTree.children[altIdx]==null) altIdx++;
     174          for(int idx=0;idx<searchTree.children.Length;idx++) {
     175            var c = searchTree.children[idx];
     176            if(c==null || c.done || Grammar.minDepth[Grammar.transition[state][idx]] > maxDepth) continue;
     177            if(searchTree.children[idx].bestQuality > searchTree.children[altIdx].bestQuality) {
     178              altIdx = idx;
     179            }
     180          }
     181        } else {
     182          // select random
     183          var allowedIndexes = (searchTree.children
     184                         .Select((e,i) => new {Elem = e, Idx = i})
     185                         .Where(p => p.Elem != null && !p.Elem.done && Grammar.minDepth[Grammar.transition[state][p.Idx]] <= maxDepth)
     186                         .Select(p => p.Idx)).ToArray();
     187          altIdx = allowedIndexes[random.Next(allowedIndexes.Length)];
     188        }
    168189        Debug.Assert(altIdx > -1);
    169190        return altIdx;
Note: See TracChangeset for help on using the changeset viewer.