Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
04/13/10 20:44:31 (15 years ago)
Author:
gkronber
Message:

Fixed bugs related to dynamic symbol constraints with ADFs. #290 (Implement ADFs)

Location:
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3
Files:
7 added
29 edited

Legend:

Unmodified
Added
Removed

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

    r3294 r3338  
    6060      var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>();
    6161
    62       var allowedArgumentIndexes = Enumerable.Range(0, maxFunctionArguments);
    63 
    6462      if (functionDefiningBranches.Count() == 0)
    6563        // no function defining branch found => abort
    6664        return false;
     65
    6766      // select a random function defining branch
    68       var selectedDefunBranch = SelectRandomBranch(random, functionDefiningBranches);
     67      var selectedDefunBranch = functionDefiningBranches.SelectRandom(random);
     68      var definedArguments = (from symbol in selectedDefunBranch.Grammar.Symbols.OfType<Argument>()
     69                              select symbol.ArgumentIndex).Distinct();
     70      if (definedArguments.Count() >= maxFunctionArguments)
     71        // max number of arguments reached => abort
     72        return false;
    6973      // select a random cut point in the function defining branch
    7074      // the branch at the cut point is to be replaced by a new argument node
    71       var cutPoints = (from node in IterateNodesPrefix(selectedDefunBranch)
     75      var cutPoints = (from node in selectedDefunBranch.IterateNodesPrefix()
    7276                       where node.SubTrees.Count > 0
    7377                       from subtree in node.SubTrees
    … …  
    7882        return false;
    7983      var selectedCutPoint = cutPoints[random.Next(cutPoints.Count)];
    80       var existingArguments = from node in IterateNodesPrefix(selectedDefunBranch)
    81                               let argNode = node as ArgumentTreeNode
    82                               where argNode != null
    83                               select argNode;
    84       var newArgumentIndex = allowedArgumentIndexes.Except(existingArguments.Select(x => x.ArgumentIndex)).First();
     84      var allowedArgumentIndexes = Enumerable.Range(0, maxFunctionArguments);
     85      var newArgumentIndex = allowedArgumentIndexes.Except(definedArguments).First();
    8586      // replace the branch at the cut point with an argument node
    8687      var newArgNode = MakeArgumentNode(newArgumentIndex);
    … …  
    8889      selectedCutPoint.Parent.RemoveSubTree(selectedCutPoint.ReplacedChildIndex);
    8990      selectedCutPoint.Parent.InsertSubTree(selectedCutPoint.ReplacedChildIndex, newArgNode);
    90       // find all invokations of the selected ADF and attach a cloned version of the originally cut out branch
     91      // find all invocations of the selected ADF and attach a cloned version of the replaced branch (with all argument-nodes expanded)
    9192      var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
    92                             where node.InvokedFunctionName == selectedDefunBranch.Name
     93                            where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
    9394                            select node;
    94       // append a new argument branch after preprocessing
    9595      foreach (var invocationNode in invocationNodes) {
     96        // append a new argument branch after expanding all argument nodes
    9697        var clonedBranch = (SymbolicExpressionTreeNode)replacedBranch.Clone();
    9798        ReplaceArgumentsInBranch(clonedBranch, invocationNode.SubTrees);
    9899        invocationNode.InsertSubTree(newArgumentIndex, clonedBranch);
    99100      }
    100       // adapt the known functions informations
     101      // increase expected number of arguments of function defining branch
     102      // it's possible that the number of actually referenced arguments was reduced (all references were replaced by a single new argument)
     103      // but the number of expected arguments is increased anyway
    101104      selectedDefunBranch.NumberOfArguments++;
    102       selectedDefunBranch.AddDynamicSymbol("ARG" + newArgumentIndex, 0);
     105      selectedDefunBranch.Grammar.AddSymbol(newArgNode.Symbol);
     106      selectedDefunBranch.Grammar.SetMinSubtreeCount(newArgNode.Symbol, 0);
     107      selectedDefunBranch.Grammar.SetMaxSubtreeCount(newArgNode.Symbol, 0);
     108      // allow the argument as child of any other symbol
     109      foreach (var symb in selectedDefunBranch.Grammar.Symbols)
     110        for (int i = 0; i < selectedDefunBranch.Grammar.GetMaxSubtreeCount(symb); i++) {
     111          selectedDefunBranch.Grammar.SetAllowedChild(symb, newArgNode.Symbol, i);
     112        }
    103113      foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
    104         if (subtree.DynamicSymbols.Contains(selectedDefunBranch.Name)) {
    105           subtree.SetDynamicSymbolArgumentCount(selectedDefunBranch.Name, selectedDefunBranch.NumberOfArguments);
     114        // 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();
     116        if (matchingSymbol != null) {
     117          subtree.Grammar.SetMinSubtreeCount(matchingSymbol, selectedDefunBranch.NumberOfArguments);
     118          subtree.Grammar.SetMaxSubtreeCount(matchingSymbol, selectedDefunBranch.NumberOfArguments);
    106119        }
    107120      }
    108       Debug.Assert(grammar.IsValidExpression(symbolicExpressionTree));
    109121      return true;
    110122    }
    … …  
    117129        if (argNode != null) {
    118130          // replace argument nodes by a clone of the original subtree that provided the result for the argument node
    119           branch.SubTrees[subtreeIndex] = (SymbolicExpressionTreeNode)argumentTrees[argNode.ArgumentIndex].Clone();
     131          branch.SubTrees[subtreeIndex] = (SymbolicExpressionTreeNode)argumentTrees[argNode.Symbol.ArgumentIndex].Clone();
    120132        } else {
    121133          // recursively replace arguments in all branches
    … …  
    125137    }
    126138
    127     private static IEnumerable<SymbolicExpressionTreeNode> IterateNodesPrefix(SymbolicExpressionTreeNode tree) {
    128       yield return tree;
    129       foreach (var subTree in tree.SubTrees) {
    130         foreach (var node in IterateNodesPrefix(subTree)) {
    131           yield return node;
    132         }
    133       }
    134     }
    135 
    136     private static T SelectRandomBranch<T>(IRandom random, IEnumerable<T> branches) {
    137       var list = branches.ToList();
    138       return list[random.Next(list.Count)];
    139     }
    140 
    141139    private static SymbolicExpressionTreeNode MakeArgumentNode(int argIndex) {
    142       var node = (ArgumentTreeNode)(new Argument()).CreateTreeNode();
    143       node.ArgumentIndex = argIndex;
     140      var node = (ArgumentTreeNode)(new Argument(argIndex)).CreateTreeNode();
    144141      return node;
    145142    }

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

    r3294 r3338  
    6161        // no function defining branch => abort
    6262        return false;
    63       var selectedDefunBranch = (DefunTreeNode)SelectRandomBranch(random, functionDefiningBranches);
     63      var selectedDefunBranch = functionDefiningBranches.SelectRandom(random);
    6464      if (selectedDefunBranch.NumberOfArguments <= 1)
    6565        // argument deletion by consolidation is not possible => abort
    6666        return false;
    67       var cutPoints = (from node in IterateNodesPrefix(selectedDefunBranch)
    68                        where node.SubTrees.Count > 0
    69                        from argNode in node.SubTrees.OfType<ArgumentTreeNode>()
    70                        select new { Parent = node, ReplacedChildIndex = node.SubTrees.IndexOf(argNode), ReplacedChild = argNode }).ToList();
    71       if (cutPoints.Count() == 0)
    72         // no cut points found => abort
    73         return false;
    74       var selectedCutPoint = cutPoints[random.Next(cutPoints.Count)];
    75       var removedArgument = selectedCutPoint.ReplacedChild.ArgumentIndex;
     67      var removedArgument = (from sym in selectedDefunBranch.Grammar.Symbols.OfType<Argument>()
     68                             select sym.ArgumentIndex).Distinct().SelectRandom(random);
     69      // find invocations of the manipulated funcion and remove the specified argument tree
    7670      var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
    77                             where node.InvokedFunctionName == selectedDefunBranch.Name
     71                            where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
    7872                            select node;
    7973      foreach (var invokeNode in invocationNodes) {
    80         invokeNode.RemoveSubTree(selectedCutPoint.ReplacedChild.ArgumentIndex);
     74        invokeNode.RemoveSubTree(removedArgument);
    8175      }
    8276
    8377      DeleteArgumentByConsolidation(random, selectedDefunBranch, removedArgument);
    8478
    85       selectedDefunBranch.RemoveDynamicSymbol("ARG" + removedArgument);
     79      // 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();
     81      selectedDefunBranch.Grammar.RemoveSymbol(matchingSymbol);
    8682      // reduce arity in known functions of all root branches
    8783      foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
    88         if (subtree.DynamicSymbols.Contains(selectedDefunBranch.Name)) {
    89           subtree.SetDynamicSymbolArgumentCount(selectedDefunBranch.Name, selectedDefunBranch.NumberOfArguments - 1);
     84        var matchingInvokeSymbol = subtree.Grammar.Symbols.OfType<InvokeFunction>().Where(s => s.FunctionName == selectedDefunBranch.FunctionName).FirstOrDefault();
     85        if (matchingInvokeSymbol != null) {
     86          subtree.Grammar.SetMinSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments - 1);
     87          subtree.Grammar.SetMaxSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments - 1);
    9088        }
    9189      }
    9290      selectedDefunBranch.NumberOfArguments--;
    93       Debug.Assert(grammar.IsValidExpression(symbolicExpressionTree));
    9491      return true;
    9592    }
    … …  
    9794    private static void DeleteArgumentByConsolidation(IRandom random, DefunTreeNode branch, int removedArgumentIndex) {
    9895      // replace references to the deleted argument with random references to existing arguments
    99       var possibleArgumentIndexes = (from node in IterateNodesPrefix(branch).OfType<ArgumentTreeNode>()
    100                                      where node.ArgumentIndex != removedArgumentIndex
    101                                      select node.ArgumentIndex).Distinct().ToList();
    102       var argNodes = from node in IterateNodesPrefix(branch).OfType<ArgumentTreeNode>()
    103                      where node.ArgumentIndex == removedArgumentIndex
     96      var possibleArgumentSymbols = (from sym in branch.Grammar.Symbols.OfType<Argument>()
     97                                     where sym.ArgumentIndex != removedArgumentIndex
     98                                     select sym).ToList();
     99      var argNodes = from node in branch.IterateNodesPrefix().OfType<ArgumentTreeNode>()
     100                     where node.Symbol.ArgumentIndex == removedArgumentIndex
    104101                     select node;
    105102      foreach (var argNode in argNodes) {
    106         var replacementArgument = possibleArgumentIndexes[random.Next(possibleArgumentIndexes.Count)];
    107         argNode.ArgumentIndex = replacementArgument;
     103        var replacementSymbol = possibleArgumentSymbols.SelectRandom(random);
     104        argNode.Symbol = replacementSymbol;
    108105      }
    109     }
    110     private static IEnumerable<SymbolicExpressionTreeNode> IterateNodesPrefix(SymbolicExpressionTreeNode tree) {
    111       yield return tree;
    112       foreach (var subTree in tree.SubTrees) {
    113         foreach (var node in IterateNodesPrefix(subTree)) {
    114           yield return node;
    115         }
    116       }
    117     }
    118 
    119     private static SymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<DefunTreeNode> branches) {
    120       var list = branches.ToList();
    121       return list[random.Next(list.Count)];
    122106    }
    123107  }

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

    r3294 r3338  
    106106      return true;
    107107    }
    108 
    109     private static IEnumerable<SymbolicExpressionTreeNode> IterateNodesPrefix(SymbolicExpressionTreeNode tree) {
    110       yield return tree;
    111       foreach (var subTree in tree.SubTrees) {
    112         foreach (var node in IterateNodesPrefix(subTree)) {
    113           yield return node;
    114         }
    115       }
    116     }
    117 
    118     private static T SelectRandomBranch<T>(IRandom random, IEnumerable<T> branches) {
    119       var list = branches.ToList();
    120       return list[random.Next(list.Count)];
    121     }
    122108  }
    123109}

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

    r3297 r3338  
    8282      if (selectedBody == null) throw new InvalidOperationException();
    8383      // select a random node in the selected branch
    84       var allCutPoints = (from parent in IterateNodesPrefix(selectedBody)
     84      var allCutPoints = (from parent in selectedBody.IterateNodesPrefix()
    8585                          from subtree in parent.SubTrees
    8686                          select new { Parent = parent, ReplacedBranchIndex = parent.SubTrees.IndexOf(subtree), ReplacedBranch = subtree }).ToList();
    … …  
    160160      return argumentBranches;
    161161    }
    162 
    163     private static IEnumerable<SymbolicExpressionTreeNode> IterateNodesPrefix(SymbolicExpressionTreeNode tree) {
    164       yield return tree;
    165       foreach (var subTree in tree.SubTrees) {
    166         foreach (var node in IterateNodesPrefix(subTree)) {
    167           yield return node;
    168         }
    169       }
    170     }
    171 
     162   
    172163    private static IEnumerable<string> UsedFunctionNames(SymbolicExpressionTree symbolicExpressionTree) {
    173164      return from node in symbolicExpressionTree.IterateNodesPrefix()
    … …  
    175166             select ((DefunTreeNode)node).Name;
    176167    }
    177 
    178     private static SymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<DefunTreeNode> branches) {
    179       var list = branches.ToList();
    180       return list[random.Next(list.Count)];
    181     }
    182168  }
    183169}

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

    r3294 r3338  
    6363        // no ADF to delete => abort
    6464        return false;
    65       var selectedDefunBranch = (DefunTreeNode)SelectRandomBranch(random, functionDefiningBranches);
     65      var selectedDefunBranch = functionDefiningBranches.SelectRandom(random);
    6666      // remove the selected defun
    6767      int defunSubtreeIndex = symbolicExpressionTree.Root.SubTrees.IndexOf(selectedDefunBranch);
    … …  
    104104      return true;
    105105    }
    106 
    107     private static SymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<DefunTreeNode> branches) {
    108       var list = branches.ToList();
    109       return list[random.Next(list.Count)];
    110     }
    111106  }
    112107}

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

    r3294 r3338  
    6565        // no function defining branches to duplicate or already reached the max number of ADFs
    6666        return false;
    67       var selectedBranch = (DefunTreeNode)SelectRandomBranch(random, functionDefiningBranches);
     67      var selectedBranch = functionDefiningBranches.SelectRandom(random);
    6868      var clonedBranch = (DefunTreeNode)selectedBranch.Clone();
    6969      clonedBranch.Name = allowedFunctionNames.Except(UsedFunctionNames(symbolicExpressionTree)).First();
    … …  
    7373        if (invokeFunctionNode != null && invokeFunctionNode.InvokedFunctionName == selectedBranch.Name) {
    7474          // add the new function name to the list of known functions in the branches that used the originating function
    75           var branch = FindDefiningBranch(symbolicExpressionTree, invokeFunctionNode);
     75          var branch = symbolicExpressionTree.GetTopLevelBranchOf(invokeFunctionNode);
    7676          branch.AddDynamicSymbol(clonedBranch.Name, clonedBranch.NumberOfArguments);
    7777          // flip coin wether to replace with newly defined function
    … …  
    8383      Debug.Assert(grammar.IsValidExpression(symbolicExpressionTree));
    8484      return true;
    85     }
    86 
    87     private static SymbolicExpressionTreeNode FindDefiningBranch(SymbolicExpressionTree tree, SymbolicExpressionTreeNode node) {
    88       foreach (var subtree in tree.Root.SubTrees) {
    89         if (ContainsNode(subtree, node)) return subtree;
    90       }
    91       return null;
    9285    }
    9386
    … …  
    10699    }
    107100
    108     private static SymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<DefunTreeNode> branches) {
    109       var list = branches.ToList();
    110       return list[random.Next(list.Count)];
    111     }
     101
    112102  }
    113103}

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

    r3297 r3338  
    2727using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2828using System.Collections.Generic;
     29using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols;
     30using System.Text;
    2931
    3032namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    … …  
    3234  [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed size")]
    3335  public class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator {
     36
    3437    public ProbabilisticTreeCreator()
    3538      : base() {
    3639    }
    3740
    38     protected override SymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight) {
    39       return Create(random, grammar, maxTreeSize.Value, maxTreeHeight.Value);
    40     }
    41 
    42     public static SymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar, int maxTreeSize, int maxTreeHeight) {
     41    protected override SymbolicExpressionTree Create(
     42      IRandom random,
     43      ISymbolicExpressionGrammar grammar,
     44      IntValue maxTreeSize, IntValue maxTreeHeight,
     45      IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
     46      return Create(random, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
     47    }
     48
     49    public static SymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar,
     50      int maxTreeSize, int maxTreeHeight,
     51      int maxFunctionDefinitions, int maxFunctionArguments
     52      ) {
    4353      // tree size is limited by the grammar and by the explicit size constraints
    4454      int allowedMinSize = grammar.GetMinExpressionLength(grammar.StartSymbol);
    … …  
    4959      do {
    5060        try {
    51           tree.Root = grammar.ProgramRootSymbol.CreateTreeNode();
    52           tree.Root.AddSubTree(PTC2(random, grammar, grammar.StartSymbol, treeSize + 1, maxTreeHeight + 1));
     61          tree.Root = PTC2(random, grammar, grammar.StartSymbol, treeSize + 1, maxTreeHeight + 1, maxFunctionDefinitions, maxFunctionArguments);
    5362        }
    5463        catch (ArgumentException) {
    … …  
    5665          treeSize = random.Next(allowedMinSize, allowedMaxSize);
    5766        }
    58       } while (tree.Root.SubTrees.Count == 0 || tree.Size > maxTreeSize || tree.Height > maxTreeHeight);
     67      } while (tree.Root == null || tree.Size > maxTreeSize || tree.Height > maxTreeHeight);
    5968      return tree;
     69    }
     70
     71    private class TreeExtensionPoint {
     72      public SymbolicExpressionTreeNode Parent { get; set; }
     73      public int ChildIndex { get; set; }
     74      public int ExtensionPointDepth { get; set; }
     75    }
     76    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);
     82      return root;
     83    }
     84
     85    private static void CreateFullTreeFromSeed(IRandom random, SymbolicExpressionTreeNode root, int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
     86      List<TreeExtensionPoint> extensionPoints = new List<TreeExtensionPoint>();
     87      int currentSize = 1;
     88      int totalListMinSize = root.Grammar.GetMinExpressionLength(root.Symbol) - 1;
     89      int actualArity = SampleArity(random, root, size);
     90      for (int i = 0; i < actualArity; i++) {
     91        // insert a dummy sub-tree and add the pending extension to the list
     92        var dummy = new SymbolicExpressionTreeNode();
     93        root.AddSubTree(dummy);
     94        dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone();
     95        extensionPoints.Add(new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 2 });
     96      }
     97      // while there are pending extension points and we have not reached the limit of adding new extension points
     98      while (extensionPoints.Count > 0 && totalListMinSize + currentSize < size) {
     99        int randomIndex = random.Next(extensionPoints.Count);
     100        TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
     101        extensionPoints.RemoveAt(randomIndex);
     102        SymbolicExpressionTreeNode parent = nextExtension.Parent;
     103        int argumentIndex = nextExtension.ChildIndex;
     104        int extensionDepth = nextExtension.ExtensionPointDepth;
     105        if (extensionDepth + parent.Grammar.GetMinExpressionDepth(parent.Symbol) >= maxDepth) {
     106          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();
     115        } else {
     116          var allowedSymbols = from s in parent.Grammar.Symbols
     117                               where parent.Grammar.IsAllowedChild(parent.Symbol, s, argumentIndex)
     118                               where parent.Grammar.GetMinExpressionDepth(s) + extensionDepth - 1 < maxDepth
     119                               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)
     124                               select s;
     125          Symbol selectedSymbol = SelectRandomSymbol(random, allowedSymbols);
     126          SymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();
     127          parent.RemoveSubTree(argumentIndex);
     128          parent.InsertSubTree(argumentIndex, newTree);
     129
     130          InitializeNewTreeNode(random, root, newTree, maxFunctionDefinitions, maxFunctionArguments);
     131
     132          currentSize++;
     133          totalListMinSize--;
     134
     135          actualArity = SampleArity(random, newTree, size - currentSize);
     136          for (int i = 0; i < actualArity; i++) {
     137            // insert a dummy sub-tree and add the pending extension to the list
     138            var dummy = new SymbolicExpressionTreeNode();
     139            newTree.AddSubTree(dummy);
     140            if (IsTopLevelBranch(root, dummy))
     141              dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone();
     142            extensionPoints.Add(new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 });
     143          }
     144          totalListMinSize += newTree.Grammar.GetMinExpressionLength(newTree.Symbol);
     145        }
     146      }
     147      // fill all pending extension points
     148      while (extensionPoints.Count > 0) {
     149        int randomIndex = random.Next(extensionPoints.Count);
     150        TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
     151        extensionPoints.RemoveAt(randomIndex);
     152        SymbolicExpressionTreeNode parent = nextExtension.Parent;
     153        int a = nextExtension.ChildIndex;
     154        int d = nextExtension.ExtensionPointDepth;
     155        ReplaceWithMinimalTree(random, root, parent, a, maxFunctionDefinitions, maxFunctionArguments);
     156      }
     157    }
     158
     159    private static void ReplaceWithMinimalTree(IRandom random, SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode parent, int argumentIndex, int maxFunctionDefinitions, int maxFunctionArguments) {
     160      // determine possible symbols that will lead to the smallest possible tree
     161      var possibleSymbols = (from s in parent.GetAllowedSymbols(argumentIndex)
     162                             group s by parent.Grammar.GetMinExpressionLength(s) into g
     163                             orderby g.Key
     164                             select g).First();
     165      var selectedSymbol = SelectRandomSymbol(random, possibleSymbols);
     166      var tree = selectedSymbol.CreateTreeNode();
     167      parent.RemoveSubTree(argumentIndex);
     168      parent.InsertSubTree(argumentIndex, tree);
     169      InitializeNewTreeNode(random, root, tree, maxFunctionDefinitions, maxFunctionArguments);
     170      for (int i = 0; i < tree.GetMinSubtreeCount(); i++) {
     171        // insert a dummy sub-tree and add the pending extension to the list
     172        var dummy = new SymbolicExpressionTreeNode();
     173        tree.AddSubTree(dummy);
     174        dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone();
     175        // replace the just inserted dummy by recursive application
     176        ReplaceWithMinimalTree(random, root, tree, i, maxFunctionDefinitions, maxFunctionArguments);
     177      }
     178    }
     179   
     180    private static void InitializeNewTreeNode(IRandom random, SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode newTree, int maxFunctionDefinitions, int maxFunctionArguments) {
     181      // NB it is assumed that defuns are only allowed as children of root and nowhere else
     182      // also assumes that newTree is already attached to root somewhere
     183      if (IsTopLevelBranch(root, newTree))
     184        newTree.Grammar = (ISymbolicExpressionGrammar)newTree.Grammar.Clone();
     185      if (newTree.Symbol is Defun) {
     186        var defunTree = newTree as DefunTreeNode;
     187        string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefinitions * 10 - 1)).ToString(); // >= 100 functions => ###
     188        var allowedNames = from index in Enumerable.Range(0, maxFunctionDefinitions)
     189                           select "ADF" + index.ToString(formatString);
     190        var takenNames = (from node in root.IterateNodesPrefix().OfType<DefunTreeNode>()
     191                          select node.FunctionName).Distinct();
     192        var remainingNames = allowedNames.Except(takenNames).ToList();
     193        string functionName = remainingNames[random.Next(remainingNames.Count)];
     194        // set name and number of arguments of the ADF
     195        int nArgs = random.Next(maxFunctionArguments);
     196        defunTree.FunctionName = functionName;
     197        defunTree.NumberOfArguments = nArgs;
     198        if (nArgs > 0) {
     199          AddDynamicArguments(defunTree.Grammar, nArgs);
     200        }
     201        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)
     214        for (int i = 0; i < argIndex; i++) {
     215          // if not dummy node
     216          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);
     224          }
     225        }
     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          }
     257      }
     258    }
     259
     260    private static bool IsTopLevelBranch(SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode branch) {
     261      return root.SubTrees.IndexOf(branch) > -1;
    60262    }
    61263
    … …  
    75277    }
    76278
    77 
    78     public static SymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionGrammar grammar, Symbol rootSymbol, int size, int maxDepth) {
    79       SymbolicExpressionTreeNode root = rootSymbol.CreateTreeNode();
    80       if (size <= 1 || maxDepth <= 1) return root;
    81       List<object[]> extensionPoints = new List<object[]>();
    82       int currentSize = 1;
    83       int totalListMinSize = grammar.GetMinExpressionLength(rootSymbol) - 1;
    84 
    85       int actualArity = SampleArity(random, grammar, rootSymbol, size);
    86       for (int i = 0; i < actualArity; i++) {
    87         // insert a dummy sub-tree and add the pending extension to the list
    88         root.AddSubTree(null);
    89         extensionPoints.Add(new object[] { root, i, 2 });
    90       }
    91 
    92       // while there are pending extension points and we have not reached the limit of adding new extension points
    93       while (extensionPoints.Count > 0 && totalListMinSize + currentSize < size) {
    94         int randomIndex = random.Next(extensionPoints.Count);
    95         object[] nextExtension = extensionPoints[randomIndex];
    96         extensionPoints.RemoveAt(randomIndex);
    97         SymbolicExpressionTreeNode parent = (SymbolicExpressionTreeNode)nextExtension[0];
    98         int argumentIndex = (int)nextExtension[1];
    99         int extensionDepth = (int)nextExtension[2];
    100         if (extensionDepth + grammar.GetMinExpressionDepth(parent.Symbol) >= maxDepth) {
    101           parent.RemoveSubTree(argumentIndex);
    102           SymbolicExpressionTreeNode branch = CreateMinimalTree(random, grammar, grammar.GetAllowedSymbols(parent.Symbol, argumentIndex));
    103           parent.InsertSubTree(argumentIndex, branch); // insert a smallest possible tree
    104           currentSize += branch.GetSize();
    105           totalListMinSize -= branch.GetSize();
    106         } else {
    107           var allowedSubFunctions = from s in grammar.GetAllowedSymbols(parent.Symbol, argumentIndex)
    108                                     where grammar.GetMinExpressionDepth(parent.Symbol) + extensionDepth - 1 < maxDepth
    109                                     where grammar.GetMaxExpressionLength(s) > size - totalListMinSize - currentSize ||
    110                                           totalListMinSize + currentSize >= size * 0.9 // if the necessary size is almost reached then also allow
    111                                     // terminals or terminal-branches
    112                                     select s;
    113           Symbol selectedSymbol = SelectRandomSymbol(random, allowedSubFunctions);
    114           SymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();
    115           parent.RemoveSubTree(argumentIndex);
    116           parent.InsertSubTree(argumentIndex, newTree);
    117           currentSize++;
    118           totalListMinSize--;
    119 
    120           actualArity = SampleArity(random, grammar, selectedSymbol, size - currentSize);
    121           for (int i = 0; i < actualArity; i++) {
    122             // insert a dummy sub-tree and add the pending extension to the list
    123             newTree.AddSubTree(null);
    124             extensionPoints.Add(new object[] { newTree, i, extensionDepth + 1 });
    125           }
    126           totalListMinSize += grammar.GetMinExpressionLength(selectedSymbol);
    127         }
    128       }
    129       // fill all pending extension points
    130       while (extensionPoints.Count > 0) {
    131         int randomIndex = random.Next(extensionPoints.Count);
    132         object[] nextExtension = extensionPoints[randomIndex];
    133         extensionPoints.RemoveAt(randomIndex);
    134         SymbolicExpressionTreeNode parent = (SymbolicExpressionTreeNode)nextExtension[0];
    135         int a = (int)nextExtension[1];
    136         int d = (int)nextExtension[2];
    137         parent.RemoveSubTree(a);
    138         parent.InsertSubTree(a,
    139           CreateMinimalTree(random, grammar, grammar.GetAllowedSymbols(parent.Symbol, a))); // append a tree with minimal possible height
    140       }
    141       return root;
    142     }
    143 
    144     private static int SampleArity(IRandom random, ISymbolicExpressionGrammar grammar, Symbol symbol, int targetSize) {
     279    private static int SampleArity(IRandom random, SymbolicExpressionTreeNode node, int targetSize) {
    145280      // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
    146       int minArity = grammar.GetMinSubTreeCount(symbol);
    147       int maxArity = grammar.GetMaxSubTreeCount(symbol);
     281      int minArity = node.GetMinSubtreeCount();
     282      int maxArity = node.GetMaxSubtreeCount();
    148283      if (maxArity > targetSize) {
    149284        maxArity = targetSize;
    … …  
    153288      long aggregatedLongestExpressionLength = 0;
    154289      for (int i = 0; i < maxArity; i++) {
    155         aggregatedLongestExpressionLength += (from s in grammar.GetAllowedSymbols(symbol, i)
    156                                               select grammar.GetMaxExpressionLength(s)).Max();
     290        aggregatedLongestExpressionLength += (from s in node.GetAllowedSymbols(i)
     291                                              select node.Grammar.GetMaxExpressionLength(s)).Max();
    157292        if (aggregatedLongestExpressionLength < targetSize) minArity = i;
    158293        else break;
    … …  
    163298      long aggregatedShortestExpressionLength = 0;
    164299      for (int i = 0; i < maxArity; i++) {
    165         aggregatedShortestExpressionLength += (from s in grammar.GetAllowedSymbols(symbol, i)
    166                                                select grammar.GetMinExpressionLength(s)).Min();
     300        aggregatedShortestExpressionLength += (from s in node.GetAllowedSymbols(i)
     301                                               select node.Grammar.GetMinExpressionLength(s)).Min();
    167302        if (aggregatedShortestExpressionLength > targetSize) {
    168303          maxArity = i;
    … …  
    173308      return random.Next(minArity, maxArity + 1);
    174309    }
    175 
    176     private static SymbolicExpressionTreeNode CreateMinimalTree(IRandom random, ISymbolicExpressionGrammar grammar, IEnumerable<Symbol> symbols) {
    177       // determine possible symbols that will lead to the smallest possible tree
    178       var possibleSymbols = (from s in symbols
    179                              group s by grammar.GetMinExpressionLength(s) into g
    180                              orderby g.Key
    181                              select g).First();
    182       var selectedSymbol = SelectRandomSymbol(random, possibleSymbols);
    183       // build minimal tree by recursive application
    184       var tree = selectedSymbol.CreateTreeNode();
    185       for (int i = 0; i < grammar.GetMinSubTreeCount(selectedSymbol); i++)
    186         tree.AddSubTree(CreateMinimalTree(random, grammar, grammar.GetAllowedSymbols(selectedSymbol, i)));
    187       return tree;
    188     }
    189310  }
    190311}

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Crossovers/SubtreeCrossover.cs

    r3297 r3338  
    4949    }
    5050
    51     protected override SymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionGrammar grammar,
     51    protected override SymbolicExpressionTree Cross(IRandom random,
    5252      SymbolicExpressionTree parent0, SymbolicExpressionTree parent1,
    5353      IntValue maxTreeSize, IntValue maxTreeHeight, out bool success) {
    54       return Cross(random, grammar, parent0, parent1, InternalCrossoverPointProbabilityParameter.ActualValue.Value, maxTreeSize.Value, maxTreeHeight.Value, out success);
     54      return Cross(random, parent0, parent1, InternalCrossoverPointProbabilityParameter.ActualValue.Value, maxTreeSize.Value, maxTreeHeight.Value, out success);
    5555    }
    5656
    57     public static SymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionGrammar grammar,
     57    public static SymbolicExpressionTree Cross(IRandom random,
    5858      SymbolicExpressionTree parent0, SymbolicExpressionTree parent1,
    5959      double internalCrossoverPointProbability, int maxTreeSize, int maxTreeHeight, out bool success) {
    … …  
    6767      int maxInsertedBranchHeight = maxTreeHeight - GetBranchLevel(parent0.Root, crossoverPoint0);
    6868
    69       var allowedBranches = from branch in IterateNodes(parent1.Root)
     69      var allowedBranches = from branch in parent1.Root.IterateNodesPrefix()
    7070                            where branch.GetSize() < maxInsertedBranchSize
    7171                            where branch.GetHeight() < maxInsertedBranchHeight
    72                             where grammar.GetAllowedSymbols(crossoverPoint0.Symbol, replacedSubtreeIndex).Contains(branch.Symbol)
    73                             where IsMatchingPointType(parent0, crossoverPoint0, branch)
     72                            // where crossoverPoint0.GetAllowedSymbols(replacedSubtreeIndex).Contains(branch.Symbol)
     73                            where IsMatchingPointType(crossoverPoint0, replacedSubtreeIndex, branch)
    7474                            select branch;
    7575
    … …  
    8989    }
    9090
    91     private static bool IsMatchingPointType(SymbolicExpressionTree tree, SymbolicExpressionTreeNode parent, SymbolicExpressionTreeNode newBranch) {
    92       var functionCalls = (from node in IterateNodes(newBranch)
    93                            let invokeNode = node as InvokeFunctionTreeNode
    94                            let argNode = node as ArgumentTreeNode
    95                            where invokeNode != null || argNode != null
    96                            let name = invokeNode != null ? invokeNode.InvokedFunctionName : "ARG" + argNode.ArgumentIndex
    97                            let argCount = invokeNode != null ? invokeNode.SubTrees.Count : 0
    98                            select new { FunctionName = name, FunctionArgumentCount = argCount }).Distinct();
    99       var definingBranch = GetDefiningBranch(tree, parent);
    100       if (definingBranch == null) return false;
    101       foreach (var functionCall in functionCalls) {
    102         if (!definingBranch.DynamicSymbols.Contains(functionCall.FunctionName) ||
    103           definingBranch.GetDynamicSymbolArgumentCount(functionCall.FunctionName) != functionCall.FunctionArgumentCount)
    104           return false;
     91    private static bool IsMatchingPointType(SymbolicExpressionTreeNode parent, int replacedSubtreeIndex, SymbolicExpressionTreeNode branch) {
     92      // cannot compare dynamic symbols by reference because new instances of Invoke/Argument are created on demand
     93      // instead we must check equality by names and number of arguments
     94      var branchSymbols = (from node in branch.IterateNodesPrefix()
     95                           select new { FunctionName = node.Symbol.Name, SubtreeCount = node.SubTrees.Count }).Distinct();
     96
     97      // check syntax constraints of direct parent - child relation
     98      var matchingSymbolInParentGrammar = (from sym in parent.GetAllowedSymbols(replacedSubtreeIndex)
     99                                           where sym.Name == branch.Symbol.Name
     100                                           select sym).SingleOrDefault();
     101      if (matchingSymbolInParentGrammar == null ||
     102        branch.SubTrees.Count < parent.Grammar.GetMinSubtreeCount(matchingSymbolInParentGrammar) ||
     103        branch.SubTrees.Count > parent.Grammar.GetMaxSubtreeCount(matchingSymbolInParentGrammar)) return false;
     104
     105      // check point type for the whole branch
     106      foreach (var branchSymbol in branchSymbols) {
     107        matchingSymbolInParentGrammar = (from sym in parent.Grammar.Symbols
     108                                         where sym.Name == branchSymbol.FunctionName
     109                                         select sym).SingleOrDefault();
     110        if (matchingSymbolInParentGrammar == null ||
     111          branchSymbol.SubtreeCount < parent.Grammar.GetMinSubtreeCount(matchingSymbolInParentGrammar) ||
     112          branchSymbol.SubtreeCount > parent.Grammar.GetMaxSubtreeCount(matchingSymbolInParentGrammar)) return false;
    105113      }
     114
    106115      return true;
    107116    }
    108117
    109     private static SymbolicExpressionTreeNode GetDefiningBranch(SymbolicExpressionTree tree, SymbolicExpressionTreeNode parent) {
    110       foreach (var treeNode in tree.Root.SubTrees) {
    111         if (IterateNodes(treeNode).Contains(parent)) return treeNode;
    112       }
    113       return null;
    114     }
    115 
    116118    private static void SelectCrossoverPoint(IRandom random, SymbolicExpressionTree parent0, double internalNodeProbability, out SymbolicExpressionTreeNode crossoverPoint, out int subtreeIndex) {
    117       var crossoverPoints = from branch in IterateNodes(parent0.Root)
     119      var crossoverPoints = from branch in parent0.Root.IterateNodesPrefix()
    118120                            where branch.SubTrees.Count > 0
    119                             where !(branch.Symbol is ProgramRootSymbol)
     121                            where branch != parent0.Root
    120122                            from index in Enumerable.Range(0, branch.SubTrees.Count)
    121123                            let p = new { CrossoverPoint = branch, SubtreeIndex = index, IsLeaf = branch.SubTrees[index].SubTrees.Count == 0 }
    … …  
    172174    }
    173175
    174     private static IEnumerable<SymbolicExpressionTreeNode> IterateNodes(SymbolicExpressionTreeNode root) {
    175       foreach (var subTree in root.SubTrees) {
    176         foreach (var branch in IterateNodes(subTree)) {
    177           yield return branch;
    178         }
    179       }
    180       yield return root;
    181     }
    182 
    183176    private static int GetBranchLevel(SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode point) {
    184177      if (root == point) return 0;

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

    r3294 r3338  
    3434  public class DefaultSymbolicExpressionGrammar : Item, ISymbolicExpressionGrammar {
    3535    [Storable]
    36     private int minFunctionDefinitions;
    37     [Storable]
    38     private int maxFunctionDefinitions;
    39     [Storable]
    40     private int minFunctionArguments;
    41     [Storable]
    42     private int maxFunctionArguments;
    43 
    44     [Storable]
    4536    private Dictionary<string, int> minSubTreeCount;
    4637    [Storable]
    4738    private Dictionary<string, int> maxSubTreeCount;
    4839    [Storable]
    49     private Dictionary<string, List<HashSet<string>>> allowedFunctions;
     40    private Dictionary<string, List<HashSet<string>>> allowedChildSymbols;
    5041    [Storable]
    5142    private HashSet<Symbol> allSymbols;
    5243
    53     public DefaultSymbolicExpressionGrammar(int minFunctionDefinitions, int maxFunctionDefinitions, int minFunctionArguments, int maxFunctionArguments)
     44    public DefaultSymbolicExpressionGrammar()
    5445      : base() {
    55       this.minFunctionDefinitions = minFunctionDefinitions;
    56       this.maxFunctionDefinitions = maxFunctionDefinitions;
    57       this.minFunctionArguments = minFunctionArguments;
    58       this.maxFunctionArguments = maxFunctionArguments;
     46      Reset();
     47    }
     48
     49    private void Initialize() {
     50      startSymbol = new StartSymbol();
     51      AddSymbol(startSymbol);
     52      SetMinSubtreeCount(startSymbol, 1);
     53      SetMaxSubtreeCount(startSymbol, 1);
     54    }
     55
     56    #region ISymbolicExpressionGrammar Members
     57
     58    private Symbol startSymbol;
     59    public Symbol StartSymbol {
     60      get { return startSymbol; }
     61      set { startSymbol = value; }
     62    }
     63
     64    protected void Reset() {
    5965      minSubTreeCount = new Dictionary<string, int>();
    6066      maxSubTreeCount = new Dictionary<string, int>();
    61       allowedFunctions = new Dictionary<string, List<HashSet<string>>>();
     67      allowedChildSymbols = new Dictionary<string, List<HashSet<string>>>();
    6268      allSymbols = new HashSet<Symbol>();
    63       cachedMinExpressionLength = new Dictionary<Symbol, int>();
    64       cachedMaxExpressionLength = new Dictionary<Symbol, int>();
    65       cachedMinExpressionDepth = new Dictionary<Symbol, int>();
     69      cachedMinExpressionLength = new Dictionary<string, int>();
     70      cachedMaxExpressionLength = new Dictionary<string, int>();
     71      cachedMinExpressionDepth = new Dictionary<string, int>();
    6672      Initialize();
    6773    }
    6874
    69     private void Initialize() {
    70       programRootSymbol = new ProgramRootSymbol();
    71       var defunSymbol = new Defun();
    72       startSymbol = new StartSymbol();
    73       var invokeFunctionSymbol = new InvokeFunction();
    74 
    75       SetMinSubTreeCount(programRootSymbol, minFunctionDefinitions + 1);
    76       SetMaxSubTreeCount(programRootSymbol, maxFunctionDefinitions + 1);
    77       SetMinSubTreeCount(startSymbol, 1);
    78       SetMaxSubTreeCount(startSymbol, 1);
    79       SetMinSubTreeCount(defunSymbol, 1);
    80       SetMaxSubTreeCount(defunSymbol, 1);
    81       SetMinSubTreeCount(invokeFunctionSymbol, minFunctionArguments);
    82       SetMaxSubTreeCount(invokeFunctionSymbol, maxFunctionArguments);
    83       AddAllowedSymbols(programRootSymbol, 0, startSymbol);
    84       for (int argumentIndex = 1; argumentIndex < maxFunctionDefinitions + 1; argumentIndex++) {
    85         AddAllowedSymbols(programRootSymbol, argumentIndex, defunSymbol);
    86       }
    87     }
    88 
    89     public void AddAllowedSymbols(Symbol parent, int argumentIndex, Symbol allowedChild) {
    90       allSymbols.Add(parent); allSymbols.Add(allowedChild);
    91       if (!allowedFunctions.ContainsKey(parent.Name)) {
    92         allowedFunctions[parent.Name] = new List<HashSet<string>>();
    93       }
    94       while (allowedFunctions[parent.Name].Count <= argumentIndex)
    95         allowedFunctions[parent.Name].Add(new HashSet<string>());
    96       allowedFunctions[parent.Name][argumentIndex].Add(allowedChild.Name);
    97       ClearCaches();
    98     }
    99 
    100     public void SetMaxSubTreeCount(Symbol parent, int nSubTrees) {
    101       maxSubTreeCount[parent.Name] = nSubTrees;
    102       ClearCaches();
    103     }
    104 
    105     public void SetMinSubTreeCount(Symbol parent, int nSubTrees) {
    106       minSubTreeCount[parent.Name] = nSubTrees;
    107       ClearCaches();
    108     }
     75    public void AddSymbol(Symbol symbol) {
     76      if (allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Symbol " + symbol + " is already defined.");
     77      allSymbols.Add(symbol);
     78      allowedChildSymbols[symbol.Name] = new List<HashSet<string>>();
     79      ClearCaches();
     80    }
     81
     82    public void RemoveSymbol(Symbol symbol) {
     83      allSymbols.RemoveWhere(s => s.Name == symbol.Name);
     84      minSubTreeCount.Remove(symbol.Name);
     85      maxSubTreeCount.Remove(symbol.Name);
     86      allowedChildSymbols.Remove(symbol.Name);
     87      ClearCaches();
     88    }
     89
     90    public IEnumerable<Symbol> Symbols {
     91      get { return allSymbols.AsEnumerable(); }
     92    }
     93
     94    public void SetAllowedChild(Symbol parent, Symbol child, int argumentIndex) {
     95      if (!allSymbols.Any(s => s.Name == parent.Name)) throw new ArgumentException("Unknown symbol: " + parent, "parent");
     96      if (!allSymbols.Any(s => s.Name == child.Name)) throw new ArgumentException("Unknown symbol: " + child, "child");
     97      if (argumentIndex >= GetMaxSubtreeCount(parent)) throw new ArgumentException("Symbol " + parent + " can have only " + GetMaxSubtreeCount(parent) + " subtrees.");
     98      allowedChildSymbols[parent.Name][argumentIndex].Add(child.Name);
     99      ClearCaches();
     100    }
     101
     102    public bool IsAllowedChild(Symbol parent, Symbol child, int argumentIndex) {
     103      if (!allSymbols.Any(s => s.Name == parent.Name)) throw new ArgumentException("Unknown symbol: " + parent, "parent");
     104      if (!allSymbols.Any(s => s.Name == child.Name)) throw new ArgumentException("Unknown symbol: " + child, "child");
     105      if (argumentIndex >= GetMaxSubtreeCount(parent)) throw new ArgumentException("Symbol " + parent + " can have only " + GetMaxSubtreeCount(parent) + " subtrees.");
     106      if (allowedChildSymbols.ContainsKey(parent.Name)) return allowedChildSymbols[parent.Name][argumentIndex].Contains(child.Name);
     107      return false;
     108    }
     109
     110    private Dictionary<string, int> cachedMinExpressionLength;
     111    public int GetMinExpressionLength(Symbol symbol) {
     112      if (!allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);
     113      if (!cachedMinExpressionLength.ContainsKey(symbol.Name)) {
     114        cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
     115        long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinSubtreeCount(symbol))
     116                                              let minForSlot = (long)(from s in allSymbols
     117                                                                      where IsAllowedChild(symbol, s, argIndex)
     118                                                                      select GetMinExpressionLength(s)).DefaultIfEmpty(0).Min()
     119                                              select minForSlot).DefaultIfEmpty(0).Sum();
     120
     121        cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
     122      }
     123      return cachedMinExpressionLength[symbol.Name];
     124    }
     125
     126    private Dictionary<string, int> cachedMaxExpressionLength;
     127    public int GetMaxExpressionLength(Symbol symbol) {
     128      if (!allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);
     129      if (!cachedMaxExpressionLength.ContainsKey(symbol.Name)) {
     130        cachedMaxExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
     131        long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaxSubtreeCount(symbol))
     132                                  let maxForSlot = (long)(from s in allSymbols
     133                                                          where IsAllowedChild(symbol, s, argIndex)
     134                                                          select GetMaxExpressionLength(s)).DefaultIfEmpty(0).Max()
     135                                  select maxForSlot).DefaultIfEmpty(0).Sum();
     136        long limit = int.MaxValue;
     137        cachedMaxExpressionLength[symbol.Name] = (int)Math.Min(sumOfMaxTrees, limit);
     138      }
     139      return cachedMaxExpressionLength[symbol.Name];
     140    }
     141
     142    private Dictionary<string, int> cachedMinExpressionDepth;
     143    public int GetMinExpressionDepth(Symbol symbol) {
     144      if (!allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);
     145      if (!cachedMinExpressionDepth.ContainsKey(symbol.Name)) {
     146        cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
     147        cachedMinExpressionDepth[symbol.Name] = 1 + (from argIndex in Enumerable.Range(0, GetMinSubtreeCount(symbol))
     148                                                     let minForSlot = (from s in allSymbols
     149                                                                       where IsAllowedChild(symbol, s, argIndex)
     150                                                                       select GetMinExpressionDepth(s)).DefaultIfEmpty(0).Min()
     151                                                     select minForSlot).DefaultIfEmpty(0).Max();
     152      }
     153      return cachedMinExpressionDepth[symbol.Name];
     154    }
     155
     156    public void SetMaxSubtreeCount(Symbol symbol, int nSubTrees) {
     157      if (!allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);
     158      maxSubTreeCount[symbol.Name] = nSubTrees;
     159      while (allowedChildSymbols[symbol.Name].Count <= nSubTrees)
     160        allowedChildSymbols[symbol.Name].Add(new HashSet<string>());
     161      while (allowedChildSymbols[symbol.Name].Count > nSubTrees) {
     162        allowedChildSymbols[symbol.Name].RemoveAt(allowedChildSymbols[symbol.Name].Count - 1);
     163      }
     164      ClearCaches();
     165    }
     166
     167    public void SetMinSubtreeCount(Symbol symbol, int nSubTrees) {
     168      if (!allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);
     169      minSubTreeCount[symbol.Name] = nSubTrees;
     170      ClearCaches();
     171    }
     172
     173    public int GetMinSubtreeCount(Symbol symbol) {
     174      if (!allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);
     175      return minSubTreeCount[symbol.Name];
     176    }
     177
     178    public int GetMaxSubtreeCount(Symbol symbol) {
     179      if (!allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);
     180      return maxSubTreeCount[symbol.Name];
     181    }
     182
     183    #endregion
    109184
    110185    private void ClearCaches() {
    … …  
    114189    }
    115190
    116     private void symbol_ToStringChanged(object sender, EventArgs e) {
    117       OnToStringChanged();
    118     }
    119 
    120     #region ISymbolicExpressionGrammar Members
    121 
    122     private Symbol programRootSymbol;
    123     public Symbol ProgramRootSymbol {
    124       get { return programRootSymbol; }
    125     }
    126 
    127     private Symbol startSymbol;
    128     public Symbol StartSymbol {
    129       get { return startSymbol; }
    130     }
    131 
    132     public IEnumerable<Symbol> GetAllowedSymbols(Symbol parent, int argumentIndex) {
    133       return from name in allowedFunctions[parent.Name][argumentIndex]
    134              from sym in allSymbols
    135              where name == sym.Name
    136              select sym;
    137     }
    138 
    139 
    140     private Dictionary<Symbol, int> cachedMinExpressionLength;
    141     public int GetMinExpressionLength(Symbol start) {
    142       if (!cachedMinExpressionLength.ContainsKey(start)) {
    143         cachedMinExpressionLength[start] = int.MaxValue; // prevent infinite recursion
    144         cachedMinExpressionLength[start] = 1 + (from argIndex in Enumerable.Range(0, GetMinSubTreeCount(start))
    145                                                 let minForSlot = (from symbol in GetAllowedSymbols(start, argIndex)
    146                                                                   select GetMinExpressionLength(symbol)).DefaultIfEmpty(0).Min()
    147                                                 select minForSlot).DefaultIfEmpty(0).Sum();
    148       }
    149       return cachedMinExpressionLength[start];
    150     }
    151 
    152     private Dictionary<Symbol, int> cachedMaxExpressionLength;
    153     public int GetMaxExpressionLength(Symbol start) {
    154       if (!cachedMaxExpressionLength.ContainsKey(start)) {
    155         cachedMaxExpressionLength[start] = int.MaxValue; // prevent infinite recursion
    156         long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaxSubTreeCount(start))
    157                                   let maxForSlot = (long)(from symbol in GetAllowedSymbols(start, argIndex)
    158                                                           select GetMaxExpressionLength(symbol)).DefaultIfEmpty(0).Max()
    159                                   select maxForSlot).DefaultIfEmpty(0).Sum();
    160         long limit = int.MaxValue;
    161         cachedMaxExpressionLength[start] = (int)Math.Min(sumOfMaxTrees, limit);
    162       }
    163       return cachedMaxExpressionLength[start];
    164     }
    165 
    166     private Dictionary<Symbol, int> cachedMinExpressionDepth;
    167     public int GetMinExpressionDepth(Symbol start) {
    168       if (!cachedMinExpressionDepth.ContainsKey(start)) {
    169         cachedMinExpressionDepth[start] = int.MaxValue; // prevent infinite recursion
    170         cachedMinExpressionDepth[start] = 1 + (from argIndex in Enumerable.Range(0, GetMinSubTreeCount(start))
    171                                                let minForSlot = (from symbol in GetAllowedSymbols(start, argIndex)
    172                                                                  select GetMinExpressionDepth(symbol)).DefaultIfEmpty(0).Min()
    173                                                select minForSlot).DefaultIfEmpty(0).Max();
    174       }
    175       return cachedMinExpressionDepth[start];
    176     }
    177 
    178     public int GetMinSubTreeCount(Symbol start) {
    179       return minSubTreeCount[start.Name];
    180     }
    181 
    182     public int GetMaxSubTreeCount(Symbol start) {
    183       return maxSubTreeCount[start.Name];
    184     }
    185 
    186     public bool IsValidExpression(SymbolicExpressionTree expression) {
    187       if (expression.Root.Symbol != ProgramRootSymbol) return false;
    188       // check dynamic symbols
    189       foreach (var branch in expression.Root.SubTrees) {
    190         foreach (var dynamicNode in branch.DynamicSymbols) {
    191           if (!dynamicNode.StartsWith("ARG")) {
    192             if (FindDefinitionOfDynamicFunction(expression.Root, dynamicNode) == null) return false;
    193           }
    194         }
    195       }
    196       return IsValidExpression(expression.Root);
    197     }
    198 
    199     #endregion
    200     private bool IsValidExpression(SymbolicExpressionTreeNode root) {
    201       if (root.SubTrees.Count < GetMinSubTreeCount(root.Symbol)) return false;
    202       if (root.SubTrees.Count > GetMaxSubTreeCount(root.Symbol)) return false;
    203       if (root.Symbol is Defun || root.Symbol is StartSymbol) {
    204         // check references to dynamic symbols
    205         if (!CheckDynamicSymbolsInBranch(root, root.SubTrees[0])) return false;
    206       }
    207       for (int i = 0; i < root.SubTrees.Count; i++) {
    208         if (!GetAllowedSymbols(root.Symbol, i).Contains(root.SubTrees[i].Symbol)) return false;
    209         if (!IsValidExpression(root.SubTrees[i])) return false;
    210       }
    211       return true;
    212     }
    213 
    214     private SymbolicExpressionTreeNode FindDefinitionOfDynamicFunction(SymbolicExpressionTreeNode root, string dynamicNode) {
    215       return (from node in root.SubTrees.OfType<DefunTreeNode>()
    216               where node.Name == dynamicNode
    217               select node).FirstOrDefault();
    218     }
    219 
    220     private bool CheckDynamicSymbolsInBranch(SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode node) {
    221       var argNode = node as ArgumentTreeNode;
    222       var invokeNode = node as InvokeFunctionTreeNode;
    223       if (argNode != null) {
    224         if (!root.DynamicSymbols.Contains("ARG" + argNode.ArgumentIndex)) return false;
    225       } else if (invokeNode != null) {
    226         if (!root.DynamicSymbols.Contains(invokeNode.InvokedFunctionName)) return false;
    227         if (root.GetDynamicSymbolArgumentCount(invokeNode.InvokedFunctionName) != invokeNode.SubTrees.Count()) return false;
    228       }
    229       foreach (var subtree in node.SubTrees) {
    230         if (!CheckDynamicSymbolsInBranch(root, subtree)) return false;
    231       }
    232       return true;
    233     }
    234 
     191    //private void symbol_ToStringChanged(object sender, EventArgs e) {
     192    //  OnToStringChanged();
     193    //}
     194
     195    //private bool IsValidExpression(SymbolicExpressionTreeNode root) {
     196    //  if (root.SubTrees.Count < root.GetMinSubtreeCount()) return false;
     197    //  else if (root.SubTrees.Count > root.GetMaxSubtreeCount()) return false;
     198    //  else for (int i = 0; i < root.SubTrees.Count; i++) {
     199    //      if (!root.GetAllowedSymbols(i).Select(x => x.Name).Contains(root.SubTrees[i].Symbol.Name)) return false;
     200    //      if (!IsValidExpression(root.SubTrees[i])) return false;
     201    //    }
     202    //  return true;
     203    //}
     204
     205    public override IDeepCloneable Clone(Cloner cloner) {
     206      DefaultSymbolicExpressionGrammar clone = (DefaultSymbolicExpressionGrammar)base.Clone(cloner);
     207      clone.maxSubTreeCount = new Dictionary<string, int>(maxSubTreeCount);
     208      clone.minSubTreeCount = new Dictionary<string, int>(minSubTreeCount);
     209      clone.startSymbol = startSymbol;
     210      clone.allowedChildSymbols = new Dictionary<string, List<HashSet<string>>>(allowedChildSymbols);
     211      clone.allSymbols = new HashSet<Symbol>(allSymbols);
     212      return clone;
     213    }
    235214  }
    236215}

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

    r3294 r3338  
    8383  </ItemGroup>
    8484  <ItemGroup>
    85     <Compile Include="ArchitectureAlteringOperators\ArgumentDuplicater.cs" />
    8685    <Compile Include="ArchitectureAlteringOperators\ArgumentCreater.cs" />
    8786    <Compile Include="ArchitectureAlteringOperators\ArgumentDeleter.cs" />
    88     <Compile Include="ArchitectureAlteringOperators\RandomArchitectureAlteringOperator.cs" />
    89     <Compile Include="ArchitectureAlteringOperators\SubroutineDeleter.cs" />
    90     <Compile Include="ArchitectureAlteringOperators\SubroutineCreater.cs">
     87    <Compile Include="Crossovers\SubtreeCrossover.cs">
    9188      <SubType>Code</SubType>
    9289    </Compile>
    93     <Compile Include="ArchitectureAlteringOperators\SubroutineDuplicater.cs">
    94       <SubType>Code</SubType>
    95     </Compile>
     90    <Compile Include="GlobalSymbolicExpressionGrammar.cs" />
     91    <Compile Include="EnumerableExtensions.cs" />
     92    <Compile Include="Symbols\StartSymbolTreeNode.cs" />
    9693    <Compile Include="DefaultSymbolicExpressionGrammar.cs">
    9794      <SubType>Code</SubType>
    … …  
    103100    <Compile Include="SymbolicExpressionTreeManipulator.cs" />
    104101    <Compile Include="SymbolicExpressionTreeTerminalNode.cs" />
    105     <Compile Include="Crossovers\SubtreeCrossover.cs" />
    106102    <Compile Include="Interfaces\ISymbolicExpressionGrammar.cs" />
    107103    <Compile Include="Creators\ProbabilisticTreeCreator.cs" />
    … …  
    126122    <Compile Include="Symbols\Multiplication.cs" />
    127123    <Compile Include="Symbols\Subtraction.cs" />
    128     <Compile Include="Symbols\Values.cs">
    129       <SubType>Code</SubType>
    130     </Compile>
    131     <Compile Include="Symbols\ValuesTreeNode.cs">
    132       <SubType>Code</SubType>
    133     </Compile>
    134124  </ItemGroup>
    135125  <ItemGroup>

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Interfaces/ISymbolicExpressionGrammar.cs

    r3294 r3338  
    3131  public interface ISymbolicExpressionGrammar : IItem {
    3232    Symbol StartSymbol { get; }
    33     Symbol ProgramRootSymbol { get; }
    34     IEnumerable<Symbol> GetAllowedSymbols(Symbol parent, int argumentIndex);
     33    void AddSymbol(Symbol symbol);
     34    void RemoveSymbol(Symbol symbol);
     35    IEnumerable<Symbol> Symbols { get; }
     36    void SetAllowedChild(Symbol parent, Symbol child, int argumentIndex);
     37    bool IsAllowedChild(Symbol parent, Symbol child, int argumentIndex);
    3538    int GetMinExpressionLength(Symbol start);
    3639    int GetMaxExpressionLength(Symbol start);
    3740    int GetMinExpressionDepth(Symbol start);
    38     int GetMinSubTreeCount(Symbol start);
    39     int GetMaxSubTreeCount(Symbol start);
    40 
    41     bool IsValidExpression(SymbolicExpressionTree expression);
     41    int GetMinSubtreeCount(Symbol symbol);
     42    void SetMinSubtreeCount(Symbol symbol, int value);
     43    int GetMaxSubtreeCount(Symbol symbol);
     44    void SetMaxSubtreeCount(Symbol symbol, int value);
    4245  }
    4346}

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

    r3317 r3338  
    5050    }
    5151
    52     [Storable]
    53     private Dictionary<int, IEnumerable<string>> allowedFunctionsInBranch;
    54 
    5552    public int Size {
    5653      get {
    … …  
    6764    public SymbolicExpressionTree()
    6865      : base() {
    69       allowedFunctionsInBranch = new Dictionary<int, IEnumerable<string>>();
    7066    }
    7167
    7268    public SymbolicExpressionTree(SymbolicExpressionTreeNode root)
    7369      : base() {
    74       allowedFunctionsInBranch = new Dictionary<int, IEnumerable<string>>();
    7570    }
    7671
    7772    public IEnumerable<SymbolicExpressionTreeNode> IterateNodesPrefix() {
    78       return IterateNodesPrefix(root);
    79     }
    80     private IEnumerable<SymbolicExpressionTreeNode> IterateNodesPrefix(SymbolicExpressionTreeNode node) {
    81       yield return node;
    82       foreach (var subtree in node.SubTrees) {
    83         foreach (var n in IterateNodesPrefix(subtree))
    84           yield return n;
    85       }
     73      return root.IterateNodesPrefix();
    8674    }
    8775    public IEnumerable<SymbolicExpressionTreeNode> IterateNodesPostfix() {
    88       return IterateNodesPostfix(root);
     76      return root.IterateNodesPostfix();
    8977    }
    90     private IEnumerable<SymbolicExpressionTreeNode> IterateNodesPostfix(SymbolicExpressionTreeNode node) {
    91       foreach (var subtree in node.SubTrees) {
    92         foreach (var n in IterateNodesPrefix(subtree))
    93           yield return n;
     78
     79    public SymbolicExpressionTreeNode GetTopLevelBranchOf(SymbolicExpressionTreeNode node) {
     80      foreach (var branch in root.SubTrees) {
     81        if (branch.IterateNodesPrefix().Contains(node)) return branch;
    9482      }
    95       yield return node;
     83      throw new ArgumentException("Node was not found in tree.");
    9684    }
    9785
    … …  
    10189      clone.ReadOnlyView = ReadOnlyView;
    10290      clone.root = (SymbolicExpressionTreeNode)this.root.Clone();
    103       clone.allowedFunctionsInBranch = new Dictionary<int, IEnumerable<string>>(allowedFunctionsInBranch);
    10491      return clone;
     92    }
     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();
    10599    }
    106100  }

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeCompiler.cs

    r3294 r3338  
    3636      {typeof(Division), CodeSymbol.Div},
    3737      {typeof(InvokeFunction), CodeSymbol.Call},
    38       {typeof(Values), CodeSymbol.Values}
     38      //{typeof(Values), CodeSymbol.Values}
    3939    };
    4040    private Dictionary<string, short> entryPoint = new Dictionary<string, short>();
    … …  
    5050                             select node;
    5151      foreach (DefunTreeNode branch in functionBranches) {
    52         entryPoint[branch.Name] = (short)code.Count;
     52        entryPoint[branch.FunctionName] = (short)code.Count;
    5353        code.AddRange(Compile(branch));
    5454      }
    … …  
    6565          if (instr.symbol == CodeSymbol.Call) {
    6666            var invokeNode = (InvokeFunctionTreeNode)node;
    67             instr.iArg0 = entryPoint[invokeNode.InvokedFunctionName];
     67            instr.iArg0 = entryPoint[invokeNode.Symbol.FunctionName];
    6868          }
    6969        } else {

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeCreator.cs

    r3294 r3338  
    3535  [StorableClass]
    3636  public abstract class SymbolicExpressionTreeCreator : SymbolicExpressionTreeOperator, ISolutionCreator {
     37    private const string MaxFunctionDefinitionsParameterName = "MaxFunctionDefinitions";
     38    private const string MaxFunctionArgumentsParameterName = "MaxFunctionArguments";
     39    #region Parameter Properties
     40    public IValueLookupParameter<IntValue> MaxFunctionDefinitionsParameter {
     41      get { return (IValueLookupParameter<IntValue>)Parameters[MaxFunctionDefinitionsParameterName]; }
     42    }
     43    public IValueLookupParameter<IntValue> MaxFunctionArgumentsParameter {
     44      get { return (IValueLookupParameter<IntValue>)Parameters[MaxFunctionArgumentsParameterName]; }
     45    }
     46    #endregion
     47
     48    #region Propeties
     49    public IntValue MaxFunctionDefinitions {
     50      get { return MaxFunctionDefinitionsParameter.ActualValue; }
     51    }
     52    public IntValue MaxFunctionArguments {
     53      get { return MaxFunctionArgumentsParameter.ActualValue; }
     54    }
     55
     56    #endregion
    3757    protected SymbolicExpressionTreeCreator()
    3858      : base() {
     59      Parameters.Add(new ValueLookupParameter<IntValue>(MaxFunctionDefinitionsParameterName, "Maximal number of function definitions in the symbolic expression tree."));
     60      Parameters.Add(new ValueLookupParameter<IntValue>(MaxFunctionArgumentsParameterName, "Maximal number of arguments of automatically defined functions in the symbolic expression tree."));
    3961    }
    4062
    4163    public sealed override IOperation Apply() {
    42       SymbolicExpressionTreeParameter.ActualValue = Create(RandomParameter.ActualValue, SymbolicExpressionGrammarParameter.ActualValue,
    43         MaxTreeSizeParameter.ActualValue, MaxTreeHeightParameter.ActualValue);
     64      SymbolicExpressionTreeParameter.ActualValue = Create(Random, SymbolicExpressionGrammar,
     65        MaxTreeSize, MaxTreeHeight, MaxFunctionDefinitions, MaxFunctionArguments);
    4466
    4567      foreach (var node in SymbolicExpressionTreeParameter.ActualValue.IterateNodesPostfix()) {
    … …  
    4971    }
    5072
    51     protected abstract SymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight);
     73    protected abstract SymbolicExpressionTree Create(
     74      IRandom random,
     75      ISymbolicExpressionGrammar grammar,
     76      IntValue maxTreeSize, IntValue maxTreeHeight,
     77      IntValue maxFunctionDefinitions, IntValue maxFunctionArguments
     78      );
    5279  }
    5380}

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeCrossover.cs

    r3294 r3338  
    6767
    6868      IRandom random = RandomParameter.ActualValue;
    69       ISymbolicExpressionGrammar grammar = SymbolicExpressionGrammarParameter.ActualValue;
    7069
    7170      // randomly swap parents to remove a possible bias from selection (e.g. when using gender-specific selection)
    … …  
    7776
    7877      bool success;
    79       SymbolicExpressionTree result = Cross(random, grammar, parent0, parent1,
     78      SymbolicExpressionTree result = Cross(random, parent0, parent1,
    8079        MaxTreeSizeParameter.ActualValue, MaxTreeHeightParameter.ActualValue, out success);
    8180     
    … …  
    8988    }
    9089
    91     protected abstract SymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionGrammar grammar,
     90    protected abstract SymbolicExpressionTree Cross(IRandom random,
    9291      SymbolicExpressionTree parent0, SymbolicExpressionTree parent1,
    9392      IntValue maxTreeSize, IntValue maxTreeHeight, out bool success);

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

    r3294 r3338  
    3838    private Symbol symbol;
    3939
    40     public SymbolicExpressionTreeNode() { }
     40    public SymbolicExpressionTreeNode() {
     41      subTrees = new List<SymbolicExpressionTreeNode>();
     42    }
    4143
    42     public SymbolicExpressionTreeNode(Symbol symbol) {
    43       subTrees = new List<SymbolicExpressionTreeNode>();
     44    public SymbolicExpressionTreeNode(Symbol symbol)
     45      : this() {
    4446      this.symbol = symbol;
    4547    }
    … …  
    4951      symbol = original.symbol;
    5052      subTrees = new List<SymbolicExpressionTreeNode>();
     53      grammar = original.grammar;
    5154      foreach (var subtree in original.SubTrees) {
    52         AddSubTree((SymbolicExpressionTreeNode)subtree.Clone());
     55        SubTrees.Add((SymbolicExpressionTreeNode)subtree.Clone());
    5356      }
    54       dynamicSymbols = new Dictionary<string, int>(original.dynamicSymbols);
    5557    }
    5658
    … …  
    6870    }
    6971
     72    private ISymbolicExpressionGrammar grammar;
     73    public virtual ISymbolicExpressionGrammar Grammar {
     74      get { return grammar; }
     75      set {
     76        grammar = value;
     77        foreach (var subtree in subTrees)
     78          subtree.Grammar = value;
     79      }
     80    }
     81
    7082    public int GetSize() {
    7183      int size = 1;
    … …  
    8092    }
    8193
    82     [Storable]
    83     private Dictionary<string, int> dynamicSymbols = new Dictionary<string, int>();
    84     public void AddDynamicSymbol(string symbolName) {
    85       Debug.Assert(!dynamicSymbols.ContainsKey(symbolName));
    86       dynamicSymbols[symbolName] = 0;
    87     }
    88 
    89     public void AddDynamicSymbol(string symbolName, int nArguments) {
    90       AddDynamicSymbol(symbolName);
    91       SetDynamicSymbolArgumentCount(symbolName, nArguments);
    92     }
    93 
    94     public void RemoveDynamicSymbol(string symbolName) {
    95       dynamicSymbols.Remove(symbolName);
    96     }
    97 
    98     public IEnumerable<string> DynamicSymbols {
    99       get { return dynamicSymbols.Keys; }
    100     }
    101 
    102     public int GetDynamicSymbolArgumentCount(string symbolName) {
    103       return dynamicSymbols[symbolName];
    104     }
    105     public void SetDynamicSymbolArgumentCount(string symbolName, int nArguments) {
    106       Debug.Assert(dynamicSymbols.ContainsKey(symbolName));
    107       dynamicSymbols[symbolName] = nArguments;
    108     }
    109 
    11094    public virtual void ResetLocalParameters(IRandom random) { }
    11195    public virtual void ShakeLocalParameters(IRandom random, double shakingFactor) { }
    11296
    113     protected internal virtual void AddSubTree(SymbolicExpressionTreeNode tree) {
     97    public virtual void AddSubTree(SymbolicExpressionTreeNode tree) {
    11498      SubTrees.Add(tree);
     99      //if (tree != null)
     100      tree.Grammar = Grammar;
    115101    }
    116102
    117     protected internal virtual void InsertSubTree(int index, SymbolicExpressionTreeNode tree) {
     103    public virtual void InsertSubTree(int index, SymbolicExpressionTreeNode tree) {
    118104      SubTrees.Insert(index, tree);
     105      //if (tree != null)
     106      tree.Grammar = Grammar;
    119107    }
    120108
    121     protected internal virtual void RemoveSubTree(int index) {
     109    public virtual void RemoveSubTree(int index) {
     110      //if (SubTrees[index] != null)
     111      SubTrees[index].Grammar = null;
    122112      SubTrees.RemoveAt(index);
    123113    }
     114
     115    public IEnumerable<SymbolicExpressionTreeNode> IterateNodesPrefix() {
     116      yield return this;
     117      foreach (var subtree in subTrees) {
     118        foreach (var n in subtree.IterateNodesPrefix())
     119          yield return n;
     120      }
     121    }
     122
     123    public IEnumerable<SymbolicExpressionTreeNode> IterateNodesPostfix() {
     124      foreach (var subtree in subTrees) {
     125        foreach (var n in subtree.IterateNodesPrefix())
     126          yield return n;
     127      }
     128      yield return this;
     129    }
     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    //}
     139    public IEnumerable<Symbol> GetAllowedSymbols(int argumentIndex) {
     140      return Grammar.Symbols.Where(s => Grammar.IsAllowedChild(Symbol, s, argumentIndex));
     141    }
     142    public int GetMinSubtreeCount() {
     143      return Grammar.GetMinSubtreeCount(Symbol);
     144    }
     145    public int GetMaxSubtreeCount() {
     146      return Grammar.GetMaxSubtreeCount(Symbol);
     147    }
     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    //}
    124157
    125158    #region ICloneable Members
    … …  
    130163
    131164    #endregion
     165
     166
     167    public bool IsValidTree() {
     168      var matchingSymbol = (from symb in Grammar.Symbols
     169                            where symb.Name == Symbol.Name
     170                            select symb).SingleOrDefault();
     171
     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    }
    132180  }
    133181}

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeOperator.cs

    r3294 r3338  
    4545    }
    4646
     47    #region Parameter Properties
    4748    public ILookupParameter<IRandom> RandomParameter {
    4849      get { return (LookupParameter<IRandom>)Parameters[RandomParameterName]; }
    … …  
    6061      get { return (ILookupParameter<ISymbolicExpressionGrammar>)Parameters[SymbolicExpressionGrammarParameterName]; }
    6162    }
     63    #endregion
     64
     65    #region Properties
     66    public IRandom Random {
     67      get { return RandomParameter.ActualValue; }
     68    }
     69    public SymbolicExpressionTree SymbolicExpressionTree {
     70      get { return SymbolicExpressionTreeParameter.ActualValue; }
     71    }
     72    public IntValue MaxTreeSize {
     73      get { return MaxTreeSizeParameter.ActualValue; }
     74    }
     75    public IntValue MaxTreeHeight {
     76      get { return MaxTreeHeightParameter.ActualValue; }
     77    }
     78    public ISymbolicExpressionGrammar SymbolicExpressionGrammar {
     79      get { return SymbolicExpressionGrammarParameter.ActualValue; }
     80    }
     81    #endregion
    6282
    6383    protected SymbolicExpressionTreeOperator()

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeTerminalNode.cs

    r3256 r3338  
    3737    }
    3838
    39     protected internal override void AddSubTree(SymbolicExpressionTreeNode tree) {
     39    public override void AddSubTree(SymbolicExpressionTreeNode tree) {
    4040      throw new NotSupportedException();
    4141    }
    42     protected internal override void InsertSubTree(int index, SymbolicExpressionTreeNode tree) {
     42    public override void InsertSubTree(int index, SymbolicExpressionTreeNode tree) {
    4343      throw new NotSupportedException();
    4444    }
    45     protected internal override void RemoveSubTree(int index) {
     45    public override void RemoveSubTree(int index) {
    4646      throw new NotSupportedException();
    4747    }

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/Argument.cs

    r3294 r3338  
    3434      }
    3535    }
     36
     37    private int argumentIndex;
     38    public int ArgumentIndex {
     39      get { return argumentIndex; }
     40    }
     41
     42    public Argument(int argumentIndex)
     43      : base() {
     44      this.argumentIndex = argumentIndex;
     45      this.name = "ARG" + argumentIndex;
     46    }
     47
    3648    public override SymbolicExpressionTreeNode CreateTreeNode() {
    3749      return new ArgumentTreeNode(this);

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/ArgumentTreeNode.cs

    r3294 r3338  
    2525  [StorableClass]
    2626  public sealed class ArgumentTreeNode : SymbolicExpressionTreeNode {
    27     private int argumentIndex;
    28     [Storable]
    29     public int ArgumentIndex {
    30       get { return argumentIndex; }
    31       set { argumentIndex = value; }
     27    public new Argument Symbol {
     28      get { return (Argument)base.Symbol; }
     29      set {
     30        if (value == null) throw new ArgumentNullException();
     31        if(!(value is Argument)) throw new ArgumentException();
     32        base.Symbol = value;
     33      }
    3234    }
    33 
     35   
    3436    // copy constructor
    3537    private ArgumentTreeNode(ArgumentTreeNode original)
    3638      : base(original) {
    37       argumentIndex = original.argumentIndex;
    3839    }
    3940

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/Defun.cs

    r3294 r3338  
    3434      }
    3535    }
     36
    3637    public override SymbolicExpressionTreeNode CreateTreeNode() {
    3738      return new DefunTreeNode(this);

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

    r3294 r3338  
    2222using System;
    2323using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     24using HeuristicLab.Core;
    2425namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols {
    2526  [StorableClass]
    … …  
    3132      set { numberOfArguments = value; }
    3233    }
    33     private string name;
     34    private string functionName;
    3435    [Storable]
    35     public string Name {
    36       get { return name; }
    37       set { this.name = value; }
     36    public string FunctionName {
     37      get { return functionName; }
     38      set { this.functionName = value; }
     39    }
     40
     41    private new Defun Symbol {
     42      get { return (Defun)base.Symbol; }
    3843    }
    3944
    … …  
    4146    private DefunTreeNode(DefunTreeNode original)
    4247      : base(original) {
    43       name = original.Name;
     48      functionName = original.functionName;
    4449      numberOfArguments = original.numberOfArguments;
    4550    }
    4651
    4752    public DefunTreeNode(Defun defunSymbol) : base(defunSymbol) { }
     53
    4854
    4955    public override object Clone() {

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/InvokeFunction.cs

    r3294 r3338  
    3434      }
    3535    }
     36    public string FunctionName { get; set; }
     37
     38    public InvokeFunction(string functionName)
     39      : base() {
     40      this.FunctionName = functionName;
     41      this.name = "Invoke: " + functionName;
     42    }
     43
    3644    public override SymbolicExpressionTreeNode CreateTreeNode() {
    3745      return new InvokeFunctionTreeNode(this);

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

    r3294 r3338  
    2525  [StorableClass]
    2626  public sealed class InvokeFunctionTreeNode : SymbolicExpressionTreeNode {
    27     private string invokedFunctionName;
    28     [Storable]
    29     public string InvokedFunctionName {
    30       get { return invokedFunctionName; }
    31       set { this.invokedFunctionName = value; }
     27    public new InvokeFunction Symbol {
     28      get { return (InvokeFunction)base.Symbol; }
    3229    }
    3330
    … …  
    3532    private InvokeFunctionTreeNode(InvokeFunctionTreeNode original)
    3633      : base(original) {
    37       invokedFunctionName = original.invokedFunctionName;
    3834    }
    3935

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/StartSymbol.cs

    r3294 r3338  
    3131      }
    3232    }
     33
     34    public override SymbolicExpressionTreeNode CreateTreeNode() {
     35      return new StartSymbolTreeNode(this);
     36    }
    3337  }
    3438}

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

    r3297 r3338  
    3939  </ItemGroup>
    4040  <ItemGroup>
    41     <Compile Include="SubroutineCreaterTest.cs" />
    42     <Compile Include="SubtreeCrossoverTest.cs" />
     41    <Compile Include="ArgumentCreaterTest.cs" />
     42    <Compile Include="ArgumentDeleterTest.cs" />
     43    <Compile Include="Grammars.cs" />
     44    <Compile Include="SubtreeCrossoverTest.cs">
     45      <SubType>Code</SubType>
     46    </Compile>
     47    <Compile Include="Util.cs" />
    4348    <Compile Include="Properties\AssemblyInfo.cs" />
    4449    <Compile Include="ProbabilisticTreeCreaterTest.cs" />

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

    r3297 r3338  
    1111  [TestClass]
    1212  public class ProbabilisticTreeCreaterTest {
    13     public ProbabilisticTreeCreaterTest() {
    14       int populationSize = 1000;
    15       randomTrees = new List<SymbolicExpressionTree>();
    16       var grammar = new TestGrammar();
    17       var random = new MersenneTwister();
    18       for (int i = 0; i < populationSize; i++) {
    19         randomTrees.Add(ProbabilisticTreeCreator.Create(random, grammar, 100, 10));
    20       }
    21       foreach (var tree in randomTrees)
    22         Assert.IsTrue(grammar.IsValidExpression(tree));
    23     }
    24 
     13    private const int POPULATION_SIZE = 1000;
     14    private const int MAX_TREE_SIZE = 100;
     15    private const int MAX_TREE_HEIGHT = 10;
    2516    private TestContext testContextInstance;
    2617
    … …  
    3829    }
    3930
    40     private List<SymbolicExpressionTree> randomTrees;
    41 
    42 
    43     private class Addition : Symbol { }
    44     private class Subtraction : Symbol { }
    45     private class Multiplication : Symbol { }
    46     private class Division : Symbol { }
    47     private class Terminal : Symbol { }
    48 
    49     private class TestGrammar : DefaultSymbolicExpressionGrammar {
    50       public TestGrammar()
    51         : base(0, 0, 0, 0) {
    52         Initialize();
     31    [TestMethod()]
     32    public void ProbabilisticTreeCreaterDistributionsTest() {
     33      var randomTrees = new List<SymbolicExpressionTree>();
     34      var grammar = Grammars.CreateSimpleArithmeticGrammar();
     35      var random = new MersenneTwister();
     36      for (int i = 0; i < POPULATION_SIZE; i++) {
     37        randomTrees.Add(ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 0, 0));
    5338      }
    5439
    55       private void Initialize() {
    56         var add = new Addition();
    57         var sub = new Subtraction();
    58         var mul = new Multiplication();
    59         var div = new Division();
    60         var terminal = new Terminal();
    61 
    62         var allSymbols = new List<Symbol>() { add, sub, mul, div, terminal };
    63         var functionSymbols = new List<Symbol>() { add, sub, mul, div };
    64         allSymbols.ForEach(s => AddAllowedSymbols(StartSymbol, 0, s));
    65 
    66         SetMinSubTreeCount(terminal, 0);
    67         SetMaxSubTreeCount(terminal, 0);
    68         int maxSubTrees = 3;
    69         foreach (var functionSymbol in functionSymbols) {
    70           SetMinSubTreeCount(functionSymbol, 1);
    71           SetMaxSubTreeCount(functionSymbol, maxSubTrees);
    72           foreach (var childSymbol in allSymbols) {
    73             for (int argumentIndex = 0; argumentIndex < maxSubTrees; argumentIndex++) {
    74               AddAllowedSymbols(functionSymbol, argumentIndex, childSymbol);
    75             }
    76           }
    77         }
    78       }
    79     }
    80 
    81     [TestMethod()]
    82     public void ProbabilisticTreeCreaterSizeDistributionTest() {
    83       int[] histogram = new int[105 / 5];
    84       for (int i = 0; i < randomTrees.Count; i++) {
    85         histogram[randomTrees[i].Size / 5]++;
    86       }
    87       StringBuilder strBuilder = new StringBuilder();
    88       for (int i = 0; i < histogram.Length; i++) {
    89         strBuilder.Append(Environment.NewLine);
    90         strBuilder.Append("< "); strBuilder.Append((i + 1) * 5);
    91         strBuilder.Append(": "); strBuilder.AppendFormat("{0:#0.00%}", histogram[i] / (double)randomTrees.Count);
    92       }
    93       Assert.Inconclusive("Size distribution of ProbabilisticTreeCreator: " + strBuilder);
    94     }
    95 
    96     [TestMethod()]
    97     public void ProbabilisticTreeCreaterFunctionDistributionTest() {
    98       Dictionary<Symbol, int> occurances = new Dictionary<Symbol, int>();
    99       double n = 0.0;
    100       for (int i = 0; i < randomTrees.Count; i++) {
    101         foreach (var node in randomTrees[i].IterateNodesPrefix()) {
    102           if (node.SubTrees.Count > 0) {
    103             if (!occurances.ContainsKey(node.Symbol))
    104               occurances[node.Symbol] = 0;
    105             occurances[node.Symbol]++;
    106             n++;
    107           }
    108         }
    109       }
    110       StringBuilder strBuilder = new StringBuilder();
    111       foreach (var function in occurances.Keys) {
    112         strBuilder.Append(Environment.NewLine);
    113         strBuilder.Append(function.Name); strBuilder.Append(": ");
    114         strBuilder.AppendFormat("{0:#0.00%}", occurances[function] / n);
    115       }
    116       Assert.Inconclusive("Function distribution of ProbabilisticTreeCreator: " + strBuilder);
    117     }
    118 
    119     [TestMethod()]
    120     public void ProbabilisticTreeCreaterNumberOfSubTreesDistributionTest() {
    121       Dictionary<int, int> occurances = new Dictionary<int, int>();
    122       double n = 0.0;
    123       for (int i = 0; i < randomTrees.Count; i++) {
    124         foreach (var node in randomTrees[i].IterateNodesPrefix()) {
    125           if (!occurances.ContainsKey(node.SubTrees.Count))
    126             occurances[node.SubTrees.Count] = 0;
    127           occurances[node.SubTrees.Count]++;
    128           n++;
    129         }
    130       }
    131       StringBuilder strBuilder = new StringBuilder();
    132       foreach (var arity in occurances.Keys) {
    133         strBuilder.Append(Environment.NewLine);
    134         strBuilder.Append(arity); strBuilder.Append(": ");
    135         strBuilder.AppendFormat("{0:#0.00%}", occurances[arity] / n);
    136       }
    137       Assert.Inconclusive("Distribution of function arities of ProbabilisticTreeCreator: " + strBuilder);
     40      foreach (var tree in randomTrees)
     41        Assert.IsTrue(tree.IsValidExpression());
     42      Assert.Inconclusive("ProbabilisticTreeCreator: " + Environment.NewLine +
     43        Util.GetSizeDistributionString(randomTrees, 105, 5) + Environment.NewLine +
     44        Util.GetFunctionDistributionString(randomTrees) + Environment.NewLine +
     45        Util.GetNumberOfSubTreesDistributionString(randomTrees) + Environment.NewLine +
     46        Util.GetTerminalDistributionString(randomTrees) + Environment.NewLine
     47        );
    13848    }
    13949
    14050
    14151    [TestMethod()]
    142     public void ProbabilisticTreeCreaterTerminalDistributionTest() {
    143       Dictionary<Symbol, int> occurances = new Dictionary<Symbol, int>();
    144       double n = 0.0;
    145       for (int i = 0; i < randomTrees.Count; i++) {
    146         foreach (var node in randomTrees[i].IterateNodesPrefix()) {
    147           if (node.SubTrees.Count == 0) {
    148             if (!occurances.ContainsKey(node.Symbol))
    149               occurances[node.Symbol] = 0;
    150             occurances[node.Symbol]++;
    151             n++;
    152           }
    153         }
     52    public void ProbabilisticTreeCreaterWithAdfDistributionsTest() {
     53      var randomTrees = new List<SymbolicExpressionTree>();
     54      var grammar = Grammars.CreateArithmeticAndAdfGrammar();
     55      var random = new MersenneTwister();
     56      for (int i = 0; i < POPULATION_SIZE; i++) {
     57        randomTrees.Add(ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3));
    15458      }
    155       StringBuilder strBuilder = new StringBuilder();
    156       foreach (var function in occurances.Keys) {
    157         strBuilder.Append(Environment.NewLine);
    158         strBuilder.Append(function.Name); strBuilder.Append(": ");
    159         strBuilder.AppendFormat("{0:#0.00%}", occurances[function] / n);
    160       }
    161       Assert.Inconclusive("Terminal distribution of ProbabilisticTreeCreator: " + strBuilder);
     59      foreach (var tree in randomTrees)
     60        Assert.IsTrue(tree.IsValidExpression());
     61      Assert.Inconclusive("ProbabilisticTreeCreator: " + Environment.NewLine +
     62        Util.GetSizeDistributionString(randomTrees, 105, 5) + Environment.NewLine +
     63        Util.GetFunctionDistributionString(randomTrees) + Environment.NewLine +
     64        Util.GetNumberOfSubTreesDistributionString(randomTrees) + Environment.NewLine +
     65        Util.GetTerminalDistributionString(randomTrees) + Environment.NewLine
     66        );
    16267    }
    16368  }

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

    r3307 r3338  
    1313  [TestClass]
    1414  public class SubroutineCreaterTest {
    15     public SubroutineCreaterTest() {
    16     }
     15    private static ISymbolicExpressionGrammar grammar;
     16    private static List<SymbolicExpressionTree> subroutineTrees;
     17    private static int failedEvents;
    1718
    1819    private TestContext testContextInstance;
    … …  
    3637      subroutineTrees = new List<SymbolicExpressionTree>();
    3738      int populationSize = 1000;
    38       var grammar = new TestGrammar();
     39      failedEvents = 0;
     40      grammar = Grammars.CreateArithmeticAndAdfGrammar();
    3941      var random = new MersenneTwister();
    4042      for (int i = 0; i < populationSize; i++) {
    4143        var randTree = ProbabilisticTreeCreator.Create(random, grammar, 100, 10);
    42         Assert.IsTrue(grammar.IsValidExpression(randTree));
     44        // PTC create is tested separately
    4345        randomTrees.Add(randTree);
    4446      }
    … …  
    4749        var par0 = (SymbolicExpressionTree)randomTrees[random.Next(populationSize)].Clone();
    4850        bool success = SubroutineCreater.CreateSubroutine(random, par0, grammar, 100, 10, 3, 3);
    49         Assert.IsTrue(grammar.IsValidExpression(par0));
     51        if (!success) failedEvents++;
    5052        subroutineTrees.Add(par0);
    5153      }
    … …  
    5355
    5456
    55 
    56     private static List<SymbolicExpressionTree> subroutineTrees;
    57     private static int failedEvents;
    58 
    59     private class Addition : Symbol { }
    60     private class Subtraction : Symbol { }
    61     private class Multiplication : Symbol { }
    62     private class Division : Symbol { }
    63     private class Terminal : Symbol { }
    64 
    65     private class TestGrammar : DefaultSymbolicExpressionGrammar {
    66       public TestGrammar()
    67         : base(0, 3, 0, 3) {
    68         Initialize();
    69       }
    70 
    71       private void Initialize() {
    72         var add = new Addition();
    73         var sub = new Subtraction();
    74         var mul = new Multiplication();
    75         var div = new Division();
    76         var terminal = new Terminal();
    77 
    78         var defun = new Defun();
    79         var invoke = new InvokeFunction();
    80 
    81         var allSymbols = new List<Symbol>() { add, sub, mul, div, terminal, invoke };
    82         var functionSymbols = new List<Symbol>() { add, sub, mul, div };
    83         foreach (var symb in allSymbols) {
    84           AddAllowedSymbols(StartSymbol, 0, symb);
    85           AddAllowedSymbols(defun, 0, symb);
    86         }
    87         SetMinSubTreeCount(invoke, 0);
    88         SetMaxSubTreeCount(invoke, 3);
    89         for (int i = 0; i < 3; i++) {
    90           allSymbols.ForEach(s => AddAllowedSymbols(invoke, i, s));
    91         }
    92         SetMinSubTreeCount(terminal, 0);
    93         SetMaxSubTreeCount(terminal, 0);
    94         int maxSubTrees = 3;
    95         foreach (var functionSymbol in functionSymbols) {
    96           SetMinSubTreeCount(functionSymbol, 1);
    97           SetMaxSubTreeCount(functionSymbol, maxSubTrees);
    98           foreach (var childSymbol in allSymbols) {
    99             for (int argumentIndex = 0; argumentIndex < maxSubTrees; argumentIndex++) {
    100               AddAllowedSymbols(functionSymbol, argumentIndex, childSymbol);
    101             }
    102           }
    103         }
    104       }
     57    [TestMethod()]
     58    public void SubroutineCreaterCreateTest() {
     59      foreach (var tree in subroutineTrees)
     60        Assert.IsTrue(grammar.IsValidExpression(tree));
    10561    }
    10662
    10763    [TestMethod()]
    10864    public void SubroutineCreaterSizeDistributionTest() {
    109       int[] histogram = new int[105 / 5];
    110       for (int i = 0; i < subroutineTrees.Count; i++) {
    111         histogram[subroutineTrees[i].Size / 5]++;
    112       }
    113       StringBuilder strBuilder = new StringBuilder();
    114       for (int i = 0; i < histogram.Length; i++) {
    115         strBuilder.Append(Environment.NewLine);
    116         strBuilder.Append("< "); strBuilder.Append((i + 1) * 5);
    117         strBuilder.Append(": "); strBuilder.AppendFormat("{0:#0.00%}", histogram[i] / (double)subroutineTrees.Count);
    118       }
    119       Assert.Inconclusive("Size distribution of SubroutineCreater: " + strBuilder);
     65      Assert.Inconclusive("SubroutineCreater: " + Util.GetSizeDistributionString(subroutineTrees, 105, 5));
    12066    }
    12167
    12268    [TestMethod()]
    12369    public void SubroutineCreaterFunctionDistributionTest() {
    124       Dictionary<Symbol, int> occurances = new Dictionary<Symbol, int>();
    125       double n = 0.0;
    126       for (int i = 0; i < subroutineTrees.Count; i++) {
    127         foreach (var node in subroutineTrees[i].IterateNodesPrefix()) {
    128           if (node.SubTrees.Count > 0) {
    129             if (!occurances.ContainsKey(node.Symbol))
    130               occurances[node.Symbol] = 0;
    131             occurances[node.Symbol]++;
    132             n++;
    133           }
    134         }
    135       }
    136       StringBuilder strBuilder = new StringBuilder();
    137       foreach (var function in occurances.Keys) {
    138         strBuilder.Append(Environment.NewLine);
    139         strBuilder.Append(function.Name); strBuilder.Append(": ");
    140         strBuilder.AppendFormat("{0:#0.00%}", occurances[function] / n);
    141       }
    142       Assert.Inconclusive("Function distribution of SubroutineCreater: " + strBuilder);
     70      Assert.Inconclusive("SubroutineCreater: " + Util.GetFunctionDistributionString(subroutineTrees));
    14371    }
    14472
    14573    [TestMethod()]
    14674    public void SubroutineCreaterNumberOfSubTreesDistributionTest() {
    147       Dictionary<int, int> occurances = new Dictionary<int, int>();
    148       double n = 0.0;
    149       for (int i = 0; i < subroutineTrees.Count; i++) {
    150         foreach (var node in subroutineTrees[i].IterateNodesPrefix()) {
    151           if (!occurances.ContainsKey(node.SubTrees.Count))
    152             occurances[node.SubTrees.Count] = 0;
    153           occurances[node.SubTrees.Count]++;
    154           n++;
    155         }
    156       }
    157       StringBuilder strBuilder = new StringBuilder();
    158       foreach (var arity in occurances.Keys) {
    159         strBuilder.Append(Environment.NewLine);
    160         strBuilder.Append(arity); strBuilder.Append(": ");
    161         strBuilder.AppendFormat("{0:#0.00%}", occurances[arity] / n);
    162       }
    163       Assert.Inconclusive("Distribution of function arities of SubroutineCreater: " + strBuilder);
     75      Assert.Inconclusive("SubroutineCreater: " + Util.GetNumberOfSubTreesDistributionString(subroutineTrees));
    16476    }
    16577
    … …  
    16779    [TestMethod()]
    16880    public void SubroutineCreaterTerminalDistributionTest() {
    169       Dictionary<Symbol, int> occurances = new Dictionary<Symbol, int>();
    170       double n = 0.0;
    171       for (int i = 0; i < subroutineTrees.Count; i++) {
    172         foreach (var node in subroutineTrees[i].IterateNodesPrefix()) {
    173           if (node.SubTrees.Count == 0) {
    174             if (!occurances.ContainsKey(node.Symbol))
    175               occurances[node.Symbol] = 0;
    176             occurances[node.Symbol]++;
    177             n++;
    178           }
    179         }
    180       }
    181       StringBuilder strBuilder = new StringBuilder();
    182       foreach (var function in occurances.Keys) {
    183         strBuilder.Append(Environment.NewLine);
    184         strBuilder.Append(function.Name); strBuilder.Append(": ");
    185         strBuilder.AppendFormat("{0:#0.00%}", occurances[function] / n);
    186       }
    187       Assert.Inconclusive("Terminal distribution of SubroutineCreater: " + strBuilder);
     81      Assert.Inconclusive("SubroutineCreater: " + Util.GetTerminalDistributionString(subroutineTrees));
    18882    }
    18983  }

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

    r3297 r3338  
    1111  [TestClass]
    1212  public class SubtreeCrossoverTest {
    13     public SubtreeCrossoverTest() {
    14     }
     13    private static ISymbolicExpressionGrammar grammar;
     14    private static List<SymbolicExpressionTree> crossoverTrees;
     15    private static double msPerCrossoverEvent;
    1516
    1617    private TestContext testContextInstance;
    … …  
    3435      int populationSize = 1000;
    3536      int generations = 5;
    36       var grammar = new TestGrammar();
     37      int failedEvents = 0;
     38      grammar = Grammars.CreateArithmeticAndAdfGrammar();
    3739      var random = new MersenneTwister();
    3840      for (int i = 0; i < populationSize; i++) {
    39         crossoverTrees.Add(ProbabilisticTreeCreator.Create(random, grammar, 100, 10));
     41        crossoverTrees.Add(ProbabilisticTreeCreator.Create(random, grammar, 100, 10, 3, 3));
    4042      }
    4143      Stopwatch stopwatch = new Stopwatch();
    … …  
    4749          var par1 = (SymbolicExpressionTree)crossoverTrees[random.Next(populationSize)].Clone();
    4850          bool success;
    49           newPopulation.Add(SubtreeCrossover.Cross(random, grammar, par0, par1, 0.9, 100, 10, out success));
     51          newPopulation.Add(SubtreeCrossover.Cross(random, par0, par1, 0.9, 100, 10, out success));
     52          if (!success) failedEvents++;
    5053        }
    5154        crossoverTrees = newPopulation;
    … …  
    5356      stopwatch.Stop();
    5457      foreach (var tree in crossoverTrees)
    55         Assert.IsTrue(grammar.IsValidExpression(tree));
    56       msPerCrossoverEvent = stopwatch.ElapsedMilliseconds / (double)populationSize / (double)generations;
     58        Assert.IsTrue(tree.IsValidExpression());
     59      msPerCrossoverEvent = stopwatch.ElapsedMilliseconds / (double)populationSize / (double)generations;     
    5760    }
    5861
    5962
    6063
    61     private static List<SymbolicExpressionTree> crossoverTrees;
    62     private static double msPerCrossoverEvent;
    63 
    64     private class Addition : Symbol { }
    65     private class Subtraction : Symbol { }
    66     private class Multiplication : Symbol { }
    67     private class Division : Symbol { }
    68     private class Terminal : Symbol { }
    69 
    70     private class TestGrammar : DefaultSymbolicExpressionGrammar {
    71       public TestGrammar()
    72         : base(0, 0, 0, 0) {
    73         Initialize();
    74       }
    75 
    76       private void Initialize() {
    77         var add = new Addition();
    78         var sub = new Subtraction();
    79         var mul = new Multiplication();
    80         var div = new Division();
    81         var terminal = new Terminal();
    82 
    83         var allSymbols = new List<Symbol>() { add, sub, mul, div, terminal };
    84         var functionSymbols = new List<Symbol>() { add, sub, mul, div };
    85         allSymbols.ForEach(s => AddAllowedSymbols(StartSymbol, 0, s));
    86 
    87         SetMinSubTreeCount(terminal, 0);
    88         SetMaxSubTreeCount(terminal, 0);
    89         int maxSubTrees = 3;
    90         foreach (var functionSymbol in functionSymbols) {
    91           SetMinSubTreeCount(functionSymbol, 1);
    92           SetMaxSubTreeCount(functionSymbol, maxSubTrees);
    93           foreach (var childSymbol in allSymbols) {
    94             for (int argumentIndex = 0; argumentIndex < maxSubTrees; argumentIndex++) {
    95               AddAllowedSymbols(functionSymbol, argumentIndex, childSymbol);
    96             }
    97           }
    98         }
    99       }
    100     }
    101 
    10264    [TestMethod()]
    10365    public void SubtreeCrossoverSpeed() {
     66
    10467      Assert.Inconclusive(msPerCrossoverEvent + " ms per crossover event (~" +
    10568        Math.Round(1000.0 / (msPerCrossoverEvent)) + "crossovers / s)");
    … …  
    10770
    10871    [TestMethod()]
    109     public void SubtreeCrossoverSizeDistributionTest() {
    110       int[] histogram = new int[105 / 5];
    111       for (int i = 0; i < crossoverTrees.Count; i++) {
    112         histogram[crossoverTrees[i].Size / 5]++;
    113       }
    114       StringBuilder strBuilder = new StringBuilder();
    115       for (int i = 0; i < histogram.Length; i++) {
    116         strBuilder.Append(Environment.NewLine);
    117         strBuilder.Append("< "); strBuilder.Append((i + 1) * 5);
    118         strBuilder.Append(": "); strBuilder.AppendFormat("{0:#0.00%}", histogram[i] / (double)crossoverTrees.Count);
    119       }
    120       Assert.Inconclusive("Size distribution of SubtreeCrossover: " + strBuilder);
     72    public void SubtreeCrossoverSizeDistributions() {
     73      Assert.Inconclusive("SubtreeCrossover: " + Util.GetSizeDistributionString(crossoverTrees, 105, 5));
    12174    }
    12275
    12376    [TestMethod()]
    12477    public void SubtreeCrossoverFunctionDistributionTest() {
    125       Dictionary<Symbol, int> occurances = new Dictionary<Symbol, int>();
    126       double n = 0.0;
    127       for (int i = 0; i < crossoverTrees.Count; i++) {
    128         foreach (var node in crossoverTrees[i].IterateNodesPrefix()) {
    129           if (node.SubTrees.Count > 0) {
    130             if (!occurances.ContainsKey(node.Symbol))
    131               occurances[node.Symbol] = 0;
    132             occurances[node.Symbol]++;
    133             n++;
    134           }
    135         }
    136       }
    137       StringBuilder strBuilder = new StringBuilder();
    138       foreach (var function in occurances.Keys) {
    139         strBuilder.Append(Environment.NewLine);
    140         strBuilder.Append(function.Name); strBuilder.Append(": ");
    141         strBuilder.AppendFormat("{0:#0.00%}", occurances[function] / n);
    142       }
    143       Assert.Inconclusive("Function distribution of SubtreeCrossover: " + strBuilder);
     78      Assert.Inconclusive("SubtreeCrossover: " + Util.GetFunctionDistributionString(crossoverTrees));
    14479    }
    14580
    14681    [TestMethod()]
    14782    public void SubtreeCrossoverNumberOfSubTreesDistributionTest() {
    148       Dictionary<int, int> occurances = new Dictionary<int, int>();
    149       double n = 0.0;
    150       for (int i = 0; i < crossoverTrees.Count; i++) {
    151         foreach (var node in crossoverTrees[i].IterateNodesPrefix()) {
    152           if (!occurances.ContainsKey(node.SubTrees.Count))
    153             occurances[node.SubTrees.Count] = 0;
    154           occurances[node.SubTrees.Count]++;
    155           n++;
    156         }
    157       }
    158       StringBuilder strBuilder = new StringBuilder();
    159       foreach (var arity in occurances.Keys) {
    160         strBuilder.Append(Environment.NewLine);
    161         strBuilder.Append(arity); strBuilder.Append(": ");
    162         strBuilder.AppendFormat("{0:#0.00%}", occurances[arity] / n);
    163       }
    164       Assert.Inconclusive("Distribution of function arities of SubtreeCrossover: " + strBuilder);
     83      Assert.Inconclusive("SubtreeCrossover: " + Util.GetNumberOfSubTreesDistributionString(crossoverTrees));
    16584    }
    16685
    … …  
    16887    [TestMethod()]
    16988    public void SubtreeCrossoverTerminalDistributionTest() {
    170       Dictionary<Symbol, int> occurances = new Dictionary<Symbol, int>();
    171       double n = 0.0;
    172       for (int i = 0; i < crossoverTrees.Count; i++) {
    173         foreach (var node in crossoverTrees[i].IterateNodesPrefix()) {
    174           if (node.SubTrees.Count == 0) {
    175             if (!occurances.ContainsKey(node.Symbol))
    176               occurances[node.Symbol] = 0;
    177             occurances[node.Symbol]++;
    178             n++;
    179           }
    180         }
    181       }
    182       StringBuilder strBuilder = new StringBuilder();
    183       foreach (var function in occurances.Keys) {
    184         strBuilder.Append(Environment.NewLine);
    185         strBuilder.Append(function.Name); strBuilder.Append(": ");
    186         strBuilder.AppendFormat("{0:#0.00%}", occurances[function] / n);
    187       }
    188       Assert.Inconclusive("Terminal distribution of SubtreeCrossover: " + strBuilder);
     89      Assert.Inconclusive("SubtreeCrossover: " + Util.GetTerminalDistributionString(crossoverTrees));
    18990    }
    19091  }
Note: See TracChangeset for help on using the changeset viewer.