Changeset 17347


Ignore:
Timestamp:
10/30/19 14:53:54 (2 weeks ago)
Author:
bburlacu
Message:

#3039: Enable construction of subtrees from an arbitrary root node. Introduce IrregularityBias parameter as a means to bias tree initialization towards less balanced/regular shapes.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/BalancedTreeCreator.cs

    r17345 r17347  
    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, 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);
     75      return CreateExpressionTree(random, grammar, targetLength, maxDepth, irregularityBias);
    5476    }
    5577
     
    6183
    6284    private class SymbolCache {
    63       public SymbolCache(ISymbolicExpressionGrammar grammar) {
     85      public SymbolCache(ISymbolicExpressionGrammarBase grammar) {
    6486        Grammar = grammar;
    6587      }
     
    81103          weights.Add(child.InitialFrequency);
    82104        }
    83         if (!symbols.Any()) {
     105        if (symbols.Count == 0) {
    84106          throw new ArgumentException("SampleNode: parent symbol " + parent.Name
    85107            + " does not have any allowed child symbols with min arity " + minArity
     
    94116      }
    95117
    96       public ISymbolicExpressionGrammar Grammar {
     118      public ISymbolicExpressionGrammarBase Grammar {
    97119        get { return grammar; }
    98120        set {
     
    153175      }
    154176
    155       private ISymbolicExpressionGrammar grammar;
     177      private ISymbolicExpressionGrammarBase grammar;
    156178      private Dictionary<Tuple<ISymbol, ISymbol>, bool[]> allowedCache;
    157179      private Dictionary<ISymbol, SymbolCacheEntry> symbolCache;
    158180    }
    159181
    160     public static ISymbolicExpressionTree CreateExpressionTree(IRandom random, ISymbolicExpressionGrammar grammar, int targetLength, int maxDepth) {
     182    public static ISymbolicExpressionTree CreateExpressionTree(IRandom random, ISymbolicExpressionGrammar grammar, int targetLength, int maxDepth, double irregularityBias = 1) {
    161183      // even lengths cannot be achieved without symbols of odd arity
    162184      // therefore we randomly pick a neighbouring odd length value
     185      var tree = MakeStump(random, grammar); // create a stump consisting of just a ProgramRootSymbol and a StartSymbol
     186      CreateExpression(random, tree.Root.GetSubtree(0), targetLength - 2, maxDepth - 2, irregularityBias); // -2 because the stump has length 2 and depth 2
     187      return tree;
     188    }
     189
     190    public static void CreateExpression(IRandom random, ISymbolicExpressionTreeNode root, int targetLength, int maxDepth, double irregularityBias = 1) {
     191      var grammar = root.Grammar;
    163192      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) {
     193      var entry = symbolCache[root.Symbol];
     194      var arity = random.Next(entry.MinSubtreeCount, entry.MaxSubtreeCount + 1);
     195      var tuples = new List<NodeInfo>(targetLength) { new NodeInfo { Node = root, Depth = 0, Arity = arity } };
     196      int openSlots = arity;
     197
     198      for (int i = 0; i < tuples.Count; ++i) {
    181199        var t = tuples[i];
    182200        var node = t.Node;
     
    186204          // min and max arity here refer to the required arity limits for the child node
    187205          int maxChildArity = t.Depth == maxDepth - 1 ? 0 : Math.Min(parentEntry.MaxChildArity[childIndex], targetLength - openSlots);
    188           int minChildArity = Math.Min(1, maxChildArity);
     206          int minChildArity = Math.Min((openSlots - tuples.Count > 1 && random.NextDouble() < irregularityBias) ? 0 : 1, maxChildArity);
    189207          var child = symbolCache.SampleNode(random, node.Symbol, childIndex, minChildArity, maxChildArity);
    190208          var childEntry = symbolCache[child.Symbol];
     
    196214        }
    197215      }
    198       return tree;
    199216    }
    200217
Note: See TracChangeset for help on using the changeset viewer.