Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/17/21 18:34:49 (3 years ago)
Author:
gkronber
Message:

#3039: merged r17344,r17345,r17347,r17437,r17441,r18008,r18018 from trunk to stable

Location:
stable
Files:
3 edited
1 copied

Legend:

Unmodified
Added
Removed

  • stable

  • stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding

  • stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/BalancedTreeCreator.cs

    r17345 r18019  
    2626using HeuristicLab.Common;
    2727using HeuristicLab.Core;
     28using HeuristicLab.Data;
     29using HeuristicLab.Parameters;
    2830using HeuristicLab.PluginInfrastructure;
    2931using HeuristicLab.Random;
    … …  
    3436  [Item("BalancedTreeCreator", "An operator that produces trees with a specified distribution")]
    3537  public class BalancedTreeCreator : SymbolicExpressionTreeCreator {
     38    private const string IrregularityBiasParameterName = "IrregularityBias";
     39
     40    public IFixedValueParameter<PercentValue> IrregularityBiasParameter {
     41      get { return (IFixedValueParameter<PercentValue>)Parameters[IrregularityBiasParameterName]; }
     42    }
     43
     44    public double IrregularityBias {
     45      get { return IrregularityBiasParameter.Value.Value; }
     46      set { IrregularityBiasParameter.Value.Value = value; }
     47    }
     48
    3649    [StorableConstructor]
    3750    protected BalancedTreeCreator(StorableConstructorFlag _) : base(_) { }
    3851
     52    [StorableHook(HookType.AfterDeserialization)]
     53    private void AfterDeserialization() {
     54      if (!Parameters.ContainsKey(IrregularityBiasParameterName)) {
     55        Parameters.Add(new FixedValueParameter<PercentValue>(IrregularityBiasParameterName, "Allows to bias tree initialization towards less balanced/regular shapes. Set to 0% for most balanced and 100% for least balanced trees. (default = 0%)", new PercentValue(0.0)));
     56      }
     57    }
     58
    3959    protected BalancedTreeCreator(BalancedTreeCreator original, Cloner cloner) : base(original, cloner) { }
    4060
    41     public BalancedTreeCreator() { }
     61    public BalancedTreeCreator() {
     62      Parameters.Add(new FixedValueParameter<PercentValue>(IrregularityBiasParameterName, new PercentValue(0.0)));
     63    }
    4264
    4365    public override IDeepCloneable Clone(Cloner cloner) {
    … …  
    4668
    4769    public override ISymbolicExpressionTree CreateTree(IRandom random, ISymbolicExpressionGrammar grammar, int maxLength, int maxDepth) {
    48       return Create(random, grammar, maxLength, maxDepth);
    49     }
    50 
    51     public static ISymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar, int maxLength, int maxDepth) {
     70      return Create(random, grammar, maxLength, maxDepth, IrregularityBias);
     71    }
     72
     73    public static ISymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar, int maxLength, int maxDepth, double irregularityBias = 0) {
    5274      int targetLength = random.Next(3, maxLength); // because we have 2 extra nodes for the root and start symbols, and the end is exclusive
    53       return CreateExpressionTree(random, grammar, targetLength, maxDepth);
    54     }
    55 
    56     private class SymbolCacheEntry {
    57       public int MinSubtreeCount;
    58       public int MaxSubtreeCount;
    59       public int[] MaxChildArity;
    60     }
    61 
    62     private class SymbolCache {
    63       public SymbolCache(ISymbolicExpressionGrammar grammar) {
    64         Grammar = grammar;
    65       }
    66 
    67       public ISymbolicExpressionTreeNode SampleNode(IRandom random, ISymbol parent, int childIndex, int minArity, int maxArity) {
    68         var symbols = new List<ISymbol>();
    69         var weights = new List<double>();
    70         foreach (var child in AllowedSymbols.Where(x => !(x is StartSymbol || x is Defun))) {
    71           var t = Tuple.Create(parent, child);
    72           if (!allowedCache.TryGetValue(t, out bool[] allowed)) { continue; }
    73           if (!allowed[childIndex]) { continue; }
    74 
    75           if (symbolCache.TryGetValue(child, out SymbolCacheEntry cacheItem)) {
    76             if (cacheItem.MinSubtreeCount < minArity) { continue; }
    77             if (cacheItem.MaxSubtreeCount > maxArity) { continue; }
    78           }
    79 
    80           symbols.Add(child);
    81           weights.Add(child.InitialFrequency);
    82         }
    83         if (!symbols.Any()) {
    84           throw new ArgumentException("SampleNode: parent symbol " + parent.Name
    85             + " does not have any allowed child symbols with min arity " + minArity
    86             + " and max arity " + maxArity + ". Please ensure the grammar is properly configured.");
    87         }
    88         var symbol = symbols.SampleProportional(random, 1, weights).First();
    89         var node = symbol.CreateTreeNode();
    90         if (node.HasLocalParameters) {
    91           node.ResetLocalParameters(random);
    92         }
    93         return node;
    94       }
    95 
    96       public ISymbolicExpressionGrammar Grammar {
    97         get { return grammar; }
    98         set {
    99           grammar = value;
    100           RebuildCache();
    101         }
    102       }
    103 
    104       public IList<ISymbol> AllowedSymbols { get; private set; }
    105 
    106       public SymbolCacheEntry this[ISymbol symbol] {
    107         get { return symbolCache[symbol]; }
    108       }
    109 
    110       public bool[] this[ISymbol parent, ISymbol child] {
    111         get { return allowedCache[Tuple.Create(parent, child)]; }
    112       }
    113 
    114       public bool HasUnarySymbols { get; private set; }
    115 
    116       private void RebuildCache() {
    117         AllowedSymbols = Grammar.AllowedSymbols.Where(x => x.InitialFrequency > 0 && !(x is ProgramRootSymbol)).ToList();
    118 
    119         allowedCache = new Dictionary<Tuple<ISymbol, ISymbol>, bool[]>();
    120         symbolCache = new Dictionary<ISymbol, SymbolCacheEntry>();
    121 
    122         SymbolCacheEntry TryAddItem(ISymbol symbol) {
    123           if (!symbolCache.TryGetValue(symbol, out SymbolCacheEntry cacheItem)) {
    124             cacheItem = new SymbolCacheEntry {
    125               MinSubtreeCount = Grammar.GetMinimumSubtreeCount(symbol),
    126               MaxSubtreeCount = Grammar.GetMaximumSubtreeCount(symbol)
    127             };
    128             symbolCache[symbol] = cacheItem;
    129           }
    130           return cacheItem;
    131         }
    132 
    133         foreach (var parent in AllowedSymbols) {
    134           var parentCacheEntry = TryAddItem(parent);
    135           var maxChildArity = new int[parentCacheEntry.MaxSubtreeCount];
    136 
    137           if (!(parent is StartSymbol || parent is Defun)) {
    138             HasUnarySymbols |= parentCacheEntry.MaxSubtreeCount == 1;
    139           }
    140 
    141           foreach (var child in AllowedSymbols) {
    142             var childCacheEntry = TryAddItem(child);
    143             var allowed = new bool[parentCacheEntry.MaxSubtreeCount];
    144 
    145             for (int childIndex = 0; childIndex < parentCacheEntry.MaxSubtreeCount; ++childIndex) {
    146               allowed[childIndex] = Grammar.IsAllowedChildSymbol(parent, child, childIndex);
    147               maxChildArity[childIndex] = Math.Max(maxChildArity[childIndex], allowed[childIndex] ? childCacheEntry.MaxSubtreeCount : 0);
    148             }
    149             allowedCache[Tuple.Create(parent, child)] = allowed;
    150           }
    151           parentCacheEntry.MaxChildArity = maxChildArity;
    152         }
    153       }
    154 
    155       private ISymbolicExpressionGrammar grammar;
    156       private Dictionary<Tuple<ISymbol, ISymbol>, bool[]> allowedCache;
    157       private Dictionary<ISymbol, SymbolCacheEntry> symbolCache;
    158     }
    159 
    160     public static ISymbolicExpressionTree CreateExpressionTree(IRandom random, ISymbolicExpressionGrammar grammar, int targetLength, int maxDepth) {
     75      return CreateExpressionTree(random, grammar, targetLength, maxDepth, irregularityBias);
     76    }
     77
     78    public static ISymbolicExpressionTree CreateExpressionTree(IRandom random, ISymbolicExpressionGrammar grammar, int targetLength, int maxDepth, double irregularityBias = 1) {
    16179      // even lengths cannot be achieved without symbols of odd arity
    16280      // therefore we randomly pick a neighbouring odd length value
    163       var symbolCache = new SymbolCache(grammar);
    164       if (!symbolCache.HasUnarySymbols && targetLength % 2 == 0) {
    165         targetLength += random.NextDouble() < 0.5 ? -1 : +1;
    166       }
    167       return CreateExpressionTree(random, symbolCache, targetLength, maxDepth);
    168     }
    169 
    170     private static ISymbolicExpressionTree CreateExpressionTree(IRandom random, SymbolCache symbolCache, int targetLength, int maxDepth) {
    171       var allowedSymbols = symbolCache.AllowedSymbols;
    172       var tree = MakeStump(random, symbolCache.Grammar);
    173       var tuples = new List<NodeInfo>(targetLength) {
    174         new NodeInfo { Node = tree.Root, Depth = 0, Arity = 1 },
    175         new NodeInfo { Node = tree.Root.GetSubtree(0), Depth = 1, Arity = 1 }
    176       };
    177       targetLength -= 2; // remaining length; -2 because we already have a root and start node
    178       int openSlots = 1; // remaining extension points; startNode has arity 1
    179 
    180       for (int i = 1; i < tuples.Count; ++i) {
     81      var tree = MakeStump(random, grammar); // create a stump consisting of just a ProgramRootSymbol and a StartSymbol
     82      CreateExpression(random, tree.Root.GetSubtree(0), targetLength - tree.Length, maxDepth - 2, irregularityBias); // -2 because the stump has length 2 and depth 2
     83      return tree;
     84    }
     85
     86    private static ISymbolicExpressionTreeNode SampleNode(IRandom random, ISymbolicExpressionTreeGrammar grammar, IEnumerable<ISymbol> allowedSymbols, int minChildArity, int maxChildArity) {
     87      var candidates = new List<ISymbol>();
     88      var weights = new List<double>();
     89
     90      foreach (var s in allowedSymbols) {
     91        var minSubtreeCount = grammar.GetMinimumSubtreeCount(s);
     92        var maxSubtreeCount = grammar.GetMaximumSubtreeCount(s);
     93
     94        if (maxChildArity < minSubtreeCount || minChildArity > maxSubtreeCount) { continue; }
     95
     96        candidates.Add(s);
     97        weights.Add(s.InitialFrequency);
     98      }
     99      var symbol = candidates.SampleProportional(random, 1, weights).First();
     100      var node = symbol.CreateTreeNode();
     101      if (node.HasLocalParameters) {
     102        node.ResetLocalParameters(random);
     103      }
     104      return node;
     105    }
     106
     107    public static void CreateExpression(IRandom random, ISymbolicExpressionTreeNode root, int targetLength, int maxDepth, double irregularityBias = 1) {
     108      var grammar = root.Grammar;
     109      var minSubtreeCount = grammar.GetMinimumSubtreeCount(root.Symbol);
     110      var maxSubtreeCount = grammar.GetMaximumSubtreeCount(root.Symbol);
     111      var arity = random.Next(minSubtreeCount, maxSubtreeCount + 1);
     112      int openSlots = arity;
     113
     114      var allowedSymbols = grammar.AllowedSymbols.Where(x => !(x is ProgramRootSymbol || x is GroupSymbol || x is Defun || x is StartSymbol)).ToList();
     115      bool hasUnarySymbols = allowedSymbols.Any(x => grammar.GetMinimumSubtreeCount(x) <= 1 && grammar.GetMaximumSubtreeCount(x) >= 1);
     116
     117      if (!hasUnarySymbols && targetLength % 2 == 0) {
     118        // without functions of arity 1 some target lengths cannot be reached
     119        targetLength = random.NextDouble() < 0.5 ? targetLength - 1 : targetLength + 1;
     120      }
     121
     122      var tuples = new List<NodeInfo>(targetLength) { new NodeInfo { Node = root, Depth = 0, Arity = arity } };
     123
     124      // we use tuples.Count instead of targetLength in the if condition
     125      // because depth limits may prevent reaching the target length
     126      for (int i = 0; i < tuples.Count; ++i) {
    181127        var t = tuples[i];
    182128        var node = t.Node;
    183         var parentEntry = symbolCache[node.Symbol];
    184129
    185130        for (int childIndex = 0; childIndex < t.Arity; ++childIndex) {
    186131          // min and max arity here refer to the required arity limits for the child node
    187           int maxChildArity = t.Depth == maxDepth - 1 ? 0 : Math.Min(parentEntry.MaxChildArity[childIndex], targetLength - openSlots);
    188           int minChildArity = Math.Min(1, maxChildArity);
    189           var child = symbolCache.SampleNode(random, node.Symbol, childIndex, minChildArity, maxChildArity);
    190           var childEntry = symbolCache[child.Symbol];
    191           var childArity = random.Next(childEntry.MinSubtreeCount, childEntry.MaxSubtreeCount + 1);
     132          int minChildArity = 0;
     133          int maxChildArity = 0;
     134
     135          var allowedChildSymbols = allowedSymbols.Where(x => grammar.IsAllowedChildSymbol(node.Symbol, x, childIndex)).ToList();
     136
     137          // if we are reaching max depth we have to fill the slot with a leaf node (max arity will be zero)
     138          // otherwise, find the maximum value from the grammar which does not exceed the length limit
     139          if (t.Depth < maxDepth - 1 && openSlots < targetLength) {
     140
     141            // we don't want to allow sampling a leaf symbol if it prevents us from reaching the target length
     142            // this should be allowed only when we have enough open expansion points (more than one)
     143            // the random check against the irregularity bias helps to increase shape variability when the conditions are met
     144            int minAllowedArity = allowedChildSymbols.Min(x => grammar.GetMaximumSubtreeCount(x));
     145            if (minAllowedArity == 0 && (openSlots - tuples.Count <= 1 || random.NextDouble() > irregularityBias)) {
     146              minAllowedArity = 1;
     147            }
     148
     149            // finally adjust min and max arity according to the expansion limits
     150            int maxAllowedArity = allowedChildSymbols.Max(x => grammar.GetMaximumSubtreeCount(x));
     151            maxChildArity = Math.Min(maxAllowedArity, targetLength - openSlots);
     152            minChildArity = Math.Min(minAllowedArity, maxChildArity);
     153          }
     154         
     155          // sample a random child with the arity limits
     156          var child = SampleNode(random, grammar, allowedChildSymbols, minChildArity, maxChildArity);
     157
     158          // get actual child arity limits
     159          minChildArity = Math.Max(minChildArity, grammar.GetMinimumSubtreeCount(child.Symbol));
     160          maxChildArity = Math.Min(maxChildArity, grammar.GetMaximumSubtreeCount(child.Symbol));
     161          minChildArity = Math.Min(minChildArity, maxChildArity);
     162
     163          // pick a random arity for the new child node
     164          var childArity = random.Next(minChildArity, maxChildArity + 1);
    192165          var childDepth = t.Depth + 1;
    193166          node.AddSubtree(child);
    … …  
    196169        }
    197170      }
    198       return tree;
    199171    }
    200172
    … …  
    227199      return tree;
    228200    }
     201
     202    public void CreateExpression(IRandom random, ISymbolicExpressionTreeNode seedNode, int maxTreeLength, int maxTreeDepth) {
     203      CreateExpression(random, seedNode, maxTreeLength, maxTreeDepth, IrregularityBias);
     204    }
    229205    #endregion
    230206  }

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

    r17105 r18019  
    129129    <Compile Include="ArchitectureManipulators\SubroutineDuplicater.cs" />
    130130    <Compile Include="ArchitectureManipulators\SymbolicExpressionTreeArchitectureManipulator.cs" />
     131    <Compile Include="Creators\BalancedTreeCreator.cs" />
    131132    <Compile Include="Grammars\GrammarUtils.cs" />
    132133    <Compile Include="SymbolicExpressionTreeProblem.cs" />
Note: See TracChangeset for help on using the changeset viewer.