Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.GP/3.3/Manipulation/SubstituteSubTreeManipulation.cs @ 1711

Last change on this file since 1711 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: 5.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 System.Linq;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Operators;
28using HeuristicLab.Random;
29using System.Diagnostics;
30
31namespace HeuristicLab.GP {
32  public class SubstituteSubTreeManipulation : OperatorBase {
33
34    public override string Description {
35      get { return "Selects a random node of the tree and replaces it with randomly initialized subtree."; }
36    }
37
38    public SubstituteSubTreeManipulation()
39      : base() {
40      AddVariableInfo(new VariableInfo("Random", "Uniform random number generator", typeof(MersenneTwister), VariableKind.In));
41      AddVariableInfo(new VariableInfo("OperatorLibrary", "The operator library containing all available operators", typeof(GPOperatorLibrary), VariableKind.In));
42      AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
43      AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
44      AddVariableInfo(new VariableInfo("FunctionTree", "The tree to manipulate", typeof(IFunctionTree), VariableKind.In | VariableKind.Out));
45      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
46      AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
47    }
48
49    public override IOperation Apply(IScope scope) {
50      IFunctionTree root = GetVariableValue<IFunctionTree>("FunctionTree", scope, true);
51      MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);
52      GPOperatorLibrary library = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
53      int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;
54      int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;
55      int treeSize = GetVariableValue<IntData>("TreeSize", scope, true).Data;
56      int treeHeight = GetVariableValue<IntData>("TreeHeight", scope, true).Data;
57      TreeGardener gardener = new TreeGardener(random, library);
58      IFunctionTree parent = gardener.GetRandomParentNode(root);
59      if(parent == null) {
60        // parent == null means we should subsitute the whole tree
61        // => create a new random tree
62        IFunctionTree newTree = gardener.CreateRandomTree(gardener.AllFunctions, maxTreeSize, maxTreeHeight);
63        Debug.Assert(gardener.IsValidTree(newTree));
64
65        // update the variables in the scope with the new values
66        GetVariableValue<IntData>("TreeSize", scope, true).Data = newTree.Size;
67        GetVariableValue<IntData>("TreeHeight", scope, true).Data = newTree.Height;
68        scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newTree;
69       
70        // return a CompositeOperation that randomly initializes the new tree
71        return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newTree), scope);
72      } else {
73        // determine a random child of the parent to be replaced
74        int childIndex = random.Next(parent.SubTrees.Count);
75        // get the list of allowed functions for the new sub-tree
76        ICollection<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
77        if(allowedFunctions.Count == 0) {
78          // don't change anything
79          // this shouldn't happen
80          throw new InvalidProgramException();
81        }
82
83        // calculate the maximum size and height of the new sub-tree based on the location where
84        // it will be inserted
85        int parentLevel = gardener.GetBranchLevel(root, parent);
86        int maxSubTreeHeight = maxTreeHeight - parentLevel;
87        int maxSubTreeSize = maxTreeSize - (treeSize - parent.SubTrees[childIndex].Size);
88
89        // create a random function tree
90        IFunctionTree newTree = gardener.CreateRandomTree(allowedFunctions, maxSubTreeSize, maxSubTreeHeight);
91        parent.RemoveSubTree(childIndex);
92        parent.InsertSubTree(childIndex, newTree);
93
94        Debug.Assert(gardener.IsValidTree(root));
95        // update the values of treeSize and treeHeight
96        GetVariableValue<IntData>("TreeSize", scope, true).Data = root.Size;
97        GetVariableValue<IntData>("TreeHeight", scope, true).Data = root.Height;
98        // the root hasn't changed so we don't need to update
99        // return a CompositeOperation that randomly initializes all nodes of the new subtree
100        return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newTree), scope);
101      }
102    }
103  }
104}
Note: See TracBrowser for help on using the repository browser.