Free cookie consent management tool by TermsFeed Policy Generator

source: branches/3.2/sources/HeuristicLab.GP/3.3/TreeGardener.cs @ 6225

Last change on this file since 6225 was 2730, checked in by gkronber, 15 years ago

Made PTC2 operator more robust. #859 (PTC2 initialization operator fails if it is used with restrictive function libraries)

File size: 21.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 System;
23using System.Collections.Generic;
24using HeuristicLab.Core;
25using System.Linq;
26using System.Collections;
27using HeuristicLab.GP.Interfaces;
28
29namespace HeuristicLab.GP {
30  public class TreeGardener {
31    private IRandom random;
32    private FunctionLibrary funLibrary;
33    private List<IFunction> functions;
34
35    private List<IFunction> terminals;
36    public IList<IFunction> Terminals {
37      get { return terminals; }
38    }
39
40    private List<IFunction> allFunctions;
41    public IList<IFunction> AllFunctions {
42      get { return allFunctions; }
43    }
44
45    #region constructors
46    public TreeGardener(IRandom random, FunctionLibrary funLibrary) {
47      this.random = random;
48      this.funLibrary = funLibrary;
49      this.allFunctions = new List<IFunction>();
50      terminals = new List<IFunction>();
51      functions = new List<IFunction>();
52      // init functions and terminals based on constraints
53      foreach (IFunction fun in funLibrary.Functions) {
54        if (fun.MaxSubTrees == 0) {
55          terminals.Add(fun);
56          allFunctions.Add(fun);
57        } else {
58          functions.Add(fun);
59          allFunctions.Add(fun);
60        }
61      }
62    }
63    #endregion
64
65    #region random initialization
66    /// <summary>
67    /// Creates a random balanced tree with a maximal size and height. When the max-height or max-size are 1 it will return a random terminal.
68    /// In other cases it will return either a terminal (tree of size 1) or any other tree with a function in it's root (at least height 2).
69    /// </summary>
70    /// <param name="maxTreeSize">Maximal size of the tree (number of nodes).</param>
71    /// <param name="maxTreeHeight">Maximal height of the tree.</param>
72    /// <returns></returns>
73    public IFunctionTree CreateBalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
74      IFunction rootFunction = GetRandomRoot(maxTreeSize, maxTreeHeight);
75      IFunctionTree tree = MakeBalancedTree(rootFunction, maxTreeHeight - 1);
76      return tree;
77    }
78
79    /// <summary>
80    /// Creates a random (unbalanced) tree with a maximal size and height. When the max-height or max-size are 1 it will return a random terminal.
81    /// In other cases it will return either a terminal (tree of size 1) or any other tree with a function in it's root (at least height 2).
82    /// </summary>
83    /// <param name="maxTreeSize">Maximal size of the tree (number of nodes).</param>
84    /// <param name="maxTreeHeight">Maximal height of the tree.</param>
85    /// <returns></returns>
86    public IFunctionTree CreateUnbalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
87      IFunction rootFunction = GetRandomRoot(maxTreeSize, maxTreeHeight);
88      IFunctionTree tree = MakeUnbalancedTree(rootFunction, maxTreeHeight - 1);
89      return tree;
90    }
91
92    public IFunctionTree PTC2(int size, int maxDepth) {
93      return PTC2(GetRandomRoot(size, maxDepth), size, maxDepth);
94    }
95
96    private IFunctionTree PTC2(IFunction rootFunction, int size, int maxDepth) {
97      IFunctionTree root = rootFunction.GetTreeNode();
98      if (size <= 1 || maxDepth <= 1) return root;
99      List<object[]> list = new List<object[]>();
100      int currentSize = 1;
101      int totalListMinSize = 0;
102      int minArity = root.Function.MinSubTrees;
103      int maxArity = root.Function.MaxSubTrees;
104      if (maxArity >= size) {
105        maxArity = size;
106      }
107      int actualArity = random.Next(minArity, maxArity + 1);
108      totalListMinSize += root.Function.MinTreeSize - 1;
109      for (int i = 0; i < actualArity; i++) {
110        // insert a dummy sub-tree and add the pending extension to the list
111        root.AddSubTree(null);
112        list.Add(new object[] { root, i, 2 });
113      }
114      if (IsRecursiveExpansionPossible(root.Function)) {
115        while (list.Count > 0 && totalListMinSize + currentSize < size) {
116          int randomIndex = random.Next(list.Count);
117          object[] nextExtension = list[randomIndex];
118          list.RemoveAt(randomIndex);
119          IFunctionTree parent = (IFunctionTree)nextExtension[0];
120          int a = (int)nextExtension[1];
121          int d = (int)nextExtension[2];
122          if (d + parent.Function.MinTreeHeight >= maxDepth) {
123            parent.RemoveSubTree(a);
124            IFunctionTree branch = CreateRandomTree(GetAllowedSubFunctions(parent.Function, a), 1, 1);
125            parent.InsertSubTree(a, branch); // insert a smallest possible tree
126            currentSize += branch.GetSize();
127            totalListMinSize -= branch.GetSize();
128          } else {
129            var allowedSubFunctions = from f in GetAllowedSubFunctions(parent.Function, a)
130                                      where f.MinTreeHeight + (d - 1) < maxDepth
131                                      where IsRecursiveExpansionPossible(f) ||
132                                            totalListMinSize + currentSize >= size * 0.9 // if the necessary size is almost reached then also allow
133                                                                                         // terminals or terminal-branches
134                                      select f;
135            IFunction selectedFunction = TreeGardener.RandomSelect(random, allowedSubFunctions.ToList());
136            IFunctionTree newTree = selectedFunction.GetTreeNode();
137            parent.RemoveSubTree(a);
138            parent.InsertSubTree(a, newTree);
139            currentSize++;
140            totalListMinSize--;
141
142            minArity = selectedFunction.MinSubTrees;
143            maxArity = selectedFunction.MaxSubTrees;
144            if (maxArity >= size) {
145              maxArity = size;
146            }
147            actualArity = random.Next(minArity, maxArity + 1);
148            for (int i = 0; i < actualArity; i++) {
149              // insert a dummy sub-tree and add the pending extension to the list
150              newTree.AddSubTree(null);
151              list.Add(new object[] { newTree, i, d + 1 });
152            }
153            totalListMinSize += newTree.Function.MinTreeSize;
154          }
155        }
156      }
157      while (list.Count > 0) {
158        int randomIndex = random.Next(list.Count);
159        object[] nextExtension = list[randomIndex];
160        list.RemoveAt(randomIndex);
161        IFunctionTree parent = (IFunctionTree)nextExtension[0];
162        int a = (int)nextExtension[1];
163        int d = (int)nextExtension[2];
164        parent.RemoveSubTree(a);
165        parent.InsertSubTree(a,
166          CreateRandomTree(GetAllowedSubFunctions(parent.Function, a), 1, 1)); // append a tree with minimal possible height
167      }
168      return root;
169    }
170
171    private bool IsRecursiveExpansionPossible(IFunction function) {
172      return FindCycle(function, new Stack<IFunction>());
173    }
174
175    private Dictionary<IFunction, bool> inCycle = new Dictionary<IFunction, bool>();
176    private bool FindCycle(IFunction function, Stack<IFunction> functionChain) {
177      if (inCycle.ContainsKey(function)) {
178        return inCycle[function];
179      } else if (IsTerminal(function)) {
180        inCycle[function] = false;
181        return false;
182      } else if (functionChain.Contains(function)) {
183        inCycle[function] = true;
184        return true;
185      } else {
186        functionChain.Push(function);
187        bool result = false;
188        // all slot indexes
189        for (int i = 0; i < function.MaxSubTrees; i++) {
190          foreach (IFunction subFunction in GetAllowedSubFunctions(function, i)) {
191            result |= FindCycle(subFunction, functionChain);
192          }
193        }
194
195        functionChain.Pop();
196        inCycle[function] = result;
197        return result;
198      }
199    }
200
201    /// <summary>
202    /// selects a random function from allowedFunctions and creates a random (unbalanced) tree with maximal size and height.
203    /// </summary>
204    /// <param name="allowedFunctions">Set of allowed functions.</param>
205    /// <param name="maxTreeSize">Maximal size of the tree (number of nodes).</param>
206    /// <param name="maxTreeHeight">Maximal height of the tree.</param>
207    /// <returns>New random unbalanced tree</returns>
208    public IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight) {
209      // get the minimal needed height based on allowed functions and extend the max-height if necessary
210      int minTreeHeight = allowedFunctions.Select(f => f.MinTreeHeight).Min();
211      if (minTreeHeight > maxTreeHeight)
212        maxTreeHeight = minTreeHeight;
213      // get the minimal needed size based on allowed functions and extend the max-size if necessary
214      int minTreeSize = allowedFunctions.Select(f => f.MinTreeSize).Min();
215      if (minTreeSize > maxTreeSize)
216        maxTreeSize = minTreeSize;
217
218      // select a random value for the size and height
219      int treeHeight = random.Next(minTreeHeight, maxTreeHeight + 1);
220      int treeSize = random.Next(minTreeSize, maxTreeSize + 1);
221
222      // filter the set of allowed functions and select only from those that fit into the given maximal size and height limits
223      IFunction[] possibleFunctions = allowedFunctions.Where(f => f.MinTreeHeight <= treeHeight &&
224        f.MinTreeSize <= treeSize).ToArray();
225      IFunction selectedFunction = RandomSelect(possibleFunctions);
226
227      // build the tree
228      IFunctionTree root;
229      root = PTC2(selectedFunction, maxTreeSize, maxTreeHeight);
230      return root;
231    }
232    #endregion
233
234    #region tree information gathering
235    public IFunctionTree GetRandomParentNode(IFunctionTree tree) {
236      List<IFunctionTree> parentNodes = new List<IFunctionTree>();
237
238      // add null for the parent of the root node
239      parentNodes.Add(null);
240
241      TreeForEach(tree, delegate(IFunctionTree possibleParentNode) {
242        if (possibleParentNode.SubTrees.Count > 0) {
243          parentNodes.Add(possibleParentNode);
244        }
245      });
246
247      return parentNodes[random.Next(parentNodes.Count)];
248    }
249
250    public static ICollection<IFunctionTree> GetAllSubTrees(IFunctionTree root) {
251      List<IFunctionTree> allTrees = new List<IFunctionTree>();
252      TreeForEach(root, t => { allTrees.Add(t); });
253      return allTrees;
254    }
255
256    /// <summary>
257    /// returns the height level of branch in the tree
258    /// if the branch == tree => 1
259    /// if branch is in the sub-trees of tree => 2
260    /// ...
261    /// if branch is not found => -1
262    /// </summary>
263    /// <param name="tree">root of the function tree to process</param>
264    /// <param name="branch">branch that is searched in the tree</param>
265    /// <returns></returns>
266    public int GetBranchLevel(IFunctionTree tree, IFunctionTree branch) {
267      return GetBranchLevelHelper(tree, branch, 1);
268    }
269
270    // 'tail-recursive' helper
271    private int GetBranchLevelHelper(IFunctionTree tree, IFunctionTree branch, int level) {
272      if (branch == tree) return level;
273
274      foreach (IFunctionTree subTree in tree.SubTrees) {
275        int result = GetBranchLevelHelper(subTree, branch, level + 1);
276        if (result != -1) return result;
277      }
278
279      return -1;
280    }
281
282    public bool IsValidTree(IFunctionTree tree) {
283      for (int i = 0; i < tree.SubTrees.Count; i++) {
284        if (!tree.Function.GetAllowedSubFunctions(i).Contains(tree.SubTrees[i].Function)) return false;
285      }
286
287      if (tree.SubTrees.Count < tree.Function.MinSubTrees || tree.SubTrees.Count > tree.Function.MaxSubTrees)
288        return false;
289      foreach (IFunctionTree subTree in tree.SubTrees) {
290        if (!IsValidTree(subTree)) return false;
291      }
292      return true;
293    }
294
295    // returns a random branch from the specified level in the tree
296    public IFunctionTree GetRandomBranch(IFunctionTree tree, int level) {
297      if (level == 0) return tree;
298      List<IFunctionTree> branches = new List<IFunctionTree>();
299      GetBranchesAtLevel(tree, level, branches);
300      return branches[random.Next(branches.Count)];
301    }
302    #endregion
303
304    #region function information (arity, allowed childs and parents)
305    internal ICollection<IFunction> GetPossibleParents(List<IFunction> list) {
306      List<IFunction> result = new List<IFunction>();
307      foreach (IFunction f in functions) {
308        if (IsPossibleParent(f, list)) {
309          result.Add(f);
310        }
311      }
312      return result;
313    }
314
315    private bool IsPossibleParent(IFunction f, List<IFunction> children) {
316      int minArity = f.MinSubTrees;
317      int maxArity = f.MaxSubTrees;
318      // note: we can't assume that the operators in the children list have different types!
319
320      // when the maxArity of this function is smaller than the list of operators that
321      // should be included as sub-operators then it can't be a parent
322      if (maxArity < children.Count()) {
323        return false;
324      }
325      int nSlots = Math.Max(minArity, children.Count);
326
327      List<HashSet<IFunction>> slotSets = new List<HashSet<IFunction>>();
328
329      // we iterate through all slots for sub-trees and calculate the set of
330      // allowed functions for this slot.
331      // we only count those slots that can hold at least one of the children that we should combine
332      for (int slot = 0; slot < nSlots; slot++) {
333        HashSet<IFunction> functionSet = new HashSet<IFunction>(f.GetAllowedSubFunctions(slot));
334        if (functionSet.Count() > 0) {
335          slotSets.Add(functionSet);
336        }
337      }
338
339      // ok at the end of this operation we know how many slots of the parent can actually
340      // hold one of our children.
341      // if the number of slots is smaller than the number of children we can be sure that
342      // we can never combine all children as sub-trees of the function and thus the function
343      // can't be a parent.
344      if (slotSets.Count() < children.Count()) {
345        return false;
346      }
347
348      // finally we sort the sets by size and beginning from the first set select one
349      // function for the slot and thus remove it as possible sub-tree from the remaining sets.
350      // when we can successfully assign all available children to a slot the function is a valid parent
351      // when only a subset of all children can be assigned to slots the function is no valid parent
352      slotSets.Sort((p, q) => p.Count() - q.Count());
353
354      int assignments = 0;
355      for (int i = 0; i < slotSets.Count() - 1; i++) {
356        if (slotSets[i].Count > 0) {
357          IFunction selected = slotSets[i].ElementAt(0);
358          assignments++;
359          for (int j = i + 1; j < slotSets.Count(); j++) {
360            slotSets[j].Remove(selected);
361          }
362        }
363      }
364
365      // sanity check
366      if (assignments > children.Count) throw new InvalidProgramException();
367      return assignments == children.Count - 1;
368    }
369    public IList<IFunction> GetAllowedParents(IFunction child, int childIndex) {
370      List<IFunction> parents = new List<IFunction>();
371      foreach (IFunction function in functions) {
372        ICollection<IFunction> allowedSubFunctions = GetAllowedSubFunctions(function, childIndex);
373        if (allowedSubFunctions.Contains(child)) {
374          parents.Add(function);
375        }
376      }
377      return parents;
378    }
379    public static bool IsTerminal(IFunction f) {
380      return f.MinSubTrees == 0 && f.MaxSubTrees == 0;
381    }
382    public ICollection<IFunction> GetAllowedSubFunctions(IFunction f, int index) {
383      if (f == null) {
384        return allFunctions;
385      } else {
386        return f.GetAllowedSubFunctions(index);
387      }
388    }
389    #endregion
390
391    #region private utility methods
392    public IFunction GetRandomRoot(int maxTreeSize, int maxTreeHeight) {
393      if (maxTreeHeight == 1 || maxTreeSize == 1) {
394        IFunction selectedTerminal = RandomSelect(terminals);
395        return selectedTerminal;
396      } else {
397        int minExpandableTreeSize = (from f in functions
398                                     where IsRecursiveExpansionPossible(f)
399                                     select f.MinTreeSize).Min();
400        int minExpandableTreeHeight = (from f in functions
401                                       where IsRecursiveExpansionPossible(f)
402                                       select f.MinTreeHeight).Min();
403        IFunction[] possibleFunctions;
404        if (maxTreeSize < minExpandableTreeSize || maxTreeHeight < minExpandableTreeHeight) {
405          possibleFunctions = functions.Where(f => f.MinTreeHeight <= maxTreeHeight &&
406            f.MinTreeSize <= maxTreeSize).ToArray();
407        } else {
408          possibleFunctions = functions.Where(f => f.MinTreeHeight <= maxTreeHeight &&
409            f.MinTreeSize <= maxTreeSize && IsRecursiveExpansionPossible(f)).ToArray();
410        }
411        return RandomSelect(possibleFunctions);
412      }
413    }
414
415
416    private IFunctionTree MakeUnbalancedTree(IFunction parent, int maxTreeHeight) {
417      if (maxTreeHeight == 0) return parent.GetTreeNode();
418      int minArity = parent.MinSubTrees;
419      int maxArity = parent.MaxSubTrees;
420      int actualArity = random.Next(minArity, maxArity + 1);
421      if (actualArity > 0) {
422        IFunctionTree parentTree = parent.GetTreeNode();
423        for (int i = 0; i < actualArity; i++) {
424          IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => f.MinTreeHeight <= maxTreeHeight).ToArray();
425          IFunction selectedFunction = RandomSelect(possibleFunctions);
426          IFunctionTree newSubTree = MakeUnbalancedTree(selectedFunction, maxTreeHeight - 1);
427          parentTree.InsertSubTree(i, newSubTree);
428        }
429        return parentTree;
430      }
431      return parent.GetTreeNode();
432    }
433
434
435    // NOTE: this method doesn't build fully balanced trees because we have constraints on the
436    // types of possible sub-functions which can indirectly impose a limit for the depth of a given sub-tree
437    private IFunctionTree MakeBalancedTree(IFunction parent, int maxTreeHeight) {
438      if (maxTreeHeight == 0) return parent.GetTreeNode();
439      int minArity = parent.MinSubTrees;
440      int maxArity = parent.MaxSubTrees;
441      int actualArity = random.Next(minArity, maxArity + 1);
442      if (actualArity > 0) {
443        IFunctionTree parentTree = parent.GetTreeNode();
444        for (int i = 0; i < actualArity; i++) {
445          // first try to find a function that fits into the maxHeight limit
446          IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => f.MinTreeHeight <= maxTreeHeight &&
447            !IsTerminal(f)).ToArray();
448          // no possible function found => extend function set to terminals
449          if (possibleFunctions.Length == 0) {
450            possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => IsTerminal(f)).ToArray();
451            IFunction selectedTerminal = RandomSelect(possibleFunctions);
452            IFunctionTree newTree = selectedTerminal.GetTreeNode();
453            parentTree.InsertSubTree(i, newTree);
454          } else {
455            IFunction selectedFunction = RandomSelect(possibleFunctions);
456            IFunctionTree newTree = MakeBalancedTree(selectedFunction, maxTreeHeight - 1);
457            parentTree.InsertSubTree(i, newTree);
458          }
459        }
460        return parentTree;
461      }
462      return parent.GetTreeNode();
463    }
464
465    private static void TreeForEach(IFunctionTree tree, Action<IFunctionTree> action) {
466      action(tree);
467      foreach (IFunctionTree subTree in tree.SubTrees) {
468        TreeForEach(subTree, action);
469      }
470    }
471
472    private static void GetBranchesAtLevel(IFunctionTree tree, int level, List<IFunctionTree> result) {
473      if (level == 1) result.AddRange(tree.SubTrees);
474      foreach (IFunctionTree subTree in tree.SubTrees) {
475        if (subTree.GetHeight() >= level - 1)
476          GetBranchesAtLevel(subTree, level - 1, result);
477      }
478    }
479
480    private IFunction RandomSelect(IList<IFunction> functionSet) {
481      return RandomSelect(random, functionSet);
482    }
483
484    public static IFunction RandomSelect(IRandom random, IList<IFunction> functionSet) {
485      if (random == null || functionSet == null) throw new ArgumentNullException();
486      if (functionSet.Count == 0) throw new ArgumentException("Empty function set");
487      if (functionSet.Select(x => x.Tickets).Sum() <= 0) throw new ArgumentException("All functions in set have 0 tickets");
488      double[] accumulatedTickets = new double[functionSet.Count];
489      double ticketAccumulator = 0;
490      int i = 0;
491      // precalculate the slot-sizes
492      foreach (IFunction function in functionSet) {
493        ticketAccumulator += function.Tickets;
494        accumulatedTickets[i] = ticketAccumulator;
495        i++;
496      }
497      // throw ball
498      double r = random.NextDouble() * ticketAccumulator;
499      // find the slot that has been hit
500      for (i = 0; i < accumulatedTickets.Length; i++) {
501        if (r < accumulatedTickets[i]) return functionSet[i];
502      }
503      throw new ArgumentException();
504    }
505
506    #endregion
507
508  }
509}
Note: See TracBrowser for help on using the repository browser.