Changeset 14355

Timestamp:

10/23/16 19:50:36 (7 years ago)

Author:

bburlacu

Message:

#2685: Add correction step to account for grammar cycles. Update unit test/

Location:

trunk/sources

Files:

• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs (modified) (5 diffs)
• HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/GrammarsTest.cs (modified) (3 diffs)

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs

@@ -66 +66 @@
                 continue;
 
-              if (visited.Add(childSymbol)) {
+              if (visited.Add(childSymbol))
                 numberedSymbols.Add(Tuple.Create(childSymbol, ++index));
-              }
             }
           }
@@ -88 +87 @@
             minLength = Math.Min(minLength, oldLength);
           minimumExpressionLengths[symbol.Name] = (int)Math.Min(int.MaxValue, minLength);
+        }
+        // correction step for cycles
+        bool changed = true;
+        while (changed) {
+          changed = false;
+          foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
+            long minLength = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))
+              .Sum(x => grammar.GetAllowedChildSymbols(symbol, x)
+              .Min(s => (long)minimumExpressionLengths[s.Name])) + 1;
+            if (minLength < minimumExpressionLengths[symbol.Name]) {
+              minimumExpressionLengths[symbol.Name] = (int)Math.Min(minLength, int.MaxValue);
+              changed = true;
+            }
+          }
         }
       }
@@ -121 +134 @@
                 continue;
 
-              if (visited.Add(childSymbol)) {
+              if (visited.Add(childSymbol))
                 numberedSymbols.Add(Tuple.Create(childSymbol, ++index));
-              }
             }
           }
@@ -132 +144 @@
         // going bottom-up (reverse breadth order), we ensure depths are calculated bottom-up
         foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
-          long minDepth = int.MaxValue;
+          long minDepth = -1;
           for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
             long depth = grammar.GetAllowedChildSymbols(symbol, argIndex)
               .Where(x => minimumExpressionDepths.ContainsKey(x.Name))
-              .Select(x => minimumExpressionDepths[x.Name]).DefaultIfEmpty(int.MaxValue).Min();
-            minDepth = Math.Min(minDepth, depth + 1);
+              .Select(x => (long)minimumExpressionDepths[x.Name]).DefaultIfEmpty(int.MaxValue).Min() + 1;
+            minDepth = Math.Max(minDepth, depth);
           }
           int oldDepth;
@@ -143 +155 @@
             minDepth = Math.Min(minDepth, oldDepth);
           minimumExpressionDepths[symbol.Name] = (int)Math.Min(int.MaxValue, minDepth);
+        }
+        // correction step for cycles
+        bool changed = true;
+        while (changed) {
+          changed = false;
+          foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
+            long minDepth = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))
+              .Max(x => grammar.GetAllowedChildSymbols(symbol, x)
+              .Min(s => (long)minimumExpressionDepths[s.Name])) + 1;
+            if (minDepth < minimumExpressionDepths[symbol.Name]) {
+              minimumExpressionDepths[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
+              changed = true;
+            }
+          }
         }
       }

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

@@ -87 +87 @@
         Assert.AreEqual(2, grammar.GetMinimumExpressionLength(y));
       }
+
+      {
+        var grammar = CreateTestGrammar6();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        var s_ = grammar.Symbols.First(s => s.Name == "<s>");
+        var a = grammar.Symbols.First(s => s.Name == "<a>");
+        var b = grammar.Symbols.First(s => s.Name == "<b>");
+        var c = grammar.Symbols.First(s => s.Name == "<c>");
+        var d = grammar.Symbols.First(s => s.Name == "<d>");
+        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(prs));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(ss));
+        Assert.AreEqual(2, grammar.GetMinimumExpressionLength(x));
+        Assert.AreEqual(5, grammar.GetMinimumExpressionLength(s_));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(a));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(b));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(c));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(d));
+      }
     }
 
@@ -170 +190 @@
         Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(y));
       }
+
+      {
+        var grammar = CreateTestGrammar6();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        var s_ = grammar.Symbols.First(s => s.Name == "<s>");
+        var a = grammar.Symbols.First(s => s.Name == "<a>");
+        var b = grammar.Symbols.First(s => s.Name == "<b>");
+        var c = grammar.Symbols.First(s => s.Name == "<c>");
+        var d = grammar.Symbols.First(s => s.Name == "<d>");
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(prs));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(ss));
+        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(x));
+        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(s_));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(a));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(b));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(c));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(d));
+      }
     }
 
@@ -286 +326 @@
       return grammar;
     }
+
+    private static ISymbolicExpressionGrammar CreateTestGrammar6() {
+      var grammar = new SimpleSymbolicExpressionGrammar();
+      var x = new SimpleSymbol("<x>", 1);
+      var s = new SimpleSymbol("<s>", 1);
+      var a = new SimpleSymbol("<a>", 1);
+      var b = new SimpleSymbol("<b>", 1);
+      var c = new SimpleSymbol("<c>", 1);
+      var d = new SimpleSymbol("<d>", 1);
+      var e = new SimpleSymbol("<e>", 1);
+
+      var _x = new SimpleSymbol("x", 0);
+      var _y = new SimpleSymbol("y", 0);
+
+      grammar.AddSymbol(x);
+      grammar.AddSymbol(s);
+      grammar.AddSymbol(a);
+      grammar.AddSymbol(b);
+      grammar.AddSymbol(c);
+      grammar.AddSymbol(d);
+      grammar.AddSymbol(e);
+      grammar.AddSymbol(_x);
+      grammar.AddSymbol(_y);
+
+      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
+      grammar.AddAllowedChildSymbol(x, s);
+      grammar.AddAllowedChildSymbol(x, _x);
+      grammar.AddAllowedChildSymbol(s, a);
+      grammar.AddAllowedChildSymbol(a, b);
+      grammar.AddAllowedChildSymbol(a, c);
+      grammar.AddAllowedChildSymbol(b, x);
+      grammar.AddAllowedChildSymbol(c, d);
+      grammar.AddAllowedChildSymbol(d, e);
+      grammar.AddAllowedChildSymbol(e, _y);
+
+      return grammar;
+    }
   }
 }