Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 3338 was 3338, checked in by gkronber, 12 years ago

Fixed bugs related to dynamic symbol constraints with ADFs. #290 (Implement ADFs)

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