Changeset 6911 for trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs

Timestamp:

10/12/11 17:06:14 (13 years ago)

Author:

mkommend

Message:

#1657: Corrected and adapted implementation of !PTC2 to handle symbol frequencies correctly and to always create trees of the target size. Additionally the performance of the grammars have been improved and a unit test was added.

File:

• trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs (modified) (13 diffs)

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs

@@ -120 +120 @@
       public int ChildIndex { get; set; }
       public int ExtensionPointDepth { get; set; }
+      public int MaximumExtensionLength { get; set; }
+      public int MinimumExtensionLength { get; set; }
     }
 
@@ -132 +134 @@
       // tree length is limited by the grammar and by the explicit size constraints
       int allowedMinLength = seedNode.Grammar.GetMinimumExpressionLength(seedNode.Symbol);
-      int allowedMaxLength = Math.Min(maxLength, seedNode.Grammar.GetMaximumExpressionLength(seedNode.Symbol));
+      int allowedMaxLength = Math.Min(maxLength, seedNode.Grammar.GetMaximumExpressionLength(seedNode.Symbol, maxDepth));
       int tries = 0;
       while (tries++ < MAX_TRIES) {
@@ -140 +142 @@
         if (targetTreeLength <= 1 || maxDepth <= 1) return;
 
-        bool success = TryCreateFullTreeFromSeed(random, seedNode, seedNode.Grammar, targetTreeLength, maxDepth);
+        bool success = TryCreateFullTreeFromSeed(random, seedNode, targetTreeLength - 1, maxDepth - 1);
 
         // if successful => check constraints and return the tree if everything looks ok        
@@ -154 +156 @@
     }
 
-    private static bool TryCreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeGrammar globalGrammar,
+    private static bool TryCreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root,
       int targetLength, int maxDepth) {
       List<TreeExtensionPoint> extensionPoints = new List<TreeExtensionPoint>();
-      int currentLength = 1;
-      int totalListMinLength = globalGrammar.GetMinimumExpressionLength(root.Symbol) - 1;
-      int actualArity = SampleArity(random, root, targetLength);
+      int currentLength = 0;
+      int actualArity = SampleArity(random, root, targetLength, maxDepth);
       if (actualArity < 0) return false;
 
@@ -166 +167 @@
         var dummy = new SymbolicExpressionTreeNode();
         root.AddSubtree(dummy);
-        extensionPoints.Add(new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 0 });
-      }
+        var x = new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 0 };
+        FillExtensionLengths(x, maxDepth);
+        extensionPoints.Add(x);
+      }
+      long minExtensionPointsLength = extensionPoints.Select(x => x.MinimumExtensionLength).Sum();
+      long maxExtensionPointsLength = extensionPoints.Select(x => x.MaximumExtensionLength).Sum();
+
       // while there are pending extension points and we have not reached the limit of adding new extension points
-      while (extensionPoints.Count > 0 && totalListMinLength + currentLength < targetLength) {
+      while (extensionPoints.Count > 0 && minExtensionPointsLength + currentLength <= targetLength) {
         int randomIndex = random.Next(extensionPoints.Count);
         TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
@@ -176 +182 @@
         int argumentIndex = nextExtension.ChildIndex;
         int extensionDepth = nextExtension.ExtensionPointDepth;
-        if (parent.Grammar.GetMinimumExpressionDepth(parent.Symbol) >= maxDepth - extensionDepth) {
+
+        if (parent.Grammar.GetMinimumExpressionDepth(parent.Symbol) > maxDepth - extensionDepth) {
           ReplaceWithMinimalTree(random, root, parent, argumentIndex);
+          int insertedTreeLength = parent.GetSubtree(argumentIndex).GetLength();
+          currentLength += insertedTreeLength;
+          minExtensionPointsLength -= insertedTreeLength;
+          maxExtensionPointsLength -= insertedTreeLength;
         } else {
-          var allowedSymbols = (from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, argumentIndex)
-                                where s.InitialFrequency > 0.0
-                                where parent.Grammar.GetMinimumExpressionDepth(s) < maxDepth - extensionDepth + 1
-                                where parent.Grammar.GetMaximumExpressionLength(s) > targetLength - totalListMinLength - currentLength
-                                select s)
-                               .ToList();
+          //remove currently chosen extension point from calculation
+          minExtensionPointsLength -= nextExtension.MinimumExtensionLength;
+          maxExtensionPointsLength -= nextExtension.MaximumExtensionLength;
+
+          var symbols = from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, argumentIndex)
+                        where s.InitialFrequency > 0.0
+                        where parent.Grammar.GetMinimumExpressionDepth(s) <= maxDepth - extensionDepth
+                        where parent.Grammar.GetMinimumExpressionLength(s) <= targetLength - currentLength - minExtensionPointsLength
+                        select s;
+          if (maxExtensionPointsLength < targetLength - currentLength)
+            symbols = from s in symbols
+                      where parent.Grammar.GetMaximumExpressionLength(s, maxDepth - extensionDepth) >= targetLength - currentLength - maxExtensionPointsLength
+                      select s;
+          var allowedSymbols = symbols.ToList();
+
           if (allowedSymbols.Count == 0) return false;
           var weights = allowedSymbols.Select(x => x.InitialFrequency).ToList();
@@ -198 +218 @@
 
           currentLength++;
-          totalListMinLength--;
-
-          actualArity = SampleArity(random, newTree, targetLength - currentLength);
+          actualArity = SampleArity(random, newTree, targetLength - currentLength, maxDepth - extensionDepth);
           if (actualArity < 0) return false;
           for (int i = 0; i < actualArity; i++) {
@@ -206 +224 @@
             var dummy = new SymbolicExpressionTreeNode();
             newTree.AddSubtree(dummy);
-            extensionPoints.Add(new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 });
+            var x = new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 };
+            FillExtensionLengths(x, maxDepth);
+            extensionPoints.Add(x);
+            maxExtensionPointsLength += x.MaximumExtensionLength;
+            minExtensionPointsLength += x.MinimumExtensionLength;
           }
-          totalListMinLength += newTree.Grammar.GetMinimumExpressionLength(newTree.Symbol);
         }
       }
@@ -218 +239 @@
         ISymbolicExpressionTreeNode parent = nextExtension.Parent;
         int a = nextExtension.ChildIndex;
-        int d = nextExtension.ExtensionPointDepth;
         ReplaceWithMinimalTree(random, root, parent, a);
       }
@@ -252 +272 @@
     }
 
-    private static bool IsTopLevelBranch(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode branch) {
-      return branch is SymbolicExpressionTreeTopLevelNode;
-    }
-
-    private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetLength) {
+    private static void FillExtensionLengths(TreeExtensionPoint extension, int maxDepth) {
+      var grammar = extension.Parent.Grammar;
+      int maxLength = int.MinValue;
+      int minLength = int.MaxValue;
+      foreach (ISymbol s in grammar.GetAllowedChildSymbols(extension.Parent.Symbol, extension.ChildIndex)) {
+        if (s.InitialFrequency > 0.0) {
+          int max = grammar.GetMaximumExpressionLength(s, maxDepth - extension.ExtensionPointDepth);
+          maxLength = Math.Max(maxLength, max);
+          int min = grammar.GetMinimumExpressionLength(s);
+          minLength = Math.Min(minLength, min);
+        }
+      }
+
+      extension.MaximumExtensionLength = maxLength;
+      extension.MinimumExtensionLength = minLength;
+    }
+
+    private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetLength, int maxDepth) {
       // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
       int minArity = node.Grammar.GetMinimumSubtreeCount(node.Symbol);
@@ -263 +296 @@
         maxArity = targetLength;
       }
+      if (minArity == maxArity) return minArity;
+
       // 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
@@ -269 +304 @@
         aggregatedLongestExpressionLength += (from s in node.Grammar.GetAllowedChildSymbols(node.Symbol, i)
                                               where s.InitialFrequency > 0.0
-                                              select node.Grammar.GetMaximumExpressionLength(s)).Max();
+                                              select node.Grammar.GetMaximumExpressionLength(s, maxDepth)).Max();
         if (i > minArity && aggregatedLongestExpressionLength < targetLength) minArity = i + 1;
         else break;
@@ -289 +324 @@
       return random.Next(minArity, maxArity + 1);
     }
+
   }
 }