Changeset 448

Timestamp:

08/05/08 15:23:43 (16 years ago)

Author:

gkronber

Message:

removed size limit check in MakeBalancedTree and MakeUnbalancedTree. The methods are used for classic RampedHalfHalfInitialization where only the height constraint is checked. Use PTC2 initialization if the size constraint should also be checked. (ticket #225)

File:

• trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs (modified) (8 diffs)

trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs

@@ -82 +82 @@
     internal IFunctionTree CreateBalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
       IFunction rootFunction = GetRandomRoot(maxTreeSize, maxTreeHeight);
-      IFunctionTree tree = MakeBalancedTree(rootFunction, maxTreeSize - 1, maxTreeHeight - 1);
+      IFunctionTree tree = MakeBalancedTree(rootFunction, maxTreeHeight - 1);
       return tree;
     }
@@ -95 +95 @@
     internal IFunctionTree CreateUnbalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
       IFunction rootFunction = GetRandomRoot(maxTreeSize, maxTreeHeight);
-      IFunctionTree tree = MakeUnbalancedTree(rootFunction, maxTreeSize - 1, maxTreeHeight - 1);
+      IFunctionTree tree = MakeUnbalancedTree(rootFunction, maxTreeHeight - 1);
       return tree;
     }
 
     internal IFunctionTree PTC2(IRandom random, int size, int maxDepth) {
-      if(size <= 1 || maxDepth<=1) return RandomSelect(terminals).GetTreeNode();
+      if(size <= 1 || maxDepth <= 1) return RandomSelect(terminals).GetTreeNode();
       List<object[]> list = new List<object[]>();
       IFunctionTree root = GetRandomRoot(size, maxDepth).GetTreeNode();
@@ -132 +132 @@
           parent.InsertSubTree(a, branch); // insert a smallest possible tree
           currentSize += branch.Size;
-          totalListMinSize-=branch.Size;
+          totalListMinSize -= branch.Size;
         } else {
           IFunction selectedFunction = RandomSelect(GetAllowedSubFunctions(parent.Function, a).Where(
@@ -192 +192 @@
     internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight, bool balanceTrees) {
       // get the minimal needed height based on allowed functions and extend the max-height if necessary
-      int minTreeHeight = allowedFunctions.Select(f => GetMinimalTreeSize(f)).Min();
+      int minTreeHeight = allowedFunctions.Select(f => GetMinimalTreeHeight(f)).Min();
       if(minTreeHeight > maxTreeHeight)
         maxTreeHeight = minTreeHeight;
@@ -212 +212 @@
       IFunctionTree root;
       if(balanceTrees) {
-        root = MakeBalancedTree(selectedFunction, maxTreeSize - 1, maxTreeHeight - 1);
+        root = MakeBalancedTree(selectedFunction, maxTreeHeight - 1);
       } else {
-        root = MakeUnbalancedTree(selectedFunction, maxTreeSize - 1, maxTreeHeight - 1);
+        root = MakeUnbalancedTree(selectedFunction, maxTreeHeight - 1);
       }
       return root;
@@ -446 +446 @@
     }
 
-    private IFunctionTree MakeUnbalancedTree(IFunction parent, int maxTreeSize, int maxTreeHeight) {
-      if(maxTreeHeight == 0 || maxTreeSize == 0) return parent.GetTreeNode();
+
+    private IFunctionTree MakeUnbalancedTree(IFunction parent, int maxTreeHeight) {
+      if(maxTreeHeight == 0) return parent.GetTreeNode();
       int minArity;
       int maxArity;
       GetMinMaxArity(parent, out minArity, out maxArity);
-      if(maxArity >= maxTreeSize) {
-        maxArity = maxTreeSize;
-      }
       int actualArity = random.Next(minArity, maxArity + 1);
       if(actualArity > 0) {
         IFunctionTree parentTree = parent.GetTreeNode();
-        int maxSubTreeSize = maxTreeSize / actualArity;
         for(int i = 0; i < actualArity; i++) {
-          IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
-            GetMinimalTreeSize(f) <= maxSubTreeSize).ToArray();
+          IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight).ToArray();
           IFunction selectedFunction = RandomSelect(possibleFunctions);
-          IFunctionTree newSubTree = MakeUnbalancedTree(selectedFunction, maxSubTreeSize - 1, maxTreeHeight - 1);
+          IFunctionTree newSubTree = MakeUnbalancedTree(selectedFunction, maxTreeHeight - 1);
           parentTree.InsertSubTree(i, newSubTree);
         }
@@ -469 +465 @@
       return parent.GetTreeNode();
     }
+
 
     // NOTE: this method doesn't build fully balanced trees because we have constraints on the
     // types of possible sub-functions which can indirectly impose a limit for the depth of a given sub-tree
-    private IFunctionTree MakeBalancedTree(IFunction parent, int maxTreeSize, int maxTreeHeight) {
-      if(maxTreeHeight == 0 || maxTreeSize == 0) return parent.GetTreeNode();
+    private IFunctionTree MakeBalancedTree(IFunction parent, int maxTreeHeight) {
+      if(maxTreeHeight == 0) return parent.GetTreeNode();
       int minArity;
       int maxArity;
       GetMinMaxArity(parent, out minArity, out maxArity);
-      if(maxArity >= maxTreeSize) {
-        maxArity = maxTreeSize;
-      }
       int actualArity = random.Next(minArity, maxArity + 1);
       if(actualArity > 0) {
         IFunctionTree parentTree = parent.GetTreeNode();
-        int maxSubTreeSize = maxTreeSize / actualArity;
         for(int i = 0; i < actualArity; i++) {
-          // first try to find a function that fits into the maxHeight and maxSize limits 
-          IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(
-            f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
-            GetMinimalTreeSize(f) <= maxSubTreeSize &&
+          // first try to find a function that fits into the maxHeight limit
+          IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight && 
             !IsTerminal(f)).ToArray();
           // no possible function found => extend function set to terminals
@@ -498 +489 @@
           } else {
             IFunction selectedFunction = RandomSelect(possibleFunctions);
-            IFunctionTree newTree = MakeBalancedTree(selectedFunction, maxSubTreeSize - 1, maxTreeHeight - 1);
+            IFunctionTree newTree = MakeBalancedTree(selectedFunction, maxTreeHeight - 1);
             parentTree.InsertSubTree(i, newTree);
           }