Changeset 149

Timestamp:

04/22/08 12:48:01 (16 years ago)

Author:

gkronber

Message:

minor changes in GP manipulation operators (#112)

Location:

branches/FunctionsAndStructIdRefactoring/HeuristicLab.StructureIdentification/Manipulation

Files:

• ChangeNodeTypeManipulation.cs (modified) (7 diffs)
• CutOutNodeManipulation.cs (modified) (5 diffs)
• DeleteSubTreeManipulation.cs (modified) (3 diffs)
• SubstituteSubTreeManipulation.cs (modified) (1 diff)

branches/FunctionsAndStructIdRefactoring/HeuristicLab.StructureIdentification/Manipulation/ChangeNodeTypeManipulation.cs

@@ -66 +66 @@
       } else {
         selectedChildIndex = random.Next(parent.SubTrees.Count);
-        selectedChild = parent.SubTrees [selectedChildIndex];
+        selectedChild = parent.SubTrees[selectedChildIndex];
       }
 
@@ -123 +123 @@
 
     private IFunctionTree ChangeTerminalType(IFunctionTree parent, IFunctionTree child, int childIndex, TreeGardener gardener, MersenneTwister random) {
-
       IList<IFunction> allowedChildren;
       if (parent == null) {
@@ -159 +158 @@
       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);
@@ -165 +166 @@
       }).ToList();
 
+      // create a new tree-node for a randomly selected function
       IFunctionTree newTree = new FunctionTree(allowedFunctions[random.Next(allowedFunctions.Count)]);
 
       gardener.GetMinMaxArity(newTree.Function, out minArity, out maxArity);
-      // if the old child had too many sub-trees then make the new child with the maximal arity
+      // if the old child had too many sub-trees then the new child should keep as many sub-trees as possible
       if (actualArity > maxArity)
         actualArity = maxArity;
@@ -185 +187 @@
       for (int i = 0; i < actualArity; i++) {
         // fill all sub-tree slots of the new tree
-        // if for a given slot i there are existing sub-trees that can be used in that slot
+        // if for a given slot i there are multiple existing sub-trees that can be used in that slot
         // 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
-        IList<IFunction> allowedOperators = analyser.GetAllowedOperators(newTree.Function, i).Cast<IFunction>().ToList();
-        var matchingSubTrees = availableSubTrees.Where(subTree => allowedOperators.Contains(subTree.Function));
+        IList<IFunction> allowedSubFunctions = analyser.GetAllowedOperators(newTree.Function, i).Cast<IFunction>().ToList();
+        var matchingSubTrees = availableSubTrees.Where(subTree => allowedSubFunctions.Contains(subTree.Function));
 
         if (matchingSubTrees.Count() > 0) {
@@ -197 +199 @@
           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;
           if(random.NextDouble() <= balancedTreesRate) {
-            freshTree = gardener.CreateRandomTree(allowedOperators, maxSubTreeSize, maxSubTreeHeight, true);
+            freshTree = gardener.CreateRandomTree(allowedSubFunctions, maxSubTreeSize, maxSubTreeHeight, true);
           } else {
-            freshTree = gardener.CreateRandomTree(allowedOperators, maxSubTreeSize, maxSubTreeHeight, false);
+            freshTree = gardener.CreateRandomTree(allowedSubFunctions, maxSubTreeSize, maxSubTreeHeight, false);
           }
           freshSubTrees.AddRange(gardener.GetAllSubTrees(freshTree));
@@ -208 +211 @@
         }
       }
-
       uninitializedBranches = freshSubTrees;
       return newTree;

branches/FunctionsAndStructIdRefactoring/HeuristicLab.StructureIdentification/Manipulation/CutOutNodeManipulation.cs

@@ -80 +80 @@
           GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
 
-          // this is not really necessary (we can leave it in until the tree is stable)
-          if (!gardener.IsValidTree(root)) {
-            throw new InvalidProgramException();
-          }
-
           // update the variable
           scope.GetVariable(scope.TranslateName("FunctionTree")).Value = root;
@@ -90 +85 @@
             throw new InvalidProgramException();
           }
-          // the tree is already initialized so we don't have to schedule initialization operations
+          // we reused a sub-tree so we don't have to schedule initialization operations
           return null;
         } else {
-          // create a new random tree
+          // we want to cut the root node and there are no sub-trees => create a new random terminal
           IFunctionTree newTree;
-          if(random.NextDouble() <= balancedTreesRate) {
-            newTree = gardener.CreateRandomTree(gardener.AllFunctions, maxTreeSize, maxTreeHeight, true);
-          } else {
-            newTree = gardener.CreateRandomTree(gardener.AllFunctions, maxTreeSize, maxTreeHeight, false);
-          }
-
+          newTree = gardener.CreateRandomTree(gardener.Terminals, 1, 1, false);
           GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newTree);
           GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(newTree);
-
           // update the variable
           scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newTree;
-
           if (!gardener.IsValidTree(newTree)) {
             throw new InvalidProgramException();
           }
-
           // schedule an operation to initialize the whole tree
           return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newTree), scope);
@@ -116 +103 @@
       }
 
+      // select a child to cut away
       int childIndex = random.Next(parent.SubTrees.Count);
       IFunctionTree child = parent.SubTrees[childIndex];
 
       // match the sub-trees of the child with the allowed sub-trees of the parent
-      IFunctionTree[] possibleChilds = gardener.GetAllowedSubFunctions(parent.Function, childIndex).SelectMany(allowedFun => child.SubTrees
-        .Where(subTree => allowedFun == subTree.Function)).ToArray(); // Actually we should probably use OperatorEqualityComparer here (gkronber 21.04.08)
+      IList<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
+      IFunctionTree[] possibleChilds = child.SubTrees.Where(t => allowedFunctions.Contains(t.Function)).ToArray();
 
       if (possibleChilds.Length > 0) {
-        // replace child with a random child of the child
-        // make a clone to simplify removing obsolete branches from the function-tree
+        // replace child with a random child of that child
         IFunctionTree selectedChild = possibleChilds[random.Next(possibleChilds.Length)];        
         parent.RemoveSubTree(childIndex);
@@ -140 +127 @@
         return null;
       } else {
+        // can't reuse an existing branch => create a new tree
         // determine the level of the parent
         int parentLevel = gardener.GetBranchLevel(root, parent);
@@ -148 +136 @@
         int remainingNodes = gardener.GetTreeSize(root);
 
-        IList<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
-        IFunctionTree newFunctionTree = gardener.CreateRandomTree(allowedFunctions, maxTreeSize - remainingNodes, maxTreeHeight - parentLevel, true);
+        allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
+        IFunctionTree newFunctionTree = gardener.CreateRandomTree(allowedFunctions, maxTreeSize - remainingNodes, maxTreeHeight - parentLevel, false);
 
         parent.InsertSubTree(childIndex, newFunctionTree);

branches/FunctionsAndStructIdRefactoring/HeuristicLab.StructureIdentification/Manipulation/DeleteSubTreeManipulation.cs

@@ -59 +59 @@
       // => return a new minimal random tree
       if(parent == null) {
-        IFunctionTree newTree = gardener.CreateRandomTree(1, 1, true);
+        IFunctionTree newTree = gardener.CreateRandomTree(1, 1, false);
 
         // check if the tree is ok
@@ -75 +75 @@
       }
 
+      // select a branch to prune
       int childIndex = random.Next(parent.SubTrees.Count);
-
       int min;
       int max;
@@ -112 +112 @@
         GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
         // again the root hasn't changed so we don't need to update the 'FunctionTree' variable
+        // but we have to return an initialization operation for the newly created tree
         return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newFunctionTree), scope);
       }

branches/FunctionsAndStructIdRefactoring/HeuristicLab.StructureIdentification/Manipulation/SubstituteSubTreeManipulation.cs

@@ -110 +110 @@
         }
 
-        IFunctionTree oldChild = parent.SubTrees[childIndex];
         parent.RemoveSubTree(childIndex);
         parent.InsertSubTree(childIndex, newTree);