Free cookie consent management tool by TermsFeed Policy Generator

Changeset 448


Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs

    r444 r448  
    8282    internal IFunctionTree CreateBalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
    8383      IFunction rootFunction = GetRandomRoot(maxTreeSize, maxTreeHeight);
    84       IFunctionTree tree = MakeBalancedTree(rootFunction, maxTreeSize - 1, maxTreeHeight - 1);
     84      IFunctionTree tree = MakeBalancedTree(rootFunction, maxTreeHeight - 1);
    8585      return tree;
    8686    }
     
    9595    internal IFunctionTree CreateUnbalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
    9696      IFunction rootFunction = GetRandomRoot(maxTreeSize, maxTreeHeight);
    97       IFunctionTree tree = MakeUnbalancedTree(rootFunction, maxTreeSize - 1, maxTreeHeight - 1);
     97      IFunctionTree tree = MakeUnbalancedTree(rootFunction, maxTreeHeight - 1);
    9898      return tree;
    9999    }
    100100
    101101    internal IFunctionTree PTC2(IRandom random, int size, int maxDepth) {
    102       if(size <= 1 || maxDepth<=1) return RandomSelect(terminals).GetTreeNode();
     102      if(size <= 1 || maxDepth <= 1) return RandomSelect(terminals).GetTreeNode();
    103103      List<object[]> list = new List<object[]>();
    104104      IFunctionTree root = GetRandomRoot(size, maxDepth).GetTreeNode();
     
    132132          parent.InsertSubTree(a, branch); // insert a smallest possible tree
    133133          currentSize += branch.Size;
    134           totalListMinSize-=branch.Size;
     134          totalListMinSize -= branch.Size;
    135135        } else {
    136136          IFunction selectedFunction = RandomSelect(GetAllowedSubFunctions(parent.Function, a).Where(
     
    192192    internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight, bool balanceTrees) {
    193193      // get the minimal needed height based on allowed functions and extend the max-height if necessary
    194       int minTreeHeight = allowedFunctions.Select(f => GetMinimalTreeSize(f)).Min();
     194      int minTreeHeight = allowedFunctions.Select(f => GetMinimalTreeHeight(f)).Min();
    195195      if(minTreeHeight > maxTreeHeight)
    196196        maxTreeHeight = minTreeHeight;
     
    212212      IFunctionTree root;
    213213      if(balanceTrees) {
    214         root = MakeBalancedTree(selectedFunction, maxTreeSize - 1, maxTreeHeight - 1);
     214        root = MakeBalancedTree(selectedFunction, maxTreeHeight - 1);
    215215      } else {
    216         root = MakeUnbalancedTree(selectedFunction, maxTreeSize - 1, maxTreeHeight - 1);
     216        root = MakeUnbalancedTree(selectedFunction, maxTreeHeight - 1);
    217217      }
    218218      return root;
     
    446446    }
    447447
    448     private IFunctionTree MakeUnbalancedTree(IFunction parent, int maxTreeSize, int maxTreeHeight) {
    449       if(maxTreeHeight == 0 || maxTreeSize == 0) return parent.GetTreeNode();
     448
     449    private IFunctionTree MakeUnbalancedTree(IFunction parent, int maxTreeHeight) {
     450      if(maxTreeHeight == 0) return parent.GetTreeNode();
    450451      int minArity;
    451452      int maxArity;
    452453      GetMinMaxArity(parent, out minArity, out maxArity);
    453       if(maxArity >= maxTreeSize) {
    454         maxArity = maxTreeSize;
    455       }
    456454      int actualArity = random.Next(minArity, maxArity + 1);
    457455      if(actualArity > 0) {
    458456        IFunctionTree parentTree = parent.GetTreeNode();
    459         int maxSubTreeSize = maxTreeSize / actualArity;
    460457        for(int i = 0; i < actualArity; i++) {
    461           IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
    462             GetMinimalTreeSize(f) <= maxSubTreeSize).ToArray();
     458          IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight).ToArray();
    463459          IFunction selectedFunction = RandomSelect(possibleFunctions);
    464           IFunctionTree newSubTree = MakeUnbalancedTree(selectedFunction, maxSubTreeSize - 1, maxTreeHeight - 1);
     460          IFunctionTree newSubTree = MakeUnbalancedTree(selectedFunction, maxTreeHeight - 1);
    465461          parentTree.InsertSubTree(i, newSubTree);
    466462        }
     
    469465      return parent.GetTreeNode();
    470466    }
     467
    471468
    472469    // NOTE: this method doesn't build fully balanced trees because we have constraints on the
    473470    // types of possible sub-functions which can indirectly impose a limit for the depth of a given sub-tree
    474     private IFunctionTree MakeBalancedTree(IFunction parent, int maxTreeSize, int maxTreeHeight) {
    475       if(maxTreeHeight == 0 || maxTreeSize == 0) return parent.GetTreeNode();
     471    private IFunctionTree MakeBalancedTree(IFunction parent, int maxTreeHeight) {
     472      if(maxTreeHeight == 0) return parent.GetTreeNode();
    476473      int minArity;
    477474      int maxArity;
    478475      GetMinMaxArity(parent, out minArity, out maxArity);
    479       if(maxArity >= maxTreeSize) {
    480         maxArity = maxTreeSize;
    481       }
    482476      int actualArity = random.Next(minArity, maxArity + 1);
    483477      if(actualArity > 0) {
    484478        IFunctionTree parentTree = parent.GetTreeNode();
    485         int maxSubTreeSize = maxTreeSize / actualArity;
    486479        for(int i = 0; i < actualArity; i++) {
    487           // first try to find a function that fits into the maxHeight and maxSize limits
    488           IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(
    489             f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
    490             GetMinimalTreeSize(f) <= maxSubTreeSize &&
     480          // first try to find a function that fits into the maxHeight limit
     481          IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
    491482            !IsTerminal(f)).ToArray();
    492483          // no possible function found => extend function set to terminals
     
    498489          } else {
    499490            IFunction selectedFunction = RandomSelect(possibleFunctions);
    500             IFunctionTree newTree = MakeBalancedTree(selectedFunction, maxSubTreeSize - 1, maxTreeHeight - 1);
     491            IFunctionTree newTree = MakeBalancedTree(selectedFunction, maxTreeHeight - 1);
    501492            parentTree.InsertSubTree(i, newTree);
    502493          }
Note: See TracChangeset for help on using the changeset viewer.