Changeset 14355


Ignore:
Timestamp:
10/23/16 19:50:36 (3 years ago)
Author:
bburlacu
Message:

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

Location:
trunk/sources
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs

    r14354 r14355  
    6666                continue;
    6767
    68               if (visited.Add(childSymbol)) {
     68              if (visited.Add(childSymbol))
    6969                numberedSymbols.Add(Tuple.Create(childSymbol, ++index));
    70               }
    7170            }
    7271          }
     
    8887            minLength = Math.Min(minLength, oldLength);
    8988          minimumExpressionLengths[symbol.Name] = (int)Math.Min(int.MaxValue, minLength);
     89        }
     90        // correction step for cycles
     91        bool changed = true;
     92        while (changed) {
     93          changed = false;
     94          foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
     95            long minLength = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))
     96              .Sum(x => grammar.GetAllowedChildSymbols(symbol, x)
     97              .Min(s => (long)minimumExpressionLengths[s.Name])) + 1;
     98            if (minLength < minimumExpressionLengths[symbol.Name]) {
     99              minimumExpressionLengths[symbol.Name] = (int)Math.Min(minLength, int.MaxValue);
     100              changed = true;
     101            }
     102          }
    90103        }
    91104      }
     
    121134                continue;
    122135
    123               if (visited.Add(childSymbol)) {
     136              if (visited.Add(childSymbol))
    124137                numberedSymbols.Add(Tuple.Create(childSymbol, ++index));
    125               }
    126138            }
    127139          }
     
    132144        // going bottom-up (reverse breadth order), we ensure depths are calculated bottom-up
    133145        foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
    134           long minDepth = int.MaxValue;
     146          long minDepth = -1;
    135147          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
    136148            long depth = grammar.GetAllowedChildSymbols(symbol, argIndex)
    137149              .Where(x => minimumExpressionDepths.ContainsKey(x.Name))
    138               .Select(x => minimumExpressionDepths[x.Name]).DefaultIfEmpty(int.MaxValue).Min();
    139             minDepth = Math.Min(minDepth, depth + 1);
     150              .Select(x => (long)minimumExpressionDepths[x.Name]).DefaultIfEmpty(int.MaxValue).Min() + 1;
     151            minDepth = Math.Max(minDepth, depth);
    140152          }
    141153          int oldDepth;
     
    143155            minDepth = Math.Min(minDepth, oldDepth);
    144156          minimumExpressionDepths[symbol.Name] = (int)Math.Min(int.MaxValue, minDepth);
     157        }
     158        // correction step for cycles
     159        bool changed = true;
     160        while (changed) {
     161          changed = false;
     162          foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
     163            long minDepth = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))
     164              .Max(x => grammar.GetAllowedChildSymbols(symbol, x)
     165              .Min(s => (long)minimumExpressionDepths[s.Name])) + 1;
     166            if (minDepth < minimumExpressionDepths[symbol.Name]) {
     167              minimumExpressionDepths[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
     168              changed = true;
     169            }
     170          }
    145171        }
    146172      }
  • trunk/sources/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/GrammarsTest.cs

    r14354 r14355  
    8787        Assert.AreEqual(2, grammar.GetMinimumExpressionLength(y));
    8888      }
     89
     90      {
     91        var grammar = CreateTestGrammar6();
     92        var prs = grammar.ProgramRootSymbol;
     93        var ss = grammar.StartSymbol;
     94        var x = grammar.Symbols.First(s => s.Name == "<x>");
     95        var s_ = grammar.Symbols.First(s => s.Name == "<s>");
     96        var a = grammar.Symbols.First(s => s.Name == "<a>");
     97        var b = grammar.Symbols.First(s => s.Name == "<b>");
     98        var c = grammar.Symbols.First(s => s.Name == "<c>");
     99        var d = grammar.Symbols.First(s => s.Name == "<d>");
     100        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(prs));
     101        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(ss));
     102        Assert.AreEqual(2, grammar.GetMinimumExpressionLength(x));
     103        Assert.AreEqual(5, grammar.GetMinimumExpressionLength(s_));
     104        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(a));
     105        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(b));
     106        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(c));
     107        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(d));
     108      }
    89109    }
    90110
     
    170190        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(y));
    171191      }
     192
     193      {
     194        var grammar = CreateTestGrammar6();
     195        var prs = grammar.ProgramRootSymbol;
     196        var ss = grammar.StartSymbol;
     197        var x = grammar.Symbols.First(s => s.Name == "<x>");
     198        var s_ = grammar.Symbols.First(s => s.Name == "<s>");
     199        var a = grammar.Symbols.First(s => s.Name == "<a>");
     200        var b = grammar.Symbols.First(s => s.Name == "<b>");
     201        var c = grammar.Symbols.First(s => s.Name == "<c>");
     202        var d = grammar.Symbols.First(s => s.Name == "<d>");
     203        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(prs));
     204        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(ss));
     205        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(x));
     206        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(s_));
     207        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(a));
     208        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(b));
     209        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(c));
     210        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(d));
     211      }
    172212    }
    173213
     
    286326      return grammar;
    287327    }
     328
     329    private static ISymbolicExpressionGrammar CreateTestGrammar6() {
     330      var grammar = new SimpleSymbolicExpressionGrammar();
     331      var x = new SimpleSymbol("<x>", 1);
     332      var s = new SimpleSymbol("<s>", 1);
     333      var a = new SimpleSymbol("<a>", 1);
     334      var b = new SimpleSymbol("<b>", 1);
     335      var c = new SimpleSymbol("<c>", 1);
     336      var d = new SimpleSymbol("<d>", 1);
     337      var e = new SimpleSymbol("<e>", 1);
     338
     339      var _x = new SimpleSymbol("x", 0);
     340      var _y = new SimpleSymbol("y", 0);
     341
     342      grammar.AddSymbol(x);
     343      grammar.AddSymbol(s);
     344      grammar.AddSymbol(a);
     345      grammar.AddSymbol(b);
     346      grammar.AddSymbol(c);
     347      grammar.AddSymbol(d);
     348      grammar.AddSymbol(e);
     349      grammar.AddSymbol(_x);
     350      grammar.AddSymbol(_y);
     351
     352      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
     353      grammar.AddAllowedChildSymbol(x, s);
     354      grammar.AddAllowedChildSymbol(x, _x);
     355      grammar.AddAllowedChildSymbol(s, a);
     356      grammar.AddAllowedChildSymbol(a, b);
     357      grammar.AddAllowedChildSymbol(a, c);
     358      grammar.AddAllowedChildSymbol(b, x);
     359      grammar.AddAllowedChildSymbol(c, d);
     360      grammar.AddAllowedChildSymbol(d, e);
     361      grammar.AddAllowedChildSymbol(e, _y);
     362
     363      return grammar;
     364    }
    288365  }
    289366}
Note: See TracChangeset for help on using the changeset viewer.