Changeset 14353 for trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding

Timestamp:

10/23/16 19:31:18 (8 years ago)

Author:

bburlacu

Message:

#2685: Add correction step for values miscalculated due to cyclical symbol dependencies in the grammar. Updated unit test.

File:

• trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs (modified) (5 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;
+            }
+          }
         }
       }