Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
04/22/08 18:05:14 (17 years ago)
Author:
gkronber
Message:

merged FunctionsAndStructIdRefactoring-branch (r142, r143, r144, r145, r146, r147, r148, r149, r152, r153) back into the trunk (ticket #112)

Location:
trunk/sources/HeuristicLab.StructureIdentification/Manipulation
Files:
6 edited

Legend:

Unmodified
Added
Removed

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

    r23 r155  
    2929using HeuristicLab.Data;
    3030using HeuristicLab.Constraints;
     31using HeuristicLab.Functions;
    3132
    3233namespace HeuristicLab.StructureIdentification {
    … …  
    3940      AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
    4041      AddVariableInfo(new VariableInfo("BalancedTreesRate", "Determines how many trees should be balanced", typeof(DoubleData), VariableKind.In));
    41       AddVariableInfo(new VariableInfo("OperatorTree", "The tree to mutate", typeof(IOperator), VariableKind.In));
    42       AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
    43       AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.In));
     42      AddVariableInfo(new VariableInfo("FunctionTree", "The tree to mutate", typeof(IFunctionTree), VariableKind.In | VariableKind.Out));
     43      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
     44      AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
    4445    }
    4546
    4647
    4748    public override IOperation Apply(IScope scope) {
    48       IOperator rootOperator = GetVariableValue<IOperator>("OperatorTree", scope, false);
     49      IFunctionTree root = GetVariableValue<IFunctionTree>("FunctionTree", scope, false);
    4950      MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);
    5051      GPOperatorLibrary library = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
    … …  
    5657
    5758      TreeGardener gardener = new TreeGardener(random, library);
    58 
    59       IOperator parent = gardener.GetRandomParentNode(rootOperator);
    60 
    61       IOperator selectedChild;
     59      IFunctionTree parent = gardener.GetRandomParentNode(root);
     60
     61      IFunctionTree selectedChild;
    6262      int selectedChildIndex;
    6363      if (parent == null) {
    6464        selectedChildIndex = 0;
    65         selectedChild = rootOperator;
     65        selectedChild = root;
    6666      } else {
    67         selectedChildIndex = random.Next(parent.SubOperators.Count);
    68         selectedChild = parent.SubOperators[selectedChildIndex];
    69       }
    70 
    71       if (selectedChild.SubOperators.Count == 0) {
    72         IOperator newTerminal = ChangeTerminalType(parent, selectedChild, selectedChildIndex, gardener, random);
     67        selectedChildIndex = random.Next(parent.SubTrees.Count);
     68        selectedChild = parent.SubTrees[selectedChildIndex];
     69      }
     70
     71      if (selectedChild.SubTrees.Count == 0) {
     72        IFunctionTree newTerminal = ChangeTerminalType(parent, selectedChild, selectedChildIndex, gardener, random);
    7373
    7474        if (parent == null) {
    7575          // no parent means the new child is the initial operator
    7676          // and we have to update the value in the variable
    77           scope.GetVariable("OperatorTree").Value = newTerminal;
     77          scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newTerminal;
    7878        } else {
    79           parent.RemoveSubOperator(selectedChildIndex);
    80           parent.AddSubOperator(newTerminal, selectedChildIndex);
     79          parent.RemoveSubTree(selectedChildIndex);
     80          parent.InsertSubTree(selectedChildIndex, newTerminal);
    8181          // updating the variable is not necessary because it stays the same
    8282        }
     83        if(!gardener.IsValidTree(root)) throw new InvalidProgramException();
    8384
    8485        // size and height stays the same when changing a terminal so no need to update the variables
    8586        // schedule an operation to initialize the new terminal
    86         return gardener.CreateInitializationOperation(gardener.GetAllOperators(newTerminal), scope);
     87        return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newTerminal), scope);
    8788      } else {
    88         List<IOperator> uninitializedOperators;
    89         IOperator newFunction = ChangeFunctionType(parent, selectedChild, selectedChildIndex, gardener, random, balancedTreesRate, out uninitializedOperators);
     89        List<IFunctionTree> uninitializedBranches;
     90        IFunctionTree newFunction = ChangeFunctionType(parent, selectedChild, selectedChildIndex, gardener, random, balancedTreesRate, out uninitializedBranches);
    9091
    9192        if (parent == null) {
    9293          // no parent means the new function is the initial operator
    9394          // and we have to update the value in the variable
    94           scope.GetVariable("OperatorTree").Value = newFunction;
    95           rootOperator = newFunction;
     95          scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newFunction;
     96          root = newFunction;
    9697        } else {
    9798          // remove the old child
    98           parent.RemoveSubOperator(selectedChildIndex);
     99          parent.RemoveSubTree(selectedChildIndex);
    99100          // add the new child as sub-tree of parent
    100           parent.AddSubOperator(newFunction, selectedChildIndex);
     101          parent.InsertSubTree(selectedChildIndex, newFunction);
    101102        }
    102103
    103104        // recalculate size and height
    104         treeSize.Data = gardener.GetTreeSize(rootOperator);
    105         treeHeight.Data = gardener.GetTreeHeight(rootOperator);
    106 
     105        treeSize.Data = gardener.GetTreeSize(root);
     106        treeHeight.Data = gardener.GetTreeHeight(root);
     107
     108        // check if whole tree is ok
    107109        // check if the size of the new tree is still in the allowed bounds
    108         if (treeHeight.Data > maxTreeHeight ||
     110        if (!gardener.IsValidTree(root) ||
     111          treeHeight.Data > maxTreeHeight ||
    109112          treeSize.Data > maxTreeSize) {
    110113          throw new InvalidProgramException();
    111114        }
    112115
    113         // check if whole tree is ok
    114         if (!gardener.IsValidTree(rootOperator)) {
    115           throw new InvalidProgramException();
    116         }
    117 
    118116        // return a composite operation that initializes all created sub-trees
    119         return gardener.CreateInitializationOperation(uninitializedOperators, scope);
    120       }
    121     }
    122 
    123 
    124     private IOperator ChangeTerminalType(IOperator parent, IOperator child, int childIndex, TreeGardener gardener, MersenneTwister random) {
    125 
    126       IList<IOperator> allowedChildren;
     117        return gardener.CreateInitializationOperation(uninitializedBranches, scope);
     118      }
     119    }
     120
     121    private IFunctionTree ChangeTerminalType(IFunctionTree parent, IFunctionTree child, int childIndex, TreeGardener gardener, MersenneTwister random) {
     122      IList<IFunction> allowedChildren;
    127123      if (parent == null) {
    128124        allowedChildren = gardener.Terminals;
    129125      } else {
    130         SubOperatorsConstraintAnalyser analyser = new SubOperatorsConstraintAnalyser();
    131         analyser.AllPossibleOperators = gardener.Terminals;
    132         allowedChildren = analyser.GetAllowedOperators(parent, childIndex);
     126        allowedChildren = new List<IFunction>();
     127        var allAllowedChildren = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
     128        foreach(IFunction c in allAllowedChildren) {
     129          if(gardener.IsTerminal(c)) allowedChildren.Add(c);
     130        }
    133131      }
    134132
    135133      // selecting from the terminals should always work since the current child was also a terminal
    136134      // so in the worst case we will just create a new terminal of the same type again.
    137       return gardener.CreateRandomTree((IOperator)allowedChildren[random.Next(allowedChildren.Count)].Clone(), 1, 1, false);
    138     }
    139 
    140     private IOperator ChangeFunctionType(IOperator parent, IOperator child, int childIndex, TreeGardener gardener, MersenneTwister random,
    141       double balancedTreesRate, out List<IOperator> uninitializedOperators) {
    142       // since there are suboperators, we have to check which
    143       // and how many of the existing suboperators we can reuse
    144 
    145       // let's choose the operator we want to use instead of the old child. For this we have to determine the
    146       // pool of allowed operators based on constraints of the parent if there is one.
    147       IList<IOperator> allowedSubOperators;
    148       SubOperatorsConstraintAnalyser analyser = new SubOperatorsConstraintAnalyser();
    149       analyser.AllPossibleOperators = gardener.AllOperators;
    150       if (parent == null) {
    151         allowedSubOperators = gardener.AllOperators;
    152       } else {
    153         allowedSubOperators = analyser.GetAllowedOperators(parent, childIndex);
    154       }
     135      return gardener.CreateRandomTree(allowedChildren[random.Next(allowedChildren.Count)], 1, 1, false);
     136    }
     137
     138    private IFunctionTree ChangeFunctionType(IFunctionTree parent, IFunctionTree child, int childIndex, TreeGardener gardener, MersenneTwister random,
     139      double balancedTreesRate, out List<IFunctionTree> uninitializedBranches) {
     140      // since there are subtrees, we have to check which
     141      // and how many of the existing subtrees we can reuse
     142
     143      // let's choose the function we want to use instead of the old child. For this we have to determine the
     144      // pool of allowed functions based on constraints of the parent if there is one.
     145      IList<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent!=null?parent.Function:null, childIndex);
    155146
    156147      // try to make a tree with the same arity as the old child.
    157       int actualArity = child.SubOperators.Count;
     148      int actualArity = child.SubTrees.Count;
    158149      // arity of the selected operator
    159150      int minArity;
    160151      int maxArity;
    161 
    162       allowedSubOperators = allowedSubOperators.Where(f => {
     152      // only allow functions where we can keep all existing sub-trees
     153      // we don't want to create new sub-trees here
     154      // this restriction can be removed if we add code that creates sub-trees where necessary (gkronber 22.04.08)
     155      allowedFunctions = allowedFunctions.Where(f => {
    163156        gardener.GetMinMaxArity(f, out minArity, out maxArity);
    164157        return minArity <= actualArity;
    165158      }).ToList();
    166159
    167       IOperator newOperator = (IOperator)allowedSubOperators[random.Next(allowedSubOperators.Count)].Clone();
    168 
    169       gardener.GetMinMaxArity(newOperator, out minArity, out maxArity);
    170       // if the old child had too many sub-operators then make the new child with the maximal arity
     160      // create a new tree-node for a randomly selected function
     161      IFunctionTree newTree = new FunctionTree(allowedFunctions[random.Next(allowedFunctions.Count)]);
     162
     163      gardener.GetMinMaxArity(newTree.Function, out minArity, out maxArity);
     164      // if the old child had too many sub-trees then the new child should keep as many sub-trees as possible
    171165      if (actualArity > maxArity)
    172166        actualArity = maxArity;
    … …  
    175169      // use the size of the smallest subtree as the maximal allowed size for new subtrees to
    176170      // prevent that we ever create trees over the MaxTreeSize limit
    177       int maxSubTreeSize = child.SubOperators.Select(subOp => gardener.GetTreeSize(subOp)).Min();
     171      int maxSubTreeSize = child.SubTrees.Select(subTree => gardener.GetTreeSize(subTree)).Min();
    178172      int maxSubTreeHeight = gardener.GetTreeHeight(child) - 1;
    179173
    180174      // create a list that holds old sub-trees that we can reuse in the new tree
    181       List<IOperator> availableSubOperators = new List<IOperator>(child.SubOperators);
    182       List<IOperator> freshSubTrees = new List<IOperator>() { newOperator };
    183 
    184       // randomly select the suboperators that we keep
     175      List<IFunctionTree> availableSubTrees = new List<IFunctionTree>(child.SubTrees);
     176      List<IFunctionTree> freshSubTrees = new List<IFunctionTree>() { newTree };
     177
     178      // randomly select the sub-trees that we keep
    185179      for (int i = 0; i < actualArity; i++) {
    186         // fill all sub-operator slots of the new operator
    187         // if for a given slot i there are existing sub-operators that can be used in that slot
    188         // then use a random existing sub-operator. When there are no existing sub-operators
     180        // fill all sub-tree slots of the new tree
     181        // if for a given slot i there are multiple existing sub-trees that can be used in that slot
     182        // then use a random existing sub-tree. When there are no existing sub-trees
    189183        // that fit in the given slot then create a new random tree and use it for the slot
    190         IList<IOperator> allowedOperators = analyser.GetAllowedOperators(newOperator, i);
    191         var matchingOperators = availableSubOperators.Where(subOp => allowedOperators.Contains(subOp, new TreeGardener.OperatorEqualityComparer()));
    192 
    193         if (matchingOperators.Count() > 0) {
    194           IOperator selectedSubOperator = matchingOperators.ElementAt(random.Next(matchingOperators.Count()));
    195           // we can just add it as suboperator
    196           newOperator.AddSubOperator(selectedSubOperator, i);
    197           availableSubOperators.Remove(selectedSubOperator); // the operator shouldn't be available for the following slots
     184        ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(newTree.Function, i);
     185        var matchingSubTrees = availableSubTrees.Where(subTree => allowedSubFunctions.Contains(subTree.Function));
     186
     187        if (matchingSubTrees.Count() > 0) {
     188          IFunctionTree selectedSubTree = matchingSubTrees.ElementAt(random.Next(matchingSubTrees.Count()));
     189          // we can just add it as subtree
     190          newTree.InsertSubTree(i, selectedSubTree);
     191          availableSubTrees.Remove(selectedSubTree); // the branch shouldn't be available for the following slots
    198192        } else {
    199           IOperator freshOperatorTree;
     193          // no existing matching tree found => create a new one
     194          IFunctionTree freshTree;
    200195          if(random.NextDouble() <= balancedTreesRate) {
    201             freshOperatorTree = gardener.CreateRandomTree(allowedOperators, maxSubTreeSize, maxSubTreeHeight, true);
     196            freshTree = gardener.CreateRandomTree(allowedSubFunctions, maxSubTreeSize, maxSubTreeHeight, true);
    202197          } else {
    203             freshOperatorTree = gardener.CreateRandomTree(allowedOperators, maxSubTreeSize, maxSubTreeHeight, false);
     198            freshTree = gardener.CreateRandomTree(allowedSubFunctions, maxSubTreeSize, maxSubTreeHeight, false);
    204199          }
    205           freshSubTrees.AddRange(gardener.GetAllOperators(freshOperatorTree));
    206 
    207           newOperator.AddSubOperator(freshOperatorTree, i);
    208         }
    209       }
    210 
    211       uninitializedOperators = freshSubTrees;
    212       return newOperator;
     200          freshSubTrees.AddRange(gardener.GetAllSubTrees(freshTree));
     201
     202          newTree.InsertSubTree(i, freshTree);
     203        }
     204      }
     205      uninitializedBranches = freshSubTrees;
     206      return newTree;
    213207    }
    214208  }

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

    r23 r155  
    2727using HeuristicLab.Random;
    2828using System;
     29using HeuristicLab.Functions;
    2930
    3031namespace HeuristicLab.StructureIdentification {
    … …  
    3233    public override string Description {
    3334      get {
    34         return @"Takes a tree, selects a random node of the tree and then tries to replace a random child
     35        return @"Takes a tree, selects a random node of the tree and then tries to replace a random sub-tree
    3536of that node with one of the childs of the selected child.
    3637
    … …  
    5354      AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
    5455      AddVariableInfo(new VariableInfo("BalancedTreesRate", "Determines how many trees should be balanced", typeof(DoubleData), VariableKind.In));
    55       AddVariableInfo(new VariableInfo("OperatorTree", "The tree to mutate", typeof(IOperator), VariableKind.In));
    56       AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
    57       AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.In));
     56      AddVariableInfo(new VariableInfo("FunctionTree", "The tree to mutate", typeof(IFunctionTree), VariableKind.In | VariableKind.Out));
     57      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
     58      AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
    5859    }
    5960
    6061
    6162    public override IOperation Apply(IScope scope) {
    62       IOperator rootOperator = GetVariableValue<IOperator>("OperatorTree", scope, true);
     63      IFunctionTree root = GetVariableValue<IFunctionTree>("FunctionTree", scope, true);
    6364      MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);
    6465      GPOperatorLibrary library = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
    … …  
    6869
    6970      TreeGardener gardener = new TreeGardener(random, library);
    70       IOperator parent = gardener.GetRandomParentNode(rootOperator);
     71      IFunctionTree parent = gardener.GetRandomParentNode(root);
    7172      // parent == null means we should cut out the root node
    72       // => return a random suboperator of the root
     73      // => return a random sub-tree of the root
    7374      if (parent == null) {
    74         // when there are suboperators then replace the old operator with a random suboperator
    75         if (rootOperator.SubOperators.Count > 0) {
    76           rootOperator = rootOperator.SubOperators[random.Next(rootOperator.SubOperators.Count)];
     75        // when there are sub-trees then replace the old tree with a random sub-tree
     76        if (root.SubTrees.Count > 0) {
     77          root = root.SubTrees[random.Next(root.SubTrees.Count)];
    7778
    78           GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(rootOperator);
    79           GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(rootOperator);
     79          GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
     80          GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
    8081
    81           // this is not really necessary (we can leave it in until the operator is stable)
    82           if (!gardener.IsValidTree(rootOperator)) {
     82          // update the variable
     83          scope.GetVariable(scope.TranslateName("FunctionTree")).Value = root;
     84          if (!gardener.IsValidTree(root)) {
    8385            throw new InvalidProgramException();
    8486          }
    85 
     87          // we reused a sub-tree so we don't have to schedule initialization operations
     88          return null;
     89        } else {
     90          // we want to cut the root node and there are no sub-trees => create a new random terminal
     91          IFunctionTree newTree;
     92          newTree = gardener.CreateRandomTree(gardener.Terminals, 1, 1, false);
     93          GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newTree);
     94          GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(newTree);
    8695          // update the variable
    87           scope.GetVariable("OperatorTree").Value = rootOperator;
    88           if (!gardener.IsValidTree(rootOperator)) {
     96          scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newTree;
     97          if (!gardener.IsValidTree(newTree)) {
    8998            throw new InvalidProgramException();
    9099          }
    91 
    92 
    93           // the tree is already initialized so we don't have to schedule initialization operations
    94           return null;
    95         } else {
    96           // create a new random tree
    97           IOperator newOperator;
    98           if(random.NextDouble() <= balancedTreesRate) {
    99             newOperator = gardener.CreateRandomTree(gardener.AllOperators, maxTreeSize, maxTreeHeight, true);
    100           } else {
    101             newOperator = gardener.CreateRandomTree(gardener.AllOperators, maxTreeSize, maxTreeHeight, false);
    102           }
    103 
    104           GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newOperator);
    105           GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(newOperator);
    106 
    107           if (!gardener.IsValidTree(newOperator)) {
    108             throw new InvalidProgramException();
    109           }
    110 
    111           // update the variable
    112           scope.GetVariable("OperatorTree").Value = newOperator;
    113 
    114           if (!gardener.IsValidTree(newOperator)) {
    115             throw new InvalidProgramException();
    116           }
    117 
    118           // schedule an operation to initialize the whole operator graph
    119           return gardener.CreateInitializationOperation(gardener.GetAllOperators(newOperator), scope);
     100          // schedule an operation to initialize the whole tree
     101          return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newTree), scope);
    120102        }
    121103      }
    122104
    123       int childIndex = random.Next(parent.SubOperators.Count);
    124       IOperator child = parent.SubOperators[childIndex];
     105      // select a child to cut away
     106      int childIndex = random.Next(parent.SubTrees.Count);
     107      IFunctionTree child = parent.SubTrees[childIndex];
    125108
    126       // match the suboperators of the child with the allowed suboperators of the parent
    127       IOperator[] possibleChilds = gardener.GetAllowedSubOperators(parent, childIndex).SelectMany(allowedOp => child.SubOperators
    128         .Where(subOp => ((StringData)subOp.GetVariable(GPOperatorLibrary.TYPE_ID).Value).Data ==
    129           ((StringData)allowedOp.GetVariable(GPOperatorLibrary.TYPE_ID).Value).Data)).ToArray();
    130 
     109      // match the sub-trees of the child with the allowed sub-trees of the parent
     110      ICollection<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
     111      IFunctionTree[] possibleChilds = child.SubTrees.Where(t => allowedFunctions.Contains(t.Function)).ToArray();
    131112
    132113      if (possibleChilds.Length > 0) {
    133         // replace child with a random child of the child
    134         // make a clone to simplify removing obsolete operators from the operator-graph
    135         IOperator selectedChild = (IOperator)possibleChilds[random.Next(possibleChilds.Length)].Clone();       
    136         parent.RemoveSubOperator(childIndex);
    137         parent.AddSubOperator(selectedChild, childIndex);
     114        // replace child with a random child of that child
     115        IFunctionTree selectedChild = possibleChilds[random.Next(possibleChilds.Length)];       
     116        parent.RemoveSubTree(childIndex);
     117        parent.InsertSubTree(childIndex, selectedChild);
    138118
    139         if (!gardener.IsValidTree(rootOperator)) {
     119        if (!gardener.IsValidTree(root)) {
    140120          throw new InvalidProgramException();
    141121        }
    142122
    143123        // update the size and height of our tree
    144         GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(rootOperator);
    145         GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(rootOperator);
     124        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
     125        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
    146126        // don't need to schedule initialization operations
    147127        return null;
    148128      } else {
     129        // can't reuse an existing branch => create a new tree
    149130        // determine the level of the parent
    150         int parentLevel = gardener.GetNodeLevel(rootOperator, parent);
     131        int parentLevel = gardener.GetBranchLevel(root, parent);
    151132
    152133        // first remove the old child (first step essential!)
    153         parent.RemoveSubOperator(childIndex);
     134        parent.RemoveSubTree(childIndex);
    154135        // then determine the number of nodes left over after the child has been removed!
    155         int remainingNodes = gardener.GetTreeSize(rootOperator);
     136        int remainingNodes = gardener.GetTreeSize(root);
    156137
    157         IList<IOperator> allowedOperators = gardener.GetAllowedSubOperators(parent, childIndex);
    158         IOperator newOperatorTree = gardener.CreateRandomTree(allowedOperators, maxTreeSize - remainingNodes, maxTreeHeight - parentLevel, true);
     138        allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
     139        IFunctionTree newFunctionTree = gardener.CreateRandomTree(allowedFunctions, maxTreeSize - remainingNodes, maxTreeHeight - parentLevel, false);
    159140
    160         parent.AddSubOperator(newOperatorTree, childIndex);
     141        parent.InsertSubTree(childIndex, newFunctionTree);
    161142
    162         GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(rootOperator);
    163         GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(rootOperator);
     143        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
     144        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
    164145
    165         if (!gardener.IsValidTree(rootOperator)) {
     146        if (!gardener.IsValidTree(root)) {
    166147          throw new InvalidProgramException();
    167148        }
    168149
    169         // schedule an initialization operation for the new operator
    170         return gardener.CreateInitializationOperation(gardener.GetAllOperators(newOperatorTree), scope);
     150        // schedule an initialization operation for the new function-tree
     151        return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newFunctionTree), scope);
    171152      }
    172153    }

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

    r23 r155  
    2626using HeuristicLab.Operators;
    2727using HeuristicLab.Random;
     28using HeuristicLab.Functions;
    2829
    2930namespace HeuristicLab.StructureIdentification {
    … …  
    4243      AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
    4344      AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
    44       AddVariableInfo(new VariableInfo("OperatorTree", "The tree to mutate", typeof(IOperator), VariableKind.In | VariableKind.Out));
     45      AddVariableInfo(new VariableInfo("FunctionTree", "The tree to mutate", typeof(IFunctionTree), VariableKind.In | VariableKind.Out));
    4546      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
    4647      AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
    … …  
    4950
    5051    public override IOperation Apply(IScope scope) {
    51       IOperator rootOperator = GetVariableValue<IOperator>("OperatorTree", scope, true);
     52      IFunctionTree root = GetVariableValue<IFunctionTree>("FunctionTree", scope, true);
    5253      MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);
    5354      GPOperatorLibrary library = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
    54 
    5555      TreeGardener gardener = new TreeGardener(random, library);
    56 
    57       IOperator parent = gardener.GetRandomParentNode(rootOperator);
     56      IFunctionTree parent = gardener.GetRandomParentNode(root);
    5857
    5958      // parent==null means the whole tree should be deleted.
    6059      // => return a new minimal random tree
    6160      if(parent == null) {
    62         IOperator newTree = gardener.CreateRandomTree(1, 1, true);
     61        IFunctionTree newTree = gardener.CreateRandomTree(1, 1, false);
    6362
    6463        // check if the tree is ok
    … …  
    7069        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newTree);
    7170        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(newTree);
    72         scope.GetVariable("OperatorTree").Value = newTree;
     71        scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newTree;
    7372
    7473        // schedule an operation to initialize the newly created operator
    75         return gardener.CreateInitializationOperation(gardener.GetAllOperators(newTree), scope);
     74        return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newTree), scope);
    7675      }
    7776
    78       int childIndex = random.Next(parent.SubOperators.Count);
    79 
     77      // select a branch to prune
     78      int childIndex = random.Next(parent.SubTrees.Count);
    8079      int min;
    8180      int max;
    82       gardener.GetMinMaxArity(parent, out min, out max);
    83       if(parent.SubOperators.Count > min) {
    84         parent.RemoveSubOperator(childIndex);
    85         // actually since the next suboperators are shifted in the place of the removed operator
    86         // it might be possible that these suboperators are not allowed in the place of the old operator
     81      gardener.GetMinMaxArity(parent.Function, out min, out max);
     82      if(parent.SubTrees.Count > min) {
     83        parent.RemoveSubTree(childIndex);
     84        // actually since the next sub-trees are shifted in the place of the removed branch
     85        // it might be possible that these sub-trees are not allowed in the place of the old branch
    8786        // we ignore this problem for now.
    88         // when this starts to become a problem a possible solution is to go through the shifted operators from the place of the shifted
     87        // when this starts to become a problem a possible solution is to go through the shifted branches from the place of the shifted
    8988        // and find the first one that doesn't fit. At this position we insert a new randomly initialized subtree of matching type (gkronber 25.12.07)
    9089
    91         if(!gardener.IsValidTree(rootOperator)) {
     90        if(!gardener.IsValidTree(root)) {
    9291          throw new InvalidOperationException();
    9392        }
    9493
    95         GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(rootOperator);
    96         GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(rootOperator);
    97         // root hasn't changed so don't need to update 'OperatorTree' variable
    98 
     94        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
     95        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
     96        // root hasn't changed so don't need to update 'FunctionTree' variable
    9997        return null;
    10098      } else {
    10199        // replace with a minimal random seedling
    102         parent.RemoveSubOperator(childIndex);
     100        parent.RemoveSubTree(childIndex);
    103101
    104         IList<IOperator> allowedOperators = gardener.GetAllowedSubOperators(parent, childIndex);
    105         IOperator newOperatorTree = gardener.CreateRandomTree(allowedOperators, 1, 1, true);
     102        ICollection<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
     103        IFunctionTree newFunctionTree = gardener.CreateRandomTree(allowedFunctions, 1, 1, true);
    106104
    107         parent.AddSubOperator(newOperatorTree, childIndex);
     105        parent.InsertSubTree(childIndex, newFunctionTree);
    108106
    109         if(!gardener.IsValidTree(rootOperator)) {
     107        if(!gardener.IsValidTree(root)) {
    110108          throw new InvalidProgramException();
    111109        }
    112110
    113         GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(rootOperator);
    114         GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(rootOperator);
    115         // again the root hasn't changed so we don't need to update the 'OperatorTree' variable
    116 
    117         return gardener.CreateInitializationOperation(gardener.GetAllOperators(newOperatorTree), scope);
     111        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
     112        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
     113        // again the root hasn't changed so we don't need to update the 'FunctionTree' variable
     114        // but we have to return an initialization operation for the newly created tree
     115        return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newFunctionTree), scope);
    118116      }
    119117    }

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

    r88 r155  
    2929using HeuristicLab.Data;
    3030using HeuristicLab.Selection;
     31using HeuristicLab.Functions;
    3132
    3233namespace HeuristicLab.StructureIdentification {
    … …  
    3839    public FullTreeShaker()
    3940      : base() {
     41      AddVariableInfo(new VariableInfo("Random", "A random generator (uniform)", typeof(MersenneTwister), VariableKind.In));
    4042      AddVariableInfo(new VariableInfo("OperatorLibrary", "Operator library that defines operator mutations", typeof(GPOperatorLibrary), VariableKind.In));
    41       AddVariableInfo(new VariableInfo("OperatorTree", "The operator tree that should be mutated", typeof(IOperator), VariableKind.In));
    42       AddVariableInfo(new VariableInfo("Random", "A random generator (uniform)", typeof(MersenneTwister), VariableKind.In));
    43       AddVariableInfo(new VariableInfo("ShakingFactor", "Variable that determines the force of the shakeing operation", typeof(DoubleData), VariableKind.In));
     43      AddVariableInfo(new VariableInfo("ShakingFactor", "Variable that determines the force of the shaking operation", typeof(DoubleData), VariableKind.In));
     44      AddVariableInfo(new VariableInfo("FunctionTree", "The function tree that should be mutated", typeof(IFunctionTree), VariableKind.In | VariableKind.Out));
    4445    }
    4546
    4647    public override IOperation Apply(IScope scope) {
    4748      GPOperatorLibrary library = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
    48       IOperator op = GetVariableValue<IOperator>("OperatorTree", scope, false);
     49      IFunctionTree tree = GetVariableValue<IFunctionTree>("FunctionTree", scope, false);
    4950      MersenneTwister mt = GetVariableValue<MersenneTwister>("Random", scope, true);
    5051
    … …  
    5657
    5758      TreeGardener gardener = new TreeGardener(mt, library);
    58       var parametricNodes = gardener.GetAllOperators(op).Where(o => o.GetVariable(GPOperatorLibrary.MANIPULATION) != null);
    59       foreach(IOperator subOperator in parametricNodes) {
    60         IOperator mutation =(IOperator)subOperator.GetVariable(GPOperatorLibrary.MANIPULATION).Value;
     59      var parametricBranches = gardener.GetAllSubTrees(tree).Where(branch => branch.Function.GetVariable(GPOperatorLibrary.MANIPULATION) != null);
     60      foreach(IFunctionTree subTree in parametricBranches) {
     61        IOperator mutation =(IOperator)subTree.Function.GetVariable(GPOperatorLibrary.MANIPULATION).Value;
    6162
    6263        // store all local variables into a temporary scope
    6364        Scope mutationScope = new Scope();
    64         foreach(IVariableInfo info in subOperator.VariableInfos) {
    65           if(info.Local) {
    66             mutationScope.AddVariable(subOperator.GetVariable(info.FormalName));
    67           }
     65        foreach(IVariable variable in subTree.LocalVariables) {
     66          mutationScope.AddVariable(variable);
    6867        }
    6968

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

    r88 r155  
    2929using HeuristicLab.Data;
    3030using HeuristicLab.Selection;
     31using HeuristicLab.Functions;
    3132
    3233namespace HeuristicLab.StructureIdentification {
    … …  
    3940      : base() {
    4041      AddVariableInfo(new VariableInfo("OperatorLibrary", "Operator library that defines mutation operations for operators", typeof(GPOperatorLibrary), VariableKind.In));
    41       AddVariableInfo(new VariableInfo("OperatorTree", "The operator tree that should be mutated", typeof(IOperator), VariableKind.In));
    4242      AddVariableInfo(new VariableInfo("Random", "A random generator (uniform)", typeof(MersenneTwister), VariableKind.In));
    4343      AddVariableInfo(new VariableInfo("ShakingFactor", "Factor that determines the force of the shaking operation", typeof(DoubleData), VariableKind.In));
     44      AddVariableInfo(new VariableInfo("FunctionTree", "The function tree that should be mutated", typeof(IFunctionTree), VariableKind.In | VariableKind.Out));
    4445    }
    4546
    4647    public override IOperation Apply(IScope scope) {
    4748      GPOperatorLibrary library = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
    48       IOperator op = GetVariableValue<IOperator>("OperatorTree", scope, false);
     49      IFunctionTree tree = GetVariableValue<IFunctionTree>("FunctionTree", scope, false);
    4950      MersenneTwister mt = GetVariableValue<MersenneTwister>("Random", scope, true);
    5051      TreeGardener gardener = new TreeGardener(mt, library);
    5152
    5253      // get all nodes for which a manipulation is defined
    53       var parametricNodes = gardener.GetAllOperators(op).Where(o => o.GetVariable(GPOperatorLibrary.MANIPULATION) != null);
    54       IOperator selectedOp = parametricNodes.ElementAt(mt.Next(parametricNodes.Count()));
    55 
    56       IOperator mutation = (IOperator)selectedOp.GetVariable(GPOperatorLibrary.MANIPULATION).Value;
    57 
     54      var parametricBranches = gardener.GetAllSubTrees(tree).Where(branch => branch.Function.GetVariable(GPOperatorLibrary.MANIPULATION) != null);
     55      IFunctionTree selectedBranch = parametricBranches.ElementAt(mt.Next(parametricBranches.Count()));
     56      IOperator mutation = (IOperator)selectedBranch.Function.GetVariable(GPOperatorLibrary.MANIPULATION).Value;
    5857      CompositeOperation next = new CompositeOperation();
    5958
    6059      // store all local variables into a temporary scope
    6160      Scope tempScope = new Scope("Temp. manipulation scope");
    62       // add aliases
    63       foreach(IVariableInfo variableInfo in VariableInfos)
    64         tempScope.AddAlias(variableInfo.FormalName, variableInfo.ActualName);
    65 
    66       foreach(IVariableInfo info in selectedOp.VariableInfos) {
    67         if(info.Local) {
    68           tempScope.AddVariable(selectedOp.GetVariable(info.FormalName));
    69         }
     61      foreach(IVariable variable in selectedBranch.LocalVariables) {
     62        tempScope.AddVariable(variable);
    7063      }
    7164

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

    r23 r155  
    2727using HeuristicLab.Operators;
    2828using HeuristicLab.Random;
     29using HeuristicLab.Functions;
    2930
    3031namespace HeuristicLab.StructureIdentification {
    … …  
    4243      AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
    4344      AddVariableInfo(new VariableInfo("BalancedTreesRate", "Determines how many trees should be balanced", typeof(DoubleData), VariableKind.In));
    44       AddVariableInfo(new VariableInfo("OperatorTree", "The tree to manipulate", typeof(IOperator), VariableKind.In));
    45       AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
    46       AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.In));
     45      AddVariableInfo(new VariableInfo("FunctionTree", "The tree to manipulate", typeof(IFunctionTree), VariableKind.In | VariableKind.Out));
     46      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
     47      AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
    4748    }
    4849
    4950    public override IOperation Apply(IScope scope) {
    50       IOperator rootOperator = GetVariableValue<IOperator>("OperatorTree", scope, true);
    51 
     51      IFunctionTree root = GetVariableValue<IFunctionTree>("FunctionTree", scope, true);
    5252      MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);
    5353      GPOperatorLibrary library = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
    … …  
    6060      TreeGardener gardener = new TreeGardener(random, library);
    6161
    62       IOperator parent = gardener.GetRandomParentNode(rootOperator);
     62      IFunctionTree parent = gardener.GetRandomParentNode(root);
    6363      if(parent == null) {
    6464        // parent == null means we should subsitute the whole tree
    6565        // => create a new random tree
    6666
    67         // create a new random operator tree
    68 
    69         IOperator newOperatorTree;
     67        // create a new random function tree
     68        IFunctionTree newTree;
    7069        if(random.NextDouble() <= balancedTreesRate) {
    71           newOperatorTree = gardener.CreateRandomTree(gardener.AllOperators, maxTreeSize, maxTreeHeight, true);
     70          newTree = gardener.CreateRandomTree(gardener.AllFunctions, maxTreeSize, maxTreeHeight, true);
    7271        } else {
    73           newOperatorTree = gardener.CreateRandomTree(gardener.AllOperators, maxTreeSize, maxTreeHeight, false);
     72          newTree = gardener.CreateRandomTree(gardener.AllFunctions, maxTreeSize, maxTreeHeight, false);
    7473        }
    7574
    76         if(!gardener.IsValidTree(newOperatorTree)) {
     75        if(!gardener.IsValidTree(newTree)) {
    7776          throw new InvalidProgramException();
    7877        }
    7978
    8079        // update the variables in the scope with the new values
    81         GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newOperatorTree);
    82         GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(newOperatorTree);
    83         scope.GetVariable("OperatorTree").Value = newOperatorTree;
     80        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newTree);
     81        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(newTree);
     82        scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newTree;
    8483       
    85         // return a CompositeOperation that randomly initializes the new operator
    86         return gardener.CreateInitializationOperation(gardener.GetAllOperators(newOperatorTree), scope);
     84        // return a CompositeOperation that randomly initializes the new tree
     85        return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newTree), scope);
    8786      } else {
    8887        // determine a random child of the parent to be replaced
    89         int childIndex = random.Next(parent.SubOperators.Count);
    90 
    91         // get the list of allowed suboperators as the new child
    92         IList<IOperator> allowedOperators = gardener.GetAllowedSubOperators(parent, childIndex);
    93 
    94         if(allowedOperators.Count == 0) {
     88        int childIndex = random.Next(parent.SubTrees.Count);
     89        // get the list of allowed functions for the new sub-tree
     90        ICollection<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
     91        if(allowedFunctions.Count == 0) {
    9592          // don't change anything
    9693          // this shouldn't happen
    … …  
    10097        // calculate the maximum size and height of the new sub-tree based on the location where
    10198        // it will be inserted
    102         int parentLevel = gardener.GetNodeLevel(rootOperator, parent);
     99        int parentLevel = gardener.GetBranchLevel(root, parent);
    103100
    104101        int maxSubTreeHeight = maxTreeHeight - parentLevel;
    105         int maxSubTreeSize = maxTreeSize - (treeSize - gardener.GetTreeSize(parent.SubOperators[childIndex]));
     102        int maxSubTreeSize = maxTreeSize - (treeSize - gardener.GetTreeSize(parent.SubTrees[childIndex]));
    106103
    107         // get a random operatorTree
    108         IOperator newOperatorTree;
     104        // create a random function tree
     105        IFunctionTree newTree;
    109106        if(random.NextDouble() <= balancedTreesRate) {
    110           newOperatorTree = gardener.CreateRandomTree(allowedOperators, maxSubTreeSize, maxSubTreeHeight, true);
     107          newTree = gardener.CreateRandomTree(allowedFunctions, maxSubTreeSize, maxSubTreeHeight, true);
    111108        } else {
    112           newOperatorTree = gardener.CreateRandomTree(allowedOperators, maxSubTreeSize, maxSubTreeHeight, false);
     109          newTree = gardener.CreateRandomTree(allowedFunctions, maxSubTreeSize, maxSubTreeHeight, false);
    113110        }
    114111
    115         IOperator oldChild = parent.SubOperators[childIndex];
    116         parent.RemoveSubOperator(childIndex);
    117         parent.AddSubOperator(newOperatorTree, childIndex);
     112        parent.RemoveSubTree(childIndex);
     113        parent.InsertSubTree(childIndex, newTree);
    118114
    119         if(!gardener.IsValidTree(rootOperator)) {
     115        if(!gardener.IsValidTree(root)) {
    120116          throw new InvalidProgramException();
    121117        }
    122118
    123119        // update the values of treeSize and treeHeight
    124         GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(rootOperator);
    125         GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(rootOperator);
    126         // the root operator hasn't changed so we don't need to update
    127 
     120        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
     121        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
     122        // the root hasn't changed so we don't need to update
    128123        // return a CompositeOperation that randomly initializes all nodes of the new subtree
    129         return gardener.CreateInitializationOperation(gardener.GetAllOperators(newOperatorTree), scope);
     124        return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newTree), scope);
    130125      }
    131126    }
Note: See TracChangeset for help on using the changeset viewer.