Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.GP/3.3/Manipulation/CutOutNodeManipulation.cs @ 1814

Last change on this file since 1814 was 656, checked in by gkronber, 16 years ago

merged changesets r644:647 and r651:655 from the GpPluginsRefactoringBranch back into the trunk (#177)

File size: 7.0 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.Collections.Generic;
23using System.Linq;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Operators;
27using HeuristicLab.Random;
28using System;
29using System.Diagnostics;
30
31namespace HeuristicLab.GP {
32  public class CutOutNodeManipulation : OperatorBase {
33    public override string Description {
34      get {
35        return @"Takes a tree, selects a random node of the tree and then tries to replace a random sub-tree
36of that node with one of the childs of the selected child.
37
38               O                             O
39              / \                           / \
40             O   X                         O   2
41                / \    2 is selected =>       / \
42               1   2                         4   5
43              /   / \
44             3   4   5
45";
46      }
47    }
48
49    public CutOutNodeManipulation()
50      : base() {
51      AddVariableInfo(new VariableInfo("Random", "Uniform random number generator", typeof(MersenneTwister), VariableKind.In));
52      AddVariableInfo(new VariableInfo("OperatorLibrary", "The operator library containing all available operators", typeof(GPOperatorLibrary), VariableKind.In));
53      AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
54      AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
55      AddVariableInfo(new VariableInfo("FunctionTree", "The tree to mutate", typeof(IFunctionTree), VariableKind.In | VariableKind.Out));
56      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
57      AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
58    }
59
60
61    public override IOperation Apply(IScope scope) {
62      IFunctionTree root = GetVariableValue<IFunctionTree>("FunctionTree", scope, true);
63      MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);
64      GPOperatorLibrary library = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
65      int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;
66      int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;
67      TreeGardener gardener = new TreeGardener(random, library);
68      IFunctionTree parent = gardener.GetRandomParentNode(root);
69      // parent == null means we should cut out the root node
70      // => return a random sub-tree of the root
71      if (parent == null) {
72        // when there are sub-trees then replace the old tree with a random sub-tree
73        if (root.SubTrees.Count > 0) {
74          root = root.SubTrees[random.Next(root.SubTrees.Count)];
75          GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
76          GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
77          // update the variable
78          scope.GetVariable(scope.TranslateName("FunctionTree")).Value = root;
79          Debug.Assert(gardener.IsValidTree(root));
80          // we reused a sub-tree so we don't have to schedule initialization operations
81          return null;
82        } else {
83          // we want to cut the root node and there are no sub-trees => create a new random terminal
84          IFunctionTree newTree;
85          newTree = gardener.CreateRandomTree(gardener.Terminals, 1, 1);
86          GetVariableValue<IntData>("TreeSize", scope, true).Data = newTree.Size;
87          GetVariableValue<IntData>("TreeHeight", scope, true).Data = newTree.Height;
88          // update the variable
89          scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newTree;
90          Debug.Assert(gardener.IsValidTree(newTree));
91          // schedule an operation to initialize the whole tree
92          return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newTree), scope);
93        }
94      }
95      // select a child to cut away
96      int childIndex = random.Next(parent.SubTrees.Count);
97      IFunctionTree child = parent.SubTrees[childIndex];
98      // match the sub-trees of the child with the allowed sub-trees of the parent
99      ICollection<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
100      IFunctionTree[] possibleChilds = child.SubTrees.Where(t => allowedFunctions.Contains(t.Function)).ToArray();
101      if (possibleChilds.Length > 0) {
102        // replace child with a random child of that child
103        IFunctionTree selectedChild = possibleChilds[random.Next(possibleChilds.Length)];       
104        parent.RemoveSubTree(childIndex);
105        parent.InsertSubTree(childIndex, selectedChild);
106        Debug.Assert(gardener.IsValidTree(root));
107        // update the size and height of our tree
108        GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
109        GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
110        // don't need to schedule initialization operations
111        return null;
112      } else {
113        // can't reuse an existing branch => create a new tree
114        // determine the level of the parent
115        int parentLevel = gardener.GetBranchLevel(root, parent);
116        // first remove the old child (first step essential!)
117        parent.RemoveSubTree(childIndex);
118        // then determine the number of nodes left over after the child has been removed!
119        int remainingNodes = root.Size;
120        allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
121        IFunctionTree newFunctionTree = gardener.CreateRandomTree(allowedFunctions, maxTreeSize - remainingNodes, maxTreeHeight - parentLevel);
122        parent.InsertSubTree(childIndex, newFunctionTree);
123        GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
124        GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
125        Debug.Assert(gardener.IsValidTree(root));
126        // schedule an initialization operation for the new function-tree
127        return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newFunctionTree), scope);
128      }
129    }
130  }
131}
Note: See TracBrowser for help on using the repository browser.