Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
12/15/13 12:34:33 (10 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.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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.