Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs @ 154

Last change on this file since 154 was 23, checked in by gkronber, 17 years ago

changed boolean variable BalanceTrees to double BalancedTreesRate (ticket #11)

File size: 17.6 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;
33
34namespace HeuristicLab.StructureIdentification {
35  internal class TreeGardener {
36    private IRandom random;
37    private IOperatorLibrary opLibrary;
38    private List<IOperator> functions;
39    private List<IOperator> terminals;
40
41    internal IList<IOperator> Terminals {
42      get { return terminals.AsReadOnly(); }
43    }
44    private List<IOperator> allOperators;
45
46    internal IList<IOperator> AllOperators {
47      get { return allOperators.AsReadOnly(); }
48    }
49
50    internal TreeGardener(IRandom random, IOperatorLibrary opLibrary) {
51      this.random = random;
52      this.opLibrary = opLibrary;
53
54      this.allOperators = new List<IOperator>();
55      terminals = new List<IOperator>();
56      functions = new List<IOperator>();
57
58      // init functions and terminals based on constraints
59      foreach (IOperator op in opLibrary.Group.Operators) {
60        int maxA, minA;
61        GetMinMaxArity(op, out minA, out maxA);
62        if (maxA == 0) {
63          terminals.Add(op);
64        } else {
65          functions.Add(op);
66        }
67      }
68
69      allOperators.AddRange(functions);
70      allOperators.AddRange(terminals);
71    }
72
73    #region random initialization
74    internal IOperator CreateRandomTree(ICollection<IOperator> allowedOperators, int maxTreeSize, int maxTreeHeight, bool balanceTrees) {
75
76      int minTreeHeight = allowedOperators.Select(op => ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data).Min();
77      if (minTreeHeight > maxTreeHeight)
78        maxTreeHeight = minTreeHeight;
79
80      int minTreeSize = allowedOperators.Select(op => ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data).Min();
81      if (minTreeSize > maxTreeSize)
82        maxTreeSize = minTreeSize;
83
84      int treeHeight = random.Next(minTreeHeight, maxTreeHeight + 1);
85      int treeSize = random.Next(minTreeSize, maxTreeSize + 1);
86
87      IOperator[] possibleOperators = allowedOperators.Where(op => ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data <= treeHeight &&
88        ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data <= treeSize).ToArray();
89      IOperator selectedOperator = (IOperator)possibleOperators[random.Next(possibleOperators.Length)].Clone();
90
91      IOperator rootOperator = CreateRandomTree(selectedOperator, treeSize, treeHeight, balanceTrees);
92
93      return rootOperator;
94    }
95
96    internal IOperator CreateRandomTree(int maxTreeSize, int maxTreeHeight, bool balanceTrees) {
97      if (balanceTrees) {
98        if (maxTreeHeight == 1 || maxTreeSize==1) {
99          IOperator selectedTerminal = (IOperator)terminals[random.Next(terminals.Count())].Clone();
100          return selectedTerminal;
101        } else {
102          IOperator[] possibleFunctions = functions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
103            GetMinimalTreeSize(f) <= maxTreeSize).ToArray();
104          IOperator selectedFunction = (IOperator)possibleFunctions[random.Next(possibleFunctions.Length)].Clone();
105          MakeBalancedTree(selectedFunction, maxTreeSize - 1, maxTreeHeight - 1);
106          return selectedFunction;
107        }
108
109      } else {
110        IOperator[] possibleOperators = allOperators.Where(op => GetMinimalTreeHeight(op) <= maxTreeHeight &&
111          GetMinimalTreeSize(op) <= maxTreeSize).ToArray();
112        IOperator selectedOperator = (IOperator)possibleOperators[random.Next(possibleOperators.Length)].Clone();
113        MakeUnbalancedTree(selectedOperator, maxTreeSize - 1, maxTreeHeight - 1);
114        return selectedOperator;
115      }
116    }
117
118    internal IOperator CreateRandomTree(IOperator root, int maxTreeSize, int maxTreeHeight, bool balanceTrees) {
119      if (balanceTrees) {
120        MakeBalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
121      } else {
122        MakeUnbalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);
123      }
124      if (GetTreeSize(root) > maxTreeSize ||
125         GetTreeHeight(root) > maxTreeHeight) {
126        throw new InvalidProgramException();
127      }
128      return root;
129    }
130
131
132    private void MakeUnbalancedTree(IOperator parent, int maxTreeSize, int maxTreeHeight) {
133      if (maxTreeHeight == 0 || maxTreeSize == 0) return;
134      int minArity;
135      int maxArity;
136      GetMinMaxArity(parent, out minArity, out maxArity);
137      if (maxArity >= maxTreeSize) {
138        maxArity = maxTreeSize;
139      }
140      int actualArity = random.Next(minArity, maxArity + 1);
141      if (actualArity > 0) {
142        int maxSubTreeSize = maxTreeSize / actualArity;
143        for (int i = 0; i < actualArity; i++) {
144          IOperator[] possibleOperators = GetAllowedSubOperators(parent, i).Where(op => GetMinimalTreeHeight(op) <= maxTreeHeight &&
145            GetMinimalTreeSize(op) <= maxSubTreeSize).ToArray();
146          IOperator selectedOperator = (IOperator)possibleOperators[random.Next(possibleOperators.Length)].Clone();
147          parent.AddSubOperator(selectedOperator, i);
148          MakeUnbalancedTree(selectedOperator, maxSubTreeSize - 1, maxTreeHeight - 1);
149        }
150      }
151    }
152
153    // NOTE: this method doesn't build fully balanced trees because we have constraints on the
154    // types of possible suboperators which can indirectly impose a limit for the depth of a given suboperator
155    private void MakeBalancedTree(IOperator parent, int maxTreeSize, int maxTreeHeight) {
156      if (maxTreeHeight == 0 || maxTreeSize == 0) return; // should never happen anyway
157      int minArity;
158      int maxArity;
159      GetMinMaxArity(parent, out minArity, out maxArity);
160      if (maxArity >= maxTreeSize) {
161        maxArity = maxTreeSize;
162      }
163      int actualArity = random.Next(minArity, maxArity + 1);
164      if (actualArity > 0) {
165        int maxSubTreeSize = maxTreeSize / actualArity;
166        for (int i = 0; i < actualArity; i++) {
167          if (maxTreeHeight == 1 || maxSubTreeSize == 1) {
168            IOperator[] possibleTerminals = GetAllowedSubOperators(parent, i).Where(
169              op => GetMinimalTreeHeight(op) <= maxTreeHeight &&
170              GetMinimalTreeSize(op) <= maxSubTreeSize &&
171              IsTerminal(op)).ToArray();
172            IOperator selectedTerminal = (IOperator)possibleTerminals[random.Next(possibleTerminals.Length)].Clone();
173            parent.AddSubOperator(selectedTerminal, i);
174          } else {
175            IOperator[] possibleFunctions = GetAllowedSubOperators(parent, i).Where(
176              op => GetMinimalTreeHeight(op) <= maxTreeHeight &&
177              GetMinimalTreeSize(op) <= maxSubTreeSize &&
178              !IsTerminal(op)).ToArray();
179            IOperator selectedFunction = (IOperator)possibleFunctions[random.Next(possibleFunctions.Length)].Clone();
180            parent.AddSubOperator(selectedFunction, i);
181            MakeBalancedTree(selectedFunction, maxSubTreeSize - 1, maxTreeHeight - 1);
182          }
183        }
184      }
185    }
186
187    internal CompositeOperation CreateInitializationOperation(ICollection<IOperator> operators, IScope scope) {
188      // needed for the parameter shaking operation
189      CompositeOperation initializationOperation = new CompositeOperation();
190      Scope tempScope = new Scope("Temp. initialization scope");
191
192      var parametricOperators = operators.Where(o => o.GetVariable(GPOperatorLibrary.INITIALIZATION) != null);
193
194      foreach (IOperator op in parametricOperators) {
195        // enqueue an initialization operation for each operator with local variables
196        IOperator initialization = (IOperator)op.GetVariable(GPOperatorLibrary.INITIALIZATION).Value;
197        Scope initScope = new Scope();
198
199        // copy the local variables into a temporary scope used for initialization
200        foreach (VariableInfo info in op.VariableInfos) {
201          if (info.Local) {
202            initScope.AddVariable(op.GetVariable(info.FormalName));
203          }
204        }
205
206        tempScope.AddSubScope(initScope);
207        initializationOperation.AddOperation(new AtomicOperation(initialization, initScope));
208      }
209
210      Scope backupScope = new Scope("backup");
211      foreach (Scope subScope in scope.SubScopes) {
212        backupScope.AddSubScope(subScope);
213      }
214
215      scope.AddSubScope(tempScope);
216      scope.AddSubScope(backupScope);
217
218      // add an operation to remove the temporary scopes       
219      initializationOperation.AddOperation(new AtomicOperation(new RightReducer(), scope));
220      return initializationOperation;
221    }
222    #endregion
223
224    #region tree information gathering
225    internal int GetTreeSize(IOperator tree) {
226      return 1 + tree.SubOperators.Sum(f => GetTreeSize(f));
227    }
228
229    internal int GetTreeHeight(IOperator tree) {
230      if (tree.SubOperators.Count == 0) return 1;
231      return 1 + tree.SubOperators.Max(f => GetTreeHeight(f));
232    }
233
234    internal IOperator GetRandomParentNode(IOperator tree) {
235      List<IOperator> parentNodes = new List<IOperator>();
236
237      // add null for the parent of the root node
238      parentNodes.Add(null);
239
240      TreeForEach(tree, delegate(IOperator op) {
241        if (op.SubOperators.Count > 0) {
242          parentNodes.Add(op);
243        }
244      });
245
246      return parentNodes[random.Next(parentNodes.Count)];
247    }
248
249    internal IList<IOperator> GetAllowedSubOperators(IOperator op, int index) {
250      if (op == null) {
251        return allOperators;
252      } else {
253
254        SubOperatorsConstraintAnalyser analyser = new SubOperatorsConstraintAnalyser();
255        analyser.AllPossibleOperators = allOperators;
256
257        return analyser.GetAllowedOperators(op, index);
258      }
259    }
260    internal void GetMinMaxArity(IOperator root, out int minArity, out int maxArity) {
261      foreach (IConstraint constraint in root.Constraints) {
262        NumberOfSubOperatorsConstraint theConstraint = constraint as NumberOfSubOperatorsConstraint;
263        if (theConstraint != null) {
264          minArity = theConstraint.MinOperators.Data;
265          maxArity = theConstraint.MaxOperators.Data;
266          return;
267        }
268      }
269      // the default arity is 2
270      minArity = 2;
271      maxArity = 2;
272    }
273    internal bool IsTerminal(IOperator f) {
274      int minArity;
275      int maxArity;
276      GetMinMaxArity(f, out minArity, out maxArity);
277      return minArity == 0 && maxArity == 0;
278    }
279
280    internal IList<IOperator> GetAllowedParents(IOperator child, int childIndex) {
281      List<IOperator> parents = new List<IOperator>();
282      foreach (IOperator function in functions) {
283        IList<IOperator> allowedSubOperators = GetAllowedSubOperators(function, childIndex);
284        if (allowedSubOperators.Contains(child, new OperatorEqualityComparer())) {
285          parents.Add(function);
286        }
287      }
288      return parents;
289    }
290
291    internal ICollection<IOperator> GetAllOperators(IOperator root) {
292      List<IOperator> allOps = new List<IOperator>();
293      TreeForEach(root, t => { allOps.Add(t); });
294      return allOps;
295    }
296
297    /// <summary>
298    /// returns the height level of op in the tree
299    /// if the op == tree => 1
300    /// if op is in the suboperators of tree => 2
301    /// ...
302    /// if op is not found => -1
303    /// </summary>
304    /// <param name="tree">operator tree to process</param>
305    /// <param name="op">operater that is searched in the tree</param>
306    /// <returns></returns>
307    internal int GetNodeLevel(IOperator tree, IOperator op) {
308      return GetNodeLevelHelper(tree, op, 1);
309    }
310
311    private int GetNodeLevelHelper(IOperator tree, IOperator op, int level) {
312      if (op == tree) return level;
313
314      foreach (IOperator subTree in tree.SubOperators) {
315        int result = GetNodeLevelHelper(subTree, op, level + 1);
316        if (result != -1) return result;
317      }
318
319      return -1;
320    }
321
322    internal bool IsValidTree(IOperator tree) {
323      if (!tree.IsValid())
324        return false;
325      foreach (IOperator subTree in tree.SubOperators) {
326        if (!subTree.IsValid())
327          return false;
328      }
329
330      return true;
331    }
332
333    // returns a random node from the specified level in the tree
334    internal IOperator GetRandomNode(IOperator tree, int level) {
335      if (level == 0) return tree;
336      List<IOperator> nodes = GetOperatorsAtLevel(tree, level);
337      return nodes[random.Next(nodes.Count)];
338    }
339    #endregion
340
341    #region private utility methods
342
343    private int GetMinimalTreeHeight(IOperator op) {
344      return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data;
345    }
346
347    private int GetMinimalTreeSize(IOperator op) {
348      return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data;
349    }
350
351    private void TreeForEach(IOperator tree, Action<IOperator> action) {
352      action(tree);
353      foreach (IOperator child in tree.SubOperators) {
354        TreeForEach(child, action);
355      }
356    }
357
358    private List<IOperator> GetOperatorsAtLevel(IOperator tree, int level) {
359      if (level == 1) return new List<IOperator>(tree.SubOperators);
360
361      List<IOperator> result = new List<IOperator>();
362      foreach (IOperator subOperator in tree.SubOperators) {
363        result.AddRange(GetOperatorsAtLevel(subOperator, level - 1));
364      }
365      return result;
366    }
367
368
369    #endregion
370
371    internal class OperatorEqualityComparer : IEqualityComparer<IOperator> {
372      #region IEqualityComparer<IOperator> Members
373
374      public bool Equals(IOperator x, IOperator y) {
375        return ((StringData)x.GetVariable(GPOperatorLibrary.TYPE_ID).Value).Data ==
376          ((StringData)y.GetVariable(GPOperatorLibrary.TYPE_ID).Value).Data;
377      }
378
379      public int GetHashCode(IOperator obj) {
380        return ((StringData)obj.GetVariable(GPOperatorLibrary.TYPE_ID).Value).Data.GetHashCode();
381      }
382
383      #endregion
384    }
385
386    internal ICollection<IOperator> GetPossibleParents(List<IOperator> list) {
387      List<IOperator> result = new List<IOperator>();
388      foreach (IOperator op in functions) {
389        if (IsPossibleParent(op, list)) {
390          result.Add(op);
391        }
392      }
393      return result;
394    }
395
396    private bool IsPossibleParent(IOperator op, List<IOperator> children) {
397      int minArity;
398      int maxArity;
399      GetMinMaxArity(op, out minArity, out maxArity);
400
401      // note: we can't assume that the operators in the children list have different types!
402
403      // when the maxArity of this function is smaller than the list of operators that
404      // should be included as sub-operators then it can't be a parent
405      if (maxArity < children.Count()) {
406        return false;
407      }
408      int nSlots = Math.Max(minArity, children.Count);
409
410      SubOperatorsConstraintAnalyser analyzer = new SubOperatorsConstraintAnalyser();
411      analyzer.AllPossibleOperators = children;
412
413      List<HashSet<IOperator>> slotSets = new List<HashSet<IOperator>>();
414
415      // we iterate through all slots for sub-operators and calculate the set of
416      // allowed sub-operators for this slot.
417      // we only count those slots that can hold at least one of the children that we should combine
418      for (int slot = 0; slot < nSlots; slot++) {
419        HashSet<IOperator> operatorSet = new HashSet<IOperator>(analyzer.GetAllowedOperators(op, slot));
420        if (operatorSet.Count() > 0) {
421          slotSets.Add(operatorSet);
422        }
423      }
424
425      // ok at the end of this operation we know how many slots of the parent can actually
426      // hold one of our children.
427      // if the number of slots is smaller than the number of children we can be sure that
428      // we can never combine all children as sub-operators of the operator and thus the operator
429      // can't be a parent.
430      if (slotSets.Count() < children.Count()) {
431        return false;
432      }
433
434      // finally we sort the sets by size and beginning from the first set select one
435      // operator for the slot and thus remove it as possible sub-operator from the remaining sets.
436      // when we can successfully assign all available children to a slot the operator is a valid parent
437      // when only a subset of all children can be assigned to slots the operator is no valid parent
438      slotSets.Sort((p, q) => p.Count() - q.Count());
439
440      int assignments = 0;
441      for (int i = 0; i < slotSets.Count() - 1; i++) {
442        if (slotSets[i].Count > 0) {
443          IOperator selected = slotSets[i].ElementAt(0);
444          assignments++;
445          for (int j = i + 1; j < slotSets.Count(); j++) {
446            slotSets[j].Remove(selected);
447          }
448        }
449      }
450
451      // sanity check
452      if (assignments > children.Count) throw new InvalidProgramException();
453      return assignments == children.Count - 1;
454    }
455  }
456}
Note: See TracBrowser for help on using the repository browser.