Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Creators/ProbabilisticTreeCreator.cs @ 7211

Last change on this file since 7211 was 5445, checked in by swagner, 14 years ago

Updated year of copyrights (#1406)

File size: 15.3 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 System.Text;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureManipulators;
30using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Creators {
34  [StorableClass]
35  [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed size")]
36  public sealed class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator {
37    private const int MAX_TRIES = 100;
38    [StorableConstructor]
39    private ProbabilisticTreeCreator(bool deserializing) : base(deserializing) { }
40    private ProbabilisticTreeCreator(ProbabilisticTreeCreator original, Cloner cloner) : base(original, cloner) { }
41    public ProbabilisticTreeCreator() : base() { }
42
43    public override IDeepCloneable Clone(Cloner cloner) {
44      return new ProbabilisticTreeCreator(this, cloner);
45    }
46
47    protected override SymbolicExpressionTree Create(
48      IRandom random,
49      ISymbolicExpressionGrammar grammar,
50      IntValue maxTreeSize, IntValue maxTreeHeight,
51      IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
52      return Create(random, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
53    }
54
55    public static SymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar,
56      int maxTreeSize, int maxTreeHeight,
57      int maxFunctionDefinitions, int maxFunctionArguments
58      ) {
59      SymbolicExpressionTree tree = new SymbolicExpressionTree();
60      var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
61      if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);
62      rootNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
63      tree.Root = PTC2(random, rootNode, maxTreeSize, maxTreeHeight, maxFunctionDefinitions, maxFunctionArguments);
64      return tree;
65    }
66
67    private class TreeExtensionPoint {
68      public SymbolicExpressionTreeNode Parent { get; set; }
69      public int ChildIndex { get; set; }
70      public int ExtensionPointDepth { get; set; }
71    }
72
73    public static SymbolicExpressionTreeNode PTC2(IRandom random, SymbolicExpressionTreeNode seedNode,
74      int maxTreeSize, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
75      // tree size is limited by the grammar and by the explicit size constraints
76      int allowedMinSize = seedNode.Grammar.GetMinExpressionLength(seedNode.Symbol);
77      int allowedMaxSize = Math.Min(maxTreeSize, seedNode.Grammar.GetMaxExpressionLength(seedNode.Symbol));
78      int tries = 0;
79      while (tries++ < MAX_TRIES) {
80        // select a target tree size uniformly in the possible range (as determined by explicit limits and limits of the grammar)
81        int treeSize = random.Next(allowedMinSize, allowedMaxSize + 1);
82        if (treeSize <= 1 || maxDepth <= 1) return seedNode;
83
84        bool success = CreateFullTreeFromSeed(random, seedNode, seedNode.Grammar, treeSize, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
85
86        // if successful => check constraints and return the tree if everything looks ok       
87        if (success && seedNode.GetSize() <= maxTreeSize && seedNode.GetHeight() <= maxDepth) {
88          return seedNode;
89        } else {
90          // clean seedNode
91          while (seedNode.SubTrees.Count > 0) seedNode.RemoveSubTree(0);
92        }
93        // try a different size MAX_TRIES times
94      }
95      throw new ArgumentException("Couldn't create a random valid tree.");
96    }
97
98    private static bool CreateFullTreeFromSeed(IRandom random, SymbolicExpressionTreeNode root, ISymbolicExpressionGrammar globalGrammar,
99      int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
100      try {
101        TryCreateFullTreeFromSeed(random, root, globalGrammar, size, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
102        return true;
103      }
104      catch (ArgumentException) { return false; }
105    }
106
107    private static void TryCreateFullTreeFromSeed(IRandom random, SymbolicExpressionTreeNode root, ISymbolicExpressionGrammar globalGrammar,
108      int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
109      List<TreeExtensionPoint> extensionPoints = new List<TreeExtensionPoint>();
110      int currentSize = 1;
111      int totalListMinSize = globalGrammar.GetMinExpressionLength(root.Symbol) - 1;
112      int actualArity = SampleArity(random, root, size);
113      for (int i = 0; i < actualArity; i++) {
114        // insert a dummy sub-tree and add the pending extension to the list
115        var dummy = new SymbolicExpressionTreeNode();
116        root.AddSubTree(dummy);
117        extensionPoints.Add(new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 0 });
118      }
119      // while there are pending extension points and we have not reached the limit of adding new extension points
120      while (extensionPoints.Count > 0 && totalListMinSize + currentSize < size) {
121        int randomIndex = random.Next(extensionPoints.Count);
122        TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
123        extensionPoints.RemoveAt(randomIndex);
124        SymbolicExpressionTreeNode parent = nextExtension.Parent;
125        int argumentIndex = nextExtension.ChildIndex;
126        int extensionDepth = nextExtension.ExtensionPointDepth;
127        if (extensionDepth + parent.Grammar.GetMinExpressionDepth(parent.Symbol) >= maxDepth) {
128          ReplaceWithMinimalTree(random, root, parent, argumentIndex, maxFunctionDefinitions, maxFunctionArguments);
129        } else {
130          var allowedSymbols = from s in parent.Grammar.Symbols
131                               where parent.Grammar.IsAllowedChild(parent.Symbol, s, argumentIndex)
132                               where parent.Grammar.GetMinExpressionDepth(s) + extensionDepth - 1 < maxDepth
133                               where parent.Grammar.GetMaxExpressionLength(s) > size - totalListMinSize - currentSize
134                               select s;
135          Symbol selectedSymbol = SelectRandomSymbol(random, allowedSymbols);
136          SymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();
137          if (newTree.HasLocalParameters) newTree.ResetLocalParameters(random);
138          parent.RemoveSubTree(argumentIndex);
139          parent.InsertSubTree(argumentIndex, newTree);
140
141          InitializeNewTreeNode(random, root, newTree, maxFunctionDefinitions, maxFunctionArguments);
142
143          currentSize++;
144          totalListMinSize--;
145
146          actualArity = SampleArity(random, newTree, size - currentSize);
147          for (int i = 0; i < actualArity; i++) {
148            // insert a dummy sub-tree and add the pending extension to the list
149            var dummy = new SymbolicExpressionTreeNode();
150            newTree.AddSubTree(dummy);
151            extensionPoints.Add(new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 });
152          }
153          totalListMinSize += newTree.Grammar.GetMinExpressionLength(newTree.Symbol);
154        }
155      }
156      // fill all pending extension points
157      while (extensionPoints.Count > 0) {
158        int randomIndex = random.Next(extensionPoints.Count);
159        TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
160        extensionPoints.RemoveAt(randomIndex);
161        SymbolicExpressionTreeNode parent = nextExtension.Parent;
162        int a = nextExtension.ChildIndex;
163        int d = nextExtension.ExtensionPointDepth;
164        ReplaceWithMinimalTree(random, root, parent, a, maxFunctionDefinitions, maxFunctionArguments);
165      }
166    }
167
168    private static void ReplaceWithMinimalTree(IRandom random, SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode parent, int argumentIndex, int maxFunctionDefinitions, int maxFunctionArguments) {
169      // determine possible symbols that will lead to the smallest possible tree
170      var possibleSymbols = (from s in parent.GetAllowedSymbols(argumentIndex)
171                             group s by parent.Grammar.GetMinExpressionLength(s) into g
172                             orderby g.Key
173                             select g).First();
174      var selectedSymbol = SelectRandomSymbol(random, possibleSymbols);
175      var tree = selectedSymbol.CreateTreeNode();
176      if (tree.HasLocalParameters) tree.ResetLocalParameters(random);
177      parent.RemoveSubTree(argumentIndex);
178      parent.InsertSubTree(argumentIndex, tree);
179      InitializeNewTreeNode(random, root, tree, maxFunctionDefinitions, maxFunctionArguments);
180      for (int i = 0; i < tree.GetMinSubtreeCount(); i++) {
181        // insert a dummy sub-tree and add the pending extension to the list
182        var dummy = new SymbolicExpressionTreeNode();
183        tree.AddSubTree(dummy);
184        // replace the just inserted dummy by recursive application
185        ReplaceWithMinimalTree(random, root, tree, i, maxFunctionDefinitions, maxFunctionArguments);
186      }
187    }
188
189    private static void InitializeNewTreeNode(IRandom random, SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode newTree, int maxFunctionDefinitions, int maxFunctionArguments) {
190      // NB it is assumed that defuns are only allowed as children of root and nowhere else
191      // also assumes that newTree is already attached to root somewhere
192      if (IsTopLevelBranch(root, newTree)) {
193        ((SymbolicExpressionTreeTopLevelNode)newTree).SetGrammar((ISymbolicExpressionGrammar)root.Grammar.Clone());
194
195        // allow invokes of existing ADFs with higher index
196        int argIndex = root.SubTrees.IndexOf(newTree);
197        for (int i = argIndex + 1; i < root.SubTrees.Count; i++) {
198          var otherDefunNode = root.SubTrees[i] as DefunTreeNode;
199          if (otherDefunNode != null) {
200            GrammarModifier.AddDynamicSymbol(newTree.Grammar, newTree.Symbol, otherDefunNode.FunctionName, otherDefunNode.NumberOfArguments);
201          }
202        }
203      }
204      if (newTree.Symbol is Defun) {
205        var defunTree = newTree as DefunTreeNode;
206        string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefinitions * 10 - 1)).ToString(); // >= 100 functions => ###
207        var allowedNames = from index in Enumerable.Range(0, maxFunctionDefinitions)
208                           select "ADF" + index.ToString(formatString);
209        var takenNames = (from node in root.IterateNodesPrefix().OfType<DefunTreeNode>()
210                          select node.FunctionName).Distinct();
211        var remainingNames = allowedNames.Except(takenNames).ToList();
212        string functionName = remainingNames[random.Next(remainingNames.Count)];
213        // set name and number of arguments of the ADF
214        int nArgs = random.Next(maxFunctionArguments);
215        defunTree.FunctionName = functionName;
216        defunTree.NumberOfArguments = nArgs;
217        if (nArgs > 0) {
218          GrammarModifier.AddDynamicArguments(defunTree.Grammar, defunTree.Symbol, Enumerable.Range(0, nArgs));
219        }
220        // in existing branches with smaller index allow invoke of current function
221        int argIndex = root.SubTrees.IndexOf(newTree);
222        for (int i = 0; i < argIndex; i++) {
223          // if not dummy node
224          if (root.SubTrees[i].Symbol != null) {
225            var existingBranch = root.SubTrees[i];
226            GrammarModifier.AddDynamicSymbol(existingBranch.Grammar, existingBranch.Symbol, functionName, nArgs);
227          }
228        }
229      }
230    }
231
232    private static bool IsTopLevelBranch(SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode branch) {
233      return branch is SymbolicExpressionTreeTopLevelNode;
234    }
235
236    private static Symbol SelectRandomSymbol(IRandom random, IEnumerable<Symbol> symbols) {
237      var symbolList = symbols.ToList();
238      var ticketsSum = symbolList.Select(x => x.InitialFrequency).Sum();
239      if (ticketsSum == 0.0) throw new ArgumentException("The initial frequency of all allowed symbols is zero.");
240      var r = random.NextDouble() * ticketsSum;
241      double aggregatedTickets = 0;
242      for (int i = 0; i < symbolList.Count; i++) {
243        aggregatedTickets += symbolList[i].InitialFrequency;
244        if (aggregatedTickets > r) {
245          return symbolList[i];
246        }
247      }
248      // this should never happen
249      throw new ArgumentException("There is a problem with the initial frequency setting of allowed symbols.");
250    }
251
252    private static int SampleArity(IRandom random, SymbolicExpressionTreeNode node, int targetSize) {
253      // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
254      int minArity = node.GetMinSubtreeCount();
255      int maxArity = node.GetMaxSubtreeCount();
256      if (maxArity > targetSize) {
257        maxArity = targetSize;
258      }
259      // 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 size
260      // if 1..3 trees are possible and the largest possible first sub-tree is smaller larger than the target size then minArity should be at least 2
261      long aggregatedLongestExpressionLength = 0;
262      for (int i = 0; i < maxArity; i++) {
263        aggregatedLongestExpressionLength += (from s in node.GetAllowedSymbols(i)
264                                              select node.Grammar.GetMaxExpressionLength(s)).Max();
265        if (aggregatedLongestExpressionLength < targetSize) minArity = i;
266        else break;
267      }
268
269      // 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 size
270      // if 1..3 trees are possible and the smallest possible first sub-tree is already larger than the target size then maxArity should be at most 0
271      long aggregatedShortestExpressionLength = 0;
272      for (int i = 0; i < maxArity; i++) {
273        aggregatedShortestExpressionLength += (from s in node.GetAllowedSymbols(i)
274                                               select node.Grammar.GetMinExpressionLength(s)).Min();
275        if (aggregatedShortestExpressionLength > targetSize) {
276          maxArity = i;
277          break;
278        }
279      }
280      if (minArity > maxArity) throw new ArgumentException();
281      return random.Next(minArity, maxArity + 1);
282    }
283  }
284}
Note: See TracBrowser for help on using the repository browser.