Free cookie consent management tool by TermsFeed Policy Generator

source: branches/3.1/sources/HeuristicLab.StructureIdentification/TreeGardener.cs @ 11082

Last change on this file since 11082 was 527, checked in by gkronber, 16 years ago

small improvement for crossover

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