Changeset 3360 for trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators

Timestamp:

04/15/10 19:58:42 (15 years ago)

Author:

gkronber

Message:

Fixed bugs in ADF operators and added test classes for ADF operators. #290 (Implement ADFs)

Location:

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators

Files:

• ArgumentCreater.cs (modified) (3 diffs)
• ArgumentDeleter.cs (modified) (2 diffs)
• ArgumentDuplicater.cs (modified) (1 diff)
• GrammarModifier.cs (added)
• RandomArchitectureAlteringOperator.cs (modified) (1 diff)
• SubroutineCreater.cs (modified) (6 diffs)
• SubroutineDeleter.cs (modified) (2 diffs)
• SubroutineDuplicater.cs (modified) (3 diffs)

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/ArgumentCreater.cs

@@ -96 +96 @@
         // append a new argument branch after expanding all argument nodes
         var clonedBranch = (SymbolicExpressionTreeNode)replacedBranch.Clone();
-        ReplaceArgumentsInBranch(clonedBranch, invocationNode.SubTrees);
+        clonedBranch = ReplaceArgumentsInBranch(clonedBranch, invocationNode.SubTrees);
         invocationNode.InsertSubTree(newArgumentIndex, clonedBranch);
       }
@@ -113 +113 @@
       foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
         // when the changed function is known in the branch then update the number of arguments
-        var matchingSymbol = subtree.Grammar.Symbols.Where(s => s.Name == selectedDefunBranch.FunctionName).SingleOrDefault();
+        var matchingSymbol = subtree.Grammar.Symbols.OfType<InvokeFunction>().Where(s => s.FunctionName == selectedDefunBranch.FunctionName).SingleOrDefault();
         if (matchingSymbol != null) {
           subtree.Grammar.SetMinSubtreeCount(matchingSymbol, selectedDefunBranch.NumberOfArguments);
           subtree.Grammar.SetMaxSubtreeCount(matchingSymbol, selectedDefunBranch.NumberOfArguments);
+          foreach (var child in subtree.GetAllowedSymbols(0)) {
+            for (int i = 0; i < subtree.Grammar.GetMaxSubtreeCount(matchingSymbol); i++) {
+              subtree.Grammar.SetAllowedChild(matchingSymbol, child, i);
+            }
+          }
         }
       }
@@ -122 +127 @@
     }
 
-    private static void ReplaceArgumentsInBranch(SymbolicExpressionTreeNode branch, IList<SymbolicExpressionTreeNode> argumentTrees) {
-      // check if any subtree is an argument node 
-      for (int subtreeIndex = 0; subtreeIndex < branch.SubTrees.Count; subtreeIndex++) {
-        var subtree = branch.SubTrees[subtreeIndex];
-        var argNode = subtree as ArgumentTreeNode;
-        if (argNode != null) {
-          // replace argument nodes by a clone of the original subtree that provided the result for the argument node
-          branch.SubTrees[subtreeIndex] = (SymbolicExpressionTreeNode)argumentTrees[argNode.Symbol.ArgumentIndex].Clone();
-        } else {
-          // recursively replace arguments in all branches
-          ReplaceArgumentsInBranch(subtree, argumentTrees);
+    private static SymbolicExpressionTreeNode ReplaceArgumentsInBranch(SymbolicExpressionTreeNode branch, IList<SymbolicExpressionTreeNode> argumentTrees) {
+      if (branch is ArgumentTreeNode) {
+        var argNode = branch as ArgumentTreeNode;
+        // replace argument nodes by a clone of the original subtree that provided the result for the argument node
+        return (SymbolicExpressionTreeNode)argumentTrees[argNode.Symbol.ArgumentIndex].Clone();
+      } else {
+        // call recursively for all subtree
+        List<SymbolicExpressionTreeNode> subtrees = new List<SymbolicExpressionTreeNode>(branch.SubTrees);
+        while (branch.SubTrees.Count > 0) branch.SubTrees.RemoveAt(0);
+        foreach (var subtree in subtrees) {
+          branch.AddSubTree(ReplaceArgumentsInBranch(subtree, argumentTrees));
         }
+        return branch;
       }
     }

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/ArgumentDeleter.cs

@@ -65 +65 @@
         // argument deletion by consolidation is not possible => abort
         return false;
+      // the argument to be removed is always the one with the largest index 
+      // (otherwise we would have to decrement the index of the larger argument symbols)
       var removedArgument = (from sym in selectedDefunBranch.Grammar.Symbols.OfType<Argument>()
-                             select sym.ArgumentIndex).Distinct().SelectRandom(random);
+                             select sym.ArgumentIndex).Distinct().OrderBy(x => x).Last();
       // find invocations of the manipulated funcion and remove the specified argument tree
-      var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
-                            where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
-                            select node;
+      var invocationNodes = (from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
+                             where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
+                             select node).ToList();
       foreach (var invokeNode in invocationNodes) {
         invokeNode.RemoveSubTree(removedArgument);
@@ -78 +80 @@
 
       // delete the dynamic argument symbol that matches the argument to be removed
-      var matchingSymbol = selectedDefunBranch.Grammar.Symbols.OfType<Argument>().Where(s => s.ArgumentIndex == removedArgument).First();
+      var matchingSymbol = selectedDefunBranch.Grammar.Symbols.OfType<Argument>().Where(s => s.ArgumentIndex == removedArgument).Single();
       selectedDefunBranch.Grammar.RemoveSymbol(matchingSymbol);
+      selectedDefunBranch.NumberOfArguments--;
       // reduce arity in known functions of all root branches
       foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
-        var matchingInvokeSymbol = subtree.Grammar.Symbols.OfType<InvokeFunction>().Where(s => s.FunctionName == selectedDefunBranch.FunctionName).FirstOrDefault();
+        var matchingInvokeSymbol = subtree.Grammar.Symbols.OfType<InvokeFunction>().Where(s => s.FunctionName == selectedDefunBranch.FunctionName).SingleOrDefault();
         if (matchingInvokeSymbol != null) {
-          subtree.Grammar.SetMinSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments - 1);
-          subtree.Grammar.SetMaxSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments - 1);
+          subtree.Grammar.SetMinSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments);
+          subtree.Grammar.SetMaxSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments);
         }
       }
-      selectedDefunBranch.NumberOfArguments--;
       return true;
     }

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/ArgumentDuplicater.cs

@@ -64 +64 @@
         return false;
 
-      var selectedDefunBranch = SelectRandomBranch(random, functionDefiningBranches);
-      var argumentNodes = from node in IterateNodesPrefix(selectedDefunBranch)
-                          where node is ArgumentTreeNode
-                          select (ArgumentTreeNode)node;
-      if (argumentNodes.Count() == 0 || argumentNodes.Count() >= maxFunctionArguments)
+      var selectedDefunBranch = functionDefiningBranches.SelectRandom(random);
+      var argumentSymbols = selectedDefunBranch.Grammar.Symbols.OfType<Argument>();
+      if (argumentSymbols.Count() == 0 || argumentSymbols.Count() >= maxFunctionArguments)
         // when no argument or number of arguments is already at max allowed value => abort
         return false;
-      var distinctArgumentIndexes = (from node in argumentNodes
-                                     select node.ArgumentIndex).Distinct().ToList();
-      var selectedArgumentIndex = distinctArgumentIndexes[random.Next(distinctArgumentIndexes.Count)];
-      var newArgumentIndex = allowedArgumentIndexes.Except(from argNode in argumentNodes select argNode.ArgumentIndex).First();
+      var selectedArgumentSymbol = argumentSymbols.SelectRandom(random);
+      var takenIndexes = argumentSymbols.Select(s => s.ArgumentIndex);
+      var newArgumentIndex = allowedArgumentIndexes.Except(takenIndexes).First();
+
+      var newArgSymbol = new Argument(newArgumentIndex);
+
       // replace existing references to the original argument with references to the new argument randomly in the selectedBranch
+      var argumentNodes = selectedDefunBranch.IterateNodesPrefix().OfType<ArgumentTreeNode>();
       foreach (var argNode in argumentNodes) {
-        if (argNode.ArgumentIndex == selectedArgumentIndex) {
+        if (argNode.Symbol == selectedArgumentSymbol) {
           if (random.NextDouble() < 0.5) {
-            argNode.ArgumentIndex = newArgumentIndex;
+            argNode.Symbol = newArgSymbol;
           }
         }
       }
       // find invocations of the functions and duplicate the matching argument branch
-      var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix()
-                            let invokeNode = node as InvokeFunctionTreeNode
-                            where invokeNode != null
-                            where invokeNode.InvokedFunctionName == selectedDefunBranch.Name
-                            select invokeNode;
+      var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
+                            where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
+                            select node;
       foreach (var invokeNode in invocationNodes) {
-        var argumentBranch = invokeNode.SubTrees[selectedArgumentIndex];
+        var argumentBranch = invokeNode.SubTrees[selectedArgumentSymbol.ArgumentIndex];
         var clonedArgumentBranch = (SymbolicExpressionTreeNode)argumentBranch.Clone();
         invokeNode.InsertSubTree(newArgumentIndex, clonedArgumentBranch);
       }
-      // register the new argument node and increase the number of arguments of the ADF
-      selectedDefunBranch.AddDynamicSymbol("ARG" + newArgumentIndex);
+      // register the new argument symbol and increase the number of arguments of the ADF
+      selectedDefunBranch.Grammar.AddSymbol(newArgSymbol);
+      selectedDefunBranch.Grammar.SetMinSubtreeCount(newArgSymbol, 0);
+      selectedDefunBranch.Grammar.SetMaxSubtreeCount(newArgSymbol, 0);
+      // allow the argument as child of any other symbol
+      foreach (var symb in selectedDefunBranch.Grammar.Symbols)
+        for (int i = 0; i < selectedDefunBranch.Grammar.GetMaxSubtreeCount(symb); i++) {
+          selectedDefunBranch.Grammar.SetAllowedChild(symb, newArgSymbol, i);
+        }
       selectedDefunBranch.NumberOfArguments++;
+
       // increase the arity of the changed ADF in all branches that can use this ADF
       foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
-        if (subtree.DynamicSymbols.Contains(selectedDefunBranch.Name)) {
-          subtree.SetDynamicSymbolArgumentCount(selectedDefunBranch.Name, selectedDefunBranch.NumberOfArguments);
+        var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
+                                    where symb.FunctionName == selectedDefunBranch.FunctionName
+                                    select symb).SingleOrDefault();
+        if (matchingInvokeSymbol != null) {
+          subtree.Grammar.SetMinSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments);
+          subtree.Grammar.SetMaxSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments);
+          foreach (var child in subtree.GetAllowedSymbols(0)) {
+            for (int i = 0; i < subtree.Grammar.GetMaxSubtreeCount(matchingInvokeSymbol); i++) {
+              subtree.Grammar.SetAllowedChild(matchingInvokeSymbol, child, i);
+            }
+          }
         }
       }
-      Debug.Assert(grammar.IsValidExpression(symbolicExpressionTree));
       return true;
     }

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/RandomArchitectureAlteringOperator.cs

@@ -65 +65 @@
 
     public override void ModifyArchitecture(IRandom random, SymbolicExpressionTree tree, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight, IntValue maxFunctionDefiningBranches, IntValue maxFunctionArguments, out bool success) {
-      var selectedOperator = Operators[random.Next(Operators.Count)];
+      var selectedOperator = Operators.SelectRandom(random);
       selectedOperator.ModifyArchitecture(random, tree, grammar, maxTreeSize, maxTreeHeight, maxFunctionDefiningBranches, maxFunctionArguments, out success);
     }

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/SubroutineCreater.cs

@@ -42 +42 @@
   [StorableClass]
   public sealed class SubroutineCreater : SymbolicExpressionTreeArchitectureAlteringOperator {
+    private const double ARGUMENT_CUTOFF_PROBABILITY = 0.05;
+
     public override sealed void ModifyArchitecture(
       IRandom random,
@@ -62 +64 @@
         // allowed maximum number of ADF reached => abort
         return false;
-      string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefiningBranches) + 1).ToString(); // >= 100 functions => ###
+      if (symbolicExpressionTree.Size + 4 > maxTreeSize)
+        // defining a new function causes an size increase by 4 nodes (max) if the max tree size is reached => abort
+        return false;
+      string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefiningBranches * 10 - 1)).ToString(); // >= 100 functions => ###
       var allowedFunctionNames = from index in Enumerable.Range(0, maxFunctionDefiningBranches)
                                  select "ADF" + index.ToString(formatString);
-      // find all body branches
-      var bodies = from node in symbolicExpressionTree.IterateNodesPrefix()
-                   where node.Symbol is Defun || node.Symbol is StartSymbol
+
+      // select a random body (either the result producing branch or an ADF branch)
+      var bodies = from node in symbolicExpressionTree.Root.SubTrees
                    select new { Tree = node, Size = node.GetSize() };
       var totalNumberOfBodyNodes = bodies.Select(x => x.Size).Sum();
-      // select a random body
       int r = random.Next(totalNumberOfBodyNodes);
       int aggregatedNumberOfBodyNodes = 0;
@@ -81 +85 @@
       // sanity check
       if (selectedBody == null) throw new InvalidOperationException();
-      // select a random node in the selected branch
-      var allCutPoints = (from parent in selectedBody.IterateNodesPrefix()
-                          from subtree in parent.SubTrees
-                          select new { Parent = parent, ReplacedBranchIndex = parent.SubTrees.IndexOf(subtree), ReplacedBranch = subtree }).ToList();
-      if (allCutPoints.Count == 0)
+
+      // select a random cut point in the selected branch
+      var allCutPoints = from parent in selectedBody.IterateNodesPrefix()
+                         from subtree in parent.SubTrees
+                         select new { Parent = parent, ReplacedBranchIndex = parent.SubTrees.IndexOf(subtree), ReplacedBranch = subtree };
+      if (allCutPoints.Count() == 0)
         // no cut points => abort
         return false;
-      var selectedCutPoint = allCutPoints[random.Next(allCutPoints.Count)];
+      string newFunctionName = allowedFunctionNames.Except(functionDefiningBranches.Select(x => x.FunctionName)).First();
+      var selectedCutPoint = allCutPoints.SelectRandom(random);
       // select random branches as argument cut-off points (replaced by argument terminal nodes in the function)
-      List<SymbolicExpressionTreeNode> argumentBranches = SelectRandomArgumentBranches(selectedCutPoint.ReplacedBranch, random, 0.25, maxFunctionArguments);
-      string functionName = allowedFunctionNames.Except(functionDefiningBranches.Select(x => x.Name)).First();
+      List<SymbolicExpressionTreeNode> argumentBranches = SelectRandomArgumentBranches(selectedCutPoint.ReplacedBranch, random, ARGUMENT_CUTOFF_PROBABILITY, maxFunctionArguments);
       SymbolicExpressionTreeNode functionBody = selectedCutPoint.ReplacedBranch;
       // disconnect the function body from the tree
       selectedCutPoint.Parent.RemoveSubTree(selectedCutPoint.ReplacedBranchIndex);
       // disconnect the argument branches from the function
-      DisconnectBranches(functionBody, argumentBranches);
-      // and insert a function invocation symbol instead
-      var invokeNode = (InvokeFunctionTreeNode)(new InvokeFunction()).CreateTreeNode();
-      invokeNode.InvokedFunctionName = functionName;
+      functionBody = DisconnectBranches(functionBody, argumentBranches);
+      // insert a function invocation symbol instead
+      var invokeNode = (InvokeFunctionTreeNode)(new InvokeFunction(newFunctionName)).CreateTreeNode();
       selectedCutPoint.Parent.InsertSubTree(selectedCutPoint.ReplacedBranchIndex, invokeNode);
+      // add the branches selected as argument as subtrees of the function invocation node
       foreach (var argumentBranch in argumentBranches)
         invokeNode.AddSubTree(argumentBranch);
@@ -106 +111 @@
       // insert a new function defining branch
       var defunNode = (DefunTreeNode)(new Defun()).CreateTreeNode();
-      defunNode.Name = functionName;
+      defunNode.FunctionName = newFunctionName;
       defunNode.AddSubTree(functionBody);
       symbolicExpressionTree.Root.AddSubTree(defunNode);
-      // copy known symbols from originating branch into new branch
-      foreach (var knownSymbol in selectedBody.DynamicSymbols) {
-        defunNode.AddDynamicSymbol(knownSymbol, selectedBody.GetDynamicSymbolArgumentCount(knownSymbol));
-      }
-      // add function arguments as known symbols to new branch
-      for (int i = 0; i < argumentBranches.Count; i++) {
-        defunNode.AddDynamicSymbol("ARG" + i);
-      }
-      // add new function name to original branch
-      selectedBody.AddDynamicSymbol(functionName, argumentBranches.Count);
+      // the grammar in the newly defined function is a clone of the grammar of the originating branch
+      defunNode.Grammar = (ISymbolicExpressionGrammar)selectedBody.Grammar.Clone();
+      // remove all argument symbols from grammar
+      var oldArgumentSymbols = defunNode.Grammar.Symbols.OfType<Argument>().ToList();
+      foreach (var oldArgSymb in oldArgumentSymbols)
+        defunNode.Grammar.RemoveSymbol(oldArgSymb);
+      // find unique argument indexes and matching symbols in the function defining branch 
+      var newArgumentIndexes = (from node in defunNode.IterateNodesPrefix().OfType<ArgumentTreeNode>()
+                                select node.Symbol.ArgumentIndex).Distinct();
+      // add argument symbols to grammar of function defining branch
+      GrammarModifier.AddDynamicArguments(defunNode.Grammar, defunNode.Symbol, newArgumentIndexes);
+      defunNode.NumberOfArguments = newArgumentIndexes.Count();
+      if (defunNode.NumberOfArguments != argumentBranches.Count) throw new InvalidOperationException();
+      // add invoke symbol for newly defined function to the original branch 
+      var allowedParents = from symb in selectedBody.Grammar.Symbols
+                           where !(symb is ProgramRootSymbol)
+                           select symb;
+      var allowedChildren = from symb in selectedBody.Grammar.Symbols
+                            where selectedBody.Grammar.IsAllowedChild(selectedBody.Symbol, symb, 0)
+                            select symb;
+      GrammarModifier.AddDynamicSymbol(selectedBody.Grammar, selectedBody.Symbol, defunNode.FunctionName, defunNode.NumberOfArguments);
+
+      // when the new function body was taken from another function definition
+      // add invoke symbol for newly defined function to all branches that are allowed to invoke the original branch
+      if (selectedBody.Symbol is Defun) {
+        var originalFunctionDefinition = selectedBody as DefunTreeNode;
+        foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
+          var originalBranchInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
+                                            where symb.FunctionName == originalFunctionDefinition.FunctionName
+                                            select symb).SingleOrDefault();
+          // when the original branch can be invoked from the subtree then also allow invocation of the function
+          if (originalBranchInvokeSymbol != null) {
+            allowedParents = from symb in subtree.Grammar.Symbols
+                             where !(symb is ProgramRootSymbol)
+                             select symb;
+            allowedChildren = from symb in subtree.Grammar.Symbols
+                              where subtree.Grammar.IsAllowedChild(subtree.Symbol, symb, 0)
+                              select symb;
+            GrammarModifier.AddDynamicSymbol(subtree.Grammar, subtree.Symbol, defunNode.FunctionName, defunNode.NumberOfArguments);
+          }
+        }
+      }
       return true;
     }
 
-    private static void DisconnectBranches(SymbolicExpressionTreeNode node, List<SymbolicExpressionTreeNode> argumentBranches) {
+    private static SymbolicExpressionTreeNode DisconnectBranches(SymbolicExpressionTreeNode node, List<SymbolicExpressionTreeNode> argumentBranches) {
+      if (argumentBranches.Contains(node)) {
+        var argumentIndex = argumentBranches.IndexOf(node);
+        var argSymbol = new Argument(argumentIndex);
+        return argSymbol.CreateTreeNode();
+      }
       // remove the subtrees so that we can clone only the root node
       List<SymbolicExpressionTreeNode> subtrees = new List<SymbolicExpressionTreeNode>(node.SubTrees);
@@ -128 +170 @@
       // recursively apply function for subtrees or append a argument terminal node
       foreach (var subtree in subtrees) {
-        if (argumentBranches.Contains(subtree)) {
-          node.AddSubTree(MakeArgumentNode(argumentBranches.IndexOf(subtree)));
-        } else {
-          DisconnectBranches(subtree, argumentBranches);
-          node.AddSubTree(subtree);
-        }
-      }
-    }
-
-    private static SymbolicExpressionTreeNode MakeArgumentNode(int argIndex) {
-      var node = (ArgumentTreeNode)(new Argument()).CreateTreeNode();
-      node.ArgumentIndex = argIndex;
+        node.AddSubTree(DisconnectBranches(subtree, argumentBranches));
+      }
       return node;
     }
@@ -145 +177 @@
     private static List<SymbolicExpressionTreeNode> SelectRandomArgumentBranches(SymbolicExpressionTreeNode selectedRoot,
       IRandom random,
-      double argumentProbability,
+      double cutProbability,
       int maxArguments) {
+      // breadth first determination of argument cut-off points
+      // we must make sure that we cut off all original argument nodes and that the number of new argument is smaller than the limit
       List<SymbolicExpressionTreeNode> argumentBranches = new List<SymbolicExpressionTreeNode>();
-      foreach (var subTree in selectedRoot.SubTrees) {
-        if (random.NextDouble() < argumentProbability) {
-          if (argumentBranches.Count < maxArguments)
-            argumentBranches.Add(subTree);
-        } else {
-          foreach (var argBranch in SelectRandomArgumentBranches(subTree, random, argumentProbability, maxArguments))
-            if (argumentBranches.Count < maxArguments)
-              argumentBranches.Add(argBranch);
+      if (selectedRoot is ArgumentTreeNode) {
+        argumentBranches.Add(selectedRoot);
+        return argumentBranches;
+      } else {
+        // get the number of argument nodes (which must be cut-off) in the sub-trees
+        var numberOfArgumentsInSubtrees = (from subtree in selectedRoot.SubTrees
+                                           let nArgumentsInTree = subtree.IterateNodesPrefix().OfType<ArgumentTreeNode>().Count()
+                                           select nArgumentsInTree).ToList();
+        // determine the minimal number of new argument nodes for each sub-tree
+        var minNewArgumentsForSubtrees = numberOfArgumentsInSubtrees.Select(x => x > 0 ? 1 : 0).ToList();
+        if (minNewArgumentsForSubtrees.Sum() > maxArguments) {
+          argumentBranches.Add(selectedRoot);
+          return argumentBranches;
         }
-      }
-      return argumentBranches;
-    }
-    
-    private static IEnumerable<string> UsedFunctionNames(SymbolicExpressionTree symbolicExpressionTree) {
-      return from node in symbolicExpressionTree.IterateNodesPrefix()
-             where node.Symbol is Defun
-             select ((DefunTreeNode)node).Name;
+        // cut-off in the sub-trees in random order
+        var randomIndexes = (from index in Enumerable.Range(0, selectedRoot.SubTrees.Count)
+                             select new { Index = index, OrderValue = random.NextDouble() }).OrderBy(x => x.OrderValue).Select(x => x.Index);
+        foreach (var subtreeIndex in randomIndexes) {
+          var subtree = selectedRoot.SubTrees[subtreeIndex];
+          minNewArgumentsForSubtrees[subtreeIndex] = 0;
+          // => cut-off at 0..n points somewhere in the current sub-tree
+          // determine the maximum number of new arguments that should be created in the branch
+          // as the maximum for the whole branch minus already added arguments minus minimal number of arguments still left
+          int maxArgumentsFromBranch = maxArguments - argumentBranches.Count - minNewArgumentsForSubtrees.Sum();
+          // when no argument is allowed from the current branch then we have to include the whole branch into the function
+          // otherwise: choose randomly wether to cut off immediately or wether to extend the function body into the branch
+          if (maxArgumentsFromBranch == 0) {
+            // don't cut at all => the whole sub-tree branch is included in the function body
+            // (we already checked ahead of time that there are no arguments left over in the subtree)
+          } else if (random.NextDouble() >= cutProbability) {
+            argumentBranches.AddRange(SelectRandomArgumentBranches(subtree, random, cutProbability, maxArgumentsFromBranch));
+          } else {
+            // cut-off at current sub-tree
+            argumentBranches.Add(subtree);
+          }
+        }
+        return argumentBranches;
+      }
     }
   }

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/SubroutineDeleter.cs

@@ -41 +41 @@
   [StorableClass]
   public sealed class SubroutineDeleter : SymbolicExpressionTreeArchitectureAlteringOperator {
-    private const int MAX_TRIES = 100;
     public override sealed void ModifyArchitecture(
       IRandom random,
@@ -68 +67 @@
       symbolicExpressionTree.Root.RemoveSubTree(defunSubtreeIndex);
 
-      // get all cut points that contain an invokation of the deleted defun
-      var invocationCutPoints = from node in symbolicExpressionTree.IterateNodesPrefix()
-                                where node.SubTrees.Count > 0
-                                from argIndex in Enumerable.Range(0, node.SubTrees.Count)
-                                let subtree = node.SubTrees[argIndex] as InvokeFunctionTreeNode
-                                where subtree != null
-                                where subtree.InvokedFunctionName == selectedDefunBranch.Name
-                                select new { Parent = node, ReplacedChildIndex = argIndex, ReplacedChild = subtree };
-      // deletion by random regeneration
-      foreach (var cutPoint in invocationCutPoints) {
-        SymbolicExpressionTreeNode replacementTree = null;
-        int targetSize = random.Next(cutPoint.ReplacedChild.GetSize());
-        int targetHeight = cutPoint.ReplacedChild.GetHeight();
-        int tries = 0;
-        do {
-          try {
-            replacementTree = ProbabilisticTreeCreator.PTC2(random, grammar, cutPoint.Parent.Symbol, targetSize, targetHeight);
-          }
-          catch (ArgumentException) {
-            // try different size
-            targetSize = random.Next(cutPoint.ReplacedChild.GetSize());
-            if (tries++ > MAX_TRIES) throw;
-          }
-        } while (replacementTree == null);
-        cutPoint.Parent.RemoveSubTree(cutPoint.ReplacedChildIndex);
-        cutPoint.Parent.InsertSubTree(cutPoint.ReplacedChildIndex, replacementTree);
-      }
       // remove references to deleted function
       foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
-        if (subtree.DynamicSymbols.Contains(selectedDefunBranch.Name)) {
-          subtree.RemoveDynamicSymbol(selectedDefunBranch.Name);
+        var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
+                                    where symb.FunctionName == selectedDefunBranch.FunctionName
+                                    select symb).SingleOrDefault();
+        if (matchingInvokeSymbol != null) {
+          subtree.Grammar.RemoveSymbol(matchingInvokeSymbol);
         }
       }
-      Debug.Assert(grammar.IsValidExpression(symbolicExpressionTree));
+
+      DeletionByRandomRegeneration(random, symbolicExpressionTree, selectedDefunBranch);
       return true;
+    }
+
+    private static void DeletionByRandomRegeneration(IRandom random, SymbolicExpressionTree symbolicExpressionTree, DefunTreeNode selectedDefunBranch) {
+      // find first invocation and replace it with a randomly generated tree
+      // can't find all invocations in one step because once we replaced a top level invocation
+      // the invocations below it are removed already
+      var invocationCutPoint = (from node in symbolicExpressionTree.IterateNodesPrefix()
+                                from subtree in node.SubTrees.OfType<InvokeFunctionTreeNode>()
+                                where subtree.Symbol.FunctionName == selectedDefunBranch.FunctionName
+                                select new { Parent = node, ReplacedChildIndex = node.SubTrees.IndexOf(subtree), ReplacedChild = subtree }).FirstOrDefault();
+      while (invocationCutPoint != null) {
+        // deletion by random regeneration
+        SymbolicExpressionTreeNode replacementTree = null;
+        // TODO: should weight symbols by tickets
+        var selectedSymbol = invocationCutPoint.Parent.GetAllowedSymbols(invocationCutPoint.ReplacedChildIndex).SelectRandom(random);
+
+        int minPossibleSize = invocationCutPoint.Parent.Grammar.GetMinExpressionLength(selectedSymbol);
+        int maxSize = Math.Max(minPossibleSize, invocationCutPoint.ReplacedChild.GetSize());
+        int minPossibleHeight = invocationCutPoint.Parent.Grammar.GetMinExpressionDepth(selectedSymbol);
+        int maxHeight = Math.Max(minPossibleHeight, invocationCutPoint.ReplacedChild.GetHeight());
+
+        replacementTree = ProbabilisticTreeCreator.PTC2(random, invocationCutPoint.Parent.Grammar, selectedSymbol, maxSize, maxHeight, 0, 0);
+        invocationCutPoint.Parent.RemoveSubTree(invocationCutPoint.ReplacedChildIndex);
+        invocationCutPoint.Parent.InsertSubTree(invocationCutPoint.ReplacedChildIndex, replacementTree);
+
+        invocationCutPoint = (from node in symbolicExpressionTree.IterateNodesPrefix()
+                              from subtree in node.SubTrees.OfType<InvokeFunctionTreeNode>()
+                              where subtree.Symbol.FunctionName == selectedDefunBranch.FunctionName
+                              select new { Parent = node, ReplacedChildIndex = node.SubTrees.IndexOf(subtree), ReplacedChild = subtree }).FirstOrDefault();
+      }
     }
   }

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/SubroutineDuplicater.cs

@@ -48 +48 @@
       IntValue maxFunctionDefiningBranches, IntValue maxFunctionArguments,
       out bool success) {
-      success = DuplicateRandomSubroutine(random, symbolicExpressionTree, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefiningBranches.Value, maxFunctionArguments.Value);
+      success = DuplicateSubroutine(random, symbolicExpressionTree, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefiningBranches.Value, maxFunctionArguments.Value);
     }
 
-    public static bool DuplicateRandomSubroutine(
+    public static bool DuplicateSubroutine(
       IRandom random,
       SymbolicExpressionTree symbolicExpressionTree,
@@ -66 +66 @@
         return false;
       var selectedBranch = functionDefiningBranches.SelectRandom(random);
-      var clonedBranch = (DefunTreeNode)selectedBranch.Clone();
-      clonedBranch.Name = allowedFunctionNames.Except(UsedFunctionNames(symbolicExpressionTree)).First();
-      foreach (var node in symbolicExpressionTree.IterateNodesPrefix()) {
-        var invokeFunctionNode = node as InvokeFunctionTreeNode;
-        // find all invokations of the old function 
-        if (invokeFunctionNode != null && invokeFunctionNode.InvokedFunctionName == selectedBranch.Name) {
-          // add the new function name to the list of known functions in the branches that used the originating function
-          var branch = symbolicExpressionTree.GetTopLevelBranchOf(invokeFunctionNode);
-          branch.AddDynamicSymbol(clonedBranch.Name, clonedBranch.NumberOfArguments);
-          // flip coin wether to replace with newly defined function
-          if (random.NextDouble() < 0.5) {
-            invokeFunctionNode.InvokedFunctionName = clonedBranch.Name;
-          }
+      var duplicatedDefunBranch = (DefunTreeNode)selectedBranch.Clone();
+      string newFunctionName = allowedFunctionNames.Except(UsedFunctionNames(symbolicExpressionTree)).First();
+      duplicatedDefunBranch.FunctionName = newFunctionName;
+      symbolicExpressionTree.Root.SubTrees.Add(duplicatedDefunBranch);
+      duplicatedDefunBranch.Grammar = (ISymbolicExpressionGrammar)selectedBranch.Grammar.Clone();
+      // add an invoke symbol for each branch that is allowed to invoke the original function
+      foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
+        var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
+                                    where symb.FunctionName == selectedBranch.FunctionName
+                                    select symb).SingleOrDefault();
+        if (matchingInvokeSymbol != null) {
+          GrammarModifier.AddDynamicSymbol(subtree.Grammar, subtree.Symbol, duplicatedDefunBranch.FunctionName, duplicatedDefunBranch.NumberOfArguments);
         }
       }
-      Debug.Assert(grammar.IsValidExpression(symbolicExpressionTree));
+      // for all invoke nodes of the original function replace the invoke of the original function with an invoke of the new function randomly
+      var originalFunctionInvocations = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
+                                        where node.Symbol.FunctionName == selectedBranch.FunctionName
+                                        select node;
+      foreach (var originalFunctionInvokeNode in originalFunctionInvocations) {
+        var newInvokeSymbol = (from symb in originalFunctionInvokeNode.Grammar.Symbols.OfType<InvokeFunction>()
+                               where symb.FunctionName == duplicatedDefunBranch.FunctionName
+                               select symb).Single();
+        // flip coin wether to replace with newly defined function
+        if (random.NextDouble() < 0.5) {
+          originalFunctionInvokeNode.Symbol = newInvokeSymbol;
+        }
+      }
       return true;
-    }
-
-    private static bool ContainsNode(SymbolicExpressionTreeNode branch, SymbolicExpressionTreeNode node) {
-      if (branch == node) return true;
-      else foreach (var subtree in branch.SubTrees) {
-          if (ContainsNode(subtree, node)) return true;
-        }
-      return false;
     }
 
@@ -96 +99 @@
       return from node in symbolicExpressionTree.IterateNodesPrefix()
              where node.Symbol is Defun
-             select ((DefunTreeNode)node).Name;
+             select ((DefunTreeNode)node).FunctionName;
     }
-
-
   }
 }