Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
09/27/10 17:31:09 (13 years ago)
Author:
gkronber
Message:

Fixed #1214. The size of the manipulated tree is checked and only if the new tree fulfills the size requirements it is accepted otherwise the original tree is returned instead. Additionally the calculation of tree sizes is checked for overflows now.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureManipulators/ArgumentCreater.cs

    r4477 r4524  
    2626using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
    2727using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     28using System;
    2829
    2930namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureManipulators {
     
    5152      int maxTreeSize, int maxTreeHeight,
    5253      int maxFunctionDefiningBranches, int maxFunctionArguments) {
     54      // work on a copy in case we find out later that the tree would be too big
     55      // in this case it's easiest to simply return the original tree.
     56      SymbolicExpressionTree clonedTree = (SymbolicExpressionTree)symbolicExpressionTree.Clone();
    5357
    54       var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>();
    55 
     58      var functionDefiningBranches = clonedTree.IterateNodesPrefix().OfType<DefunTreeNode>();
    5659      if (functionDefiningBranches.Count() == 0)
    5760        // no function defining branch found => abort
     
    6568        // max number of arguments reached => abort
    6669        return false;
     70
     71      var allowedArgumentIndexes = Enumerable.Range(0, maxFunctionArguments);
     72      var newArgumentIndex = allowedArgumentIndexes.Except(definedArguments).First();
     73      ArgumentTreeNode newArgumentNode = MakeArgumentNode(newArgumentIndex);
     74
     75      // this operation potentially creates very big trees so the access to the size property might throw overflow exception
     76      try {
     77        if (CreateNewArgumentForDefun(random, clonedTree, selectedDefunBranch, newArgumentNode) && clonedTree.Size < maxTreeSize && clonedTree.Height < maxTreeHeight) {
     78
     79          // size constraints are fulfilled
     80          // replace root of original tree with root of manipulated tree
     81          symbolicExpressionTree.Root = clonedTree.Root;
     82          return true;
     83        } else {
     84          // keep originalTree
     85          return false;
     86        }
     87      }
     88      catch (OverflowException) {
     89        // keep original tree
     90        return false;
     91      }
     92    }
     93
     94
     95    private static bool CreateNewArgumentForDefun(IRandom random, SymbolicExpressionTree tree, DefunTreeNode defunBranch, ArgumentTreeNode newArgumentNode) {
    6796      // select a random cut point in the function defining branch
    6897      // the branch at the cut point is to be replaced by a new argument node
    69       var cutPoints = (from node in selectedDefunBranch.IterateNodesPrefix()
     98      var cutPoints = (from node in defunBranch.IterateNodesPrefix()
    7099                       where node.SubTrees.Count > 0
    71100                       from subtree in node.SubTrees
     
    76105        return false;
    77106      var selectedCutPoint = cutPoints[random.Next(cutPoints.Count)];
    78       var allowedArgumentIndexes = Enumerable.Range(0, maxFunctionArguments);
    79       var newArgumentIndex = allowedArgumentIndexes.Except(definedArguments).First();
    80107      // replace the branch at the cut point with an argument node
    81       var newArgNode = MakeArgumentNode(newArgumentIndex);
    82108      var replacedBranch = selectedCutPoint.ReplacedChild;
    83109      selectedCutPoint.Parent.RemoveSubTree(selectedCutPoint.ReplacedChildIndex);
    84       selectedCutPoint.Parent.InsertSubTree(selectedCutPoint.ReplacedChildIndex, newArgNode);
     110      selectedCutPoint.Parent.InsertSubTree(selectedCutPoint.ReplacedChildIndex, newArgumentNode);
    85111
    86       // find all invocations of the selected ADF and attach a cloned version of the replaced branch (with all argument-nodes expanded)
    87       var invocationNodes = (from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
    88                              where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
    89                              where node.SubTrees.Count == selectedDefunBranch.NumberOfArguments
     112      // find all old invocations of the selected ADF and attach a cloned version of the replaced branch (with all argument-nodes expanded)
     113      // iterate in post-fix order to make sure that the subtrees of n are already adapted when n is processed
     114      var invocationNodes = (from node in tree.IterateNodesPostfix().OfType<InvokeFunctionTreeNode>()
     115                             where node.Symbol.FunctionName == defunBranch.FunctionName
     116                             where node.SubTrees.Count == defunBranch.NumberOfArguments
    90117                             select node).ToList();
    91118      // do this repeatedly until no matching invocations are found     
    92       while (invocationNodes.Count() > 0) {
     119      while (invocationNodes.Count > 0) {
    93120        List<SymbolicExpressionTreeNode> newlyAddedBranches = new List<SymbolicExpressionTreeNode>();
    94121        foreach (var invocationNode in invocationNodes) {
     122          // check that the invocation node really has the correct number of arguments
     123          if (invocationNode.SubTrees.Count != defunBranch.NumberOfArguments) throw new InvalidOperationException();
    95124          // append a new argument branch after expanding all argument nodes
    96125          var clonedBranch = (SymbolicExpressionTreeNode)replacedBranch.Clone();
    97126          clonedBranch = ReplaceArgumentsInBranch(clonedBranch, invocationNode.SubTrees);
    98           invocationNode.InsertSubTree(newArgumentIndex, clonedBranch);
     127          invocationNode.InsertSubTree(newArgumentNode.Symbol.ArgumentIndex, clonedBranch);
    99128          newlyAddedBranches.Add(clonedBranch);
    100129        }
     130        // iterate in post-fix order to make sure that the subtrees of n are already adapted when n is processed
    101131        invocationNodes = (from newlyAddedBranch in newlyAddedBranches
    102                            from node in newlyAddedBranch.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
    103                            where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
    104                            where node.SubTrees.Count == selectedDefunBranch.NumberOfArguments
     132                           from node in newlyAddedBranch.IterateNodesPostfix().OfType<InvokeFunctionTreeNode>()
     133                           where node.Symbol.FunctionName == defunBranch.FunctionName
     134                           where node.SubTrees.Count == defunBranch.NumberOfArguments
    105135                           select node).ToList();
    106136      }
     
    108138      // it's possible that the number of actually referenced arguments was reduced (all references were replaced by a single new argument)
    109139      // but the number of expected arguments is increased anyway
    110       selectedDefunBranch.NumberOfArguments++;
    111       selectedDefunBranch.Grammar.AddSymbol(newArgNode.Symbol);
    112       selectedDefunBranch.Grammar.SetMinSubtreeCount(newArgNode.Symbol, 0);
    113       selectedDefunBranch.Grammar.SetMaxSubtreeCount(newArgNode.Symbol, 0);
     140      defunBranch.NumberOfArguments++;
     141      defunBranch.Grammar.AddSymbol(newArgumentNode.Symbol);
     142      defunBranch.Grammar.SetMinSubtreeCount(newArgumentNode.Symbol, 0);
     143      defunBranch.Grammar.SetMaxSubtreeCount(newArgumentNode.Symbol, 0);
    114144      // allow the argument as child of any other symbol
    115       foreach (var symb in selectedDefunBranch.Grammar.Symbols)
    116         for (int i = 0; i < selectedDefunBranch.Grammar.GetMaxSubtreeCount(symb); i++) {
    117           selectedDefunBranch.Grammar.SetAllowedChild(symb, newArgNode.Symbol, i);
     145      foreach (var symb in defunBranch.Grammar.Symbols)
     146        for (int i = 0; i < defunBranch.Grammar.GetMaxSubtreeCount(symb); i++) {
     147          defunBranch.Grammar.SetAllowedChild(symb, newArgumentNode.Symbol, i);
    118148        }
    119       foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
     149      foreach (var subtree in tree.Root.SubTrees) {
    120150        // when the changed function is known in the branch then update the number of arguments
    121         var matchingSymbol = subtree.Grammar.Symbols.OfType<InvokeFunction>().Where(s => s.FunctionName == selectedDefunBranch.FunctionName).SingleOrDefault();
     151        var matchingSymbol = subtree.Grammar.Symbols.OfType<InvokeFunction>().Where(s => s.FunctionName == defunBranch.FunctionName).SingleOrDefault();
    122152        if (matchingSymbol != null) {
    123           subtree.Grammar.SetMinSubtreeCount(matchingSymbol, selectedDefunBranch.NumberOfArguments);
    124           subtree.Grammar.SetMaxSubtreeCount(matchingSymbol, selectedDefunBranch.NumberOfArguments);
     153          subtree.Grammar.SetMinSubtreeCount(matchingSymbol, defunBranch.NumberOfArguments);
     154          subtree.Grammar.SetMaxSubtreeCount(matchingSymbol, defunBranch.NumberOfArguments);
    125155          foreach (var child in subtree.GetAllowedSymbols(0)) {
    126156            for (int i = 0; i < subtree.Grammar.GetMaxSubtreeCount(matchingSymbol); i++) {
     
    130160        }
    131161      }
     162
    132163      return true;
    133164    }
    134165
    135166    private static SymbolicExpressionTreeNode ReplaceArgumentsInBranch(SymbolicExpressionTreeNode branch, IList<SymbolicExpressionTreeNode> argumentTrees) {
    136       if (branch is ArgumentTreeNode) {
    137         var argNode = branch as ArgumentTreeNode;
     167      ArgumentTreeNode argNode = branch as ArgumentTreeNode;
     168      if (argNode != null) {
    138169        // replace argument nodes by a clone of the original subtree that provided the result for the argument node
    139170        return (SymbolicExpressionTreeNode)argumentTrees[argNode.Symbol.ArgumentIndex].Clone();
     
    149180    }
    150181
    151     private static SymbolicExpressionTreeNode MakeArgumentNode(int argIndex) {
     182    private static ArgumentTreeNode MakeArgumentNode(int argIndex) {
    152183      var node = (ArgumentTreeNode)(new Argument(argIndex)).CreateTreeNode();
    153184      return node;
Note: See TracChangeset for help on using the changeset viewer.