Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs @ 11874

Last change on this file since 11874 was 11874, checked in by mkommend, 8 years ago

#2268: Merged r11494, r11495, r11496, r11497, r11498, r11504, r11532, r11536 into stable.

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