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

Last change on this file since 12422 was 12422, checked in by mkommend, 5 years ago

#2320: Merged the encoding class and all accompanying changes in the trunk.

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