Changeset 5686 for branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs

Timestamp:

03/15/11 13:34:38 (14 years ago)

Author:

mkommend

Message:

#1418: Finally added results from the grammar refactoring.

File:

• branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs (modified) (18 diffs)

branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs

@@ -23 +23 @@
 using System.Collections.Generic;
 using System.Linq;
-using System.Text;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -34 +33 @@
   [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed length")]
   public class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator,
-    ISymbolicExpressionTreeSizeConstraintOperator, ISymbolicExpressionTreeGrammarBasedOperator, ISymbolicExpressionTreeArchitectureAlteringOperator {
+    ISymbolicExpressionTreeSizeConstraintOperator, ISymbolicExpressionTreeGrammarBasedOperator {
     private const int MAX_TRIES = 100;
     private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
     private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
-    private const string MaximumFunctionDefinitionsParameterName = "MaximumFunctionDefinitions";
-    private const string MaximumFunctionArgumentsParameterName = "MaximumFunctionArguments";
     private const string SymbolicExpressionTreeGrammarParameterName = "SymbolicExpressionTreeGrammar";
     #region Parameter Properties
@@ -48 +45 @@
       get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeDepthParameterName]; }
     }
-    public IValueLookupParameter<IntValue> MaximumFunctionDefinitionsParameter {
-      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumFunctionDefinitionsParameterName]; }
-    }
-    public IValueLookupParameter<IntValue> MaximumFunctionArgumentsParameter {
-      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumFunctionArgumentsParameterName]; }
-    }
-    public IValueLookupParameter<ISymbolicExpressionTreeGrammar> SymbolicExpressionTreeGrammarParameter {
-      get { return (IValueLookupParameter<ISymbolicExpressionTreeGrammar>)Parameters[SymbolicExpressionTreeGrammarParameterName]; }
+    public IValueLookupParameter<ISymbolicExpressionGrammar> SymbolicExpressionTreeGrammarParameter {
+      get { return (IValueLookupParameter<ISymbolicExpressionGrammar>)Parameters[SymbolicExpressionTreeGrammarParameterName]; }
     }
     #endregion
@@ -65 +56 @@
       get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
     }
-    public IntValue MaximumFunctionDefinitions {
-      get { return MaximumFunctionDefinitionsParameter.ActualValue; }
-    }
-    public IntValue MaximumFunctionArguments {
-      get { return MaximumFunctionArgumentsParameter.ActualValue; }
-    }
-    public ISymbolicExpressionTreeGrammar SymbolicExpressionTreeGrammar {
+    public ISymbolicExpressionGrammar SymbolicExpressionTreeGrammar {
       get { return SymbolicExpressionTreeGrammarParameter.ActualValue; }
     }
@@ -83 +68 @@
       Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
       Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
-      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumFunctionDefinitionsParameterName, "The maximum allowed number of automatically defined functions."));
-      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumFunctionArgumentsParameterName, "The maximum allowed number of arguments of automatically defined functions."));
-      Parameters.Add(new ValueLookupParameter<ISymbolicExpressionTreeGrammar>(SymbolicExpressionTreeGrammarParameterName, "The tree grammar that defines the correct syntax of symbolic expression trees that should be created."));
+      Parameters.Add(new ValueLookupParameter<ISymbolicExpressionGrammar>(SymbolicExpressionTreeGrammarParameterName, "The tree grammar that defines the correct syntax of symbolic expression trees that should be created."));
     }
 
@@ -93 +76 @@
 
     protected override ISymbolicExpressionTree Create(IRandom random) {
-      return Create(random, SymbolicExpressionTreeGrammar, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value,
-        MaximumFunctionDefinitions.Value, MaximumFunctionArguments.Value);
-    }
-
-    public static ISymbolicExpressionTree Create(IRandom random, ISymbolicExpressionTreeGrammar grammar,
-      int maxTreeLength, int maxTreeDepth,
-      int maxFunctionDefinitions, int maxFunctionArguments
-      ) {
+      return Create(random, SymbolicExpressionTreeGrammar, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value);
+
+    }
+
+    public static ISymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar,
+      int maxTreeLength, int maxTreeDepth) {
       SymbolicExpressionTree tree = new SymbolicExpressionTree();
-      var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
+      var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
       if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);
       rootNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
-      tree.Root = PTC2(random, rootNode, maxTreeLength, maxTreeDepth, maxFunctionDefinitions, maxFunctionArguments);
+      var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
+      startNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
+      if (startNode.HasLocalParameters) startNode.ResetLocalParameters(random);
+      rootNode.AddSubTree(startNode);
+      PTC2(random, startNode, maxTreeLength, maxTreeDepth);
+      tree.Root = rootNode;
       return tree;
     }
@@ -115 +101 @@
     }
 
-    public static ISymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionTreeNode seedNode,
-      int maxLength, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
+    public static void PTC2(IRandom random, ISymbolicExpressionTreeNode seedNode,
+      int maxLength, int maxDepth) {
       // tree length is limited by the grammar and by the explicit size constraints
-      int allowedMinLength = seedNode.Grammar.GetMinExpressionLength(seedNode.Symbol);
-      int allowedMaxLength = Math.Min(maxLength, seedNode.Grammar.GetMaxExpressionLength(seedNode.Symbol));
+      int allowedMinLength = seedNode.Grammar.GetMinimumExpressionLength(seedNode.Symbol);
+      int allowedMaxLength = Math.Min(maxLength, seedNode.Grammar.GetMaximumExpressionLength(seedNode.Symbol));
       int tries = 0;
       while (tries++ < MAX_TRIES) {
@@ -125 +111 @@
         int targetTreeLength;
         targetTreeLength = random.Next(allowedMinLength, allowedMaxLength + 1);
-        if (targetTreeLength <= 1 || maxDepth <= 1) return seedNode;
-
-        bool success = CreateFullTreeFromSeed(random, seedNode, seedNode.Grammar, targetTreeLength, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
+        if (targetTreeLength <= 1 || maxDepth <= 1) return;
+
+        bool success = CreateFullTreeFromSeed(random, seedNode, seedNode.Grammar, targetTreeLength, maxDepth);
 
         // if successful => check constraints and return the tree if everything looks ok        
         if (success && seedNode.GetLength() <= maxLength && seedNode.GetDepth() <= maxDepth) {
-          return seedNode;
+          return;
         } else {
           // clean seedNode
@@ -142 +128 @@
 
     private static bool CreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeGrammar globalGrammar,
-      int targetLength, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
+      int targetLength, int maxDepth) {
       try {
-        TryCreateFullTreeFromSeed(random, root, globalGrammar, targetLength, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
+        TryCreateFullTreeFromSeed(random, root, globalGrammar, targetLength, maxDepth);
         return true;
       }
@@ -151 +137 @@
 
     private static void TryCreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeGrammar globalGrammar,
-      int targetLength, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
+      int targetLength, int maxDepth) {
       List<TreeExtensionPoint> extensionPoints = new List<TreeExtensionPoint>();
       int currentLength = 1;
-      int totalListMinLength = globalGrammar.GetMinExpressionLength(root.Symbol) - 1;
+      int totalListMinLength = globalGrammar.GetMinimumExpressionLength(root.Symbol) - 1;
       int actualArity = SampleArity(random, root, targetLength);
       for (int i = 0; i < actualArity; i++) {
@@ -170 +156 @@
         int argumentIndex = nextExtension.ChildIndex;
         int extensionDepth = nextExtension.ExtensionPointDepth;
-        if (extensionDepth + parent.Grammar.GetMinExpressionDepth(parent.Symbol) >= maxDepth) {
-          ReplaceWithMinimalTree(random, root, parent, argumentIndex, maxFunctionDefinitions, maxFunctionArguments);
+        if (extensionDepth + parent.Grammar.GetMinimumExpressionDepth(parent.Symbol) >= maxDepth) {
+          ReplaceWithMinimalTree(random, root, parent, argumentIndex);
         } else {
           var allowedSymbols = (from s in parent.Grammar.Symbols
-                                where parent.Grammar.IsAllowedChild(parent.Symbol, s, argumentIndex)
-                                where parent.Grammar.GetMinExpressionDepth(s) + extensionDepth - 1 < maxDepth
-                                where parent.Grammar.GetMaxExpressionLength(s) > targetLength - totalListMinLength - currentLength
+                                where parent.Grammar.IsAllowedChildSymbol(parent.Symbol, s, argumentIndex)
+                                where parent.Grammar.GetMinimumExpressionDepth(s) + extensionDepth - 1 < maxDepth
+                                where parent.Grammar.GetMaximumExpressionLength(s) > targetLength - totalListMinLength - currentLength
                                 select s)
                                .ToList();
@@ -186 +172 @@
           parent.InsertSubTree(argumentIndex, newTree);
 
-          InitializeNewTreeNode(random, root, newTree, maxFunctionDefinitions, maxFunctionArguments);
+          var topLevelNode = newTree as SymbolicExpressionTreeTopLevelNode;
+          if (topLevelNode != null)
+            topLevelNode.SetGrammar((ISymbolicExpressionTreeGrammar)root.Grammar.Clone());
 
           currentLength++;
@@ -198 +186 @@
             extensionPoints.Add(new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 });
           }
-          totalListMinLength += newTree.Grammar.GetMinExpressionLength(newTree.Symbol);
+          totalListMinLength += newTree.Grammar.GetMinimumExpressionLength(newTree.Symbol);
         }
       }
@@ -209 +197 @@
         int a = nextExtension.ChildIndex;
         int d = nextExtension.ExtensionPointDepth;
-        ReplaceWithMinimalTree(random, root, parent, a, maxFunctionDefinitions, maxFunctionArguments);
+        ReplaceWithMinimalTree(random, root, parent, a);
       }
     }
 
     private static void ReplaceWithMinimalTree(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode parent,
-      int argumentIndex, int maxFunctionDefinitions, int maxFunctionArguments) {
+      int childIndex) {
       // determine possible symbols that will lead to the smallest possible tree
-      var possibleSymbols = (from s in parent.Grammar.GetAllowedSymbols(parent.Symbol, argumentIndex)
-                             group s by parent.Grammar.GetMinExpressionLength(s) into g
+      var possibleSymbols = (from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)
+                             group s by parent.Grammar.GetMinimumExpressionLength(s) into g
                              orderby g.Key
                              select g).First().ToList();
@@ -224 +212 @@
       var tree = selectedSymbol.CreateTreeNode();
       if (tree.HasLocalParameters) tree.ResetLocalParameters(random);
-      parent.RemoveSubTree(argumentIndex);
-      parent.InsertSubTree(argumentIndex, tree);
-      InitializeNewTreeNode(random, root, tree, maxFunctionDefinitions, maxFunctionArguments);
-      for (int i = 0; i < tree.Grammar.GetMinSubtreeCount(tree.Symbol); i++) {
+      parent.RemoveSubTree(childIndex);
+      parent.InsertSubTree(childIndex, tree);
+
+      var topLevelNode = tree as SymbolicExpressionTreeTopLevelNode;
+      if (topLevelNode != null)
+        topLevelNode.SetGrammar((ISymbolicExpressionTreeGrammar)root.Grammar.Clone());
+
+      for (int i = 0; i < tree.Grammar.GetMinimumSubtreeCount(tree.Symbol); i++) {
         // insert a dummy sub-tree and add the pending extension to the list
         var dummy = new SymbolicExpressionTreeNode();
         tree.AddSubTree(dummy);
         // replace the just inserted dummy by recursive application
-        ReplaceWithMinimalTree(random, root, tree, i, maxFunctionDefinitions, maxFunctionArguments);
-      }
-    }
-
-    private static void InitializeNewTreeNode(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode newTree, int maxFunctionDefinitions, int maxFunctionArguments) {
-      // NB it is assumed that defuns are only allowed as children of root and nowhere else
-      // also assumes that newTree is already attached to root somewhere
-      if (IsTopLevelBranch(root, newTree)) {
-        ((SymbolicExpressionTreeTopLevelNode)newTree).SetGrammar((ISymbolicExpressionTreeGrammar)root.Grammar.Clone());
-
-        // allow invokes of existing ADFs with higher index
-        int argIndex = root.IndexOfSubTree(newTree);
-        for (int i = argIndex + 1; i < root.SubTrees.Count(); i++) {
-          var otherDefunNode = root.GetSubTree(i) as DefunTreeNode;
-          if (otherDefunNode != null) {
-            GrammarModifier.AddDynamicSymbol(newTree.Grammar, newTree.Symbol, otherDefunNode.FunctionName, otherDefunNode.NumberOfArguments);
-          }
-        }
-      }
-      if (newTree.Symbol is Defun) {
-        var defunTree = newTree as DefunTreeNode;
-        string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefinitions * 10 - 1)).ToString(); // >= 100 functions => ###
-        var allowedNames = from index in Enumerable.Range(0, maxFunctionDefinitions)
-                           select "ADF" + index.ToString(formatString);
-        var takenNames = (from node in root.IterateNodesPrefix().OfType<DefunTreeNode>()
-                          select node.FunctionName).Distinct();
-        var remainingNames = allowedNames.Except(takenNames).ToList();
-        string functionName = remainingNames[random.Next(remainingNames.Count)];
-        // set name and number of arguments of the ADF
-        int nArgs = random.Next(maxFunctionArguments);
-        defunTree.FunctionName = functionName;
-        defunTree.NumberOfArguments = nArgs;
-        if (nArgs > 0) {
-          GrammarModifier.AddDynamicArguments(defunTree.Grammar, defunTree.Symbol, Enumerable.Range(0, nArgs));
-        }
-        // in existing branches with smaller index allow invoke of current function
-        int argIndex = root.IndexOfSubTree(newTree);
-        for (int i = 0; i < argIndex; i++) {
-          // if not dummy node
-          if (root.GetSubTree(i).Symbol != null) {
-            var existingBranch = root.GetSubTree(i);
-            GrammarModifier.AddDynamicSymbol(existingBranch.Grammar, existingBranch.Symbol, functionName, nArgs);
-          }
-        }
+        ReplaceWithMinimalTree(random, root, tree, i);
       }
     }
@@ -285 +234 @@
     private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetLength) {
       // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
-      int minArity = node.Grammar.GetMinSubtreeCount(node.Symbol);
-      int maxArity = node.Grammar.GetMaxSubtreeCount(node.Symbol);
+      int minArity = node.Grammar.GetMinimumSubtreeCount(node.Symbol);
+      int maxArity = node.Grammar.GetMaximumSubtreeCount(node.Symbol);
       if (maxArity > targetLength) {
         maxArity = targetLength;
@@ -294 +243 @@
       long aggregatedLongestExpressionLength = 0;
       for (int i = 0; i < maxArity; i++) {
-        aggregatedLongestExpressionLength += (from s in node.Grammar.GetAllowedSymbols(node.Symbol, i)
-                                              select node.Grammar.GetMaxExpressionLength(s)).Max();
+        aggregatedLongestExpressionLength += (from s in node.Grammar.GetAllowedChildSymbols(node.Symbol, i)
+                                              select node.Grammar.GetMaximumExpressionLength(s)).Max();
         if (aggregatedLongestExpressionLength < targetLength) minArity = i;
         else break;
@@ -304 +253 @@
       long aggregatedShortestExpressionLength = 0;
       for (int i = 0; i < maxArity; i++) {
-        aggregatedShortestExpressionLength += (from s in node.Grammar.GetAllowedSymbols(node.Symbol, i)
-                                               select node.Grammar.GetMinExpressionLength(s)).Min();
+        aggregatedShortestExpressionLength += (from s in node.Grammar.GetAllowedChildSymbols(node.Symbol, i)
+                                               select node.Grammar.GetMinimumExpressionLength(s)).Min();
         if (aggregatedShortestExpressionLength > targetLength) {
           maxArity = i;