source: trunk/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/BalancedTreeCreator.cs @ 17347

Last change on this file since 17347 was 17347, checked in by bburlacu, 23 months ago

#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 size: 10.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using HEAL.Attic;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Parameters;
30using HeuristicLab.PluginInfrastructure;
31using HeuristicLab.Random;
32
33namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
34  [NonDiscoverableType]
35  [StorableType("AA3649C4-18CF-480B-AA41-F5D6F148B494")]
36  [Item("BalancedTreeCreator", "An operator that produces trees with a specified distribution")]
37  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
49    [StorableConstructor]
50    protected BalancedTreeCreator(StorableConstructorFlag _) : base(_) { }
51
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
59    protected BalancedTreeCreator(BalancedTreeCreator original, Cloner cloner) : base(original, cloner) { }
60
61    public BalancedTreeCreator() {
62      Parameters.Add(new FixedValueParameter<PercentValue>(IrregularityBiasParameterName, new PercentValue(0.0)));
63    }
64
65    public override IDeepCloneable Clone(Cloner cloner) {
66      return new BalancedTreeCreator(this, cloner);
67    }
68
69    public override ISymbolicExpressionTree CreateTree(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) {
74      int targetLength = random.Next(3, maxLength); // because we have 2 extra nodes for the root and start symbols, and the end is exclusive
75      return CreateExpressionTree(random, grammar, targetLength, maxDepth, irregularityBias);
76    }
77
78    private class SymbolCacheEntry {
79      public int MinSubtreeCount;
80      public int MaxSubtreeCount;
81      public int[] MaxChildArity;
82    }
83
84    private class SymbolCache {
85      public SymbolCache(ISymbolicExpressionGrammarBase grammar) {
86        Grammar = grammar;
87      }
88
89      public ISymbolicExpressionTreeNode SampleNode(IRandom random, ISymbol parent, int childIndex, int minArity, int maxArity) {
90        var symbols = new List<ISymbol>();
91        var weights = new List<double>();
92        foreach (var child in AllowedSymbols.Where(x => !(x is StartSymbol || x is Defun))) {
93          var t = Tuple.Create(parent, child);
94          if (!allowedCache.TryGetValue(t, out bool[] allowed)) { continue; }
95          if (!allowed[childIndex]) { continue; }
96
97          if (symbolCache.TryGetValue(child, out SymbolCacheEntry cacheItem)) {
98            if (cacheItem.MinSubtreeCount < minArity) { continue; }
99            if (cacheItem.MaxSubtreeCount > maxArity) { continue; }
100          }
101
102          symbols.Add(child);
103          weights.Add(child.InitialFrequency);
104        }
105        if (symbols.Count == 0) {
106          throw new ArgumentException("SampleNode: parent symbol " + parent.Name
107            + " does not have any allowed child symbols with min arity " + minArity
108            + " and max arity " + maxArity + ". Please ensure the grammar is properly configured.");
109        }
110        var symbol = symbols.SampleProportional(random, 1, weights).First();
111        var node = symbol.CreateTreeNode();
112        if (node.HasLocalParameters) {
113          node.ResetLocalParameters(random);
114        }
115        return node;
116      }
117
118      public ISymbolicExpressionGrammarBase Grammar {
119        get { return grammar; }
120        set {
121          grammar = value;
122          RebuildCache();
123        }
124      }
125
126      public IList<ISymbol> AllowedSymbols { get; private set; }
127
128      public SymbolCacheEntry this[ISymbol symbol] {
129        get { return symbolCache[symbol]; }
130      }
131
132      public bool[] this[ISymbol parent, ISymbol child] {
133        get { return allowedCache[Tuple.Create(parent, child)]; }
134      }
135
136      public bool HasUnarySymbols { get; private set; }
137
138      private void RebuildCache() {
139        AllowedSymbols = Grammar.AllowedSymbols.Where(x => x.InitialFrequency > 0 && !(x is ProgramRootSymbol)).ToList();
140
141        allowedCache = new Dictionary<Tuple<ISymbol, ISymbol>, bool[]>();
142        symbolCache = new Dictionary<ISymbol, SymbolCacheEntry>();
143
144        SymbolCacheEntry TryAddItem(ISymbol symbol) {
145          if (!symbolCache.TryGetValue(symbol, out SymbolCacheEntry cacheItem)) {
146            cacheItem = new SymbolCacheEntry {
147              MinSubtreeCount = Grammar.GetMinimumSubtreeCount(symbol),
148              MaxSubtreeCount = Grammar.GetMaximumSubtreeCount(symbol)
149            };
150            symbolCache[symbol] = cacheItem;
151          }
152          return cacheItem;
153        }
154
155        foreach (var parent in AllowedSymbols) {
156          var parentCacheEntry = TryAddItem(parent);
157          var maxChildArity = new int[parentCacheEntry.MaxSubtreeCount];
158
159          if (!(parent is StartSymbol || parent is Defun)) {
160            HasUnarySymbols |= parentCacheEntry.MaxSubtreeCount == 1;
161          }
162
163          foreach (var child in AllowedSymbols) {
164            var childCacheEntry = TryAddItem(child);
165            var allowed = new bool[parentCacheEntry.MaxSubtreeCount];
166
167            for (int childIndex = 0; childIndex < parentCacheEntry.MaxSubtreeCount; ++childIndex) {
168              allowed[childIndex] = Grammar.IsAllowedChildSymbol(parent, child, childIndex);
169              maxChildArity[childIndex] = Math.Max(maxChildArity[childIndex], allowed[childIndex] ? childCacheEntry.MaxSubtreeCount : 0);
170            }
171            allowedCache[Tuple.Create(parent, child)] = allowed;
172          }
173          parentCacheEntry.MaxChildArity = maxChildArity;
174        }
175      }
176
177      private ISymbolicExpressionGrammarBase grammar;
178      private Dictionary<Tuple<ISymbol, ISymbol>, bool[]> allowedCache;
179      private Dictionary<ISymbol, SymbolCacheEntry> symbolCache;
180    }
181
182    public static ISymbolicExpressionTree CreateExpressionTree(IRandom random, ISymbolicExpressionGrammar grammar, int targetLength, int maxDepth, double irregularityBias = 1) {
183      // even lengths cannot be achieved without symbols of odd arity
184      // 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;
192      var symbolCache = new SymbolCache(grammar);
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) {
199        var t = tuples[i];
200        var node = t.Node;
201        var parentEntry = symbolCache[node.Symbol];
202
203        for (int childIndex = 0; childIndex < t.Arity; ++childIndex) {
204          // min and max arity here refer to the required arity limits for the child node
205          int maxChildArity = t.Depth == maxDepth - 1 ? 0 : Math.Min(parentEntry.MaxChildArity[childIndex], targetLength - openSlots);
206          int minChildArity = Math.Min((openSlots - tuples.Count > 1 && random.NextDouble() < irregularityBias) ? 0 : 1, maxChildArity);
207          var child = symbolCache.SampleNode(random, node.Symbol, childIndex, minChildArity, maxChildArity);
208          var childEntry = symbolCache[child.Symbol];
209          var childArity = random.Next(childEntry.MinSubtreeCount, childEntry.MaxSubtreeCount + 1);
210          var childDepth = t.Depth + 1;
211          node.AddSubtree(child);
212          tuples.Add(new NodeInfo { Node = child, Depth = childDepth, Arity = childArity });
213          openSlots += childArity;
214        }
215      }
216    }
217
218    protected override ISymbolicExpressionTree Create(IRandom random) {
219      var maxLength = MaximumSymbolicExpressionTreeLengthParameter.ActualValue.Value;
220      var maxDepth = MaximumSymbolicExpressionTreeDepthParameter.ActualValue.Value;
221      var grammar = ClonedSymbolicExpressionTreeGrammarParameter.ActualValue;
222      return Create(random, grammar, maxLength, maxDepth);
223    }
224
225    #region helpers
226    private class NodeInfo {
227      public ISymbolicExpressionTreeNode Node;
228      public int Depth;
229      public int Arity;
230    }
231
232    private static ISymbolicExpressionTree MakeStump(IRandom random, ISymbolicExpressionGrammar grammar) {
233      SymbolicExpressionTree tree = new SymbolicExpressionTree();
234      var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
235      if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);
236      rootNode.SetGrammar(grammar.CreateExpressionTreeGrammar());
237
238      var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
239      if (startNode.HasLocalParameters) startNode.ResetLocalParameters(random);
240      startNode.SetGrammar(grammar.CreateExpressionTreeGrammar());
241
242      rootNode.AddSubtree(startNode);
243      tree.Root = rootNode;
244      return tree;
245    }
246    #endregion
247  }
248}
Note: See TracBrowser for help on using the repository browser.