Changeset 167 for trunk/sources/HeuristicLab.StructureIdentification

Timestamp:

04/22/08 23:52:28 (17 years ago)

Author:

gkronber

Message:

simplified and improved ChangeNodeTypeManipulation (ticket #120)

Location:

trunk/sources/HeuristicLab.StructureIdentification

Files:

• Manipulation/ChangeNodeTypeManipulation.cs (modified) (6 diffs)
• TreeGardener.cs (modified) (2 diffs)

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

@@ -66 +66 @@
       IFunctionTree selectedChild;
       int selectedChildIndex;
-      if (parent == null) {
+      if(parent == null) {
         selectedChildIndex = 0;
         selectedChild = root;
@@ -74 +74 @@
       }
 
-      if (selectedChild.SubTrees.Count == 0) {
+      if(selectedChild.SubTrees.Count == 0) {
         IFunctionTree newTerminal = ChangeTerminalType(parent, selectedChild, selectedChildIndex, gardener, random);
-        if (parent == null) {
+        if(parent == null) {
           // no parent means the new child is the initial operator
           // and we have to update the value in the variable
@@ -91 +91 @@
       } else {
         List<IFunctionTree> uninitializedBranches;
-        IFunctionTree newFunction = ChangeFunctionType(parent, selectedChild, selectedChildIndex, gardener, random, out uninitializedBranches);
-        if (parent == null) {
+        IFunctionTree newFunctionTree = ChangeFunctionType(parent, selectedChild, selectedChildIndex, gardener, random, out uninitializedBranches);
+        // in rare cases the function creates a tree that breaks the size limits
+        // calculate the height and size difference and 
+        // check if the size of the new tree is still in the allowed bounds
+        int oldChildSize = gardener.GetTreeSize(selectedChild);
+        int oldChildHeight = gardener.GetTreeSize(selectedChild);
+        int newChildSize = gardener.GetTreeSize(newFunctionTree);
+        int newChildHeight = gardener.GetTreeHeight(newFunctionTree);
+        if((treeHeight.Data - oldChildHeight) + newChildHeight > maxTreeHeight ||
+          (treeSize.Data - oldChildSize) + newChildSize > maxTreeSize) {
+          // if size-constraints are violated don't change anything
+          return null;
+        }
+        if(parent == null) {
           // no parent means the new function is the initial operator
           // and we have to update the value in the variable
-          scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newFunction;
-          root = newFunction;
+          scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newFunctionTree;
+          root = newFunctionTree;
         } else {
           // remove the old child
           parent.RemoveSubTree(selectedChildIndex);
           // add the new child as sub-tree of parent
-          parent.InsertSubTree(selectedChildIndex, newFunction);
+          parent.InsertSubTree(selectedChildIndex, newFunctionTree);
         }
-        // recalculate size and height
-        treeSize.Data = gardener.GetTreeSize(root);
-        treeHeight.Data = gardener.GetTreeHeight(root);
+        // update size and height
+        treeSize.Data = (treeSize.Data - oldChildSize) + newChildSize;
+        treeHeight.Data = gardener.GetTreeHeight(root); // must recalculate height because we can't know wether the manipulated branch was the deepest branch
         // check if whole tree is ok
-        // check if the size of the new tree is still in the allowed bounds
-        if (!gardener.IsValidTree(root) ||
-          treeHeight.Data > maxTreeHeight ||
-          treeSize.Data > maxTreeSize) {
+        if(!gardener.IsValidTree(root))
           throw new InvalidProgramException();
-        }
         // return a composite operation that initializes all created sub-trees
         return gardener.CreateInitializationOperation(uninitializedBranches, scope);
       }
     }
+  
 
     private IFunctionTree ChangeTerminalType(IFunctionTree parent, IFunctionTree child, int childIndex, TreeGardener gardener, MersenneTwister random) {
@@ -146 +155 @@
       int minArity;
       int maxArity;
-      // only allow functions where we can keep all existing sub-trees
-      // we don't want to create new sub-trees here 
-      // this restriction can be removed if we add code that creates sub-trees where necessary (gkronber 22.04.08)
-      allowedFunctions = allowedFunctions.Where(f => {
-        gardener.GetMinMaxArity(f, out minArity, out maxArity);
-        return minArity <= actualArity;
-      }).ToList();
       // create a new tree-node for a randomly selected function
       IFunctionTree newTree = new FunctionTree(allowedFunctions[random.Next(allowedFunctions.Count)]);
@@ -159 +161 @@
       if (actualArity > maxArity)
         actualArity = maxArity;
-      // get the allowed size and height for new sub-trees
-      // use the size of the smallest subtree as the maximal allowed size for new subtrees to
-      // prevent that we ever create trees over the MaxTreeSize limit
-      int maxSubTreeSize = child.SubTrees.Select(subTree => gardener.GetTreeSize(subTree)).Min();
-      int maxSubTreeHeight = gardener.GetTreeHeight(child) - 1;
+      if(actualArity < minArity)
+        actualArity = minArity;
       // create a list that holds old sub-trees that we can reuse in the new tree
       List<IFunctionTree> availableSubTrees = new List<IFunctionTree>(child.SubTrees);
@@ -181 +180 @@
           availableSubTrees.Remove(selectedSubTree); // the branch shouldn't be available for the following slots
         } else {
-          // no existing matching tree found => create a new one
-          IFunctionTree freshTree = gardener.CreateRandomTree(allowedSubFunctions, maxSubTreeSize, maxSubTreeHeight);
+          // no existing matching tree found => create a new tree of minimal size
+          IFunctionTree freshTree = gardener.CreateRandomTree(allowedSubFunctions, 1, 1);
           freshSubTrees.AddRange(gardener.GetAllSubTrees(freshTree));
           newTree.InsertSubTree(i, freshTree);

trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs

@@ -53 +53 @@
       this.random = random;
       this.funLibrary = funLibrary;
-
       this.allFunctions = new List<IFunction>();
       terminals = new List<IFunction>();
       functions = new List<IFunction>();
-
       // init functions and terminals based on constraints
       foreach (IFunction fun in funLibrary.Group.Operators) {
@@ -68 +66 @@
         }
       }
-
       allFunctions.AddRange(functions);
       allFunctions.AddRange(terminals);