Changeset 7076

Timestamp:

11/25/11 15:25:54 (12 years ago)

Author:

mkommend

Message:

#1654: Corrected tree creators for symbolic expression encoding.

Location:

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4

Files:

• Creators/FullTreeCreator.cs (modified) (4 diffs)
• Creators/GrowTreeCreator.cs (modified) (2 diffs)
• Interfaces/ISymbolicExpressionGrammarBase.cs (modified) (1 diff)
• SymbolicExpressionGrammarBase.cs (modified) (5 diffs)

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/FullTreeCreator.cs

@@ -63 +63 @@
       get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
     }
-    
+
     public IntValue MaximumSymbolicExpressionTreeLength {
       get { return MaximumSymbolicExpressionTreeLengthParameter.ActualValue; }
@@ -107 +107 @@
 
     public override ISymbolicExpressionTree CreateTree(IRandom random, ISymbolicExpressionGrammar grammar, int maxTreeLength, int maxTreeDepth) {
-     return Create(random, grammar, maxTreeLength, maxTreeDepth);
+      return Create(random, grammar, maxTreeLength, maxTreeDepth);
     }
 
@@ -149 +149 @@
 
       for (var i = 0; i != arity; ++i) {
-        var possibleSymbols = seedNode.Grammar.GetAllowedChildSymbols(seedNode.Symbol,i).Where(s => s.InitialFrequency > 0.0 && seedNode.Grammar.GetMaximumSubtreeCount(s) > 0);
+        var possibleSymbols = seedNode.Grammar.GetAllowedChildSymbols(seedNode.Symbol, i).Where(s => s.InitialFrequency > 0.0 && seedNode.Grammar.GetMaximumSubtreeCount(s) > 0);
         var selectedSymbol = possibleSymbols.SelectRandom(random);
         var tree = selectedSymbol.CreateTreeNode();
@@ -168 +168 @@
         throw new ArgumentException("Cannot grow node of arity zero. Expected a function node.");
 
+      for (var i = 0; i != arity; ++i) {
+        var possibleSymbols = root.Grammar.GetAllowedChildSymbols(root.Symbol, i);
+        possibleSymbols = possibleSymbols.Where(s => s.InitialFrequency > 0.0 &&
+                                          root.Grammar.GetMinimumExpressionDepth(s) - 1 <= maxDepth - currentDepth &&
+                                          root.Grammar.GetMaximumExpressionDepth(s) > maxDepth - currentDepth);
 
-      for (var i = 0; i != arity; ++i) {
-        var possibleSymbols = currentDepth < maxDepth ?
-          root.Grammar.GetAllowedChildSymbols(root.Symbol,i).Where(s => s.InitialFrequency > 0.0 && root.Grammar.GetMaximumSubtreeCount(s) > 0) :
-          root.Grammar.GetAllowedChildSymbols(root.Symbol,i).Where(s => s.InitialFrequency > 0.0 && root.Grammar.GetMaximumSubtreeCount(s) == 0);
+
+        if (!possibleSymbols.Any()) throw new InvalidOperationException("No symbols are available for the tree.");
         var selectedSymbol = possibleSymbols.SelectRandom(random);
         var tree = selectedSymbol.CreateTreeNode();

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/GrowTreeCreator.cs

@@ -64 +64 @@
     }
 
-    public IntValue MaximumSymbolicExpressionTreeLength { 
+    public IntValue MaximumSymbolicExpressionTreeLength {
       get { return MaximumSymbolicExpressionTreeLengthParameter.ActualValue; }
     }
@@ -166 +166 @@
         throw new ArgumentException("Cannot grow node of arity zero. Expected a function node.");
 
-
       for (var i = 0; i != arity; ++i) {
-        var possibleSymbols = currentDepth < maxDepth
-                                ? root.Grammar.GetAllowedChildSymbols(root.Symbol,i).Where(s => s.InitialFrequency > 0.0)
-                                : root.Grammar.GetAllowedChildSymbols(root.Symbol,i).Where(
-                                  s => s.InitialFrequency > 0.0 && root.Grammar.GetMaximumSubtreeCount(s) == 0);
+        var possibleSymbols = root.Grammar.GetAllowedChildSymbols(root.Symbol, i);
+        possibleSymbols = possibleSymbols.Where(s => s.InitialFrequency > 0.0 &&
+                                          root.Grammar.GetMinimumExpressionDepth(s) - 1 <= maxDepth - currentDepth);
+        if (!possibleSymbols.Any()) throw new InvalidOperationException("No symbols are available for the tree.");
         var selectedSymbol = possibleSymbols.SelectRandom(random);
         var tree = selectedSymbol.CreateTreeNode();

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionGrammarBase.cs

@@ -40 +40 @@
 
     int GetMinimumExpressionDepth(ISymbol start);
+    int GetMaximumExpressionDepth(ISymbol start);
     int GetMinimumExpressionLength(ISymbol start);
     int GetMaximumExpressionLength(ISymbol start, int maxDepth);

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionGrammarBase.cs

@@ -82 +82 @@
       cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
       cachedMinExpressionDepth = new Dictionary<string, int>();
+      cachedMaxExpressionDepth = new Dictionary<string, int>();
 
       cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
@@ -94 +95 @@
       cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
       cachedMinExpressionDepth = new Dictionary<string, int>();
+      cachedMaxExpressionDepth = new Dictionary<string, int>();
 
       cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
@@ -117 +119 @@
       cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
       cachedMinExpressionDepth = new Dictionary<string, int>();
+      cachedMaxExpressionDepth = new Dictionary<string, int>();
 
       cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
@@ -372 +375 @@
       cachedMaxExpressionLength.Clear();
       cachedMinExpressionDepth.Clear();
+      cachedMaxExpressionDepth.Clear();
 
       cachedIsAllowedChildSymbol.Clear();
@@ -428 +432 @@
     }
 
+    private readonly Dictionary<string, int> cachedMaxExpressionDepth;
+    public int GetMaximumExpressionDepth(ISymbol symbol) {
+      int temp;
+      if (!cachedMaxExpressionDepth.TryGetValue(symbol.Name, out temp)) {
+        cachedMaxExpressionDepth[symbol.Name] = int.MaxValue;
+        long maxDepth = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
+                             let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
+                                                     where s.InitialFrequency > 0.0
+                                                     select GetMaximumExpressionDepth(s)).DefaultIfEmpty(0).Max()
+                             select maxForSlot).DefaultIfEmpty(0).Max();
+        cachedMaxExpressionDepth[symbol.Name] = (int)Math.Min(maxDepth, int.MaxValue);
+        return cachedMaxExpressionDepth[symbol.Name];
+      }
+      return temp;
+    }
+
     public event EventHandler Changed;
     protected virtual void OnChanged() {