Free cookie consent management tool by TermsFeed Policy Generator

source: branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs @ 5686

Last change on this file since 5686 was 5686, checked in by mkommend, 12 years ago

#1418: Finally added results from the grammar refactoring.

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