Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/22/11 19:04:54 (13 years ago)
Author:
gkronber
Message:

#1418 unified size/height vs. length/depth terminology and adapted unit tests for symbolic expression tree encoding version 3.4

File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs

    r5529 r5549  
    3232namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    3333  [StorableClass]
    34   [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed size")]
     34  [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed length")]
    3535  public sealed class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator,
    3636    ISymbolicExpressionTreeSizeConstraintOperator, ISymbolicExpressionTreeGrammarBasedOperator, ISymbolicExpressionTreeArchitectureAlteringOperator {
    … …  
    9898
    9999    public static ISymbolicExpressionTree Create(IRandom random, ISymbolicExpressionTreeGrammar grammar,
    100       int maxTreeSize, int maxTreeHeight,
     100      int maxTreeLength, int maxTreeDepth,
    101101      int maxFunctionDefinitions, int maxFunctionArguments
    102102      ) {
    … …  
    105105      if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);
    106106      rootNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
    107       tree.Root = PTC2(random, rootNode, maxTreeSize, maxTreeHeight, maxFunctionDefinitions, maxFunctionArguments);
     107      tree.Root = PTC2(random, rootNode, maxTreeLength, maxTreeDepth, maxFunctionDefinitions, maxFunctionArguments);
    108108      return tree;
    109109    }
    … …  
    116116
    117117    public static ISymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionTreeNode seedNode,
    118       int maxTreeSize, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
    119       // tree size is limited by the grammar and by the explicit size constraints
    120       int allowedMinSize = seedNode.Grammar.GetMinExpressionLength(seedNode.Symbol);
    121       int allowedMaxSize = Math.Min(maxTreeSize, seedNode.Grammar.GetMaxExpressionLength(seedNode.Symbol));
     118      int maxLength, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
     119      // tree length is limited by the grammar and by the explicit size constraints
     120      int allowedMinLength = seedNode.Grammar.GetMinExpressionLength(seedNode.Symbol);
     121      int allowedMaxLength = Math.Min(maxLength, seedNode.Grammar.GetMaxExpressionLength(seedNode.Symbol));
    122122      int tries = 0;
    123123      while (tries++ < MAX_TRIES) {
    124         // select a target tree size uniformly in the possible range (as determined by explicit limits and limits of the grammar)
    125         int treeSize;
    126         treeSize = random.Next(allowedMinSize, allowedMaxSize + 1);
    127         if (treeSize <= 1 || maxDepth <= 1) return seedNode;
    128 
    129         bool success = CreateFullTreeFromSeed(random, seedNode, seedNode.Grammar, treeSize, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
     124        // select a target tree length uniformly in the possible range (as determined by explicit limits and limits of the grammar)
     125        int targetTreeLength;
     126        targetTreeLength = random.Next(allowedMinLength, allowedMaxLength + 1);
     127        if (targetTreeLength <= 1 || maxDepth <= 1) return seedNode;
     128
     129        bool success = CreateFullTreeFromSeed(random, seedNode, seedNode.Grammar, targetTreeLength, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
    130130
    131131        // if successful => check constraints and return the tree if everything looks ok       
    132         if (success && seedNode.GetSize() <= maxTreeSize && seedNode.GetHeight() <= maxDepth) {
     132        if (success && seedNode.GetLength() <= maxLength && seedNode.GetDepth() <= maxDepth) {
    133133          return seedNode;
    134134        } else {
    … …  
    136136          while (seedNode.SubTrees.Count() > 0) seedNode.RemoveSubTree(0);
    137137        }
    138         // try a different size MAX_TRIES times
     138        // try a different length MAX_TRIES times
    139139      }
    140140      throw new ArgumentException("Couldn't create a random valid tree.");
    … …  
    142142
    143143    private static bool CreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeGrammar globalGrammar,
    144       int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
     144      int targetLength, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
    145145      try {
    146         TryCreateFullTreeFromSeed(random, root, globalGrammar, size, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
     146        TryCreateFullTreeFromSeed(random, root, globalGrammar, targetLength, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
    147147        return true;
    148148      }
    … …  
    151151
    152152    private static void TryCreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeGrammar globalGrammar,
    153       int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
     153      int targetLength, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
    154154      List<TreeExtensionPoint> extensionPoints = new List<TreeExtensionPoint>();
    155       int currentSize = 1;
    156       int totalListMinSize = globalGrammar.GetMinExpressionLength(root.Symbol) - 1;
    157       int actualArity = SampleArity(random, root, size);
     155      int currentLength = 1;
     156      int totalListMinLength = globalGrammar.GetMinExpressionLength(root.Symbol) - 1;
     157      int actualArity = SampleArity(random, root, targetLength);
    158158      for (int i = 0; i < actualArity; i++) {
    159159        // insert a dummy sub-tree and add the pending extension to the list
    … …  
    163163      }
    164164      // while there are pending extension points and we have not reached the limit of adding new extension points
    165       while (extensionPoints.Count > 0 && totalListMinSize + currentSize < size) {
     165      while (extensionPoints.Count > 0 && totalListMinLength + currentLength < targetLength) {
    166166        int randomIndex = random.Next(extensionPoints.Count);
    167167        TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
    … …  
    176176                                where parent.Grammar.IsAllowedChild(parent.Symbol, s, argumentIndex)
    177177                                where parent.Grammar.GetMinExpressionDepth(s) + extensionDepth - 1 < maxDepth
    178                                 where parent.Grammar.GetMaxExpressionLength(s) > size - totalListMinSize - currentSize
     178                                where parent.Grammar.GetMaxExpressionLength(s) > targetLength - totalListMinLength - currentLength
    179179                                select s)
    180180                               .ToList();
    … …  
    188188          InitializeNewTreeNode(random, root, newTree, maxFunctionDefinitions, maxFunctionArguments);
    189189
    190           currentSize++;
    191           totalListMinSize--;
    192 
    193           actualArity = SampleArity(random, newTree, size - currentSize);
     190          currentLength++;
     191          totalListMinLength--;
     192
     193          actualArity = SampleArity(random, newTree, targetLength - currentLength);
    194194          for (int i = 0; i < actualArity; i++) {
    195195            // insert a dummy sub-tree and add the pending extension to the list
    … …  
    198198            extensionPoints.Add(new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 });
    199199          }
    200           totalListMinSize += newTree.Grammar.GetMinExpressionLength(newTree.Symbol);
     200          totalListMinLength += newTree.Grammar.GetMinExpressionLength(newTree.Symbol);
    201201        }
    202202      }
    … …  
    283283    }
    284284
    285     private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetSize) {
     285    private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetLength) {
    286286      // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
    287287      int minArity = node.Grammar.GetMinSubtreeCount(node.Symbol);
    288288      int maxArity = node.Grammar.GetMaxSubtreeCount(node.Symbol);
    289       if (maxArity > targetSize) {
    290         maxArity = targetSize;
    291       }
    292       // the min number of sub-trees has to be set to a value that is large enough so that the largest possible tree is at least tree size
    293       // if 1..3 trees are possible and the largest possible first sub-tree is smaller larger than the target size then minArity should be at least 2
     289      if (maxArity > targetLength) {
     290        maxArity = targetLength;
     291      }
     292      // the min number of sub-trees has to be set to a value that is large enough so that the largest possible tree is at least tree length
     293      // if 1..3 trees are possible and the largest possible first sub-tree is smaller larger than the target length then minArity should be at least 2
    294294      long aggregatedLongestExpressionLength = 0;
    295295      for (int i = 0; i < maxArity; i++) {
    296296        aggregatedLongestExpressionLength += (from s in node.Grammar.GetAllowedSymbols(node.Symbol, i)
    297297                                              select node.Grammar.GetMaxExpressionLength(s)).Max();
    298         if (aggregatedLongestExpressionLength < targetSize) minArity = i;
     298        if (aggregatedLongestExpressionLength < targetLength) minArity = i;
    299299        else break;
    300300      }
    301301
    302       // the max number of sub-trees has to be set to a value that is small enough so that the smallest possible tree is at most tree size
    303       // if 1..3 trees are possible and the smallest possible first sub-tree is already larger than the target size then maxArity should be at most 0
     302      // the max number of sub-trees has to be set to a value that is small enough so that the smallest possible tree is at most tree length
     303      // if 1..3 trees are possible and the smallest possible first sub-tree is already larger than the target length then maxArity should be at most 0
    304304      long aggregatedShortestExpressionLength = 0;
    305305      for (int i = 0; i < maxArity; i++) {
    306306        aggregatedShortestExpressionLength += (from s in node.Grammar.GetAllowedSymbols(node.Symbol, i)
    307307                                               select node.Grammar.GetMinExpressionLength(s)).Min();
    308         if (aggregatedShortestExpressionLength > targetSize) {
     308        if (aggregatedShortestExpressionLength > targetLength) {
    309309          maxArity = i;
    310310          break;
Note: See TracChangeset for help on using the changeset viewer.