Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 4477 was 4477, checked in by gkronber, 14 years ago

Merged r4458, r4459,r4462,r4464 from data analysis exploration branch into trunk. #1142

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