Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
05/10/17 15:44:17 (7 years ago)
Author:
mkommend
Message:

#2685: Merged r14340, r14341, r14342, r14352, r14353, r14354, r14355, r14356, r14357 into stable.

Location:
stable
Files:
5 edited
1 copied

Legend:

Unmodified
Added
Removed

  • stable

  • stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding

  • stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs

    r14342 r14958  
    2525using System.Collections.Generic;
    2626using System.Linq;
    27 
    2827namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    2928  public static class GrammarUtils {
     29    private static IEnumerable<ISymbol> GetTopmostSymbols(this ISymbolicExpressionGrammarBase grammar) {
     30      // build parents list so we can find out the topmost symbol(s)
     31      var parents = new Dictionary<ISymbol, List<ISymbol>>();
     32      foreach (var symbol in grammar.Symbols.Where(x => grammar.GetMinimumSubtreeCount(x) > 0)) {
     33        var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);
     34        for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {
     35          foreach (var childSymbol in grammar.GetAllowedActiveSymbols(symbol, argIndex)) {
     36            if (!parents.ContainsKey(childSymbol))
     37              parents[childSymbol] = new List<ISymbol>();
     38            parents[childSymbol].Add(symbol);
     39          }
     40        }
     41      }
     42      // the topmost symbols have no parents
     43      return parents.Values.SelectMany(x => x).Distinct().Where(x => !parents.ContainsKey(x));
     44    }
     45
     46    private static IReadOnlyCollection<ISymbol> IterateBreadthReverse(this ISymbolicExpressionGrammarBase grammar, ISymbol topSymbol) {
     47      // sort symbols in reverse breadth order (starting from the topSymbol)
     48      // each symbol is visited only once (this avoids infinite recursion)
     49      var symbols = new List<ISymbol> { topSymbol };
     50      var visited = new HashSet<ISymbol> { topSymbol };
     51      int i = 0;
     52      while (i < symbols.Count) {
     53        var symbol = symbols[i];
     54        var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);
     55
     56        for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {
     57          foreach (var childSymbol in grammar.GetAllowedActiveSymbols(symbol, argIndex)) {
     58            if (grammar.GetMinimumSubtreeCount(childSymbol) == 0)
     59              continue;
     60
     61            if (visited.Add(childSymbol))
     62              symbols.Add(childSymbol);
     63          }
     64        }
     65        ++i;
     66      }
     67      symbols.Reverse();
     68      return symbols;
     69    }
     70
     71    private static IEnumerable<ISymbol> GetAllowedActiveSymbols(this ISymbolicExpressionGrammarBase grammar, ISymbol symbol, int argIndex) {
     72      return grammar.GetAllowedChildSymbols(symbol, argIndex).Where(s => s.InitialFrequency > 0);
     73    }
    3074
    3175    public static void CalculateMinimumExpressionLengths(ISymbolicExpressionGrammarBase grammar,
    3276      Dictionary<string, int> minimumExpressionLengths) {
    33 
    3477      minimumExpressionLengths.Clear();
    3578      //terminal symbols => minimum expression length = 1
    36       foreach (var s in grammar.Symbols.Where(s => grammar.GetMinimumSubtreeCount(s) == 0))
    37         minimumExpressionLengths[s.Name] = 1;
     79      foreach (var s in grammar.Symbols) {
     80        if (grammar.GetMinimumSubtreeCount(s) == 0)
     81          minimumExpressionLengths[s.Name] = 1;
     82        else
     83          minimumExpressionLengths[s.Name] = int.MaxValue;
     84      }
    3885
    39       var symbolAdded = true;
    40       while (symbolAdded) {
    41         symbolAdded = false;
    42         foreach (var remainingSymbol in grammar.Symbols) {
    43           if (minimumExpressionLengths.ContainsKey(remainingSymbol.Name)) continue;
    44 
    45           var arguments = grammar.GetMinimumSubtreeCount(remainingSymbol);
    46           int minLength = 1;
    47 
    48           foreach (int argumentIndex in Enumerable.Range(0, arguments)) {
    49             var capturedMinimumLengths = minimumExpressionLengths;
    50             var childSymbols = grammar.GetAllowedChildSymbols(remainingSymbol, argumentIndex)
    51               .Where(c => c.InitialFrequency > 0.0 && capturedMinimumLengths.ContainsKey(c.Name));
    52 
    53             if (!childSymbols.Any()) {
    54               minLength = -1;
    55               break;
     86      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
     87        // get all symbols below in reverse breadth order
     88        // this way we ensure lengths are calculated bottom-up
     89        var symbols = grammar.IterateBreadthReverse(topSymbol);
     90        foreach (var symbol in symbols) {
     91          long minLength = 1;
     92          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
     93            long length = grammar.GetAllowedActiveSymbols(symbol, argIndex)
     94              .Where(x => minimumExpressionLengths.ContainsKey(x.Name))
     95              .Select(x => minimumExpressionLengths[x.Name]).DefaultIfEmpty(int.MaxValue).Min();
     96            minLength += length;
     97          }
     98          int oldLength;
     99          if (minimumExpressionLengths.TryGetValue(symbol.Name, out oldLength))
     100            minLength = Math.Min(minLength, oldLength);
     101          minimumExpressionLengths[symbol.Name] = (int)Math.Min(int.MaxValue, minLength);
     102        }
     103        // correction step for cycles
     104        bool changed = true;
     105        while (changed) {
     106          changed = false;
     107          foreach (var symbol in symbols) {
     108            long minLength = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))
     109              .Sum(x => grammar.GetAllowedActiveSymbols(symbol, x)
     110              .Select(s => (long)minimumExpressionLengths[s.Name]).DefaultIfEmpty(int.MaxValue).Min()) + 1;
     111            if (minLength < minimumExpressionLengths[symbol.Name]) {
     112              minimumExpressionLengths[symbol.Name] = (int)Math.Min(minLength, int.MaxValue);
     113              changed = true;
    56114            }
    57             var minLengthPerArgument = childSymbols.Min(c => capturedMinimumLengths[c.Name]);
    58             minLength += minLengthPerArgument;
    59           }
    60 
    61           if (minLength != -1) {
    62             minimumExpressionLengths[remainingSymbol.Name] = minLength;
    63             symbolAdded = true;
    64115          }
    65116        }
    66117      }
    67 
    68       //set minLength to int.Maxvalue for all symbols that are not reacheable
    69       foreach (var remainingSymbols in grammar.Symbols) {
    70         if (!minimumExpressionLengths.ContainsKey(remainingSymbols.Name))
    71           minimumExpressionLengths[remainingSymbols.Name] = int.MaxValue;
    72       }
    73118    }
    74 
    75119
    76120    public static void CalculateMinimumExpressionDepth(ISymbolicExpressionGrammarBase grammar,
    … …  
    79123      minimumExpressionDepths.Clear();
    80124      //terminal symbols => minimum expression depth = 1
    81       foreach (var s in grammar.Symbols.Where(s => grammar.GetMinimumSubtreeCount(s) == 0))
    82         minimumExpressionDepths[s.Name] = 1;
     125      foreach (var s in grammar.Symbols) {
     126        if (grammar.GetMinimumSubtreeCount(s) == 0)
     127          minimumExpressionDepths[s.Name] = 1;
     128        else
     129          minimumExpressionDepths[s.Name] = int.MaxValue;
     130      }
    83131
    84       var symbolAdded = true;
    85       while (symbolAdded) {
    86         symbolAdded = false;
    87         foreach (var remainingSymbol in grammar.Symbols) {
    88           if (minimumExpressionDepths.ContainsKey(remainingSymbol.Name)) continue;
    89 
    90           var arguments = grammar.GetMinimumSubtreeCount(remainingSymbol);
    91           int minDepth = -1;
    92 
    93           foreach (int argumentIndex in Enumerable.Range(0, arguments)) {
    94             var capturedMinimumDepths = minimumExpressionDepths;
    95             var childSymbols = grammar.GetAllowedChildSymbols(remainingSymbol, argumentIndex)
    96               .Where(c => c.InitialFrequency > 0.0 && capturedMinimumDepths.ContainsKey(c.Name));
    97             if (!childSymbols.Any()) {
    98               minDepth = -1;
    99               break;
     132      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
     133        // get all symbols below in reverse breadth order
     134        // this way we ensure lengths are calculated bottom-up
     135        var symbols = grammar.IterateBreadthReverse(topSymbol);
     136        foreach (var symbol in symbols) {
     137          long minDepth = -1;
     138          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
     139            long depth = grammar.GetAllowedActiveSymbols(symbol, argIndex)
     140              .Where(x => minimumExpressionDepths.ContainsKey(x.Name))
     141              .Select(x => (long)minimumExpressionDepths[x.Name]).DefaultIfEmpty(int.MaxValue).Min() + 1;
     142            minDepth = Math.Max(minDepth, depth);
     143          }
     144          int oldDepth;
     145          if (minimumExpressionDepths.TryGetValue(symbol.Name, out oldDepth))
     146            minDepth = Math.Min(minDepth, oldDepth);
     147          minimumExpressionDepths[symbol.Name] = (int)Math.Min(int.MaxValue, minDepth);
     148        }
     149        // correction step for cycles
     150        bool changed = true;
     151        while (changed) {
     152          changed = false;
     153          foreach (var symbol in symbols) {
     154            long minDepth = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))
     155              .Max(x => grammar.GetAllowedActiveSymbols(symbol, x)
     156              .Select(s => (long)minimumExpressionDepths[s.Name]).DefaultIfEmpty(int.MaxValue).Min()) + 1;
     157            if (minDepth < minimumExpressionDepths[symbol.Name]) {
     158              minimumExpressionDepths[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
     159              changed = true;
    100160            }
    101             var minDepthPerArgument = childSymbols.Min(c => capturedMinimumDepths[c.Name]);
    102             minDepth = Math.Max(minDepth, 1 + minDepthPerArgument);
    103           }
    104 
    105           if (minDepth != -1) {
    106             minimumExpressionDepths[remainingSymbol.Name] = minDepth;
    107             symbolAdded = true;
    108161          }
    109162        }
    110       }
    111 
    112       //set minDepth to int.Maxvalue for all symbols that are not reacheable
    113       foreach (var remainingSymbols in grammar.Symbols) {
    114         if (!minimumExpressionDepths.ContainsKey(remainingSymbols.Name))
    115           minimumExpressionDepths[remainingSymbols.Name] = int.MaxValue;
    116163      }
    117164    }

  • stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/SymbolicExpressionGrammarBase.cs

    r14186 r14958  
    8282    protected SymbolicExpressionGrammarBase(bool deserializing)
    8383      : base(deserializing) {
    84       cachedMinExpressionLength = new Dictionary<string, int>();
    85       cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    86       cachedMinExpressionDepth = new Dictionary<string, int>();
    87       cachedMaxExpressionDepth = new Dictionary<string, int>();
    88 
    89       cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
    90       cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
    9184
    9285      symbols = new Dictionary<string, ISymbol>();
    … …  
    10093    protected SymbolicExpressionGrammarBase(SymbolicExpressionGrammarBase original, Cloner cloner)
    10194      : base(original, cloner) {
    102       cachedMinExpressionLength = new Dictionary<string, int>();
    103       cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    104       cachedMinExpressionDepth = new Dictionary<string, int>();
    105       cachedMaxExpressionDepth = new Dictionary<string, int>();
    106 
    107       cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
    108       cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
    10995
    11096      symbols = original.symbols.ToDictionary(x => x.Key, y => cloner.Clone(y.Value));
    … …  
    124110    protected SymbolicExpressionGrammarBase(string name, string description)
    125111      : base(name, description) {
    126       cachedMinExpressionLength = new Dictionary<string, int>();
    127       cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    128       cachedMinExpressionDepth = new Dictionary<string, int>();
    129       cachedMaxExpressionDepth = new Dictionary<string, int>();
    130 
    131       cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
    132       cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
    133 
    134112      symbols = new Dictionary<string, ISymbol>();
    135113      symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>();
    … …  
    322300    }
    323301
    324     private readonly Dictionary<Tuple<string, string>, bool> cachedIsAllowedChildSymbol;
     302    private readonly Dictionary<Tuple<string, string>, bool> cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
    325303    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
    326304      if (allowedChildSymbols.Count == 0) return false;
    … …  
    352330    }
    353331
    354     private readonly Dictionary<Tuple<string, string, int>, bool> cachedIsAllowedChildSymbolIndex;
     332    private readonly Dictionary<Tuple<string, string, int>, bool> cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
    355333    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
    356334      if (!child.Enabled) return false;
    … …  
    412390    }
    413391
    414     private readonly Dictionary<string, int> cachedMinExpressionLength;
     392    private readonly Dictionary<string, int> cachedMinExpressionLength = new Dictionary<string, int>();
    415393    public int GetMinimumExpressionLength(ISymbol symbol) {
    416394      int res;
    … …  
    423401        if (cachedMinExpressionLength.TryGetValue(symbol.Name, out res)) return res;
    424402
    425         res = GetMinimumExpressionLengthRec(symbol);
    426         foreach (var entry in cachedMinExpressionLength.Where(e => e.Value >= int.MaxValue).ToList()) {
    427           if (entry.Key != symbol.Name) cachedMinExpressionLength.Remove(entry.Key);
    428         }
    429         return res;
    430       }
    431     }
    432 
    433     private int GetMinimumExpressionLengthRec(ISymbol symbol) {
    434       int temp;
    435       if (!cachedMinExpressionLength.TryGetValue(symbol.Name, out temp)) {
    436         cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
    437         long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
    438                                               let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
    439                                                                       where s.InitialFrequency > 0.0
    440                                                                       select GetMinimumExpressionLengthRec(s)).DefaultIfEmpty(0).Min()
    441                                               select minForSlot).DefaultIfEmpty(0).Sum();
    442 
    443         cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
     403        GrammarUtils.CalculateMinimumExpressionLengths(this, cachedMinExpressionLength);
    444404        return cachedMinExpressionLength[symbol.Name];
    445405      }
    446       return temp;
    447     }
    448 
    449     private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength;
     406    }
     407
     408
     409    private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    450410    public int GetMaximumExpressionLength(ISymbol symbol, int maxDepth) {
    451411      int temp;
    … …  
    469429    }
    470430
    471     private readonly Dictionary<string, int> cachedMinExpressionDepth;
     431    private readonly Dictionary<string, int> cachedMinExpressionDepth = new Dictionary<string, int>();
    472432    public int GetMinimumExpressionDepth(ISymbol symbol) {
    473433      int res;
    … …  
    480440        if (cachedMinExpressionDepth.TryGetValue(symbol.Name, out res)) return res;
    481441
    482         res = GetMinimumExpressionDepthRec(symbol);
    483         foreach (var entry in cachedMinExpressionDepth.Where(e => e.Value >= int.MaxValue).ToList()) {
    484           if (entry.Key != symbol.Name) cachedMinExpressionDepth.Remove(entry.Key);
    485         }
    486         return res;
    487       }
    488     }
    489     private int GetMinimumExpressionDepthRec(ISymbol symbol) {
    490       int temp;
    491       if (!cachedMinExpressionDepth.TryGetValue(symbol.Name, out temp)) {
    492         cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
    493         long minDepth = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
    494                              let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
    495                                                      where s.InitialFrequency > 0.0
    496                                                      select GetMinimumExpressionDepthRec(s)).DefaultIfEmpty(0).Min()
    497                              select minForSlot).DefaultIfEmpty(0).Max();
    498         cachedMinExpressionDepth[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
     442        GrammarUtils.CalculateMinimumExpressionDepth(this, cachedMinExpressionDepth);
    499443        return cachedMinExpressionDepth[symbol.Name];
    500444      }
    501       return temp;
    502     }
    503 
    504     private readonly Dictionary<string, int> cachedMaxExpressionDepth;
     445    }
     446
     447    private readonly Dictionary<string, int> cachedMaxExpressionDepth = new Dictionary<string, int>();
    505448    public int GetMaximumExpressionDepth(ISymbol symbol) {
    506449      int temp;

  • stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj

    r13278 r14958  
    129129    <Compile Include="ArchitectureManipulators\SubroutineDuplicater.cs" />
    130130    <Compile Include="ArchitectureManipulators\SymbolicExpressionTreeArchitectureManipulator.cs" />
     131    <Compile Include="Grammars\GrammarUtils.cs" />
    131132    <Compile Include="SymbolicExpressionTreeProblem.cs" />
    132133    <Compile Include="Compiler\Instruction.cs" />

  • stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Symbols/SimpleSymbol.cs

    r14186 r14958  
    6161    }
    6262
     63    public SimpleSymbol(string name, int arity)
     64      : this(name, string.Empty, arity, arity) {
     65    }
     66
    6367    public SimpleSymbol(string name, string description, int minimumArity, int maximumArity)
    6468      : base(name, description) {
Note: See TracChangeset for help on using the changeset viewer.