Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Hive_Milestone3/sources/HeuristicLab.GP/3.3/TreeGardener.cs @ 6319

Last change on this file since 6319 was 1529, checked in by gkronber, 16 years ago

Moved source files of plugins AdvancedOptimizationFrontEnd ... Grid into version-specific sub-folders. #576

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