Free cookie consent management tool by TermsFeed Policy Generator

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

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

Implemented manipulation operator for symbolic expression tree encoding that replaces one randomly chosen branch with a new randomly initialized branch. #1070

File size: 14.8 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 = grammar.StartSymbol.CreateTreeNode();
56      if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);
57      rootNode.Grammar = 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 = 2 });
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        newTree.Grammar = (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.