Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/20/15 16:45:08 (9 years ago)
Author:
aballeit
Message:

#2283 stable GUI; ThreadPool for runs; improved TreeAnalysis

Location:
branches/HeuristicLab.Problems.GrammaticalOptimization
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.GrammaticalOptimization

    • Property svn:ignore
      •  

        old new  
        33TestResults
        44_ReSharper.GrammaticalOptimization
         5EvaluationResults
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch

    • Property svn:global-ignores set to
      obj
    • Property svn:ignore set to
      bin
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/MonteCarloTreeSearch.cs

    r12762 r12781  
    2020    public class MonteCarloTreeSearch : SolverBase
    2121    {
    22         private readonly int maxLen;
    23         private readonly IProblem problem;
    24         private readonly IGrammar grammar;
    25         private readonly Random random;
    26         private readonly IBanditPolicy behaviourPolicy;
    27         private readonly ISimulation simulation;
    28         private TreeNode rootNode;
    29         private bool isPaused = false;
    30         private object pauseLock = new object();
     22        protected readonly int maxLen;
     23        protected readonly IProblem problem;
     24        protected readonly IGrammar grammar;
     25        protected readonly Random random;
     26        protected readonly IBanditPolicy behaviourPolicy;
     27        protected readonly ISimulation simulation;
     28        protected TreeNode rootNode;
     29        protected bool isPaused = false;
     30        protected object pauseLock = new object();
    3131
    3232        public MonteCarloTreeSearch(IProblem problem, int maxLen, Random random, IBanditPolicy behaviourPolicy,
     
    7171                string phrase = currentNode.phrase;
    7272
    73                 if (phrase.Length <= maxLen)
    74                 {
    75                     // Version 2:
    76                     if (currentNode.children != null && !currentNode.children.Any())
    77                     {
    78                         // already removed all child nodes so remove it too..
    79                         currentNode.parent.children.Remove(currentNode);
    80                         continue;
    81                     }
     73                if (!grammar.IsTerminal(phrase) && phrase.Length <= maxLen)
     74                {
    8275                    ExpandTreeNode(currentNode);
    83                     if (currentNode.children.Any())
    84                     {
    85                         currentNode =
    86                             currentNode.children[behaviourPolicy.SelectAction(random, currentNode.GetChildActionInfos())
    87                                 ];
    88                     }
    89                     else
    90                     {
    91                         // Version 2:
    92                         // remove currentNode from tree..
    93                         currentNode.parent.children.Remove(currentNode);
    94                     }
     76                    currentNode =
     77                        currentNode.children[behaviourPolicy.SelectAction(random, currentNode.GetChildActionInfos())
     78                            ];
    9579                }
    9680                if (currentNode.phrase.Length <= maxLen)
     
    10185
    10286                    Propagate(currentNode, quality);
    103 
    104                 }
    105             }
    106         }
    107 
    108         private bool HasNonTerminal(string phrase)
    109         {
    110             foreach (char symbol in phrase)
    111             {
    112                 if (grammar.IsNonTerminal(symbol))
    113                 {
    114                     return true;
    115                 }
    116             }
    117 
    118             return false;
    119         }
    120 
    121         private void ExpandTreeNode(TreeNode treeNode)
     87                }
     88            }
     89        }
     90
     91        protected void ExpandTreeNode(TreeNode treeNode)
    12292        {
    12393            // create children on the first visit
     
    150120        }
    151121
    152         private void Reset()
     122        protected void Reset()
    153123        {
    154124            StopRequested = false;
     
    157127        }
    158128
    159         private void Propagate(TreeNode node, double quality)
     129        protected void Propagate(TreeNode node, double quality)
    160130        {
    161131            var currentNode = node;
     
    167137        }
    168138
     139        private void GetTreeInfosRek(TreeInfos treeInfos, List<TreeNode> children)
     140        {
     141            treeInfos.TotalNodes += children.Count;
     142            foreach (TreeNode child in children)
     143            {
     144                if (child.children != null)
     145                {
     146                    treeInfos.ExpandedNodes++;
     147                    if (treeInfos.DeepestLevel <= child.level)
     148                    {
     149                        treeInfos.DeepestLevel = child.level + 1;
     150                    }
     151                    GetTreeInfosRek(treeInfos, child.children);
     152                }
     153                else
     154                {
     155                    if (grammar.IsTerminal(child.phrase))
     156                    {
     157                        treeInfos.LeaveNodes++;
     158                    }
     159                    else
     160                    {
     161                        treeInfos.UnexpandedNodes++;
     162                    }
     163                }
     164            }
     165        }
     166
    169167        public TreeInfos GetTreeInfos()
    170168        {
    171             int totalNodes = 0;
    172             int unexpandedNodes = 0;
    173             int expandedNodes = 0;
    174             int leaveNodes = 0;
    175             int deepestLevel = 0;
    176             int totalLevel = 0;
    177             int totalChildren = 0;
    178 
    179             List<TreeNode> toDoNodes = new List<TreeNode>();
     169            TreeInfos treeInfos = new TreeInfos();
     170
    180171            if (rootNode != null)
    181172            {
    182                 toDoNodes.Add(rootNode);
    183             }
    184             while (toDoNodes.Any())
    185             {
    186                 TreeNode currentNode = toDoNodes[0];
    187                 toDoNodes.RemoveAt(0);
    188                 totalNodes++;
    189                 if (currentNode.level > deepestLevel)
    190                 {
    191                     deepestLevel = currentNode.level;
    192                 }
    193                 totalLevel += currentNode.level;
    194 
    195                 if (currentNode.children != null)
    196                 {
    197                     totalChildren += currentNode.children.Count;
    198                     toDoNodes.AddRange(currentNode.children);
    199                     expandedNodes++;
     173                treeInfos.TotalNodes++;
     174                if (rootNode.children != null)
     175                {
     176                    treeInfos.ExpandedNodes++;
     177                    treeInfos.DeepestLevel = rootNode.level + 1;
     178                    GetTreeInfosRek(treeInfos, rootNode.children);
    200179                }
    201180                else
    202181                {
    203                     if (!HasNonTerminal(currentNode.phrase))
    204                     {
    205                         leaveNodes++;
     182                    treeInfos.DeepestLevel = rootNode.level;
     183                    if (grammar.IsTerminal(rootNode.phrase))
     184                    {
     185                        treeInfos.LeaveNodes++;
    206186                    }
    207187                    else
    208188                    {
    209                         unexpandedNodes++;
    210                     }
    211                 }
    212             }
    213             return new TreeInfos(totalNodes, unexpandedNodes, expandedNodes, leaveNodes, deepestLevel,
    214                 totalLevel / totalNodes, totalChildren / expandedNodes);
     189                        treeInfos.UnexpandedNodes++;
     190                    }
     191                }
     192            }
     193            return treeInfos;
    215194        }
    216195
    217196        public byte[] GenerateSvg()
    218197        {
    219             IGetStartProcessQuery getStartProcessQuery = new GetStartProcessQuery();
    220             IGetProcessStartInfoQuery getProcessStartInfoQuery = new GetProcessStartInfoQuery();
    221             IRegisterLayoutPluginCommand registerLayoutPluginCommand =
    222                 new RegisterLayoutPluginCommand(getProcessStartInfoQuery, getStartProcessQuery);
    223 
    224             GraphGeneration wrapper = new GraphGeneration(getStartProcessQuery,
    225                 getProcessStartInfoQuery,
    226                 registerLayoutPluginCommand);
    227             wrapper.GraphvizPath = @"../../../Graphviz2.38/bin";
    228             StringBuilder dotFile = new StringBuilder("digraph {");
    229             dotFile.AppendLine();
    230             dotFile.AppendLine("splines=ortho;");
    231             dotFile.AppendLine("concentrate=true;");
    232             dotFile.AppendLine("ranksep=1.2;");
    233 
    234             List<TreeNode> toDoNodes = new List<TreeNode>();
    235             if (rootNode != null)
    236             {
    237                 toDoNodes.Add(rootNode);
    238                 // declare node
    239                 string hexColor = GetHexNodeColor(Color.White, Color.OrangeRed, rootNode.actionInfo.Value);
    240 
    241                 dotFile.AppendLine(string.Format("{0} [label=\"{1}\\n{2:0.00}/{3}\", style=filled, fillcolor=\"{4}\"]",
    242                     rootNode.GetHashCode(),
    243                     rootNode.phrase, rootNode.actionInfo.Value, rootNode.actionInfo.Tries, hexColor));
    244             }
    245 
    246             // to put nodes on the same level in graph
    247             Dictionary<int, List<TreeNode>> levelMap = new Dictionary<int, List<TreeNode>>();
    248 
    249             List<TreeNode> sameLevelNodes;
    250 
    251             while (toDoNodes.Any())
    252             {
    253                 TreeNode currentNode = toDoNodes[0];
    254                 toDoNodes.RemoveAt(0);
    255                 // put currentNode into levelMap
    256                 if (levelMap.TryGetValue(currentNode.level, out sameLevelNodes))
    257                 {
    258                     sameLevelNodes.Add(currentNode);
    259                 }
    260                 else
    261                 {
    262                     sameLevelNodes = new List<TreeNode>();
    263                     sameLevelNodes.Add(currentNode);
    264                     levelMap.Add(currentNode.level, sameLevelNodes);
    265                 }
    266 
    267                 // draw line from current node to all its children
    268                 if (currentNode.children != null)
    269                 {
    270                     foreach (TreeNode childNode in currentNode.children)
    271                     {
    272                         toDoNodes.Add(childNode);
    273                         // declare node
    274 
    275                         string hexColor = GetHexNodeColor(Color.White, Color.OrangeRed, childNode.actionInfo.Value);
    276                         dotFile.AppendLine(
    277                             string.Format("{0} [label=\"{1}\\n{2:0.00}/{3}\", style=filled, fillcolor=\"{4}\"]",
    278                                 childNode.GetHashCode(),
    279                                 childNode.phrase, childNode.actionInfo.Value, childNode.actionInfo.Tries, hexColor));
    280                         // add edge
    281                         dotFile.AppendLine(string.Format("{0} -> {1}", currentNode.GetHashCode(),
    282                             childNode.GetHashCode()));
    283                     }
    284                 }
    285             }
    286 
    287             // set same level ranks..
    288             foreach (KeyValuePair<int, List<TreeNode>> entry in levelMap)
    289             {
    290                 dotFile.Append("{rank = same;");
    291                 foreach (TreeNode node in entry.Value)
    292                 {
    293                     dotFile.Append(string.Format(" {0};", node.GetHashCode()));
    294                 }
    295                 dotFile.AppendLine("}");
    296             }
    297 
    298             dotFile.Append(" }");
    299             byte[] output = wrapper.GenerateGraph(dotFile.ToString(), Enums.GraphReturnType.Svg);
    300             return output;
    301         }
    302 
    303         private String HexConverter(Color c)
     198            if (GetTreeInfos().TotalNodes < 1000)
     199            {
     200                IGetStartProcessQuery getStartProcessQuery = new GetStartProcessQuery();
     201                IGetProcessStartInfoQuery getProcessStartInfoQuery = new GetProcessStartInfoQuery();
     202                IRegisterLayoutPluginCommand registerLayoutPluginCommand =
     203                    new RegisterLayoutPluginCommand(getProcessStartInfoQuery, getStartProcessQuery);
     204
     205                GraphGeneration wrapper = new GraphGeneration(getStartProcessQuery,
     206                    getProcessStartInfoQuery,
     207                    registerLayoutPluginCommand);
     208                wrapper.GraphvizPath = @"../../../Graphviz2.38/bin";
     209                StringBuilder dotFile = new StringBuilder("digraph {");
     210                dotFile.AppendLine();
     211                dotFile.AppendLine("splines=ortho;");
     212                dotFile.AppendLine("concentrate=true;");
     213                dotFile.AppendLine("ranksep=1.2;");
     214
     215                List<TreeNode> toDoNodes = new List<TreeNode>();
     216                if (rootNode != null)
     217                {
     218                    toDoNodes.Add(rootNode);
     219                    // declare node
     220                    string hexColor = GetHexNodeColor(Color.White, Color.OrangeRed, rootNode.actionInfo.Value);
     221
     222                    dotFile.AppendLine(
     223                        string.Format("{0} [label=\"{1}\\n{2:0.00}/{3}\", style=filled, fillcolor=\"{4}\"]",
     224                            rootNode.GetHashCode(),
     225                            rootNode.phrase, rootNode.actionInfo.Value, rootNode.actionInfo.Tries, hexColor));
     226                }
     227
     228                // to put nodes on the same level in graph
     229                Dictionary<int, List<TreeNode>> levelMap = new Dictionary<int, List<TreeNode>>();
     230
     231                List<TreeNode> sameLevelNodes;
     232
     233                while (toDoNodes.Any())
     234                {
     235                    TreeNode currentNode = toDoNodes[0];
     236                    toDoNodes.RemoveAt(0);
     237                    // put currentNode into levelMap
     238                    if (levelMap.TryGetValue(currentNode.level, out sameLevelNodes))
     239                    {
     240                        sameLevelNodes.Add(currentNode);
     241                    }
     242                    else
     243                    {
     244                        sameLevelNodes = new List<TreeNode>();
     245                        sameLevelNodes.Add(currentNode);
     246                        levelMap.Add(currentNode.level, sameLevelNodes);
     247                    }
     248
     249                    // draw line from current node to all its children
     250                    if (currentNode.children != null)
     251                    {
     252                        foreach (TreeNode childNode in currentNode.children)
     253                        {
     254                            toDoNodes.Add(childNode);
     255                            // declare node
     256
     257                            string hexColor = GetHexNodeColor(Color.White, Color.OrangeRed, childNode.actionInfo.Value);
     258                            dotFile.AppendLine(
     259                                string.Format("{0} [label=\"{1}\\n{2:0.00}/{3}\", style=filled, fillcolor=\"{4}\"]",
     260                                    childNode.GetHashCode(),
     261                                    childNode.phrase, childNode.actionInfo.Value, childNode.actionInfo.Tries, hexColor));
     262                            // add edge
     263                            dotFile.AppendLine(string.Format("{0} -> {1}", currentNode.GetHashCode(),
     264                                childNode.GetHashCode()));
     265                        }
     266                    }
     267                }
     268
     269                // set same level ranks..
     270                foreach (KeyValuePair<int, List<TreeNode>> entry in levelMap)
     271                {
     272                    dotFile.Append("{rank = same;");
     273                    foreach (TreeNode node in entry.Value)
     274                    {
     275                        dotFile.Append(string.Format(" {0};", node.GetHashCode()));
     276                    }
     277                    dotFile.AppendLine("}");
     278                }
     279
     280                dotFile.Append(" }");
     281                byte[] output = wrapper.GenerateGraph(dotFile.ToString(), Enums.GraphReturnType.Svg);
     282                return output;
     283            }
     284            return null;
     285        }
     286
     287        protected String HexConverter(Color c)
    304288        {
    305289            return "#" + c.R.ToString("X2") + c.G.ToString("X2") + c.B.ToString("X2");
    306290        }
    307291
    308         private String GetHexNodeColor(Color weakColor, Color strongColor, double quality)
     292        protected String GetHexNodeColor(Color weakColor, Color strongColor, double quality)
    309293        {
    310294            // convert quality to value between 0 and 1
Note: See TracChangeset for help on using the changeset viewer.