Free cookie consent management tool by TermsFeed Policy Generator

Changeset 163 for trunk


Ignore:
Timestamp:
04/22/08 20:28:26 (17 years ago)
Author:
gkronber
Message:

fixed #119

Location:
trunk/sources/HeuristicLab.StructureIdentification
Files:
5 edited

Legend:

Unmodified
Added
Removed

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

    r162 r163  
    4848      AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
    4949      AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
    50       AddVariableInfo(new VariableInfo("BalancedTreesRate", "Determines how many trees should be balanced", typeof(DoubleData), VariableKind.In));
    5150      AddVariableInfo(new VariableInfo("FunctionTree", "The tree to mutate", typeof(IFunctionTree), VariableKind.In | VariableKind.Out));
    5251      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
    … …  
    5958      MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);
    6059      GPOperatorLibrary library = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
    61       double balancedTreesRate = GetVariableValue<DoubleData>("BalancedTreesRate", scope, true).Data;
    6260      IntData treeSize = GetVariableValue<IntData>("TreeSize", scope, false);
    6361      IntData treeHeight = GetVariableValue<IntData>("TreeHeight", scope, false);
    6462      int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;
    6563      int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;
    66 
    6764      TreeGardener gardener = new TreeGardener(random, library);
    6865      IFunctionTree parent = gardener.GetRandomParentNode(root);
    69 
    7066      IFunctionTree selectedChild;
    7167      int selectedChildIndex;
    … …  
    8076      if (selectedChild.SubTrees.Count == 0) {
    8177        IFunctionTree newTerminal = ChangeTerminalType(parent, selectedChild, selectedChildIndex, gardener, random);
    82 
    8378        if (parent == null) {
    8479          // no parent means the new child is the initial operator
    … …  
    9186        }
    9287        if(!gardener.IsValidTree(root)) throw new InvalidProgramException();
    93 
    9488        // size and height stays the same when changing a terminal so no need to update the variables
    9589        // schedule an operation to initialize the new terminal
    … …  
    9791      } else {
    9892        List<IFunctionTree> uninitializedBranches;
    99         IFunctionTree newFunction = ChangeFunctionType(parent, selectedChild, selectedChildIndex, gardener, random, balancedTreesRate, out uninitializedBranches);
    100 
     93        IFunctionTree newFunction = ChangeFunctionType(parent, selectedChild, selectedChildIndex, gardener, random, out uninitializedBranches);
    10194        if (parent == null) {
    10295          // no parent means the new function is the initial operator
    … …  
    110103          parent.InsertSubTree(selectedChildIndex, newFunction);
    111104        }
    112 
    113105        // recalculate size and height
    114106        treeSize.Data = gardener.GetTreeSize(root);
    115107        treeHeight.Data = gardener.GetTreeHeight(root);
    116 
    117108        // check if whole tree is ok
    118109        // check if the size of the new tree is still in the allowed bounds
    … …  
    122113          throw new InvalidProgramException();
    123114        }
    124 
    125115        // return a composite operation that initializes all created sub-trees
    126116        return gardener.CreateInitializationOperation(uninitializedBranches, scope);
    … …  
    139129        }
    140130      }
    141 
    142131      // selecting from the terminals should always work since the current child was also a terminal
    143132      // so in the worst case we will just create a new terminal of the same type again.
    … …  
    146135
    147136    private IFunctionTree ChangeFunctionType(IFunctionTree parent, IFunctionTree child, int childIndex, TreeGardener gardener, MersenneTwister random,
    148       double balancedTreesRate, out List<IFunctionTree> uninitializedBranches) {
     137      out List<IFunctionTree> uninitializedBranches) {
    149138      // since there are subtrees, we have to check which
    150       // and how many of the existing subtrees we can reuse
    151 
    152       // let's choose the function we want to use instead of the old child. For this we have to determine the
     139      // and how many of the existing subtrees we can reuse.
     140      // first let's choose the function we want to use instead of the old child. For this we have to determine the
    153141      // pool of allowed functions based on constraints of the parent if there is one.
    154142      IList<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent!=null?parent.Function:null, childIndex);
    155 
    156143      // try to make a tree with the same arity as the old child.
    157144      int actualArity = child.SubTrees.Count;
    … …  
    166153        return minArity <= actualArity;
    167154      }).ToList();
    168 
    169155      // create a new tree-node for a randomly selected function
    170156      IFunctionTree newTree = new FunctionTree(allowedFunctions[random.Next(allowedFunctions.Count)]);
    171 
    172157      gardener.GetMinMaxArity(newTree.Function, out minArity, out maxArity);
    173158      // if the old child had too many sub-trees then the new child should keep as many sub-trees as possible
    174159      if (actualArity > maxArity)
    175160        actualArity = maxArity;
    176 
    177161      // get the allowed size and height for new sub-trees
    178162      // use the size of the smallest subtree as the maximal allowed size for new subtrees to
    … …  
    180164      int maxSubTreeSize = child.SubTrees.Select(subTree => gardener.GetTreeSize(subTree)).Min();
    181165      int maxSubTreeHeight = gardener.GetTreeHeight(child) - 1;
    182 
    183166      // create a list that holds old sub-trees that we can reuse in the new tree
    184167      List<IFunctionTree> availableSubTrees = new List<IFunctionTree>(child.SubTrees);
    185168      List<IFunctionTree> freshSubTrees = new List<IFunctionTree>() { newTree };
    186 
    187169      // randomly select the sub-trees that we keep
    188170      for (int i = 0; i < actualArity; i++) {
    … …  
    193175        ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(newTree.Function, i);
    194176        var matchingSubTrees = availableSubTrees.Where(subTree => allowedSubFunctions.Contains(subTree.Function));
    195 
    196177        if (matchingSubTrees.Count() > 0) {
    197178          IFunctionTree selectedSubTree = matchingSubTrees.ElementAt(random.Next(matchingSubTrees.Count()));
    … …  
    201182        } else {
    202183          // no existing matching tree found => create a new one
    203           IFunctionTree freshTree;
    204           if(random.NextDouble() <= balancedTreesRate) {
    205             freshTree = gardener.CreateRandomTree(allowedSubFunctions, maxSubTreeSize, maxSubTreeHeight, true);
    206           } else {
    207             freshTree = gardener.CreateRandomTree(allowedSubFunctions, maxSubTreeSize, maxSubTreeHeight, false);
    208           }
     184          IFunctionTree freshTree = gardener.CreateRandomTree(allowedSubFunctions, maxSubTreeSize, maxSubTreeHeight);
    209185          freshSubTrees.AddRange(gardener.GetAllSubTrees(freshTree));
    210 
    211186          newTree.InsertSubTree(i, freshTree);
    212187        }

  • trunk/sources/HeuristicLab.StructureIdentification/Manipulation/CutOutNodeManipulation.cs

    r155 r163  
    5353      AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
    5454      AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
    55       AddVariableInfo(new VariableInfo("BalancedTreesRate", "Determines how many trees should be balanced", typeof(DoubleData), VariableKind.In));
    5655      AddVariableInfo(new VariableInfo("FunctionTree", "The tree to mutate", typeof(IFunctionTree), VariableKind.In | VariableKind.Out));
    5756      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
    … …  
    6665      int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;
    6766      int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;
    68       double balancedTreesRate = GetVariableValue<DoubleData>("BalancedTreesRate", scope, true).Data;
    69 
    7067      TreeGardener gardener = new TreeGardener(random, library);
    7168      IFunctionTree parent = gardener.GetRandomParentNode(root);
    … …  
    7673        if (root.SubTrees.Count > 0) {
    7774          root = root.SubTrees[random.Next(root.SubTrees.Count)];
    78 
    7975          GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
    8076          GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
    81 
    8277          // update the variable
    8378          scope.GetVariable(scope.TranslateName("FunctionTree")).Value = root;
    … …  
    9085          // we want to cut the root node and there are no sub-trees => create a new random terminal
    9186          IFunctionTree newTree;
    92           newTree = gardener.CreateRandomTree(gardener.Terminals, 1, 1, false);
     87          newTree = gardener.CreateRandomTree(gardener.Terminals, 1, 1);
    9388          GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newTree);
    9489          GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(newTree);
    … …  
    10297        }
    10398      }
    104 
    10599      // select a child to cut away
    106100      int childIndex = random.Next(parent.SubTrees.Count);
    107101      IFunctionTree child = parent.SubTrees[childIndex];
    108 
    109102      // match the sub-trees of the child with the allowed sub-trees of the parent
    110103      ICollection<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
    111104      IFunctionTree[] possibleChilds = child.SubTrees.Where(t => allowedFunctions.Contains(t.Function)).ToArray();
    112 
    113105      if (possibleChilds.Length > 0) {
    114106        // replace child with a random child of that child
    … …  
    116108        parent.RemoveSubTree(childIndex);
    117109        parent.InsertSubTree(childIndex, selectedChild);
    118 
    119110        if (!gardener.IsValidTree(root)) {
    120111          throw new InvalidProgramException();
    121112        }
    122 
    123113        // update the size and height of our tree
    124114        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
    … …  
    130120        // determine the level of the parent
    131121        int parentLevel = gardener.GetBranchLevel(root, parent);
    132 
    133122        // first remove the old child (first step essential!)
    134123        parent.RemoveSubTree(childIndex);
    135124        // then determine the number of nodes left over after the child has been removed!
    136125        int remainingNodes = gardener.GetTreeSize(root);
    137 
    138126        allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
    139         IFunctionTree newFunctionTree = gardener.CreateRandomTree(allowedFunctions, maxTreeSize - remainingNodes, maxTreeHeight - parentLevel, false);
    140 
     127        IFunctionTree newFunctionTree = gardener.CreateRandomTree(allowedFunctions, maxTreeSize - remainingNodes, maxTreeHeight - parentLevel);
    141128        parent.InsertSubTree(childIndex, newFunctionTree);
    142 
    143129        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
    144130        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
    145 
    146131        if (!gardener.IsValidTree(root)) {
    147132          throw new InvalidProgramException();
    148133        }
    149 
    150134        // schedule an initialization operation for the new function-tree
    151135        return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newFunctionTree), scope);

  • trunk/sources/HeuristicLab.StructureIdentification/Manipulation/DeleteSubTreeManipulation.cs

    r155 r163  
    6060      if(parent == null) {
    6161        IFunctionTree newTree = gardener.CreateRandomTree(1, 1, false);
    62 
    6362        // check if the tree is ok
    6463        if(!gardener.IsValidTree(newTree)) {
    6564          throw new InvalidOperationException();
    6665        }
    67 
    6866        // update sizes to match the new tree
    6967        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newTree);
    … …  
    9189          throw new InvalidOperationException();
    9290        }
    93 
    9491        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
    9592        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
    … …  
    9996        // replace with a minimal random seedling
    10097        parent.RemoveSubTree(childIndex);
    101 
    10298        ICollection<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
    103         IFunctionTree newFunctionTree = gardener.CreateRandomTree(allowedFunctions, 1, 1, true);
    104 
     99        IFunctionTree newFunctionTree = gardener.CreateRandomTree(allowedFunctions, 1, 1);
    105100        parent.InsertSubTree(childIndex, newFunctionTree);
    106 
    107101        if(!gardener.IsValidTree(root)) {
    108102          throw new InvalidProgramException();
    109103        }
    110 
    111104        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
    112105        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);

  • trunk/sources/HeuristicLab.StructureIdentification/Manipulation/SubstituteSubTreeManipulation.cs

    r155 r163  
    4242      AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
    4343      AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
    44       AddVariableInfo(new VariableInfo("BalancedTreesRate", "Determines how many trees should be balanced", typeof(DoubleData), VariableKind.In));
    4544      AddVariableInfo(new VariableInfo("FunctionTree", "The tree to manipulate", typeof(IFunctionTree), VariableKind.In | VariableKind.Out));
    4645      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
    … …  
    5453      int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;
    5554      int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;
    56       double balancedTreesRate = GetVariableValue<DoubleData>("BalancedTreesRate", scope, true).Data;
    5755      int treeSize = GetVariableValue<IntData>("TreeSize", scope, true).Data;
    5856      int treeHeight = GetVariableValue<IntData>("TreeHeight", scope, true).Data;
    59 
    6057      TreeGardener gardener = new TreeGardener(random, library);
    61 
    6258      IFunctionTree parent = gardener.GetRandomParentNode(root);
    6359      if(parent == null) {
    6460        // parent == null means we should subsitute the whole tree
    6561        // => create a new random tree
    66 
    67         // create a new random function tree
    68         IFunctionTree newTree;
    69         if(random.NextDouble() <= balancedTreesRate) {
    70           newTree = gardener.CreateRandomTree(gardener.AllFunctions, maxTreeSize, maxTreeHeight, true);
    71         } else {
    72           newTree = gardener.CreateRandomTree(gardener.AllFunctions, maxTreeSize, maxTreeHeight, false);
    73         }
    74 
     62        IFunctionTree newTree = gardener.CreateRandomTree(gardener.AllFunctions, maxTreeSize, maxTreeHeight);
    7563        if(!gardener.IsValidTree(newTree)) {
    7664          throw new InvalidProgramException();
    … …  
    9886        // it will be inserted
    9987        int parentLevel = gardener.GetBranchLevel(root, parent);
    100 
    10188        int maxSubTreeHeight = maxTreeHeight - parentLevel;
    10289        int maxSubTreeSize = maxTreeSize - (treeSize - gardener.GetTreeSize(parent.SubTrees[childIndex]));
    10390
    10491        // create a random function tree
    105         IFunctionTree newTree;
    106         if(random.NextDouble() <= balancedTreesRate) {
    107           newTree = gardener.CreateRandomTree(allowedFunctions, maxSubTreeSize, maxSubTreeHeight, true);
    108         } else {
    109           newTree = gardener.CreateRandomTree(allowedFunctions, maxSubTreeSize, maxSubTreeHeight, false);
    110         }
    111 
     92        IFunctionTree newTree = gardener.CreateRandomTree(allowedFunctions, maxSubTreeSize, maxSubTreeHeight);
    11293        parent.RemoveSubTree(childIndex);
    11394        parent.InsertSubTree(childIndex, newTree);

  • trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs

    r155 r163  
    7474
    7575    #region random initialization
     76    internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight) {
     77      // default is non-balanced trees
     78      return CreateRandomTree(allowedFunctions, maxTreeSize, maxTreeHeight, false);
     79    }
    7680    internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight, bool balanceTrees) {
    7781
Note: See TracChangeset for help on using the changeset viewer.