Changeset 5549 for branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs

Timestamp:

02/22/11 19:04:54 (14 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:

• branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs (modified) (12 diffs)

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

@@ -32 +32 @@
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
   [StorableClass]
-  [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed size")]
+  [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed length")]
   public sealed class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator,
     ISymbolicExpressionTreeSizeConstraintOperator, ISymbolicExpressionTreeGrammarBasedOperator, ISymbolicExpressionTreeArchitectureAlteringOperator {
@@ -98 +98 @@
 
     public static ISymbolicExpressionTree Create(IRandom random, ISymbolicExpressionTreeGrammar grammar,
-      int maxTreeSize, int maxTreeHeight,
+      int maxTreeLength, int maxTreeDepth,
       int maxFunctionDefinitions, int maxFunctionArguments
       ) {
@@ -105 +105 @@
       if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);
       rootNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
-      tree.Root = PTC2(random, rootNode, maxTreeSize, maxTreeHeight, maxFunctionDefinitions, maxFunctionArguments);
+      tree.Root = PTC2(random, rootNode, maxTreeLength, maxTreeDepth, maxFunctionDefinitions, maxFunctionArguments);
       return tree;
     }
@@ -116 +116 @@
 
     public static ISymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionTreeNode seedNode,
-      int maxTreeSize, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
-      // tree size is limited by the grammar and by the explicit size constraints
-      int allowedMinSize = seedNode.Grammar.GetMinExpressionLength(seedNode.Symbol);
-      int allowedMaxSize = Math.Min(maxTreeSize, seedNode.Grammar.GetMaxExpressionLength(seedNode.Symbol));
+      int maxLength, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
+      // tree length is limited by the grammar and by the explicit size constraints
+      int allowedMinLength = seedNode.Grammar.GetMinExpressionLength(seedNode.Symbol);
+      int allowedMaxLength = Math.Min(maxLength, seedNode.Grammar.GetMaxExpressionLength(seedNode.Symbol));
       int tries = 0;
       while (tries++ < MAX_TRIES) {
-        // select a target tree size uniformly in the possible range (as determined by explicit limits and limits of the grammar)
-        int treeSize;
-        treeSize = random.Next(allowedMinSize, allowedMaxSize + 1);
-        if (treeSize <= 1 || maxDepth <= 1) return seedNode;
-
-        bool success = CreateFullTreeFromSeed(random, seedNode, seedNode.Grammar, treeSize, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
+        // select a target tree length uniformly in the possible range (as determined by explicit limits and limits of the grammar)
+        int targetTreeLength;
+        targetTreeLength = random.Next(allowedMinLength, allowedMaxLength + 1);
+        if (targetTreeLength <= 1 || maxDepth <= 1) return seedNode;
+
+        bool success = CreateFullTreeFromSeed(random, seedNode, seedNode.Grammar, targetTreeLength, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
 
         // if successful => check constraints and return the tree if everything looks ok        
-        if (success && seedNode.GetSize() <= maxTreeSize && seedNode.GetHeight() <= maxDepth) {
+        if (success && seedNode.GetLength() <= maxLength && seedNode.GetDepth() <= maxDepth) {
           return seedNode;
         } else {
@@ -136 +136 @@
           while (seedNode.SubTrees.Count() > 0) seedNode.RemoveSubTree(0);
         }
-        // try a different size MAX_TRIES times
+        // try a different length MAX_TRIES times
       }
       throw new ArgumentException("Couldn't create a random valid tree.");
@@ -142 +142 @@
 
     private static bool CreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeGrammar globalGrammar,
-      int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
+      int targetLength, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
       try {
-        TryCreateFullTreeFromSeed(random, root, globalGrammar, size, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
+        TryCreateFullTreeFromSeed(random, root, globalGrammar, targetLength, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
         return true;
       }
@@ -151 +151 @@
 
     private static void TryCreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeGrammar globalGrammar,
-      int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
+      int targetLength, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
       List<TreeExtensionPoint> extensionPoints = new List<TreeExtensionPoint>();
-      int currentSize = 1;
-      int totalListMinSize = globalGrammar.GetMinExpressionLength(root.Symbol) - 1;
-      int actualArity = SampleArity(random, root, size);
+      int currentLength = 1;
+      int totalListMinLength = globalGrammar.GetMinExpressionLength(root.Symbol) - 1;
+      int actualArity = SampleArity(random, root, targetLength);
       for (int i = 0; i < actualArity; i++) {
         // insert a dummy sub-tree and add the pending extension to the list
@@ -163 +163 @@
       }
       // while there are pending extension points and we have not reached the limit of adding new extension points
-      while (extensionPoints.Count > 0 && totalListMinSize + currentSize < size) {
+      while (extensionPoints.Count > 0 && totalListMinLength + currentLength < targetLength) {
         int randomIndex = random.Next(extensionPoints.Count);
         TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
@@ -176 +176 @@
                                 where parent.Grammar.IsAllowedChild(parent.Symbol, s, argumentIndex)
                                 where parent.Grammar.GetMinExpressionDepth(s) + extensionDepth - 1 < maxDepth
-                                where parent.Grammar.GetMaxExpressionLength(s) > size - totalListMinSize - currentSize
+                                where parent.Grammar.GetMaxExpressionLength(s) > targetLength - totalListMinLength - currentLength
                                 select s)
                                .ToList();
@@ -188 +188 @@
           InitializeNewTreeNode(random, root, newTree, maxFunctionDefinitions, maxFunctionArguments);
 
-          currentSize++;
-          totalListMinSize--;
-
-          actualArity = SampleArity(random, newTree, size - currentSize);
+          currentLength++;
+          totalListMinLength--;
+
+          actualArity = SampleArity(random, newTree, targetLength - currentLength);
           for (int i = 0; i < actualArity; i++) {
             // insert a dummy sub-tree and add the pending extension to the list
@@ -198 +198 @@
             extensionPoints.Add(new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 });
           }
-          totalListMinSize += newTree.Grammar.GetMinExpressionLength(newTree.Symbol);
+          totalListMinLength += newTree.Grammar.GetMinExpressionLength(newTree.Symbol);
         }
       }
@@ -283 +283 @@
     }
 
-    private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetSize) {
+    private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetLength) {
       // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
       int minArity = node.Grammar.GetMinSubtreeCount(node.Symbol);
       int maxArity = node.Grammar.GetMaxSubtreeCount(node.Symbol);
-      if (maxArity > targetSize) {
-        maxArity = targetSize;
-      }
-      // 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
-      // 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
+      if (maxArity > targetLength) {
+        maxArity = targetLength;
+      }
+      // 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
+      // 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
       long aggregatedLongestExpressionLength = 0;
       for (int i = 0; i < maxArity; i++) {
         aggregatedLongestExpressionLength += (from s in node.Grammar.GetAllowedSymbols(node.Symbol, i)
                                               select node.Grammar.GetMaxExpressionLength(s)).Max();
-        if (aggregatedLongestExpressionLength < targetSize) minArity = i;
+        if (aggregatedLongestExpressionLength < targetLength) minArity = i;
         else break;
       }
 
-      // 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 
-      // 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
+      // 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 
+      // 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
       long aggregatedShortestExpressionLength = 0;
       for (int i = 0; i < maxArity; i++) {
         aggregatedShortestExpressionLength += (from s in node.Grammar.GetAllowedSymbols(node.Symbol, i)
                                                select node.Grammar.GetMinExpressionLength(s)).Min();
-        if (aggregatedShortestExpressionLength > targetSize) {
+        if (aggregatedShortestExpressionLength > targetLength) {
           maxArity = i;
           break;