Changeset 202

Timestamp:

04/28/08 21:35:23 (16 years ago)

Author:

gkronber

Message:

bug fixes in struct-id operators

Location:

trunk/sources/HeuristicLab.StructureIdentification

Files:

• Manipulation/ChangeNodeTypeManipulation.cs (modified) (4 diffs)
• TreeGardener.cs (modified) (7 diffs)

trunk/sources/HeuristicLab.StructureIdentification/Manipulation/ChangeNodeTypeManipulation.cs

@@ -156 +156 @@
       int maxArity;
       // create a new tree-node for a randomly selected function
-      IFunctionTree newTree = allowedFunctions[random.Next(allowedFunctions.Count)].GetTreeNode();
-      gardener.GetMinMaxArity(newTree.Function, out minArity, out maxArity);
+      IFunction selectedFunction = allowedFunctions[random.Next(allowedFunctions.Count)];
+      gardener.GetMinMaxArity(selectedFunction, out minArity, out maxArity);
       // if the old child had too many sub-trees then the new child should keep as many sub-trees as possible
       if (actualArity > maxArity)
@@ -165 +165 @@
       // create a list that holds old sub-trees that we can reuse in the new tree
       List<IFunctionTree> availableSubTrees = new List<IFunctionTree>(child.SubTrees);
-      List<IFunctionTree> freshSubTrees = new List<IFunctionTree>() { newTree };
+      List<IFunctionTree> freshSubTrees = new List<IFunctionTree>();
+      IFunctionTree newTree = selectedFunction.GetTreeNode();
       // randomly select the sub-trees that we keep
       for (int i = 0; i < actualArity; i++) {
@@ -172 +173 @@
         // then use a random existing sub-tree. When there are no existing sub-trees
         // that fit in the given slot then create a new random tree and use it for the slot
-        ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(newTree.Function, i);
+        ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(selectedFunction, i);
         var matchingSubTrees = availableSubTrees.Where(subTree => allowedSubFunctions.Contains(subTree.Function));
         if (matchingSubTrees.Count() > 0) {
@@ -186 +187 @@
         }
       }
+      freshSubTrees.Add(newTree);
       uninitializedBranches = freshSubTrees;
       return newTree;

trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs

@@ -81 +81 @@
     /// <returns></returns>
     internal IFunctionTree CreateBalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
-      IFunctionTree root = CreateRandomRoot(maxTreeSize, maxTreeHeight);
-      MakeBalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
-      return root;
+      IFunction rootFunction = GetRandomRoot(maxTreeSize, maxTreeHeight);
+      IFunctionTree tree = MakeBalancedTree(rootFunction, maxTreeSize - 1, maxTreeHeight - 1);
+      return tree;
     }
 
@@ -94 +94 @@
     /// <returns></returns>
     internal IFunctionTree CreateUnbalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
-      IFunctionTree root = CreateRandomRoot(maxTreeSize, maxTreeHeight);
-      MakeUnbalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
-      return root;
+      IFunction rootFunction = GetRandomRoot(maxTreeSize, maxTreeHeight);
+      IFunctionTree tree = MakeUnbalancedTree(rootFunction, maxTreeSize - 1, maxTreeHeight - 1);
+      return tree;
     }
 
@@ -141 +141 @@
 
       // build the tree 
-      IFunctionTree root = selectedFunction.GetTreeNode();
+      IFunctionTree root;
       if(balanceTrees) {
-        MakeBalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
+        root = MakeBalancedTree(selectedFunction, maxTreeSize - 1, maxTreeHeight - 1);
       } else {
-        MakeUnbalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
+        root = MakeUnbalancedTree(selectedFunction, maxTreeSize - 1, maxTreeHeight - 1);
       }
       return root;
@@ -373 +373 @@
 
     #region private utility methods
-    private IFunctionTree CreateRandomRoot(int maxTreeSize, int maxTreeHeight) {
+    private IFunction GetRandomRoot(int maxTreeSize, int maxTreeHeight) {
       if(maxTreeHeight == 1 || maxTreeSize == 1) {
         IFunction selectedTerminal = RandomSelect(terminals);
-        return selectedTerminal.GetTreeNode();
+        return selectedTerminal;
       } else {
         IFunction[] possibleFunctions = allFunctions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
           GetMinimalTreeSize(f) <= maxTreeSize).ToArray();
         IFunction selectedFunction = RandomSelect(possibleFunctions);
-        return selectedFunction.GetTreeNode();
-      }
-    }
-
-    private void MakeUnbalancedTree(IFunctionTree parent, int maxTreeSize, int maxTreeHeight) {
-      if(maxTreeHeight == 0 || maxTreeSize == 0) return;
+        return selectedFunction;
+      }
+    }
+
+    private IFunctionTree MakeUnbalancedTree(IFunction parent, int maxTreeSize, int maxTreeHeight) {
+      if(maxTreeHeight == 0 || maxTreeSize == 0) return parent.GetTreeNode();
       int minArity;
       int maxArity;
-      GetMinMaxArity(parent.Function, out minArity, out maxArity);
+      GetMinMaxArity(parent, out minArity, out maxArity);
       if(maxArity >= maxTreeSize) {
         maxArity = maxTreeSize;
@@ -395 +395 @@
       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.Function, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
+          IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
             GetMinimalTreeSize(f) <= maxSubTreeSize).ToArray();
           IFunction selectedFunction = RandomSelect(possibleFunctions);
-          IFunctionTree newSubTree = selectedFunction.GetTreeNode();
-          MakeUnbalancedTree(newSubTree, maxSubTreeSize - 1, maxTreeHeight - 1);
-          parent.InsertSubTree(i, newSubTree);
-        }
-      }
+          IFunctionTree newSubTree = MakeUnbalancedTree(selectedFunction, maxSubTreeSize - 1, maxTreeHeight - 1);
+          parentTree.InsertSubTree(i, newSubTree);
+        }
+        return parentTree;
+      }
+      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 void MakeBalancedTree(IFunctionTree parent, int maxTreeSize, int maxTreeHeight) {
-      if(maxTreeHeight == 0 || maxTreeSize == 0) return;
+    private IFunctionTree MakeBalancedTree(IFunction parent, int maxTreeSize, int maxTreeHeight) {
+      if(maxTreeHeight == 0 || maxTreeSize == 0) return parent.GetTreeNode();
       int minArity;
       int maxArity;
-      GetMinMaxArity(parent.Function, out minArity, out maxArity);
+      GetMinMaxArity(parent, out minArity, out maxArity);
       if(maxArity >= maxTreeSize) {
         maxArity = maxTreeSize;
@@ -419 +421 @@
       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.Function, i).Where(
+          IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(
             f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
             GetMinimalTreeSize(f) <= maxSubTreeSize &&
@@ -428 +431 @@
           // no possible function found => extend function set to terminals
           if(possibleFunctions.Length == 0) {
-            possibleFunctions = GetAllowedSubFunctions(parent.Function, i).Where(f => IsTerminal(f)).ToArray();
+            possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => IsTerminal(f)).ToArray();
             IFunction selectedTerminal = RandomSelect(possibleFunctions);
             IFunctionTree newTree = selectedTerminal.GetTreeNode();
-            parent.InsertSubTree(i, newTree);
+            parentTree.InsertSubTree(i, newTree);
           } else {
             IFunction selectedFunction = RandomSelect(possibleFunctions);
-            IFunctionTree newTree = selectedFunction.GetTreeNode();
-            parent.InsertSubTree(i, newTree);
-            MakeBalancedTree(newTree, maxSubTreeSize - 1, maxTreeHeight - 1);
+            IFunctionTree newTree = MakeBalancedTree(selectedFunction, maxSubTreeSize - 1, maxTreeHeight - 1);
+            parentTree.InsertSubTree(i, newTree);
           }
         }
-      }
+        return parentTree;
+      }
+      return parent.GetTreeNode();
     }