Changeset 6911

Timestamp:

10/12/11 17:06:14 (13 years ago)

Author:

mkommend

Message:

#1657: Corrected and adapted implementation of !PTC2 to handle symbol frequencies correctly and to always create trees of the target size. Additionally the performance of the grammars have been improved and a unit test was added.

Location:

trunk/sources

Files:

• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs (modified) (13 diffs)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionGrammarBase.cs (modified) (1 diff)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionGrammarBase.cs (modified) (7 diffs)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeGrammar.cs (modified) (2 diffs)
• HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/ProbabilisticTreeCreaterTest.cs (modified) (1 diff)
• HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/Util.cs (modified) (2 diffs)
• HeuristicLab.Tests/HeuristicLab.Tests.csproj (modified) (1 diff)
• HeuristicLab.Tests/Test References/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.accessor (added)

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

@@ -120 +120 @@
       public int ChildIndex { get; set; }
       public int ExtensionPointDepth { get; set; }
+      public int MaximumExtensionLength { get; set; }
+      public int MinimumExtensionLength { get; set; }
     }
 
@@ -132 +134 @@
       // tree length is limited by the grammar and by the explicit size constraints
       int allowedMinLength = seedNode.Grammar.GetMinimumExpressionLength(seedNode.Symbol);
-      int allowedMaxLength = Math.Min(maxLength, seedNode.Grammar.GetMaximumExpressionLength(seedNode.Symbol));
+      int allowedMaxLength = Math.Min(maxLength, seedNode.Grammar.GetMaximumExpressionLength(seedNode.Symbol, maxDepth));
       int tries = 0;
       while (tries++ < MAX_TRIES) {
@@ -140 +142 @@
         if (targetTreeLength <= 1 || maxDepth <= 1) return;
 
-        bool success = TryCreateFullTreeFromSeed(random, seedNode, seedNode.Grammar, targetTreeLength, maxDepth);
+        bool success = TryCreateFullTreeFromSeed(random, seedNode, targetTreeLength - 1, maxDepth - 1);
 
         // if successful => check constraints and return the tree if everything looks ok        
@@ -154 +156 @@
     }
 
-    private static bool TryCreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeGrammar globalGrammar,
+    private static bool TryCreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root,
       int targetLength, int maxDepth) {
       List<TreeExtensionPoint> extensionPoints = new List<TreeExtensionPoint>();
-      int currentLength = 1;
-      int totalListMinLength = globalGrammar.GetMinimumExpressionLength(root.Symbol) - 1;
-      int actualArity = SampleArity(random, root, targetLength);
+      int currentLength = 0;
+      int actualArity = SampleArity(random, root, targetLength, maxDepth);
       if (actualArity < 0) return false;
 
@@ -166 +167 @@
         var dummy = new SymbolicExpressionTreeNode();
         root.AddSubtree(dummy);
-        extensionPoints.Add(new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 0 });
-      }
+        var x = new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 0 };
+        FillExtensionLengths(x, maxDepth);
+        extensionPoints.Add(x);
+      }
+      long minExtensionPointsLength = extensionPoints.Select(x => x.MinimumExtensionLength).Sum();
+      long maxExtensionPointsLength = extensionPoints.Select(x => x.MaximumExtensionLength).Sum();
+
       // while there are pending extension points and we have not reached the limit of adding new extension points
-      while (extensionPoints.Count > 0 && totalListMinLength + currentLength < targetLength) {
+      while (extensionPoints.Count > 0 && minExtensionPointsLength + currentLength <= targetLength) {
         int randomIndex = random.Next(extensionPoints.Count);
         TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
@@ -176 +182 @@
         int argumentIndex = nextExtension.ChildIndex;
         int extensionDepth = nextExtension.ExtensionPointDepth;
-        if (parent.Grammar.GetMinimumExpressionDepth(parent.Symbol) >= maxDepth - extensionDepth) {
+
+        if (parent.Grammar.GetMinimumExpressionDepth(parent.Symbol) > maxDepth - extensionDepth) {
           ReplaceWithMinimalTree(random, root, parent, argumentIndex);
+          int insertedTreeLength = parent.GetSubtree(argumentIndex).GetLength();
+          currentLength += insertedTreeLength;
+          minExtensionPointsLength -= insertedTreeLength;
+          maxExtensionPointsLength -= insertedTreeLength;
         } else {
-          var allowedSymbols = (from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, argumentIndex)
-                                where s.InitialFrequency > 0.0
-                                where parent.Grammar.GetMinimumExpressionDepth(s) < maxDepth - extensionDepth + 1
-                                where parent.Grammar.GetMaximumExpressionLength(s) > targetLength - totalListMinLength - currentLength
-                                select s)
-                               .ToList();
+          //remove currently chosen extension point from calculation
+          minExtensionPointsLength -= nextExtension.MinimumExtensionLength;
+          maxExtensionPointsLength -= nextExtension.MaximumExtensionLength;
+
+          var symbols = from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, argumentIndex)
+                        where s.InitialFrequency > 0.0
+                        where parent.Grammar.GetMinimumExpressionDepth(s) <= maxDepth - extensionDepth
+                        where parent.Grammar.GetMinimumExpressionLength(s) <= targetLength - currentLength - minExtensionPointsLength
+                        select s;
+          if (maxExtensionPointsLength < targetLength - currentLength)
+            symbols = from s in symbols
+                      where parent.Grammar.GetMaximumExpressionLength(s, maxDepth - extensionDepth) >= targetLength - currentLength - maxExtensionPointsLength
+                      select s;
+          var allowedSymbols = symbols.ToList();
+
           if (allowedSymbols.Count == 0) return false;
           var weights = allowedSymbols.Select(x => x.InitialFrequency).ToList();
@@ -198 +218 @@
 
           currentLength++;
-          totalListMinLength--;
-
-          actualArity = SampleArity(random, newTree, targetLength - currentLength);
+          actualArity = SampleArity(random, newTree, targetLength - currentLength, maxDepth - extensionDepth);
           if (actualArity < 0) return false;
           for (int i = 0; i < actualArity; i++) {
@@ -206 +224 @@
             var dummy = new SymbolicExpressionTreeNode();
             newTree.AddSubtree(dummy);
-            extensionPoints.Add(new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 });
+            var x = new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 };
+            FillExtensionLengths(x, maxDepth);
+            extensionPoints.Add(x);
+            maxExtensionPointsLength += x.MaximumExtensionLength;
+            minExtensionPointsLength += x.MinimumExtensionLength;
           }
-          totalListMinLength += newTree.Grammar.GetMinimumExpressionLength(newTree.Symbol);
         }
       }
@@ -218 +239 @@
         ISymbolicExpressionTreeNode parent = nextExtension.Parent;
         int a = nextExtension.ChildIndex;
-        int d = nextExtension.ExtensionPointDepth;
         ReplaceWithMinimalTree(random, root, parent, a);
       }
@@ -252 +272 @@
     }
 
-    private static bool IsTopLevelBranch(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode branch) {
-      return branch is SymbolicExpressionTreeTopLevelNode;
-    }
-
-    private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetLength) {
+    private static void FillExtensionLengths(TreeExtensionPoint extension, int maxDepth) {
+      var grammar = extension.Parent.Grammar;
+      int maxLength = int.MinValue;
+      int minLength = int.MaxValue;
+      foreach (ISymbol s in grammar.GetAllowedChildSymbols(extension.Parent.Symbol, extension.ChildIndex)) {
+        if (s.InitialFrequency > 0.0) {
+          int max = grammar.GetMaximumExpressionLength(s, maxDepth - extension.ExtensionPointDepth);
+          maxLength = Math.Max(maxLength, max);
+          int min = grammar.GetMinimumExpressionLength(s);
+          minLength = Math.Min(minLength, min);
+        }
+      }
+
+      extension.MaximumExtensionLength = maxLength;
+      extension.MinimumExtensionLength = minLength;
+    }
+
+    private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetLength, int maxDepth) {
       // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
       int minArity = node.Grammar.GetMinimumSubtreeCount(node.Symbol);
@@ -263 +296 @@
         maxArity = targetLength;
       }
+      if (minArity == maxArity) return minArity;
+
       // the min number of sub-trees has to be set to a value that is large enough so that the largest possible tree is at least tree length
       // if 1..3 trees are possible and the largest possible first sub-tree is smaller larger than the target length then minArity should be at least 2
@@ -269 +304 @@
         aggregatedLongestExpressionLength += (from s in node.Grammar.GetAllowedChildSymbols(node.Symbol, i)
                                               where s.InitialFrequency > 0.0
-                                              select node.Grammar.GetMaximumExpressionLength(s)).Max();
+                                              select node.Grammar.GetMaximumExpressionLength(s, maxDepth)).Max();
         if (i > minArity && aggregatedLongestExpressionLength < targetLength) minArity = i + 1;
         else break;
@@ -289 +324 @@
       return random.Next(minArity, maxArity + 1);
     }
+
   }
 }

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

@@ -39 +39 @@
     int GetMaximumSubtreeCount(ISymbol symbol);
 
+    int GetMinimumExpressionDepth(ISymbol start);
     int GetMinimumExpressionLength(ISymbol start);
-    int GetMaximumExpressionLength(ISymbol start);
-    int GetMinimumExpressionDepth(ISymbol start);
+    int GetMaximumExpressionLength(ISymbol start, int maxDepth);
 
     event EventHandler Changed;

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

@@ -80 +80 @@
       : base(deserializing) {
       cachedMinExpressionLength = new Dictionary<string, int>();
-      cachedMaxExpressionLength = new Dictionary<string, int>();
+      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
       cachedMinExpressionDepth = new Dictionary<string, int>();
 
@@ -92 +92 @@
       : base(original, cloner) {
       cachedMinExpressionLength = new Dictionary<string, int>();
-      cachedMaxExpressionLength = new Dictionary<string, int>();
+      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
       cachedMinExpressionDepth = new Dictionary<string, int>();
 
@@ -115 +115 @@
       : base(name, description) {
       cachedMinExpressionLength = new Dictionary<string, int>();
-      cachedMaxExpressionLength = new Dictionary<string, int>();
+      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
       cachedMinExpressionDepth = new Dictionary<string, int>();
 
@@ -348 +348 @@
     }
 
-    public virtual IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
-      List<string> childs;
-      if (!allowedChildSymbols.TryGetValue(parent.Name, out childs))
-        return Enumerable.Empty<ISymbol>();
-
-      return childs.Select(GetSymbol).Where(s => s.Enabled);
-    }
-
-    public virtual IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
-      var result = Enumerable.Empty<string>();
-
-      List<string> temp;
-      if (allowedChildSymbols.TryGetValue(parent.Name, out temp))
-        result = result.Union(temp);
-      var key = Tuple.Create(parent.Name, argumentIndex);
-      if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp))
-        result = result.Union(temp);
-
-      return result.Select(GetSymbol).Where(s => s.Enabled);
+    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
+      return from child in AllowedSymbols
+             where IsAllowedChildSymbol(parent, child)
+             select child;
+    }
+
+    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
+      return from child in AllowedSymbols
+             where IsAllowedChildSymbol(parent, child, argumentIndex)
+             select child;
     }
 
@@ -392 +383 @@
         long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
                                               let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
+                                                                      where s.InitialFrequency > 0.0
                                                                       select GetMinimumExpressionLength(s)).DefaultIfEmpty(0).Min()
                                               select minForSlot).DefaultIfEmpty(0).Sum();
@@ -401 +393 @@
     }
 
-    private readonly Dictionary<string, int> cachedMaxExpressionLength;
-    public int GetMaximumExpressionLength(ISymbol symbol) {
+    private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength;
+    public int GetMaximumExpressionLength(ISymbol symbol, int maxDepth) {
       int temp;
-      if (!cachedMaxExpressionLength.TryGetValue(symbol.Name, out temp)) {
-        cachedMaxExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
+      var key = Tuple.Create(symbol.Name, maxDepth);
+      if (!cachedMaxExpressionLength.TryGetValue(key, out temp)) {
+        cachedMaxExpressionLength[key] = int.MaxValue; // prevent infinite recursion
         long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
                                   let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
-                                                          select GetMaximumExpressionLength(s)).DefaultIfEmpty(0).Max()
+                                                          where s.InitialFrequency > 0.0
+                                                          where GetMinimumExpressionDepth(s) < maxDepth
+                                                          select GetMaximumExpressionLength(s, maxDepth - 1)).DefaultIfEmpty(0).Max()
                                   select maxForSlot).DefaultIfEmpty(0).Sum();
-        cachedMaxExpressionLength[symbol.Name] = (int)Math.Min(sumOfMaxTrees, int.MaxValue);
-        return cachedMaxExpressionLength[symbol.Name];
+        cachedMaxExpressionLength[key] = (int)Math.Min(sumOfMaxTrees, int.MaxValue);
+        return cachedMaxExpressionLength[key];
       }
       return temp;
@@ -423 +418 @@
         long minDepth = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
                              let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
+                                                     where s.InitialFrequency > 0.0
                                                      select GetMinimumExpressionDepth(s)).DefaultIfEmpty(0).Min()
                              select minForSlot).DefaultIfEmpty(0).Max();

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

@@ -80 +80 @@
       return grammar.IsAllowedChildSymbol(parent, child, argumentIndex) || base.IsAllowedChildSymbol(parent, child, argumentIndex);
     }
-    public override IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
-      var symbols = grammar.GetAllowedChildSymbols(parent).Union(base.GetAllowedChildSymbols(parent));
-      return symbols.SelectMany(s => s.Flatten()).Where(s => s.Enabled).Distinct();
-    }
-    public override IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
-      var symbols = grammar.GetAllowedChildSymbols(parent, argumentIndex).Union(base.GetAllowedChildSymbols(parent, argumentIndex));
-      return symbols.SelectMany(s => s.Flatten()).Where(s => s.Enabled).Distinct();
-    }
 
     public override int GetMinimumSubtreeCount(ISymbol symbol) {
@@ -122 +114 @@
       base.SetSubtreeCount(symbol, minimumSubtreeCount, maximumSubtreeCount);
     }
+
+    int ISymbolicExpressionGrammarBase.GetMinimumExpressionDepth(ISymbol symbol) {
+      if (symbols.Count == 0) return grammar.GetMinimumExpressionDepth(symbol);
+      else return base.GetMinimumExpressionDepth(symbol);
+    }
+    int ISymbolicExpressionGrammarBase.GetMinimumExpressionLength(ISymbol symbol) {
+      if (symbols.Count == 0) return grammar.GetMinimumExpressionLength(symbol);
+      else return base.GetMinimumExpressionLength(symbol);
+    }
+    int ISymbolicExpressionGrammarBase.GetMaximumExpressionLength(ISymbol symbol, int maxDepth) {
+      if (symbols.Count == 0) return grammar.GetMaximumExpressionLength(symbol, maxDepth);
+      else return base.GetMaximumExpressionLength(symbol, maxDepth);
+    }
   }
 }

trunk/sources/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/ProbabilisticTreeCreaterTest.cs

@@ -72 +72 @@
         Util.GetTerminalDistributionString(randomTrees) + Environment.NewLine
         );
-      Assert.IsTrue(Math.Round(1000.0 / (msPerRandomTreeCreation)) > 300); // must achieve more than 500 random trees / s
+      Assert.IsTrue(Math.Round(1000.0 / (msPerRandomTreeCreation)) > 250); // must achieve more than 250 random trees / s
+    }
+
+    [TestMethod]
+    public void ProbabilisticTreeCreatorSpecificTreeSizesTest() {
+      var trees = new List<ISymbolicExpressionTree>();
+      var grammar = Grammars.CreateSimpleArithmeticGrammar();
+      var random = new MersenneTwister(31415);
+      var treeGrammarType = SymbolicExpressionTreeGrammar_Accessor.ShadowedType.ReferencedType;
+
+
+      for (int targetTreeSize = 1; targetTreeSize <= 100; targetTreeSize++) {
+        var tree = new SymbolicExpressionTree();
+        var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
+        rootNode.SetGrammar((ISymbolicExpressionTreeGrammar)Activator.CreateInstance(treeGrammarType, grammar));
+        if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);
+        var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
+        startNode.SetGrammar((ISymbolicExpressionTreeGrammar)Activator.CreateInstance(treeGrammarType, grammar));
+        if (startNode.HasLocalParameters) startNode.ResetLocalParameters(random);
+        rootNode.AddSubtree(startNode);
+
+        ProbabilisticTreeCreator_Accessor.TryCreateFullTreeFromSeed(random, startNode, targetTreeSize, ((int)Math.Log(targetTreeSize, 2)) + 1);
+        tree.Root = rootNode;
+        Assert.AreEqual(targetTreeSize + 2, tree.Length);  //the root and start node must be additionally added
+      }
     }
   }

trunk/sources/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/Util.cs

@@ -154 +154 @@
       Assert.IsTrue(grammar.Symbols.Count() == grammar.Symbols.Distinct().Count());
       foreach (ISymbol symbol in grammar.AllowedSymbols) {
-        Assert.IsTrue(grammar.GetMinimumSubtreeCount(symbol) <= grammar.GetMaximumExpressionLength(symbol));
         Assert.IsTrue(grammar.GetAllowedChildSymbols(symbol).Count() == grammar.GetAllowedChildSymbols(symbol).Distinct().Count());
         for (int i = 0; i < grammar.GetMaximumSubtreeCount(symbol); i++) {
@@ -165 +164 @@
         for (int i = 0; i < grammar.GetMaximumSubtreeCount(symbol); i++)
           Assert.IsTrue(grammar.GetAllowedChildSymbols(symbol, i).Any());
-
-        //if (symbol is ProgramRootSymbol) continue;
-        ////check if symbol is allowed as at least one child symbol
-        //bool result = false;
-        //foreach (var parentSymbol in grammar.Symbols) {
-        //  if (result) break;
-        //  for (int i = 0; i < grammar.GetMaximumSubtreeCount(parentSymbol); i++)
-        //    result = result || grammar.IsAllowedChildSymbol(parentSymbol, symbol, i);
-        //}
-        //Assert.IsTrue(result);
-
       }
     }

trunk/sources/HeuristicLab.Tests/HeuristicLab.Tests.csproj

@@ -424 +424 @@
     <EmbeddedResource Include="HeuristicLab.Problems.QuadraticAssignment-3.3\QAPLIB\wil50.dat" />
     <None Include="HeuristicLab.snk" />
+    <Shadow Include="Test References\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.accessor" />
     <Shadow Include="Test References\HeuristicLab.PluginInfrastructure-3.3.accessor" />
     <Shadow Include="Test References\HeuristicLab.MainForm.WindowsForms-3.3.accessor" />