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/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}
Note: See TracChangeset for help on using the changeset viewer.