Changeset 444

Timestamp:

08/05/08 11:34:33 (16 years ago)

Author:

gkronber

Message:

fixed #227

Location:

trunk/sources/HeuristicLab.StructureIdentification

Files:

• ProbabilisticTreeCreator.cs (modified) (2 diffs)
• Recombination/SizeFairCrossOver.cs (modified) (1 diff)
• TreeGardener.cs (modified) (7 diffs)

trunk/sources/HeuristicLab.StructureIdentification/ProbabilisticTreeCreator.cs

@@ -27 +27 @@
 using HeuristicLab.Random;
 using HeuristicLab.Functions;
+using System.Diagnostics;
 
 namespace HeuristicLab.StructureIdentification {
@@ -65 +66 @@
       scope.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(actualTreeHeight)));
 
-      if(!gardener.IsValidTree(root)) { throw new InvalidProgramException(); }
-
-      if(actualTreeHeight > maxTreeHeight) {
-        throw new InvalidProgramException();
-      }
+      Debug.Assert(gardener.IsValidTree(root) && actualTreeHeight<=maxTreeHeight);
 
       return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(root), scope);

trunk/sources/HeuristicLab.StructureIdentification/Recombination/SizeFairCrossOver.cs

@@ -96 +96 @@
 
       // check if the new tree is valid and if the height of is still in the allowed bounds (we are not so strict for the max-size)
-      Debug.Assert(gardener.IsValidTree(newTree) && newTreeHeight <= maxTreeHeight);
+      Debug.Assert(gardener.IsValidTree(newTree) && newTreeHeight <= maxTreeHeight && newTreeSize <= maxTreeSize);
       return gardener.CreateInitializationOperation(newBranches, child);
     }

trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs

@@ -100 +100 @@
 
     internal IFunctionTree PTC2(IRandom random, int size, int maxDepth) {
-      if(size == 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();
+
       int currentSize = 1;
+      int totalListMinSize = 0;
       int minArity;
       int maxArity;
@@ -111 +113 @@
       }
       int actualArity = random.Next(minArity, maxArity + 1);
-      for(int i=0;i<actualArity;i++) {
+      totalListMinSize += GetMinimalTreeSize(root.Function) - 1;
+      for(int i = 0; i < actualArity; i++) {
         // insert a dummy sub-tree and add the pending extension to the list
         root.AddSubTree(null);
-        list.Add(new object[] {root, i, 2});
-      }
-
-      while(list.Count > 0 && list.Count + currentSize < size) {
+        list.Add(new object[] { root, i, 2 });
+      }
+
+      while(list.Count > 0 && totalListMinSize + currentSize < size) {
         int randomIndex = random.Next(list.Count);
         object[] nextExtension = list[randomIndex];
@@ -126 +129 @@
         if(d == maxDepth) {
           parent.RemoveSubTree(a);
-          parent.InsertSubTree(a, RandomSelect(GetAllowedSubFunctions(parent.Function, a).Where(f => IsTerminal(f)).ToArray()).GetTreeNode());
+          IFunctionTree branch = CreateRandomTree(GetAllowedSubFunctions(parent.Function, a), 1, 1);
+          parent.InsertSubTree(a, branch); // insert a smallest possible tree
+          currentSize += branch.Size;
+          totalListMinSize-=branch.Size;
         } else {
-          IFunction selectedFunction = RandomSelect(GetAllowedSubFunctions(parent.Function, a).Where( 
-            f => !IsTerminal(f) && GetMinimalTreeHeight(f) + (d-1) <= maxDepth).ToArray());
+          IFunction selectedFunction = RandomSelect(GetAllowedSubFunctions(parent.Function, a).Where(
+            f => !IsTerminal(f) && GetMinimalTreeHeight(f) + (d - 1) <= maxDepth).ToArray());
           IFunctionTree newTree = selectedFunction.GetTreeNode();
           parent.RemoveSubTree(a);
           parent.InsertSubTree(a, newTree);
+          currentSize++;
+          totalListMinSize--;
 
           GetMinMaxArity(selectedFunction, out minArity, out maxArity);
@@ -144 +152 @@
             list.Add(new object[] { newTree, i, d + 1 });
           }
-        }
-        currentSize++;
+          totalListMinSize += GetMinimalTreeSize(newTree.Function) - 1;
+        }
       }
       while(list.Count > 0) {
@@ -184 +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 => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data).Min();
+      int minTreeHeight = allowedFunctions.Select(f => GetMinimalTreeSize(f)).Min();
       if(minTreeHeight > maxTreeHeight)
         maxTreeHeight = minTreeHeight;
       // get the minimal needed size based on allowed functions and extend the max-size if necessary
-      int minTreeSize = allowedFunctions.Select(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data).Min();
+      int minTreeSize = allowedFunctions.Select(f => GetMinimalTreeSize(f)).Min();
       if(minTreeSize > maxTreeSize)
         maxTreeSize = minTreeSize;
@@ -197 +205 @@
 
       // filter the set of allowed functions and select only from those that fit into the given maximal size and height limits
-      IFunction[] possibleFunctions = allowedFunctions.Where(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data <= treeHeight &&
-        ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data <= treeSize).ToArray();
+      IFunction[] possibleFunctions = allowedFunctions.Where(f => GetMinimalTreeHeight(f) <= treeHeight &&
+        GetMinimalTreeSize(f) <= treeSize).ToArray();
       IFunction selectedFunction = RandomSelect(possibleFunctions);
 
@@ -519 +527 @@
       List<IFunctionTree> branches = new List<IFunctionTree>();
       foreach(IFunctionTree subTree in tree.SubTrees) {
-        if(subTree.Height>=level-1)
-        branches.AddRange(GetBranchesAtLevel(subTree, level - 1));
+        if(subTree.Height >= level - 1)
+          branches.AddRange(GetBranchesAtLevel(subTree, level - 1));
       }
       return branches;