Free cookie consent management tool by TermsFeed Policy Generator

Changeset 3360


Ignore:
Timestamp:
04/15/10 19:58:42 (14 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
Files:
6 added
25 edited

Legend:

Unmodified
Added
Removed

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

    r3338 r3360  
    9696        // append a new argument branch after expanding all argument nodes
    9797        var clonedBranch = (SymbolicExpressionTreeNode)replacedBranch.Clone();
    98         ReplaceArgumentsInBranch(clonedBranch, invocationNode.SubTrees);
     98        clonedBranch = ReplaceArgumentsInBranch(clonedBranch, invocationNode.SubTrees);
    9999        invocationNode.InsertSubTree(newArgumentIndex, clonedBranch);
    100100      }
    … …  
    113113      foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
    114114        // when the changed function is known in the branch then update the number of arguments
    115         var matchingSymbol = subtree.Grammar.Symbols.Where(s => s.Name == selectedDefunBranch.FunctionName).SingleOrDefault();
     115        var matchingSymbol = subtree.Grammar.Symbols.OfType<InvokeFunction>().Where(s => s.FunctionName == selectedDefunBranch.FunctionName).SingleOrDefault();
    116116        if (matchingSymbol != null) {
    117117          subtree.Grammar.SetMinSubtreeCount(matchingSymbol, selectedDefunBranch.NumberOfArguments);
    118118          subtree.Grammar.SetMaxSubtreeCount(matchingSymbol, selectedDefunBranch.NumberOfArguments);
     119          foreach (var child in subtree.GetAllowedSymbols(0)) {
     120            for (int i = 0; i < subtree.Grammar.GetMaxSubtreeCount(matchingSymbol); i++) {
     121              subtree.Grammar.SetAllowedChild(matchingSymbol, child, i);
     122            }
     123          }
    119124        }
    120125      }
    … …  
    122127    }
    123128
    124     private static void ReplaceArgumentsInBranch(SymbolicExpressionTreeNode branch, IList<SymbolicExpressionTreeNode> argumentTrees) {
    125       // check if any subtree is an argument node
    126       for (int subtreeIndex = 0; subtreeIndex < branch.SubTrees.Count; subtreeIndex++) {
    127         var subtree = branch.SubTrees[subtreeIndex];
    128         var argNode = subtree as ArgumentTreeNode;
    129         if (argNode != null) {
    130           // replace argument nodes by a clone of the original subtree that provided the result for the argument node
    131           branch.SubTrees[subtreeIndex] = (SymbolicExpressionTreeNode)argumentTrees[argNode.Symbol.ArgumentIndex].Clone();
    132         } else {
    133           // recursively replace arguments in all branches
    134           ReplaceArgumentsInBranch(subtree, argumentTrees);
     129    private static SymbolicExpressionTreeNode ReplaceArgumentsInBranch(SymbolicExpressionTreeNode branch, IList<SymbolicExpressionTreeNode> argumentTrees) {
     130      if (branch is ArgumentTreeNode) {
     131        var argNode = branch as ArgumentTreeNode;
     132        // replace argument nodes by a clone of the original subtree that provided the result for the argument node
     133        return (SymbolicExpressionTreeNode)argumentTrees[argNode.Symbol.ArgumentIndex].Clone();
     134      } else {
     135        // call recursively for all subtree
     136        List<SymbolicExpressionTreeNode> subtrees = new List<SymbolicExpressionTreeNode>(branch.SubTrees);
     137        while (branch.SubTrees.Count > 0) branch.SubTrees.RemoveAt(0);
     138        foreach (var subtree in subtrees) {
     139          branch.AddSubTree(ReplaceArgumentsInBranch(subtree, argumentTrees));
    135140        }
     141        return branch;
    136142      }
    137143    }

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

    r3338 r3360  
    6565        // argument deletion by consolidation is not possible => abort
    6666        return false;
     67      // the argument to be removed is always the one with the largest index
     68      // (otherwise we would have to decrement the index of the larger argument symbols)
    6769      var removedArgument = (from sym in selectedDefunBranch.Grammar.Symbols.OfType<Argument>()
    68                              select sym.ArgumentIndex).Distinct().SelectRandom(random);
     70                             select sym.ArgumentIndex).Distinct().OrderBy(x => x).Last();
    6971      // find invocations of the manipulated funcion and remove the specified argument tree
    70       var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
    71                             where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
    72                             select node;
     72      var invocationNodes = (from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
     73                             where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
     74                             select node).ToList();
    7375      foreach (var invokeNode in invocationNodes) {
    7476        invokeNode.RemoveSubTree(removedArgument);
    … …  
    7880
    7981      // delete the dynamic argument symbol that matches the argument to be removed
    80       var matchingSymbol = selectedDefunBranch.Grammar.Symbols.OfType<Argument>().Where(s => s.ArgumentIndex == removedArgument).First();
     82      var matchingSymbol = selectedDefunBranch.Grammar.Symbols.OfType<Argument>().Where(s => s.ArgumentIndex == removedArgument).Single();
    8183      selectedDefunBranch.Grammar.RemoveSymbol(matchingSymbol);
     84      selectedDefunBranch.NumberOfArguments--;
    8285      // reduce arity in known functions of all root branches
    8386      foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
    84         var matchingInvokeSymbol = subtree.Grammar.Symbols.OfType<InvokeFunction>().Where(s => s.FunctionName == selectedDefunBranch.FunctionName).FirstOrDefault();
     87        var matchingInvokeSymbol = subtree.Grammar.Symbols.OfType<InvokeFunction>().Where(s => s.FunctionName == selectedDefunBranch.FunctionName).SingleOrDefault();
    8588        if (matchingInvokeSymbol != null) {
    86           subtree.Grammar.SetMinSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments - 1);
    87           subtree.Grammar.SetMaxSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments - 1);
     89          subtree.Grammar.SetMinSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments);
     90          subtree.Grammar.SetMaxSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments);
    8891        }
    8992      }
    90       selectedDefunBranch.NumberOfArguments--;
    9193      return true;
    9294    }

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

    r3338 r3360  
    6464        return false;
    6565
    66       var selectedDefunBranch = SelectRandomBranch(random, functionDefiningBranches);
    67       var argumentNodes = from node in IterateNodesPrefix(selectedDefunBranch)
    68                           where node is ArgumentTreeNode
    69                           select (ArgumentTreeNode)node;
    70       if (argumentNodes.Count() == 0 || argumentNodes.Count() >= maxFunctionArguments)
     66      var selectedDefunBranch = functionDefiningBranches.SelectRandom(random);
     67      var argumentSymbols = selectedDefunBranch.Grammar.Symbols.OfType<Argument>();
     68      if (argumentSymbols.Count() == 0 || argumentSymbols.Count() >= maxFunctionArguments)
    7169        // when no argument or number of arguments is already at max allowed value => abort
    7270        return false;
    73       var distinctArgumentIndexes = (from node in argumentNodes
    74                                      select node.ArgumentIndex).Distinct().ToList();
    75       var selectedArgumentIndex = distinctArgumentIndexes[random.Next(distinctArgumentIndexes.Count)];
    76       var newArgumentIndex = allowedArgumentIndexes.Except(from argNode in argumentNodes select argNode.ArgumentIndex).First();
     71      var selectedArgumentSymbol = argumentSymbols.SelectRandom(random);
     72      var takenIndexes = argumentSymbols.Select(s => s.ArgumentIndex);
     73      var newArgumentIndex = allowedArgumentIndexes.Except(takenIndexes).First();
     74
     75      var newArgSymbol = new Argument(newArgumentIndex);
     76
    7777      // replace existing references to the original argument with references to the new argument randomly in the selectedBranch
     78      var argumentNodes = selectedDefunBranch.IterateNodesPrefix().OfType<ArgumentTreeNode>();
    7879      foreach (var argNode in argumentNodes) {
    79         if (argNode.ArgumentIndex == selectedArgumentIndex) {
     80        if (argNode.Symbol == selectedArgumentSymbol) {
    8081          if (random.NextDouble() < 0.5) {
    81             argNode.ArgumentIndex = newArgumentIndex;
     82            argNode.Symbol = newArgSymbol;
    8283          }
    8384        }
    8485      }
    8586      // find invocations of the functions and duplicate the matching argument branch
    86       var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix()
    87                             let invokeNode = node as InvokeFunctionTreeNode
    88                             where invokeNode != null
    89                             where invokeNode.InvokedFunctionName == selectedDefunBranch.Name
    90                             select invokeNode;
     87      var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
     88                            where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
     89                            select node;
    9190      foreach (var invokeNode in invocationNodes) {
    92         var argumentBranch = invokeNode.SubTrees[selectedArgumentIndex];
     91        var argumentBranch = invokeNode.SubTrees[selectedArgumentSymbol.ArgumentIndex];
    9392        var clonedArgumentBranch = (SymbolicExpressionTreeNode)argumentBranch.Clone();
    9493        invokeNode.InsertSubTree(newArgumentIndex, clonedArgumentBranch);
    9594      }
    96       // register the new argument node and increase the number of arguments of the ADF
    97       selectedDefunBranch.AddDynamicSymbol("ARG" + newArgumentIndex);
     95      // register the new argument symbol and increase the number of arguments of the ADF
     96      selectedDefunBranch.Grammar.AddSymbol(newArgSymbol);
     97      selectedDefunBranch.Grammar.SetMinSubtreeCount(newArgSymbol, 0);
     98      selectedDefunBranch.Grammar.SetMaxSubtreeCount(newArgSymbol, 0);
     99      // allow the argument as child of any other symbol
     100      foreach (var symb in selectedDefunBranch.Grammar.Symbols)
     101        for (int i = 0; i < selectedDefunBranch.Grammar.GetMaxSubtreeCount(symb); i++) {
     102          selectedDefunBranch.Grammar.SetAllowedChild(symb, newArgSymbol, i);
     103        }
    98104      selectedDefunBranch.NumberOfArguments++;
     105
    99106      // increase the arity of the changed ADF in all branches that can use this ADF
    100107      foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
    101         if (subtree.DynamicSymbols.Contains(selectedDefunBranch.Name)) {
    102           subtree.SetDynamicSymbolArgumentCount(selectedDefunBranch.Name, selectedDefunBranch.NumberOfArguments);
     108        var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
     109                                    where symb.FunctionName == selectedDefunBranch.FunctionName
     110                                    select symb).SingleOrDefault();
     111        if (matchingInvokeSymbol != null) {
     112          subtree.Grammar.SetMinSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments);
     113          subtree.Grammar.SetMaxSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments);
     114          foreach (var child in subtree.GetAllowedSymbols(0)) {
     115            for (int i = 0; i < subtree.Grammar.GetMaxSubtreeCount(matchingInvokeSymbol); i++) {
     116              subtree.Grammar.SetAllowedChild(matchingInvokeSymbol, child, i);
     117            }
     118          }
    103119        }
    104120      }
    105       Debug.Assert(grammar.IsValidExpression(symbolicExpressionTree));
    106121      return true;
    107122    }

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

    r3294 r3360  
    6565
    6666    public override void ModifyArchitecture(IRandom random, SymbolicExpressionTree tree, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight, IntValue maxFunctionDefiningBranches, IntValue maxFunctionArguments, out bool success) {
    67       var selectedOperator = Operators[random.Next(Operators.Count)];
     67      var selectedOperator = Operators.SelectRandom(random);
    6868      selectedOperator.ModifyArchitecture(random, tree, grammar, maxTreeSize, maxTreeHeight, maxFunctionDefiningBranches, maxFunctionArguments, out success);
    6969    }

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

    r3338 r3360  
    4242  [StorableClass]
    4343  public sealed class SubroutineCreater : SymbolicExpressionTreeArchitectureAlteringOperator {
     44    private const double ARGUMENT_CUTOFF_PROBABILITY = 0.05;
     45
    4446    public override sealed void ModifyArchitecture(
    4547      IRandom random,
    … …  
    6264        // allowed maximum number of ADF reached => abort
    6365        return false;
    64       string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefiningBranches) + 1).ToString(); // >= 100 functions => ###
     66      if (symbolicExpressionTree.Size + 4 > maxTreeSize)
     67        // defining a new function causes an size increase by 4 nodes (max) if the max tree size is reached => abort
     68        return false;
     69      string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefiningBranches * 10 - 1)).ToString(); // >= 100 functions => ###
    6570      var allowedFunctionNames = from index in Enumerable.Range(0, maxFunctionDefiningBranches)
    6671                                 select "ADF" + index.ToString(formatString);
    67       // find all body branches
    68       var bodies = from node in symbolicExpressionTree.IterateNodesPrefix()
    69                    where node.Symbol is Defun || node.Symbol is StartSymbol
     72
     73      // select a random body (either the result producing branch or an ADF branch)
     74      var bodies = from node in symbolicExpressionTree.Root.SubTrees
    7075                   select new { Tree = node, Size = node.GetSize() };
    7176      var totalNumberOfBodyNodes = bodies.Select(x => x.Size).Sum();
    72       // select a random body
    7377      int r = random.Next(totalNumberOfBodyNodes);
    7478      int aggregatedNumberOfBodyNodes = 0;
    … …  
    8185      // sanity check
    8286      if (selectedBody == null) throw new InvalidOperationException();
    83       // select a random node in the selected branch
    84       var allCutPoints = (from parent in selectedBody.IterateNodesPrefix()
    85                           from subtree in parent.SubTrees
    86                           select new { Parent = parent, ReplacedBranchIndex = parent.SubTrees.IndexOf(subtree), ReplacedBranch = subtree }).ToList();
    87       if (allCutPoints.Count == 0)
     87
     88      // select a random cut point in the selected branch
     89      var allCutPoints = from parent in selectedBody.IterateNodesPrefix()
     90                         from subtree in parent.SubTrees
     91                         select new { Parent = parent, ReplacedBranchIndex = parent.SubTrees.IndexOf(subtree), ReplacedBranch = subtree };
     92      if (allCutPoints.Count() == 0)
    8893        // no cut points => abort
    8994        return false;
    90       var selectedCutPoint = allCutPoints[random.Next(allCutPoints.Count)];
     95      string newFunctionName = allowedFunctionNames.Except(functionDefiningBranches.Select(x => x.FunctionName)).First();
     96      var selectedCutPoint = allCutPoints.SelectRandom(random);
    9197      // select random branches as argument cut-off points (replaced by argument terminal nodes in the function)
    92       List<SymbolicExpressionTreeNode> argumentBranches = SelectRandomArgumentBranches(selectedCutPoint.ReplacedBranch, random, 0.25, maxFunctionArguments);
    93       string functionName = allowedFunctionNames.Except(functionDefiningBranches.Select(x => x.Name)).First();
     98      List<SymbolicExpressionTreeNode> argumentBranches = SelectRandomArgumentBranches(selectedCutPoint.ReplacedBranch, random, ARGUMENT_CUTOFF_PROBABILITY, maxFunctionArguments);
    9499      SymbolicExpressionTreeNode functionBody = selectedCutPoint.ReplacedBranch;
    95100      // disconnect the function body from the tree
    96101      selectedCutPoint.Parent.RemoveSubTree(selectedCutPoint.ReplacedBranchIndex);
    97102      // disconnect the argument branches from the function
    98       DisconnectBranches(functionBody, argumentBranches);
    99       // and insert a function invocation symbol instead
    100       var invokeNode = (InvokeFunctionTreeNode)(new InvokeFunction()).CreateTreeNode();
    101       invokeNode.InvokedFunctionName = functionName;
     103      functionBody = DisconnectBranches(functionBody, argumentBranches);
     104      // insert a function invocation symbol instead
     105      var invokeNode = (InvokeFunctionTreeNode)(new InvokeFunction(newFunctionName)).CreateTreeNode();
    102106      selectedCutPoint.Parent.InsertSubTree(selectedCutPoint.ReplacedBranchIndex, invokeNode);
     107      // add the branches selected as argument as subtrees of the function invocation node
    103108      foreach (var argumentBranch in argumentBranches)
    104109        invokeNode.AddSubTree(argumentBranch);
    … …  
    106111      // insert a new function defining branch
    107112      var defunNode = (DefunTreeNode)(new Defun()).CreateTreeNode();
    108       defunNode.Name = functionName;
     113      defunNode.FunctionName = newFunctionName;
    109114      defunNode.AddSubTree(functionBody);
    110115      symbolicExpressionTree.Root.AddSubTree(defunNode);
    111       // copy known symbols from originating branch into new branch
    112       foreach (var knownSymbol in selectedBody.DynamicSymbols) {
    113         defunNode.AddDynamicSymbol(knownSymbol, selectedBody.GetDynamicSymbolArgumentCount(knownSymbol));
    114       }
    115       // add function arguments as known symbols to new branch
    116       for (int i = 0; i < argumentBranches.Count; i++) {
    117         defunNode.AddDynamicSymbol("ARG" + i);
    118       }
    119       // add new function name to original branch
    120       selectedBody.AddDynamicSymbol(functionName, argumentBranches.Count);
     116      // the grammar in the newly defined function is a clone of the grammar of the originating branch
     117      defunNode.Grammar = (ISymbolicExpressionGrammar)selectedBody.Grammar.Clone();
     118      // remove all argument symbols from grammar
     119      var oldArgumentSymbols = defunNode.Grammar.Symbols.OfType<Argument>().ToList();
     120      foreach (var oldArgSymb in oldArgumentSymbols)
     121        defunNode.Grammar.RemoveSymbol(oldArgSymb);
     122      // find unique argument indexes and matching symbols in the function defining branch
     123      var newArgumentIndexes = (from node in defunNode.IterateNodesPrefix().OfType<ArgumentTreeNode>()
     124                                select node.Symbol.ArgumentIndex).Distinct();
     125      // add argument symbols to grammar of function defining branch
     126      GrammarModifier.AddDynamicArguments(defunNode.Grammar, defunNode.Symbol, newArgumentIndexes);
     127      defunNode.NumberOfArguments = newArgumentIndexes.Count();
     128      if (defunNode.NumberOfArguments != argumentBranches.Count) throw new InvalidOperationException();
     129      // add invoke symbol for newly defined function to the original branch
     130      var allowedParents = from symb in selectedBody.Grammar.Symbols
     131                           where !(symb is ProgramRootSymbol)
     132                           select symb;
     133      var allowedChildren = from symb in selectedBody.Grammar.Symbols
     134                            where selectedBody.Grammar.IsAllowedChild(selectedBody.Symbol, symb, 0)
     135                            select symb;
     136      GrammarModifier.AddDynamicSymbol(selectedBody.Grammar, selectedBody.Symbol, defunNode.FunctionName, defunNode.NumberOfArguments);
     137
     138      // when the new function body was taken from another function definition
     139      // add invoke symbol for newly defined function to all branches that are allowed to invoke the original branch
     140      if (selectedBody.Symbol is Defun) {
     141        var originalFunctionDefinition = selectedBody as DefunTreeNode;
     142        foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
     143          var originalBranchInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
     144                                            where symb.FunctionName == originalFunctionDefinition.FunctionName
     145                                            select symb).SingleOrDefault();
     146          // when the original branch can be invoked from the subtree then also allow invocation of the function
     147          if (originalBranchInvokeSymbol != null) {
     148            allowedParents = from symb in subtree.Grammar.Symbols
     149                             where !(symb is ProgramRootSymbol)
     150                             select symb;
     151            allowedChildren = from symb in subtree.Grammar.Symbols
     152                              where subtree.Grammar.IsAllowedChild(subtree.Symbol, symb, 0)
     153                              select symb;
     154            GrammarModifier.AddDynamicSymbol(subtree.Grammar, subtree.Symbol, defunNode.FunctionName, defunNode.NumberOfArguments);
     155          }
     156        }
     157      }
    121158      return true;
    122159    }
    123160
    124     private static void DisconnectBranches(SymbolicExpressionTreeNode node, List<SymbolicExpressionTreeNode> argumentBranches) {
     161    private static SymbolicExpressionTreeNode DisconnectBranches(SymbolicExpressionTreeNode node, List<SymbolicExpressionTreeNode> argumentBranches) {
     162      if (argumentBranches.Contains(node)) {
     163        var argumentIndex = argumentBranches.IndexOf(node);
     164        var argSymbol = new Argument(argumentIndex);
     165        return argSymbol.CreateTreeNode();
     166      }
    125167      // remove the subtrees so that we can clone only the root node
    126168      List<SymbolicExpressionTreeNode> subtrees = new List<SymbolicExpressionTreeNode>(node.SubTrees);
    … …  
    128170      // recursively apply function for subtrees or append a argument terminal node
    129171      foreach (var subtree in subtrees) {
    130         if (argumentBranches.Contains(subtree)) {
    131           node.AddSubTree(MakeArgumentNode(argumentBranches.IndexOf(subtree)));
    132         } else {
    133           DisconnectBranches(subtree, argumentBranches);
    134           node.AddSubTree(subtree);
    135         }
    136       }
    137     }
    138 
    139     private static SymbolicExpressionTreeNode MakeArgumentNode(int argIndex) {
    140       var node = (ArgumentTreeNode)(new Argument()).CreateTreeNode();
    141       node.ArgumentIndex = argIndex;
     172        node.AddSubTree(DisconnectBranches(subtree, argumentBranches));
     173      }
    142174      return node;
    143175    }
    … …  
    145177    private static List<SymbolicExpressionTreeNode> SelectRandomArgumentBranches(SymbolicExpressionTreeNode selectedRoot,
    146178      IRandom random,
    147       double argumentProbability,
     179      double cutProbability,
    148180      int maxArguments) {
     181      // breadth first determination of argument cut-off points
     182      // we must make sure that we cut off all original argument nodes and that the number of new argument is smaller than the limit
    149183      List<SymbolicExpressionTreeNode> argumentBranches = new List<SymbolicExpressionTreeNode>();
    150       foreach (var subTree in selectedRoot.SubTrees) {
    151         if (random.NextDouble() < argumentProbability) {
    152           if (argumentBranches.Count < maxArguments)
    153             argumentBranches.Add(subTree);
    154         } else {
    155           foreach (var argBranch in SelectRandomArgumentBranches(subTree, random, argumentProbability, maxArguments))
    156             if (argumentBranches.Count < maxArguments)
    157               argumentBranches.Add(argBranch);
     184      if (selectedRoot is ArgumentTreeNode) {
     185        argumentBranches.Add(selectedRoot);
     186        return argumentBranches;
     187      } else {
     188        // get the number of argument nodes (which must be cut-off) in the sub-trees
     189        var numberOfArgumentsInSubtrees = (from subtree in selectedRoot.SubTrees
     190                                           let nArgumentsInTree = subtree.IterateNodesPrefix().OfType<ArgumentTreeNode>().Count()
     191                                           select nArgumentsInTree).ToList();
     192        // determine the minimal number of new argument nodes for each sub-tree
     193        var minNewArgumentsForSubtrees = numberOfArgumentsInSubtrees.Select(x => x > 0 ? 1 : 0).ToList();
     194        if (minNewArgumentsForSubtrees.Sum() > maxArguments) {
     195          argumentBranches.Add(selectedRoot);
     196          return argumentBranches;
    158197        }
    159       }
    160       return argumentBranches;
    161     }
    162    
    163     private static IEnumerable<string> UsedFunctionNames(SymbolicExpressionTree symbolicExpressionTree) {
    164       return from node in symbolicExpressionTree.IterateNodesPrefix()
    165              where node.Symbol is Defun
    166              select ((DefunTreeNode)node).Name;
     198        // cut-off in the sub-trees in random order
     199        var randomIndexes = (from index in Enumerable.Range(0, selectedRoot.SubTrees.Count)
     200                             select new { Index = index, OrderValue = random.NextDouble() }).OrderBy(x => x.OrderValue).Select(x => x.Index);
     201        foreach (var subtreeIndex in randomIndexes) {
     202          var subtree = selectedRoot.SubTrees[subtreeIndex];
     203          minNewArgumentsForSubtrees[subtreeIndex] = 0;
     204          // => cut-off at 0..n points somewhere in the current sub-tree
     205          // determine the maximum number of new arguments that should be created in the branch
     206          // as the maximum for the whole branch minus already added arguments minus minimal number of arguments still left
     207          int maxArgumentsFromBranch = maxArguments - argumentBranches.Count - minNewArgumentsForSubtrees.Sum();
     208          // when no argument is allowed from the current branch then we have to include the whole branch into the function
     209          // otherwise: choose randomly wether to cut off immediately or wether to extend the function body into the branch
     210          if (maxArgumentsFromBranch == 0) {
     211            // don't cut at all => the whole sub-tree branch is included in the function body
     212            // (we already checked ahead of time that there are no arguments left over in the subtree)
     213          } else if (random.NextDouble() >= cutProbability) {
     214            argumentBranches.AddRange(SelectRandomArgumentBranches(subtree, random, cutProbability, maxArgumentsFromBranch));
     215          } else {
     216            // cut-off at current sub-tree
     217            argumentBranches.Add(subtree);
     218          }
     219        }
     220        return argumentBranches;
     221      }
    167222    }
    168223  }

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

    r3338 r3360  
    4141  [StorableClass]
    4242  public sealed class SubroutineDeleter : SymbolicExpressionTreeArchitectureAlteringOperator {
    43     private const int MAX_TRIES = 100;
    4443    public override sealed void ModifyArchitecture(
    4544      IRandom random,
    … …  
    6867      symbolicExpressionTree.Root.RemoveSubTree(defunSubtreeIndex);
    6968
    70       // get all cut points that contain an invokation of the deleted defun
    71       var invocationCutPoints = from node in symbolicExpressionTree.IterateNodesPrefix()
    72                                 where node.SubTrees.Count > 0
    73                                 from argIndex in Enumerable.Range(0, node.SubTrees.Count)
    74                                 let subtree = node.SubTrees[argIndex] as InvokeFunctionTreeNode
    75                                 where subtree != null
    76                                 where subtree.InvokedFunctionName == selectedDefunBranch.Name
    77                                 select new { Parent = node, ReplacedChildIndex = argIndex, ReplacedChild = subtree };
    78       // deletion by random regeneration
    79       foreach (var cutPoint in invocationCutPoints) {
    80         SymbolicExpressionTreeNode replacementTree = null;
    81         int targetSize = random.Next(cutPoint.ReplacedChild.GetSize());
    82         int targetHeight = cutPoint.ReplacedChild.GetHeight();
    83         int tries = 0;
    84         do {
    85           try {
    86             replacementTree = ProbabilisticTreeCreator.PTC2(random, grammar, cutPoint.Parent.Symbol, targetSize, targetHeight);
    87           }
    88           catch (ArgumentException) {
    89             // try different size
    90             targetSize = random.Next(cutPoint.ReplacedChild.GetSize());
    91             if (tries++ > MAX_TRIES) throw;
    92           }
    93         } while (replacementTree == null);
    94         cutPoint.Parent.RemoveSubTree(cutPoint.ReplacedChildIndex);
    95         cutPoint.Parent.InsertSubTree(cutPoint.ReplacedChildIndex, replacementTree);
    96       }
    9769      // remove references to deleted function
    9870      foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
    99         if (subtree.DynamicSymbols.Contains(selectedDefunBranch.Name)) {
    100           subtree.RemoveDynamicSymbol(selectedDefunBranch.Name);
     71        var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
     72                                    where symb.FunctionName == selectedDefunBranch.FunctionName
     73                                    select symb).SingleOrDefault();
     74        if (matchingInvokeSymbol != null) {
     75          subtree.Grammar.RemoveSymbol(matchingInvokeSymbol);
    10176        }
    10277      }
    103       Debug.Assert(grammar.IsValidExpression(symbolicExpressionTree));
     78
     79      DeletionByRandomRegeneration(random, symbolicExpressionTree, selectedDefunBranch);
    10480      return true;
     81    }
     82
     83    private static void DeletionByRandomRegeneration(IRandom random, SymbolicExpressionTree symbolicExpressionTree, DefunTreeNode selectedDefunBranch) {
     84      // find first invocation and replace it with a randomly generated tree
     85      // can't find all invocations in one step because once we replaced a top level invocation
     86      // the invocations below it are removed already
     87      var invocationCutPoint = (from node in symbolicExpressionTree.IterateNodesPrefix()
     88                                from subtree in node.SubTrees.OfType<InvokeFunctionTreeNode>()
     89                                where subtree.Symbol.FunctionName == selectedDefunBranch.FunctionName
     90                                select new { Parent = node, ReplacedChildIndex = node.SubTrees.IndexOf(subtree), ReplacedChild = subtree }).FirstOrDefault();
     91      while (invocationCutPoint != null) {
     92        // deletion by random regeneration
     93        SymbolicExpressionTreeNode replacementTree = null;
     94        // TODO: should weight symbols by tickets
     95        var selectedSymbol = invocationCutPoint.Parent.GetAllowedSymbols(invocationCutPoint.ReplacedChildIndex).SelectRandom(random);
     96
     97        int minPossibleSize = invocationCutPoint.Parent.Grammar.GetMinExpressionLength(selectedSymbol);
     98        int maxSize = Math.Max(minPossibleSize, invocationCutPoint.ReplacedChild.GetSize());
     99        int minPossibleHeight = invocationCutPoint.Parent.Grammar.GetMinExpressionDepth(selectedSymbol);
     100        int maxHeight = Math.Max(minPossibleHeight, invocationCutPoint.ReplacedChild.GetHeight());
     101
     102        replacementTree = ProbabilisticTreeCreator.PTC2(random, invocationCutPoint.Parent.Grammar, selectedSymbol, maxSize, maxHeight, 0, 0);
     103        invocationCutPoint.Parent.RemoveSubTree(invocationCutPoint.ReplacedChildIndex);
     104        invocationCutPoint.Parent.InsertSubTree(invocationCutPoint.ReplacedChildIndex, replacementTree);
     105
     106        invocationCutPoint = (from node in symbolicExpressionTree.IterateNodesPrefix()
     107                              from subtree in node.SubTrees.OfType<InvokeFunctionTreeNode>()
     108                              where subtree.Symbol.FunctionName == selectedDefunBranch.FunctionName
     109                              select new { Parent = node, ReplacedChildIndex = node.SubTrees.IndexOf(subtree), ReplacedChild = subtree }).FirstOrDefault();
     110      }
    105111    }
    106112  }

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

    r3338 r3360  
    4848      IntValue maxFunctionDefiningBranches, IntValue maxFunctionArguments,
    4949      out bool success) {
    50       success = DuplicateRandomSubroutine(random, symbolicExpressionTree, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefiningBranches.Value, maxFunctionArguments.Value);
     50      success = DuplicateSubroutine(random, symbolicExpressionTree, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefiningBranches.Value, maxFunctionArguments.Value);
    5151    }
    5252
    53     public static bool DuplicateRandomSubroutine(
     53    public static bool DuplicateSubroutine(
    5454      IRandom random,
    5555      SymbolicExpressionTree symbolicExpressionTree,
    … …  
    6666        return false;
    6767      var selectedBranch = functionDefiningBranches.SelectRandom(random);
    68       var clonedBranch = (DefunTreeNode)selectedBranch.Clone();
    69       clonedBranch.Name = allowedFunctionNames.Except(UsedFunctionNames(symbolicExpressionTree)).First();
    70       foreach (var node in symbolicExpressionTree.IterateNodesPrefix()) {
    71         var invokeFunctionNode = node as InvokeFunctionTreeNode;
    72         // find all invokations of the old function
    73         if (invokeFunctionNode != null && invokeFunctionNode.InvokedFunctionName == selectedBranch.Name) {
    74           // add the new function name to the list of known functions in the branches that used the originating function
    75           var branch = symbolicExpressionTree.GetTopLevelBranchOf(invokeFunctionNode);
    76           branch.AddDynamicSymbol(clonedBranch.Name, clonedBranch.NumberOfArguments);
    77           // flip coin wether to replace with newly defined function
    78           if (random.NextDouble() < 0.5) {
    79             invokeFunctionNode.InvokedFunctionName = clonedBranch.Name;
    80           }
     68      var duplicatedDefunBranch = (DefunTreeNode)selectedBranch.Clone();
     69      string newFunctionName = allowedFunctionNames.Except(UsedFunctionNames(symbolicExpressionTree)).First();
     70      duplicatedDefunBranch.FunctionName = newFunctionName;
     71      symbolicExpressionTree.Root.SubTrees.Add(duplicatedDefunBranch);
     72      duplicatedDefunBranch.Grammar = (ISymbolicExpressionGrammar)selectedBranch.Grammar.Clone();
     73      // add an invoke symbol for each branch that is allowed to invoke the original function
     74      foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
     75        var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
     76                                    where symb.FunctionName == selectedBranch.FunctionName
     77                                    select symb).SingleOrDefault();
     78        if (matchingInvokeSymbol != null) {
     79          GrammarModifier.AddDynamicSymbol(subtree.Grammar, subtree.Symbol, duplicatedDefunBranch.FunctionName, duplicatedDefunBranch.NumberOfArguments);
    8180        }
    8281      }
    83       Debug.Assert(grammar.IsValidExpression(symbolicExpressionTree));
     82      // for all invoke nodes of the original function replace the invoke of the original function with an invoke of the new function randomly
     83      var originalFunctionInvocations = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
     84                                        where node.Symbol.FunctionName == selectedBranch.FunctionName
     85                                        select node;
     86      foreach (var originalFunctionInvokeNode in originalFunctionInvocations) {
     87        var newInvokeSymbol = (from symb in originalFunctionInvokeNode.Grammar.Symbols.OfType<InvokeFunction>()
     88                               where symb.FunctionName == duplicatedDefunBranch.FunctionName
     89                               select symb).Single();
     90        // flip coin wether to replace with newly defined function
     91        if (random.NextDouble() < 0.5) {
     92          originalFunctionInvokeNode.Symbol = newInvokeSymbol;
     93        }
     94      }
    8495      return true;
    85     }
    86 
    87     private static bool ContainsNode(SymbolicExpressionTreeNode branch, SymbolicExpressionTreeNode node) {
    88       if (branch == node) return true;
    89       else foreach (var subtree in branch.SubTrees) {
    90           if (ContainsNode(subtree, node)) return true;
    91         }
    92       return false;
    9396    }
    9497
    … …  
    9699      return from node in symbolicExpressionTree.IterateNodesPrefix()
    97100             where node.Symbol is Defun
    98              select ((DefunTreeNode)node).Name;
     101             select ((DefunTreeNode)node).FunctionName;
    99102    }
    100 
    101 
    102103  }
    103104}

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Creators/ProbabilisticTreeCreator.cs

    r3338 r3360  
    2929using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols;
    3030using System.Text;
     31using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureAlteringOperators;
    3132
    3233namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    … …  
    5152      int maxFunctionDefinitions, int maxFunctionArguments
    5253      ) {
    53       // tree size is limited by the grammar and by the explicit size constraints
    54       int allowedMinSize = grammar.GetMinExpressionLength(grammar.StartSymbol);
    55       int allowedMaxSize = Math.Min(maxTreeSize, grammar.GetMaxExpressionLength(grammar.StartSymbol));
    56       // select a target tree size uniformly in the possible range (as determined by explicit limits and limits of the grammar)
    57       int treeSize = random.Next(allowedMinSize, allowedMaxSize);
    5854      SymbolicExpressionTree tree = new SymbolicExpressionTree();
    59       do {
    60         try {
    61           tree.Root = PTC2(random, grammar, grammar.StartSymbol, treeSize + 1, maxTreeHeight + 1, maxFunctionDefinitions, maxFunctionArguments);
    62         }
    63         catch (ArgumentException) {
    64           // try a different size
    65           treeSize = random.Next(allowedMinSize, allowedMaxSize);
    66         }
    67       } while (tree.Root == null || tree.Size > maxTreeSize || tree.Height > maxTreeHeight);
     55      tree.Root = PTC2(random, grammar, grammar.StartSymbol, maxTreeSize, maxTreeHeight, maxFunctionDefinitions, maxFunctionArguments);
    6856      return tree;
    6957    }
    … …  
    7462      public int ExtensionPointDepth { get; set; }
    7563    }
     64
     65    /// <summary>
     66    /// Creates a random tree with <paramref name="maxTreeSize"/> and <paramref name="maxDepth"/>.
     67    /// </summary>
     68    /// <param name="random"></param>
     69    /// <param name="grammar"></param>
     70    /// <param name="rootSymbol"></param>
     71    /// <param name="maxTreeSize"></param>
     72    /// <param name="maxDepth"></param>
     73    /// <param name="maxFunctionDefinitions"></param>
     74    /// <param name="maxFunctionArguments"></param>
     75    /// <returns></returns>
    7676    public static SymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionGrammar grammar, Symbol rootSymbol,
    77       int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
    78       SymbolicExpressionTreeNode root = rootSymbol.CreateTreeNode();
    79       root.Grammar = grammar;
    80       if (size <= 1 || maxDepth <= 1) return root;
    81       CreateFullTreeFromSeed(random, root, size, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
     77      int maxTreeSize, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
     78      // tree size is limited by the grammar and by the explicit size constraints
     79      int allowedMinSize = grammar.GetMinExpressionLength(rootSymbol);
     80      int allowedMaxSize = Math.Min(maxTreeSize, grammar.GetMaxExpressionLength(rootSymbol));
     81      // select a target tree size uniformly in the possible range (as determined by explicit limits and limits of the grammar)
     82      int treeSize = random.Next(allowedMinSize, allowedMaxSize + 1);
     83      SymbolicExpressionTreeNode root = null;
     84      do {
     85        try {
     86          root = rootSymbol.CreateTreeNode();
     87          root.Grammar = grammar;
     88          if (treeSize <= 1 || maxDepth <= 1) return root;
     89          CreateFullTreeFromSeed(random, root, treeSize, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
     90        }
     91        catch (ArgumentException) {
     92          // try a different size
     93          root = null;
     94          treeSize = random.Next(allowedMinSize, allowedMaxSize);
     95        }
     96      } while (root == null || root.GetSize() > maxTreeSize || root.GetHeight() > maxDepth);
    8297      return root;
    8398    }
    … …  
    105120        if (extensionDepth + parent.Grammar.GetMinExpressionDepth(parent.Symbol) >= maxDepth) {
    106121          ReplaceWithMinimalTree(random, root, parent, argumentIndex, maxFunctionDefinitions, maxFunctionArguments);
    107           //parent.RemoveSubTree(argumentIndex);
    108           //var allowedSymbols = from s in parent.Grammar.Symbols
    109           //                     where parent.Grammar.IsAllowedChild(parent.Symbol, s, argumentIndex)
    110           //                     select s;
    111           //SymbolicExpressionTreeNode branch = CreateMinimalTree(random, parent, allowedSymbols);
    112           //parent.InsertSubTree(argumentIndex, branch); // insert a smallest possible tree
    113           //currentSize += branch.GetSize();
    114           //totalListMinSize -= branch.GetSize();
    115122        } else {
    116123          var allowedSymbols = from s in parent.Grammar.Symbols
    … …  
    118125                               where parent.Grammar.GetMinExpressionDepth(s) + extensionDepth - 1 < maxDepth
    119126                               where parent.Grammar.GetMaxExpressionLength(s) > size - totalListMinSize - currentSize
    120                                /*||
    121                                      totalListMinSize + currentSize >= size * 0.9 // if the necessary size is almost reached then also allow
    122                                // terminals or terminal-branches*/
    123                                // where !IsDynamicSymbol(s) || IsDynamicSymbolAllowed(grammar, root, parent, s)
    124127                               select s;
    125128          Symbol selectedSymbol = SelectRandomSymbol(random, allowedSymbols);
    … …  
    172175        var dummy = new SymbolicExpressionTreeNode();
    173176        tree.AddSubTree(dummy);
    174         dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone(); 
     177        dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone();
    175178        // replace the just inserted dummy by recursive application
    176179        ReplaceWithMinimalTree(random, root, tree, i, maxFunctionDefinitions, maxFunctionArguments);
    177180      }
    178181    }
    179    
     182
    180183    private static void InitializeNewTreeNode(IRandom random, SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode newTree, int maxFunctionDefinitions, int maxFunctionArguments) {
    181184      // NB it is assumed that defuns are only allowed as children of root and nowhere else
    182185      // also assumes that newTree is already attached to root somewhere
    183       if (IsTopLevelBranch(root, newTree))
     186      if (IsTopLevelBranch(root, newTree)) {
    184187        newTree.Grammar = (ISymbolicExpressionGrammar)newTree.Grammar.Clone();
     188
     189        // allow invokes of existing ADFs with higher index
     190        int argIndex = root.SubTrees.IndexOf(newTree);
     191        for (int i = argIndex + 1; i < root.SubTrees.Count; i++) {
     192          var otherDefunNode = root.SubTrees[i] as DefunTreeNode;
     193          if (otherDefunNode != null) {
     194            GrammarModifier.AddDynamicSymbol(newTree.Grammar, newTree.Symbol, otherDefunNode.FunctionName, otherDefunNode.NumberOfArguments);
     195          }
     196        }
     197      }
    185198      if (newTree.Symbol is Defun) {
    186199        var defunTree = newTree as DefunTreeNode;
    … …  
    197210        defunTree.NumberOfArguments = nArgs;
    198211        if (nArgs > 0) {
    199           AddDynamicArguments(defunTree.Grammar, nArgs);
    200         }
     212          GrammarModifier.AddDynamicArguments(defunTree.Grammar, defunTree.Symbol, Enumerable.Range(0, nArgs));
     213        }
     214        // in existing branches with smaller index allow invoke of current function
    201215        int argIndex = root.SubTrees.IndexOf(newTree);
    202         // allow invokes of ADFs with higher index
    203         for (int i = argIndex + 1; i < root.SubTrees.Count; i++) {
    204           var otherDefunNode = root.SubTrees[i] as DefunTreeNode;
    205           if (otherDefunNode != null) {
    206             var allowedParents = from sym in defunTree.Grammar.Symbols
    207                                  where defunTree.Grammar.IsAllowedChild(defunTree.Symbol, sym, 0)
    208                                  select sym;
    209             var allowedChildren = allowedParents;
    210             AddDynamicSymbol(defunTree.Grammar, allowedParents, allowedChildren, otherDefunNode.FunctionName, otherDefunNode.NumberOfArguments);
    211           }
    212         }
    213         // make the ADF available as symbol for other branches (with smaller index to prevent recursions)
    214216        for (int i = 0; i < argIndex; i++) {
    215217          // if not dummy node
    216218          if (root.SubTrees[i].Symbol != null) {
    217             var topLevelGrammar = root.SubTrees[i].Grammar;
    218             var allowedParents = from sym in root.SubTrees[i].Grammar.Symbols
    219                                  where root.SubTrees[i].Grammar.IsAllowedChild(root.SubTrees[i].Symbol, sym, 0)
    220                                  select sym;
    221             var allowedChildren = allowedParents;
    222 
    223             AddDynamicSymbol(topLevelGrammar, allowedParents, allowedChildren, functionName, nArgs);
     219            var existingBranch = root.SubTrees[i];
     220            GrammarModifier.AddDynamicSymbol(existingBranch.Grammar, existingBranch.Symbol, functionName, nArgs);
    224221          }
    225222        }
    226       }
    227     }
    228 
    229     private static void AddDynamicSymbol(ISymbolicExpressionGrammar grammar, IEnumerable<Symbol> allowedParents, IEnumerable<Symbol> allowedChildren, string symbolName, int nArgs) {
    230       var invokeSym = new InvokeFunction(symbolName);
    231       grammar.AddSymbol(invokeSym);
    232       grammar.SetMinSubtreeCount(invokeSym, nArgs);
    233       grammar.SetMaxSubtreeCount(invokeSym, nArgs);
    234       foreach (var parent in allowedParents) {
    235         for (int arg = 0; arg < grammar.GetMaxSubtreeCount(parent); arg++) {
    236           grammar.SetAllowedChild(parent, invokeSym, arg);
    237         }
    238       }
    239       foreach (var child in allowedChildren) {
    240         for (int arg = 0; arg < grammar.GetMaxSubtreeCount(invokeSym); arg++) {
    241           grammar.SetAllowedChild(invokeSym, child, arg);
    242         }
    243       }
    244     }
    245 
    246     private static void AddDynamicArguments(ISymbolicExpressionGrammar grammar, int nArgs) {
    247       for (int argIndex = 0; argIndex < nArgs; argIndex++) {
    248         var argNode = new Argument(argIndex);
    249         grammar.AddSymbol(argNode);
    250         grammar.SetMinSubtreeCount(argNode, 0);
    251         grammar.SetMaxSubtreeCount(argNode, 0);
    252         // allow the argument as child of any other symbol
    253         foreach (var symb in grammar.Symbols)
    254           for (int i = 0; i < grammar.GetMaxSubtreeCount(symb); i++) {
    255             grammar.SetAllowedChild(symb, argNode, i);
    256           }
    257223      }
    258224    }

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/DefaultSymbolicExpressionGrammar.cs

    r3338 r3360  
    8181
    8282    public void RemoveSymbol(Symbol symbol) {
     83      foreach (var parent in Symbols) {
     84        for (int i = 0; i < GetMaxSubtreeCount(parent); i++)
     85          if (IsAllowedChild(parent, symbol, i))
     86            allowedChildSymbols[parent.Name][i].Remove(symbol.Name);
     87      }
    8388      allSymbols.RemoveWhere(s => s.Name == symbol.Name);
    8489      minSubTreeCount.Remove(symbol.Name);
    … …  
    208213      clone.minSubTreeCount = new Dictionary<string, int>(minSubTreeCount);
    209214      clone.startSymbol = startSymbol;
    210       clone.allowedChildSymbols = new Dictionary<string, List<HashSet<string>>>(allowedChildSymbols);
     215      clone.allowedChildSymbols = new Dictionary<string, List<HashSet<string>>>();
     216      foreach (var entry in allowedChildSymbols) {
     217        clone.allowedChildSymbols[entry.Key] = new List<HashSet<string>>();
     218        foreach (var set in entry.Value) {
     219          clone.allowedChildSymbols[entry.Key].Add(new HashSet<string>(set));
     220        }
     221      }
    211222      clone.allSymbols = new HashSet<Symbol>(allSymbols);
    212223      return clone;

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/GlobalSymbolicExpressionGrammar.cs

    r3338 r3360  
    8282    }
    8383
    84     private void Reset() {
     84    private new void Reset() {
    8585      base.Reset();
    8686      Initialize();

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.3.csproj

    r3338 r3360  
    8585    <Compile Include="ArchitectureAlteringOperators\ArgumentCreater.cs" />
    8686    <Compile Include="ArchitectureAlteringOperators\ArgumentDeleter.cs" />
     87    <Compile Include="ArchitectureAlteringOperators\ArgumentDuplicater.cs" />
     88    <Compile Include="ArchitectureAlteringOperators\GrammarModifier.cs" />
     89    <Compile Include="ArchitectureAlteringOperators\RandomArchitectureAlteringOperator.cs" />
     90    <Compile Include="ArchitectureAlteringOperators\SubroutineCreater.cs">
     91      <SubType>Code</SubType>
     92    </Compile>
     93    <Compile Include="ArchitectureAlteringOperators\SubroutineDeleter.cs" />
     94    <Compile Include="ArchitectureAlteringOperators\SubroutineDuplicater.cs" />
     95    <Compile Include="SymbolicExpressionTreeTopLevelNode.cs" />
    8796    <Compile Include="Crossovers\SubtreeCrossover.cs">
    8897      <SubType>Code</SubType>

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTree.cs

    r3338 r3360  
    7777    }
    7878
    79     public SymbolicExpressionTreeNode GetTopLevelBranchOf(SymbolicExpressionTreeNode node) {
    80       foreach (var branch in root.SubTrees) {
    81         if (branch.IterateNodesPrefix().Contains(node)) return branch;
    82       }
    83       throw new ArgumentException("Node was not found in tree.");
    84     }
    85 
    8679    public override IDeepCloneable Clone(Cloner cloner) {
    8780      SymbolicExpressionTree clone = new SymbolicExpressionTree();
    … …  
    9184      return clone;
    9285    }
    93 
    94     public bool IsValidExpression() {
    95       if (root.Symbol != root.Grammar.StartSymbol) return false;
    96       foreach (var subtree in root.SubTrees)
    97         if (subtree.Grammar == root.Grammar) return false;
    98       return root.IsValidTree();
    99     }
    10086  }
    10187}

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeNode.cs

    r3338 r3360  
    128128      yield return this;
    129129    }
    130     //public int GetMinExpressionLength() {
    131     //  return Grammar.GetMinExpressionLength(Symbol);
    132     //}
    133     //public int GetMaxExpressionLength() {
    134     //  return Grammar.GetMaxExpressionLength(Symbol);
    135     //}
    136     //public int GetMinExpressionDepth() {
    137     //  return Grammar.GetMinExpressionDepth(Symbol);
    138     //}
    139130    public IEnumerable<Symbol> GetAllowedSymbols(int argumentIndex) {
    140131      return Grammar.Symbols.Where(s => Grammar.IsAllowedChild(Symbol, s, argumentIndex));
    … …  
    146137      return Grammar.GetMaxSubtreeCount(Symbol);
    147138    }
    148     //public int GetMaxExpressionLength(Symbol s) {
    149     //  return Grammar.GetMaxExpressionLength(s);
    150     //}
    151     //public int GetMinExpressionLength(Symbol s) {
    152     //  return Grammar.GetMinExpressionLength(s);
    153     //}
    154     //public int GetMinExpressionDepth(Symbol s) {
    155     //  return Grammar.GetMinExpressionDepth(s);
    156     //}
    157139
    158140    #region ICloneable Members
    … …  
    165147
    166148
    167     public bool IsValidTree() {
    168       var matchingSymbol = (from symb in Grammar.Symbols
    169                             where symb.Name == Symbol.Name
    170                             select symb).SingleOrDefault();
    171149
    172       if (SubTrees.Count < Grammar.GetMinSubtreeCount(matchingSymbol)) return false;
    173       else if (SubTrees.Count > Grammar.GetMaxSubtreeCount(matchingSymbol)) return false;
    174       else for (int i = 0; i < SubTrees.Count; i++) {
    175           if (!GetAllowedSymbols(i).Select(x => x.Name).Contains(SubTrees[i].Symbol.Name)) return false;
    176           if (!SubTrees[i].IsValidTree()) return false;
    177         }
    178       return true;
    179     }
    180150  }
    181151}

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/DefunTreeNode.cs

    r3338 r3360  
    2525namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols {
    2626  [StorableClass]
    27   public sealed class DefunTreeNode : SymbolicExpressionTreeNode {
     27  public sealed class DefunTreeNode : SymbolicExpressionTreeTopLevelNode {
    2828    private int numberOfArguments;
    2929    [Storable]

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/InvokeFunctionTreeNode.cs

    r3338 r3360  
    2727    public new InvokeFunction Symbol {
    2828      get { return (InvokeFunction)base.Symbol; }
     29      set {
     30        if (value == null) throw new ArgumentNullException();
     31        if (!(value is InvokeFunction)) throw new ArgumentNullException();
     32        base.Symbol = value;
     33      }
    2934    }
    3035

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/StartSymbolTreeNode.cs

    r3338 r3360  
    2424namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols {
    2525  [StorableClass]
    26   public sealed class StartSymbolTreeNode : SymbolicExpressionTreeNode {
     26  public sealed class StartSymbolTreeNode : SymbolicExpressionTreeTopLevelNode {
    2727    // copy constructor
    2828    private StartSymbolTreeNode(StartSymbolTreeNode original)

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests

    • Property svn:ignore

      •  

        old new  
        11bin
        22obj
         3*.user

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/ArgumentCreaterTest.cs

    r3338 r3360  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System;
    223using System.Text;
    324using System.Collections.Generic;
    … …  
    3455      var trees = new List<SymbolicExpressionTree>();
    3556      var grammar = Grammars.CreateArithmeticAndAdfGrammar();
    36       var random = new MersenneTwister();
     57      var random = new MersenneTwister(31415);
     58      int failedEvents = 0;
    3759      for (int i = 0; i < POPULATION_SIZE; i++) {
    3860        var tree = ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3);
    39         ArgumentCreater.CreateNewArgument(random, tree, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3);
    40         Assert.IsTrue(tree.IsValidExpression());
     61        if (!ArgumentCreater.CreateNewArgument(random, tree, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3))
     62          failedEvents++;
     63        Util.IsValid(tree);
    4164        trees.Add(tree);
    4265      }
    4366      Assert.Inconclusive("ArgumentCreator: " + Environment.NewLine +
    44         Util.GetSizeDistributionString(trees, 105, 5) + Environment.NewLine +
     67        "Failed events: " + failedEvents / (double)POPULATION_SIZE * 100 + " %" + Environment.NewLine +
     68        Util.GetSizeDistributionString(trees, 200, 20) + Environment.NewLine +
    4569        Util.GetFunctionDistributionString(trees) + Environment.NewLine +
    4670        Util.GetNumberOfSubTreesDistributionString(trees) + Environment.NewLine +

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/ArgumentDeleterTest.cs

    r3338 r3360  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System;
    223using System.Text;
    324using System.Collections.Generic;
    … …  
    3455      var trees = new List<SymbolicExpressionTree>();
    3556      var grammar = Grammars.CreateArithmeticAndAdfGrammar();
    36       var random = new MersenneTwister();
     57      var random = new MersenneTwister(31415);
     58      int failedEvents = 0;
    3759      for (int i = 0; i < POPULATION_SIZE; i++) {
    3860        var tree = ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3);
    39         ArgumentDeleter.DeleteArgument(random, tree, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3);
    40         Assert.IsTrue(tree.IsValidExpression());
     61        if (!ArgumentDeleter.DeleteArgument(random, tree, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3))
     62          failedEvents++;
     63        Util.IsValid(tree);
    4164        trees.Add(tree);
    4265      }
    4366      Assert.Inconclusive("ArgumentDeleter: " + Environment.NewLine +
     67        "Failed events: " + failedEvents / (double)POPULATION_SIZE * 100 + " %" + Environment.NewLine +
    4468        Util.GetSizeDistributionString(trees, 105, 5) + Environment.NewLine +
    4569        Util.GetFunctionDistributionString(trees) + Environment.NewLine +

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/Grammars.cs

    r3338 r3360  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System;
    223using System.Text;
    324using System.Collections.Generic;
    … …  
    7495      return g;
    7596    }
     97
     98    public static void HasValidAdfGrammars(SymbolicExpressionTree tree) {
     99      Assert.AreEqual(tree.Root.Grammar.Symbols.Count(), 8);
     100      Assert.AreEqual(tree.Root.GetAllowedSymbols(0).Count(), 1); // only the start symbol is allowed
     101      // we allow 3 ADF branches
     102      Assert.AreEqual(tree.Root.GetAllowedSymbols(1).Count(), 1); // only the defun branch is allowed
     103      Assert.AreEqual(tree.Root.GetAllowedSymbols(2).Count(), 1); // only the defun symbol is allowed
     104      Assert.AreEqual(tree.Root.GetAllowedSymbols(3).Count(), 1); // only the defun symbol is allowed
     105      foreach (var subtree in tree.Root.SubTrees) {
     106        // check consistency of each sub-tree grammar independently
     107        var allowedSymbols = subtree.GetAllowedSymbols(0);
     108        int numberOfAllowedSymbols = allowedSymbols.Count();
     109        foreach (var parent in allowedSymbols) {
     110          for (int argIndex = 0; argIndex < subtree.Grammar.GetMaxSubtreeCount(parent); argIndex++) {
     111            var allowedChildren = from child in subtree.Grammar.Symbols
     112                                  where subtree.Grammar.IsAllowedChild(parent, child, argIndex)
     113                                  select child;
     114            Assert.AreEqual(numberOfAllowedSymbols, allowedChildren.Count());
     115          }
     116        }
     117      }
     118    }
     119
    76120  }
    77121}

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.3.Tests.csproj

    r3338 r3360  
    4141    <Compile Include="ArgumentCreaterTest.cs" />
    4242    <Compile Include="ArgumentDeleterTest.cs" />
     43    <Compile Include="ArgumentDuplicaterTest.cs" />
     44    <Compile Include="AllArchitectureAlteringOperatorsTest.cs" />
     45    <Compile Include="SubroutineDeleterTest.cs" />
     46    <Compile Include="SubroutineDuplicaterTest.cs" />
    4347    <Compile Include="Grammars.cs" />
     48    <Compile Include="SubroutineCreaterTest.cs">
     49      <SubType>Code</SubType>
     50    </Compile>
    4451    <Compile Include="SubtreeCrossoverTest.cs">
    4552      <SubType>Code</SubType>
    … …  
    5057  </ItemGroup>
    5158  <ItemGroup>
     59    <ProjectReference Include="..\..\..\HeuristicLab.Collections\3.3\HeuristicLab.Collections-3.3.csproj">
     60      <Project>{958B43BC-CC5C-4FA2-8628-2B3B01D890B6}</Project>
     61      <Name>HeuristicLab.Collections-3.3</Name>
     62    </ProjectReference>
    5263    <ProjectReference Include="..\..\..\HeuristicLab.Core\3.3\HeuristicLab.Core-3.3.csproj">
    5364      <Project>{C36BD924-A541-4A00-AFA8-41701378DDC5}</Project>
    5465      <Name>HeuristicLab.Core-3.3</Name>
     66    </ProjectReference>
     67    <ProjectReference Include="..\..\..\HeuristicLab.Data\3.3\HeuristicLab.Data-3.3.csproj">
     68      <Project>{BBAB9DF5-5EF3-4BA8-ADE9-B36E82114937}</Project>
     69      <Name>HeuristicLab.Data-3.3</Name>
    5570    </ProjectReference>
    5671    <ProjectReference Include="..\..\..\HeuristicLab.Operators\3.3\HeuristicLab.Operators-3.3.csproj">

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/ProbabilisticTreeCreaterTest.cs

    r3338 r3360  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System;
    223using System.Text;
    324using System.Collections.Generic;
    … …  
    3859      }
    3960
    40       foreach (var tree in randomTrees)
    41         Assert.IsTrue(tree.IsValidExpression());
     61      foreach (var tree in randomTrees) {
     62        Util.IsValid(tree);
     63      }
    4264      Assert.Inconclusive("ProbabilisticTreeCreator: " + Environment.NewLine +
    4365        Util.GetSizeDistributionString(randomTrees, 105, 5) + Environment.NewLine +
    … …  
    5577      var random = new MersenneTwister();
    5678      for (int i = 0; i < POPULATION_SIZE; i++) {
    57         randomTrees.Add(ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3));
     79        var tree = ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3);
     80        Grammars.HasValidAdfGrammars(tree);
     81        Util.IsValid(tree);
     82        randomTrees.Add(tree);
    5883      }
    59       foreach (var tree in randomTrees)
    60         Assert.IsTrue(tree.IsValidExpression());
    6184      Assert.Inconclusive("ProbabilisticTreeCreator: " + Environment.NewLine +
    6285        Util.GetSizeDistributionString(randomTrees, 105, 5) + Environment.NewLine +

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/SubroutineCreaterTest.cs

    r3338 r3360  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System;
    223using System.Text;
    324using System.Collections.Generic;
    … …  
    829using System.Diagnostics;
    930using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureAlteringOperators;
    10 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols;
    1131
    1232namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding_3._3.Tests {
    1333  [TestClass]
    1434  public class SubroutineCreaterTest {
    15     private static ISymbolicExpressionGrammar grammar;
    16     private static List<SymbolicExpressionTree> subroutineTrees;
    17     private static int failedEvents;
    18 
     35    private const int POPULATION_SIZE = 1000;
     36    private const int MAX_TREE_SIZE = 100;
     37    private const int MAX_TREE_HEIGHT = 10;
    1938    private TestContext testContextInstance;
    2039
    … …  
    3251    }
    3352
    34     [ClassInitialize()]
    35     public static void SubroutineCreaterTestInitialize(TestContext testContext) {
    36       var randomTrees = new List<SymbolicExpressionTree>();
    37       subroutineTrees = new List<SymbolicExpressionTree>();
    38       int populationSize = 1000;
    39       failedEvents = 0;
    40       grammar = Grammars.CreateArithmeticAndAdfGrammar();
    41       var random = new MersenneTwister();
    42       for (int i = 0; i < populationSize; i++) {
    43         var randTree = ProbabilisticTreeCreator.Create(random, grammar, 100, 10);
    44         // PTC create is tested separately
    45         randomTrees.Add(randTree);
     53    [TestMethod()]
     54    public void SubroutineCreaterDistributionsTest() {
     55      var trees = new List<SymbolicExpressionTree>();
     56      var grammar = Grammars.CreateArithmeticAndAdfGrammar();
     57      var random = new MersenneTwister(31415);
     58      int failedEvents = 0;
     59      for (int i = 0; i < POPULATION_SIZE; i++) {
     60        var tree = ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3);
     61        if (!SubroutineCreater.CreateSubroutine(random, tree, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3))
     62          failedEvents++;
     63        Util.IsValid(tree);
     64        trees.Add(tree);
    4665      }
    47       var newPopulation = new List<SymbolicExpressionTree>();
    48       for (int i = 0; i < populationSize; i++) {
    49         var par0 = (SymbolicExpressionTree)randomTrees[random.Next(populationSize)].Clone();
    50         bool success = SubroutineCreater.CreateSubroutine(random, par0, grammar, 100, 10, 3, 3);
    51         if (!success) failedEvents++;
    52         subroutineTrees.Add(par0);
    53       }
    54     }
    55 
    56 
    57     [TestMethod()]
    58     public void SubroutineCreaterCreateTest() {
    59       foreach (var tree in subroutineTrees)
    60         Assert.IsTrue(grammar.IsValidExpression(tree));
    61     }
    62 
    63     [TestMethod()]
    64     public void SubroutineCreaterSizeDistributionTest() {
    65       Assert.Inconclusive("SubroutineCreater: " + Util.GetSizeDistributionString(subroutineTrees, 105, 5));
    66     }
    67 
    68     [TestMethod()]
    69     public void SubroutineCreaterFunctionDistributionTest() {
    70       Assert.Inconclusive("SubroutineCreater: " + Util.GetFunctionDistributionString(subroutineTrees));
    71     }
    72 
    73     [TestMethod()]
    74     public void SubroutineCreaterNumberOfSubTreesDistributionTest() {
    75       Assert.Inconclusive("SubroutineCreater: " + Util.GetNumberOfSubTreesDistributionString(subroutineTrees));
    76     }
    77 
    78 
    79     [TestMethod()]
    80     public void SubroutineCreaterTerminalDistributionTest() {
    81       Assert.Inconclusive("SubroutineCreater: " + Util.GetTerminalDistributionString(subroutineTrees));
     66      Assert.Inconclusive("SubroutineCreator: " + Environment.NewLine +
     67        "Failed events: " + failedEvents / (double)POPULATION_SIZE * 100 + " %" + Environment.NewLine +
     68        Util.GetSizeDistributionString(trees, 105, 5) + Environment.NewLine +
     69        Util.GetFunctionDistributionString(trees) + Environment.NewLine +
     70        Util.GetNumberOfSubTreesDistributionString(trees) + Environment.NewLine +
     71        Util.GetTerminalDistributionString(trees) + Environment.NewLine
     72        );
    8273    }
    8374  }

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/SubtreeCrossoverTest.cs

    r3338 r3360  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System;
    223using System.Text;
    324using System.Collections.Generic;
    … …  
    1132  [TestClass]
    1233  public class SubtreeCrossoverTest {
    13     private static ISymbolicExpressionGrammar grammar;
    14     private static List<SymbolicExpressionTree> crossoverTrees;
    15     private static double msPerCrossoverEvent;
    16 
     34    private const int POPULATION_SIZE = 1000;
    1735    private TestContext testContextInstance;
    1836
    … …  
    3048    }
    3149
    32     [ClassInitialize()]
    33     public static void SubtreeCrossoverTestInitialize(TestContext testContext) {
    34       crossoverTrees = new List<SymbolicExpressionTree>();
    35       int populationSize = 1000;
     50    [TestMethod()]
     51    public void SubtreeCrossoverDistributionsTest() {
    3652      int generations = 5;
     53      var trees = new List<SymbolicExpressionTree>();
     54      var grammar = Grammars.CreateArithmeticAndAdfGrammar();
     55      var random = new MersenneTwister();
    3756      int failedEvents = 0;
    38       grammar = Grammars.CreateArithmeticAndAdfGrammar();
    39       var random = new MersenneTwister();
    40       for (int i = 0; i < populationSize; i++) {
    41         crossoverTrees.Add(ProbabilisticTreeCreator.Create(random, grammar, 100, 10, 3, 3));
     57      List<SymbolicExpressionTree> crossoverTrees;
     58      double msPerCrossoverEvent;
     59
     60      for (int i = 0; i < POPULATION_SIZE; i++) {
     61        trees.Add(ProbabilisticTreeCreator.Create(random, grammar, 100, 10, 3, 3));
    4262      }
    4363      Stopwatch stopwatch = new Stopwatch();
    … …  
    4565      for (int gCount = 0; gCount < generations; gCount++) {
    4666        var newPopulation = new List<SymbolicExpressionTree>();
    47         for (int i = 0; i < populationSize; i++) {
    48           var par0 = (SymbolicExpressionTree)crossoverTrees[random.Next(populationSize)].Clone();
    49           var par1 = (SymbolicExpressionTree)crossoverTrees[random.Next(populationSize)].Clone();
     67        for (int i = 0; i < POPULATION_SIZE; i++) {
     68          var par0 = (SymbolicExpressionTree)trees.SelectRandom(random).Clone();
     69          var par1 = (SymbolicExpressionTree)trees.SelectRandom(random).Clone();
    5070          bool success;
    5171          newPopulation.Add(SubtreeCrossover.Cross(random, par0, par1, 0.9, 100, 10, out success));
    … …  
    5575      }
    5676      stopwatch.Stop();
    57       foreach (var tree in crossoverTrees)
    58         Assert.IsTrue(tree.IsValidExpression());
    59       msPerCrossoverEvent = stopwatch.ElapsedMilliseconds / (double)populationSize / (double)generations;     
    60     }
     77      foreach (var tree in trees)
     78        Util.IsValid(tree);
    6179
     80      msPerCrossoverEvent = stopwatch.ElapsedMilliseconds / (double)POPULATION_SIZE / (double)generations;
    6281
    63 
    64     [TestMethod()]
    65     public void SubtreeCrossoverSpeed() {
    66 
    67       Assert.Inconclusive(msPerCrossoverEvent + " ms per crossover event (~" +
    68         Math.Round(1000.0 / (msPerCrossoverEvent)) + "crossovers / s)");
    69     }
    70 
    71     [TestMethod()]
    72     public void SubtreeCrossoverSizeDistributions() {
    73       Assert.Inconclusive("SubtreeCrossover: " + Util.GetSizeDistributionString(crossoverTrees, 105, 5));
    74     }
    75 
    76     [TestMethod()]
    77     public void SubtreeCrossoverFunctionDistributionTest() {
    78       Assert.Inconclusive("SubtreeCrossover: " + Util.GetFunctionDistributionString(crossoverTrees));
    79     }
    80 
    81     [TestMethod()]
    82     public void SubtreeCrossoverNumberOfSubTreesDistributionTest() {
    83       Assert.Inconclusive("SubtreeCrossover: " + Util.GetNumberOfSubTreesDistributionString(crossoverTrees));
    84     }
    85 
    86 
    87     [TestMethod()]
    88     public void SubtreeCrossoverTerminalDistributionTest() {
    89       Assert.Inconclusive("SubtreeCrossover: " + Util.GetTerminalDistributionString(crossoverTrees));
     82      Assert.Inconclusive("SubtreeCrossover: " + Environment.NewLine +
     83        "Failed events: " + failedEvents / (double)POPULATION_SIZE * 100 + " %" + Environment.NewLine +
     84        msPerCrossoverEvent + " ms per crossover event (~" + Math.Round(1000.0 / (msPerCrossoverEvent)) + "crossovers / s)" + Environment.NewLine +
     85        Util.GetSizeDistributionString(trees, 105, 5) + Environment.NewLine +
     86        Util.GetFunctionDistributionString(trees) + Environment.NewLine +
     87        Util.GetNumberOfSubTreesDistributionString(trees) + Environment.NewLine +
     88        Util.GetTerminalDistributionString(trees) + Environment.NewLine
     89        );
    9090    }
    9191  }

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/Util.cs

    r3338 r3360  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System;
    223using System.Text;
    324using System.Collections.Generic;
    … …  
    1334      int[] histogram = new int[maxTreeSize / binSize];
    1435      for (int i = 0; i < trees.Count; i++) {
    15         histogram[trees[i].Size / binSize]++;
     36        int binIndex = Math.Min(histogram.Length - 1, trees[i].Size / binSize);
     37        histogram[binIndex]++;
    1638      }
    1739      StringBuilder strBuilder = new StringBuilder();
    18       for (int i = 0; i < histogram.Length; i++) {
     40      for (int i = 0; i < histogram.Length - 1; i++) {
    1941        strBuilder.Append(Environment.NewLine);
    2042        strBuilder.Append("< "); strBuilder.Append((i + 1) * binSize);
    2143        strBuilder.Append(": "); strBuilder.AppendFormat("{0:#0.00%}", histogram[i] / (double)trees.Count);
    2244      }
     45      strBuilder.Append(Environment.NewLine);
     46      strBuilder.Append(">= "); strBuilder.Append(histogram.Length * binSize);
     47      strBuilder.Append(": "); strBuilder.AppendFormat("{0:#0.00%}", histogram[histogram.Length - 1] / (double)trees.Count);
     48
    2349      return "Size distribution: " + strBuilder;
    2450    }
    … …  
    88114      return "Terminal distribution: " + strBuilder;
    89115    }
     116
     117    public static void IsValid(SymbolicExpressionTree tree) {
     118      Grammars.HasValidAdfGrammars(tree);
     119      Assert.AreEqual(tree.Root.Symbol, tree.Root.Grammar.StartSymbol);
     120      foreach (var subtree in tree.Root.SubTrees)
     121        Assert.AreNotSame(subtree.Grammar, tree.Root.Grammar);
     122      IsValid(tree.Root);
     123    }
     124
     125    public static void IsValid(SymbolicExpressionTreeNode treeNode) {
     126      var matchingSymbol = (from symb in treeNode.Grammar.Symbols
     127                            where symb.Name == treeNode.Symbol.Name
     128                            select symb).SingleOrDefault();
     129      Assert.IsTrue(treeNode.SubTrees.Count >= treeNode.Grammar.GetMinSubtreeCount(matchingSymbol));
     130      Assert.IsTrue(treeNode.SubTrees.Count <= treeNode.Grammar.GetMaxSubtreeCount(matchingSymbol));
     131      for (int i = 0; i < treeNode.SubTrees.Count; i++) {
     132        Assert.IsTrue(treeNode.GetAllowedSymbols(i).Select(x => x.Name).Contains(treeNode.SubTrees[i].Symbol.Name));
     133        IsValid(treeNode.SubTrees[i]);
     134      }
     135    }
    90136  }
    91137}
Note: See TracChangeset for help on using the changeset viewer.