source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs @ 9456

Last change on this file since 9456 was 9456, checked in by swagner, 6 years ago

Updated copyright year and added some missing license headers (#1889)

File size: 18.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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 HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.PluginInfrastructure;
31
32namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
33  [NonDiscoverableType]
34  [StorableClass]
35  [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed length")]
36  public class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator,
37    ISymbolicExpressionTreeSizeConstraintOperator, ISymbolicExpressionTreeGrammarBasedOperator {
38    private const int MAX_TRIES = 100;
39    private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
40    private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
41    private const string SymbolicExpressionTreeGrammarParameterName = "SymbolicExpressionTreeGrammar";
42    private const string ClonedSymbolicExpressionTreeGrammarParameterName = "ClonedSymbolicExpressionTreeGrammar";
43    #region Parameter Properties
44    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeLengthParameter {
45      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeLengthParameterName]; }
46    }
47    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeDepthParameter {
48      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeDepthParameterName]; }
49    }
50    public IValueLookupParameter<ISymbolicExpressionGrammar> SymbolicExpressionTreeGrammarParameter {
51      get { return (IValueLookupParameter<ISymbolicExpressionGrammar>)Parameters[SymbolicExpressionTreeGrammarParameterName]; }
52    }
53    public ILookupParameter<ISymbolicExpressionGrammar> ClonedSymbolicExpressionTreeGrammarParameter {
54      get { return (ILookupParameter<ISymbolicExpressionGrammar>)Parameters[ClonedSymbolicExpressionTreeGrammarParameterName]; }
55    }
56    #endregion
57    #region Properties
58    public IntValue MaximumSymbolicExpressionTreeLength {
59      get { return MaximumSymbolicExpressionTreeLengthParameter.ActualValue; }
60    }
61    public IntValue MaximumSymbolicExpressionTreeDepth {
62      get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
63    }
64    public ISymbolicExpressionGrammar SymbolicExpressionTreeGrammar {
65      get { return ClonedSymbolicExpressionTreeGrammarParameter.ActualValue; }
66    }
67    #endregion
68
69    [StorableConstructor]
70    protected ProbabilisticTreeCreator(bool deserializing) : base(deserializing) { }
71    protected ProbabilisticTreeCreator(ProbabilisticTreeCreator original, Cloner cloner) : base(original, cloner) { }
72    public ProbabilisticTreeCreator()
73      : base() {
74      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
75      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
76      Parameters.Add(new ValueLookupParameter<ISymbolicExpressionGrammar>(SymbolicExpressionTreeGrammarParameterName, "The tree grammar that defines the correct syntax of symbolic expression trees that should be created."));
77      Parameters.Add(new LookupParameter<ISymbolicExpressionGrammar>(ClonedSymbolicExpressionTreeGrammarParameterName, "An immutable clone of the concrete grammar that is actually used to create and manipulate trees."));
78    }
79
80    public override IDeepCloneable Clone(Cloner cloner) {
81      return new ProbabilisticTreeCreator(this, cloner);
82    }
83    [StorableHook(HookType.AfterDeserialization)]
84    private void AfterDeserialization() {
85      if (!Parameters.ContainsKey(ClonedSymbolicExpressionTreeGrammarParameterName))
86        Parameters.Add(new LookupParameter<ISymbolicExpressionGrammar>(ClonedSymbolicExpressionTreeGrammarParameterName, "An immutable clone of the concrete grammar that is actually used to create and manipulate trees."));
87    }
88
89    public override IOperation Apply() {
90      if (ClonedSymbolicExpressionTreeGrammarParameter.ActualValue == null) {
91        SymbolicExpressionTreeGrammarParameter.ActualValue.ReadOnly = true;
92        IScope globalScope = ExecutionContext.Scope;
93        while (globalScope.Parent != null)
94          globalScope = globalScope.Parent;
95
96        globalScope.Variables.Add(new Variable(ClonedSymbolicExpressionTreeGrammarParameterName, (ISymbolicExpressionGrammar)SymbolicExpressionTreeGrammarParameter.ActualValue.Clone()));
97      }
98      return base.Apply();
99    }
100
101    protected override ISymbolicExpressionTree Create(IRandom random) {
102      return Create(random, SymbolicExpressionTreeGrammar, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value);
103    }
104
105    public override ISymbolicExpressionTree CreateTree(IRandom random, ISymbolicExpressionGrammar grammar, int maxTreeLength, int maxTreeDepth) {
106      return Create(random, grammar, maxTreeLength, maxTreeDepth);
107    }
108
109    public static ISymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar, int maxTreeLength, int maxTreeDepth) {
110      SymbolicExpressionTree tree = new SymbolicExpressionTree();
111      var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
112      if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);
113      rootNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
114      var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
115      startNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
116      if (startNode.HasLocalParameters) startNode.ResetLocalParameters(random);
117      rootNode.AddSubtree(startNode);
118      PTC2(random, startNode, maxTreeLength, maxTreeDepth);
119      tree.Root = rootNode;
120      return tree;
121    }
122
123    private class TreeExtensionPoint {
124      public ISymbolicExpressionTreeNode Parent { get; set; }
125      public int ChildIndex { get; set; }
126      public int ExtensionPointDepth { get; set; }
127      public int MaximumExtensionLength { get; set; }
128      public int MinimumExtensionLength { get; set; }
129    }
130
131    public static void PTC2(IRandom random, ISymbolicExpressionTreeNode seedNode,
132      int maxLength, int maxDepth) {
133      // make sure it is possible to create a trees smaller than maxLength and maxDepth
134      if (seedNode.Grammar.GetMinimumExpressionLength(seedNode.Symbol) > maxLength)
135        throw new ArgumentException("Cannot create trees of length " + maxLength + " or shorter because of grammar constraints.", "maxLength");
136      if (seedNode.Grammar.GetMinimumExpressionDepth(seedNode.Symbol) > maxDepth)
137        throw new ArgumentException("Cannot create trees of depth " + maxDepth + " or smaller because of grammar constraints.", "maxDepth");
138
139      // tree length is limited by the grammar and by the explicit size constraints
140      int allowedMinLength = seedNode.Grammar.GetMinimumExpressionLength(seedNode.Symbol);
141      int allowedMaxLength = Math.Min(maxLength, seedNode.Grammar.GetMaximumExpressionLength(seedNode.Symbol, maxDepth));
142      int tries = 0;
143      while (tries++ < MAX_TRIES) {
144        // select a target tree length uniformly in the possible range (as determined by explicit limits and limits of the grammar)
145        int targetTreeLength;
146        targetTreeLength = random.Next(allowedMinLength, allowedMaxLength + 1);
147        if (targetTreeLength <= 1 || maxDepth <= 1) return;
148
149        bool success = TryCreateFullTreeFromSeed(random, seedNode, targetTreeLength - 1, maxDepth - 1);
150
151        // if successful => check constraints and return the tree if everything looks ok       
152        if (success && seedNode.GetLength() <= maxLength && seedNode.GetDepth() <= maxDepth) {
153          return;
154        } else {
155          // clean seedNode
156          while (seedNode.Subtrees.Count() > 0) seedNode.RemoveSubtree(0);
157        }
158        // try a different length MAX_TRIES times
159      }
160      throw new ArgumentException("Couldn't create a random valid tree.");
161    }
162
163    private static bool TryCreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root,
164      int targetLength, int maxDepth) {
165      List<TreeExtensionPoint> extensionPoints = new List<TreeExtensionPoint>();
166      int currentLength = 0;
167      int actualArity = SampleArity(random, root, targetLength, maxDepth);
168      if (actualArity < 0) return false;
169
170      for (int i = 0; i < actualArity; i++) {
171        // insert a dummy sub-tree and add the pending extension to the list
172        var dummy = new SymbolicExpressionTreeNode();
173        root.AddSubtree(dummy);
174        var x = new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 0 };
175        FillExtensionLengths(x, maxDepth);
176        extensionPoints.Add(x);
177      }
178      //necessary to use long data type as the extension point length could be int.MaxValue
179      long minExtensionPointsLength = extensionPoints.Select(x => (long)x.MinimumExtensionLength).Sum();
180      long maxExtensionPointsLength = extensionPoints.Select(x => (long)x.MaximumExtensionLength).Sum();
181
182      // while there are pending extension points and we have not reached the limit of adding new extension points
183      while (extensionPoints.Count > 0 && minExtensionPointsLength + currentLength <= targetLength) {
184        int randomIndex = random.Next(extensionPoints.Count);
185        TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
186        extensionPoints.RemoveAt(randomIndex);
187        ISymbolicExpressionTreeNode parent = nextExtension.Parent;
188        int argumentIndex = nextExtension.ChildIndex;
189        int extensionDepth = nextExtension.ExtensionPointDepth;
190
191        if (parent.Grammar.GetMinimumExpressionDepth(parent.Symbol) > maxDepth - extensionDepth) {
192          ReplaceWithMinimalTree(random, root, parent, argumentIndex);
193          int insertedTreeLength = parent.GetSubtree(argumentIndex).GetLength();
194          currentLength += insertedTreeLength;
195          minExtensionPointsLength -= insertedTreeLength;
196          maxExtensionPointsLength -= insertedTreeLength;
197        } else {
198          //remove currently chosen extension point from calculation
199          minExtensionPointsLength -= nextExtension.MinimumExtensionLength;
200          maxExtensionPointsLength -= nextExtension.MaximumExtensionLength;
201
202          var symbols = from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, argumentIndex)
203                        where s.InitialFrequency > 0.0
204                        where parent.Grammar.GetMinimumExpressionDepth(s) <= maxDepth - extensionDepth
205                        where parent.Grammar.GetMinimumExpressionLength(s) <= targetLength - currentLength - minExtensionPointsLength
206                        select s;
207          if (maxExtensionPointsLength < targetLength - currentLength)
208            symbols = from s in symbols
209                      where parent.Grammar.GetMaximumExpressionLength(s, maxDepth - extensionDepth) >= targetLength - currentLength - maxExtensionPointsLength
210                      select s;
211          var allowedSymbols = symbols.ToList();
212
213          if (allowedSymbols.Count == 0) return false;
214          var weights = allowedSymbols.Select(x => x.InitialFrequency).ToList();
215          var selectedSymbol = allowedSymbols.SelectRandom(weights, random);
216          ISymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();
217          if (newTree.HasLocalParameters) newTree.ResetLocalParameters(random);
218          parent.RemoveSubtree(argumentIndex);
219          parent.InsertSubtree(argumentIndex, newTree);
220
221          var topLevelNode = newTree as SymbolicExpressionTreeTopLevelNode;
222          if (topLevelNode != null)
223            topLevelNode.SetGrammar((ISymbolicExpressionTreeGrammar)root.Grammar.Clone());
224
225          currentLength++;
226          actualArity = SampleArity(random, newTree, targetLength - currentLength, maxDepth - extensionDepth);
227          if (actualArity < 0) return false;
228          for (int i = 0; i < actualArity; i++) {
229            // insert a dummy sub-tree and add the pending extension to the list
230            var dummy = new SymbolicExpressionTreeNode();
231            newTree.AddSubtree(dummy);
232            var x = new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 };
233            FillExtensionLengths(x, maxDepth);
234            extensionPoints.Add(x);
235            maxExtensionPointsLength += x.MaximumExtensionLength;
236            minExtensionPointsLength += x.MinimumExtensionLength;
237          }
238        }
239      }
240      // fill all pending extension points
241      while (extensionPoints.Count > 0) {
242        int randomIndex = random.Next(extensionPoints.Count);
243        TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
244        extensionPoints.RemoveAt(randomIndex);
245        ISymbolicExpressionTreeNode parent = nextExtension.Parent;
246        int a = nextExtension.ChildIndex;
247        ReplaceWithMinimalTree(random, root, parent, a);
248      }
249      return true;
250    }
251
252    private static void ReplaceWithMinimalTree(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode parent,
253      int childIndex) {
254      // determine possible symbols that will lead to the smallest possible tree
255      var possibleSymbols = (from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)
256                             where s.InitialFrequency > 0.0
257                             group s by parent.Grammar.GetMinimumExpressionLength(s) into g
258                             orderby g.Key
259                             select g).First().ToList();
260      var weights = possibleSymbols.Select(x => x.InitialFrequency).ToList();
261      var selectedSymbol = possibleSymbols.SelectRandom(weights, random);
262      var tree = selectedSymbol.CreateTreeNode();
263      if (tree.HasLocalParameters) tree.ResetLocalParameters(random);
264      parent.RemoveSubtree(childIndex);
265      parent.InsertSubtree(childIndex, tree);
266
267      var topLevelNode = tree as SymbolicExpressionTreeTopLevelNode;
268      if (topLevelNode != null)
269        topLevelNode.SetGrammar((ISymbolicExpressionTreeGrammar)root.Grammar.Clone());
270
271      for (int i = 0; i < tree.Grammar.GetMinimumSubtreeCount(tree.Symbol); i++) {
272        // insert a dummy sub-tree and add the pending extension to the list
273        var dummy = new SymbolicExpressionTreeNode();
274        tree.AddSubtree(dummy);
275        // replace the just inserted dummy by recursive application
276        ReplaceWithMinimalTree(random, root, tree, i);
277      }
278    }
279
280    private static void FillExtensionLengths(TreeExtensionPoint extension, int maxDepth) {
281      var grammar = extension.Parent.Grammar;
282      int maxLength = int.MinValue;
283      int minLength = int.MaxValue;
284      foreach (ISymbol s in grammar.GetAllowedChildSymbols(extension.Parent.Symbol, extension.ChildIndex)) {
285        if (s.InitialFrequency > 0.0) {
286          int max = grammar.GetMaximumExpressionLength(s, maxDepth - extension.ExtensionPointDepth);
287          maxLength = Math.Max(maxLength, max);
288          int min = grammar.GetMinimumExpressionLength(s);
289          minLength = Math.Min(minLength, min);
290        }
291      }
292
293      extension.MaximumExtensionLength = maxLength;
294      extension.MinimumExtensionLength = minLength;
295    }
296
297    private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetLength, int maxDepth) {
298      // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
299      int minArity = node.Grammar.GetMinimumSubtreeCount(node.Symbol);
300      int maxArity = node.Grammar.GetMaximumSubtreeCount(node.Symbol);
301      if (maxArity > targetLength) {
302        maxArity = targetLength;
303      }
304      if (minArity == maxArity) return minArity;
305
306      // the min number of sub-trees has to be set to a value that is large enough so that the largest possible tree is at least tree length
307      // if 1..3 trees are possible and the largest possible first sub-tree is smaller larger than the target length then minArity should be at least 2
308      long aggregatedLongestExpressionLength = 0;
309      for (int i = 0; i < maxArity; i++) {
310        aggregatedLongestExpressionLength += (from s in node.Grammar.GetAllowedChildSymbols(node.Symbol, i)
311                                              where s.InitialFrequency > 0.0
312                                              select node.Grammar.GetMaximumExpressionLength(s, maxDepth)).Max();
313        if (i > minArity && aggregatedLongestExpressionLength < targetLength) minArity = i + 1;
314        else break;
315      }
316
317      // the max number of sub-trees has to be set to a value that is small enough so that the smallest possible tree is at most tree length
318      // if 1..3 trees are possible and the smallest possible first sub-tree is already larger than the target length then maxArity should be at most 0
319      long aggregatedShortestExpressionLength = 0;
320      for (int i = 0; i < maxArity; i++) {
321        aggregatedShortestExpressionLength += (from s in node.Grammar.GetAllowedChildSymbols(node.Symbol, i)
322                                               where s.InitialFrequency > 0.0
323                                               select node.Grammar.GetMinimumExpressionLength(s)).Min();
324        if (aggregatedShortestExpressionLength > targetLength) {
325          maxArity = i;
326          break;
327        }
328      }
329      if (minArity > maxArity) return -1;
330      return random.Next(minArity, maxArity + 1);
331    }
332
333  }
334}
Note: See TracBrowser for help on using the repository browser.