Changeset 10228


Ignore:
Timestamp:
12/15/13 12:34:33 (6 years ago)
Author:
sawinkle
Message:

#2109: Updated DepthFirstMapper and abstract base class GenotypeToPhenotypeMapper:

  • Added new method SampleArity() to GenotypeToPhenotypeMapper to determine a random arity for a given node, depending on a maximum allowed arity.
  • Replaced the recursive depth-first mapping approach by a iterative one, which uses a stack of <node, arity> tuples. The recursive approach only generated trees with very small subtrees depending on the minimumArity of each node. Now, the iterative one uses the SampleArity() method and pushes/pops the <node, arity> tuples from/to the used stack. Therefore, it is not necessary to only allow the minimumArity, but also to deal with arbitrarily sampled arities per node.
Location:
branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/DepthFirstMapper.cs

    r10075 r10228  
    2020#endregion
    2121
     22using System;
     23using System.Collections.Generic;
    2224using HeuristicLab.Common;
    2325using HeuristicLab.Core;
     
    6365      tree.Root = rootNode;
    6466
    65       int genotypeIndex = 0;
    66       int currSubtreeCount = 1;
     67      //int genotypeIndex = 0;
     68      //int currSubtreeCount = 1;
     69      //MapDepthFirstRecursively(startNode, genotype,
     70      //                         grammar, genotype.Length,
     71      //                         ref genotypeIndex, ref currSubtreeCount,
     72      //                         new MersenneTwister());
    6773
    68       MapDepthFirstRecursively(startNode, genotype,
    69                                grammar, genotype.Length,
    70                                ref genotypeIndex, ref currSubtreeCount);
    71 
     74      MapDepthFirstIteratively(startNode, genotype, grammar,
     75                               genotype.Length, new MersenneTwister());
    7276      return tree;
    7377    }
     
    8589    /// <param name="currentNode">current parent node</param>
    8690    /// <param name="genotype">integer vector, which should be mapped to a tree</param>
    87     /// <param name="grammar">grammar definition to determine the allowed child symbols for currentNode </param>
     91    /// <param name="grammar">grammar to determine the allowed child symbols for currentNode </param>
    8892    /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param>
    8993    /// <param name="genotypeIndex">current index in integer vector</param>
     
    9498                                          int maxSubtreeCount,
    9599                                          ref int genotypeIndex,
    96                                           ref int currSubtreeCount) {
     100                                          ref int currSubtreeCount,
     101                                          IRandom random) {
     102
     103      // TODO: check, if method calls of GetNewChildNode() and GetRandomTerminalNode() don't return null
    97104      if (currSubtreeCount < maxSubtreeCount) {
    98105
    99         var newNode = GetNewChildNode(currentNode, genotype, grammar, genotypeIndex);
     106        var newNode = GetNewChildNode(currentNode, genotype, grammar, genotypeIndex, random);
    100107
    101108        if ((currSubtreeCount + newNode.Symbol.MinimumArity) > maxSubtreeCount) {
    102109          // TODO: maybe check, if there is any node, which fits in the tree yet
    103           currentNode.AddSubtree(GetRandomTerminalNode(currentNode, grammar));
     110          currentNode.AddSubtree(GetRandomTerminalNode(currentNode, grammar, random));
    104111        } else {
    105112          currentNode.AddSubtree(newNode);
     
    110117            MapDepthFirstRecursively(newNode, genotype,
    111118                                     grammar, maxSubtreeCount,
    112                                      ref genotypeIndex, ref currSubtreeCount);
     119                                     ref genotypeIndex, ref currSubtreeCount, random);
    113120          }
    114121        }
     
    116123      } else {
    117124        while (currentNode.Symbol.MinimumArity > currentNode.SubtreeCount) {
    118           var newNode = GetNewChildNode(currentNode, genotype, grammar, genotypeIndex);
     125          var newNode = GetNewChildNode(currentNode, genotype, grammar, genotypeIndex, random);
    119126          currentNode.AddSubtree(newNode);
    120127          genotypeIndex++;
    121128          while (newNode.Symbol.MinimumArity > newNode.SubtreeCount) {
    122             newNode.AddSubtree(GetRandomTerminalNode(newNode, grammar));
     129            newNode.AddSubtree(GetRandomTerminalNode(newNode, grammar, random));
    123130          }
    124131        }
    125132      }
    126133    }
     134
     135
     136    /// <summary>
     137    /// Genotype-to-Phenotype mapper (iterative depth-first approach).
     138    /// </summary>
     139    /// <param name="startNode">first node of the tree with arity 1</param>
     140    /// <param name="genotype">integer vector, which should be mapped to a tree</param>
     141    /// <param name="grammar">grammar to determine the allowed child symbols for each node</param>
     142    /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param>
     143    /// <param name="random">random number generator</param>
     144    private void MapDepthFirstIteratively(ISymbolicExpressionTreeNode startNode,
     145                                          IntegerVector genotype,
     146                                          ISymbolicExpressionGrammar grammar,
     147                                          int maxSubtreeCount, IRandom random) {
     148
     149      Stack<Tuple<ISymbolicExpressionTreeNode, int>> stack
     150        = new Stack<Tuple<ISymbolicExpressionTreeNode, int>>(); // tuples of <node, arity>
     151
     152      int genotypeIndex = 0;
     153      int currSubtreeCount = 1;
     154
     155      stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(startNode, 1));
     156
     157      while ((currSubtreeCount < maxSubtreeCount) && (stack.Count > 0)) {
     158
     159        // get next node from stack and re-push it, if this node still has unhandled subtrees ...
     160        Tuple<ISymbolicExpressionTreeNode, int> current = stack.Pop();
     161        if (current.Item2 > 1) {
     162          stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(current.Item1, current.Item2 - 1));
     163        }
     164
     165        var newNode = GetNewChildNode(current.Item1, genotype, grammar, genotypeIndex, random);
     166        int arity = SampleArity(random, newNode, maxSubtreeCount - currSubtreeCount);
     167
     168        if (arity < 0) {
     169          current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));
     170        } else {
     171          current.Item1.AddSubtree(newNode);
     172          genotypeIndex++;
     173          currSubtreeCount += arity;
     174          if (arity > 0) {
     175            // new node has subtrees so push it onto the stack
     176            stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(newNode, arity));
     177          }
     178        }
     179      }
     180
     181      // maximum allowed subtree count was already reached, but there are still
     182      // incomplete subtrees (non-terminal symbols) in the tree
     183      // -> fill them with terminal symbols
     184      while (stack.Count > 0) {
     185        Tuple<ISymbolicExpressionTreeNode, int> current = stack.Pop();
     186        if (current.Item2 > 1) {
     187          stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(current.Item1, current.Item2 - 1));
     188        }
     189        current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));
     190      }
     191    }
    127192  }
    128193}
  • branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/GenotypeToPhenotypeMapper.cs

    r10075 r10228  
    2323using System.Linq;
    2424using HeuristicLab.Common;
     25using HeuristicLab.Core;
    2526using HeuristicLab.Encodings.IntegerVectorEncoding;
    2627using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    2728using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2829using HeuristicLab.Problems.GrammaticalEvolution.Mappers;
    29 using HeuristicLab.Random;
    3030
    3131namespace HeuristicLab.Problems.GrammaticalEvolution {
     
    4848    /// </summary>
    4949    /// <param name="parentNode">parent node for which a child node is returned randomly</param>
    50     /// <param name="grammar">grammar definition to determine the allowed child symbols for parentNode</param>
    51     /// <returns>randomly chosen terminal node with arity 0</returns>
     50    /// <param name="grammar">grammar to determine the allowed child symbols for parentNode</param>
     51    /// <param name="random">random number generator</param>
     52    /// <returns>randomly chosen terminal node with arity 0 or null, if no terminal node exists</returns>
    5253    protected ISymbolicExpressionTreeNode GetRandomTerminalNode(ISymbolicExpressionTreeNode parentNode,
    53                                                               ISymbolicExpressionGrammar grammar) {
     54                                                                ISymbolicExpressionGrammar grammar,
     55                                                                IRandom random) {
    5456      // only select specific symbols, which can be interpreted ...
    5557      var possibleSymbolsList = (from s in grammar.GetAllowedChildSymbols(parentNode.Symbol)
     
    5860                                 where s.MinimumArity == 0
    5961                                 select s).ToList();
    60       // TODO: Check, if symbol list is empty (no terminal nodes found) - what should happen?
    61       var newNode = possibleSymbolsList.SelectRandom(new MersenneTwister()).CreateTreeNode();
    62       if (newNode.HasLocalParameters) newNode.ResetLocalParameters(new MersenneTwister());
     62
     63      // no terminal node exists for the given parent node
     64      if (possibleSymbolsList.Count() < 1) return null;
     65
     66      var newNode = possibleSymbolsList.SelectRandom(random).CreateTreeNode();
     67      if (newNode.HasLocalParameters) newNode.ResetLocalParameters(random);
    6368      return newNode;
    6469    }
     
    7075    /// <param name="parentNode">parent node to find a child node randomly for</param>
    7176    /// <param name="genotype">integer vector, which should be mapped to a tree</param>
    72     /// <param name="grammar">grammar definition used to define the allowed child symbols</param>
     77    /// <param name="grammar">grammar used to define the allowed child symbols</param>
    7378    /// <param name="genotypeIndex">index in the integer vector; can be greater than vector length</param>
    74     /// <returns>randomly chosen child node for parentNode</returns>
     79    /// <param name="random">random number generator</param>
     80    /// <returns>randomly chosen child node or null, if no child node exits</returns>
    7581    protected ISymbolicExpressionTreeNode GetNewChildNode(ISymbolicExpressionTreeNode parentNode,
    7682                                                          IntegerVector genotype,
    7783                                                          ISymbolicExpressionGrammar grammar,
    78                                                           int genotypeIndex) {
     84                                                          int genotypeIndex,
     85                                                          IRandom random) {
    7986
    8087      // only select specific symbols, which can be interpreted ...
     
    8289                                         where s.InitialFrequency > 0.0
    8390                                         select s).ToList();
     91
    8492      int prodRuleCount = symbolList.Count();
     93
     94      // no child node exists for the given parent node
     95      if (prodRuleCount < 1) return null;
     96
    8597      int prodRuleIndex = genotype[genotypeIndex % genotype.Length] % prodRuleCount;
    8698
    8799      var newNode = symbolList.ElementAt(prodRuleIndex).CreateTreeNode();
    88       if (newNode.HasLocalParameters) newNode.ResetLocalParameters(new MersenneTwister());
     100      if (newNode.HasLocalParameters) newNode.ResetLocalParameters(random);
    89101      return newNode;
     102    }
     103
     104
     105    /// <summary>
     106    /// Randomly determines an arity for the given node.
     107    /// </summary>
     108    /// <param name="random">random number generator</param>
     109    /// <param name="node">node, for which a random arity is determined</param>
     110    /// <param name="maxAllowedArity">the resulting arity must not exceed this maximum arity</param>
     111    /// <returns>random arity in the interval [minArity, maxArity] of the node or
     112    ///          -1, if minArity exceeds maxAllowedArity</returns>
     113    protected int SampleArity(IRandom random,
     114                              ISymbolicExpressionTreeNode node,
     115                              int maxAllowedArity) {
     116      int minArity = node.Symbol.MinimumArity;
     117      int maxArity = node.Symbol.MaximumArity;
     118
     119      if (maxAllowedArity < maxArity) {
     120        maxArity = maxAllowedArity;
     121      }
     122
     123      if (maxAllowedArity < minArity) {
     124        return -1;
     125      }
     126
     127      if (minArity == maxArity) {
     128        return minArity;
     129      }
     130
     131      return random.Next(minArity, maxArity);
    90132    }
    91133  }
Note: See TracChangeset for help on using the changeset viewer.