Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 2482 was 2222, checked in by gkronber, 15 years ago

Merged changes from GP-refactoring branch back into the trunk #713.

File size: 5.3 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.Random;
26using System.Diagnostics;
27using HeuristicLab.GP.Interfaces;
28
29namespace HeuristicLab.GP.Operators {
30  public class CutOutNodeManipulation : GPManipulatorBase {
31    public override string Description {
32      get {
33        return @"Takes a tree, selects a random node of the tree and then tries to replace a random sub-tree
34of that node with one of the childs of the selected child.
35
36               O                             O
37              / \                           / \
38             O   X                         O   2
39                / \    2 is selected =>       / \
40               1   2                         4   5
41              /   / \
42             3   4   5
43";
44      }
45    }
46
47    public CutOutNodeManipulation()
48      : base() {
49    }
50
51
52    internal override IOperation Manipulate(MersenneTwister random, IGeneticProgrammingModel gpModel, FunctionLibrary library, int maxTreeSize, int maxTreeHeight, IScope scope) {
53      TreeGardener gardener = new TreeGardener(random, library);
54      IFunctionTree parent = gardener.GetRandomParentNode(gpModel.FunctionTree);
55      // parent == null means we should cut out the root node
56      // => return a random sub-tree of the root
57      if (parent == null) {
58        // when there are sub-trees then replace the old tree with a random sub-tree
59        if (gpModel.FunctionTree.SubTrees.Count > 0) {
60          gpModel.FunctionTree = gpModel.FunctionTree.SubTrees[random.Next(gpModel.FunctionTree.SubTrees.Count)];
61          Debug.Assert(gardener.IsValidTree(gpModel.FunctionTree));
62          // we reused a sub-tree so we don't have to schedule initialization operations
63          return null;
64        } else {
65          // we want to cut the root node and there are no sub-trees => create a new random terminal
66          gpModel.FunctionTree = gardener.CreateRandomTree(gardener.Terminals, 1, 1);
67          Debug.Assert(gardener.IsValidTree(gpModel.FunctionTree));
68
69          // schedule an operation to initialize the whole tree
70          return Util.CreateInitializationOperation(TreeGardener.GetAllSubTrees(gpModel.FunctionTree), scope);
71        }
72      }
73
74      // select a child to cut away
75      int childIndex = random.Next(parent.SubTrees.Count);
76      IFunctionTree child = parent.SubTrees[childIndex];
77      // match the sub-trees of the child with the allowed sub-trees of the parent
78      ICollection<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
79      IFunctionTree[] possibleChilds = child.SubTrees.Where(t => allowedFunctions.Contains(t.Function)).ToArray();
80      if (possibleChilds.Length > 0) {
81        // replace child with a random child of that child
82        IFunctionTree selectedChild = possibleChilds[random.Next(possibleChilds.Length)];
83        parent.RemoveSubTree(childIndex);
84        parent.InsertSubTree(childIndex, selectedChild);
85        Debug.Assert(gardener.IsValidTree(gpModel.FunctionTree));
86        // recalculate the size and height of our tree
87        gpModel.Size = gpModel.FunctionTree.GetSize();
88        gpModel.Height = gpModel.FunctionTree.GetHeight();
89        // don't need to schedule initialization operations
90        return null;
91      } else {
92        // can't reuse an existing branch => create a new tree
93        // determine the level of the parent
94        int parentLevel = gardener.GetBranchLevel(gpModel.FunctionTree, parent);
95        // first remove the old child (first step essential!)
96        parent.RemoveSubTree(childIndex);
97        // then determine the number of nodes left over after the child has been removed!
98        int remainingNodes = gpModel.FunctionTree.GetSize();
99        allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
100        IFunctionTree newFunctionTree = gardener.CreateRandomTree(allowedFunctions, maxTreeSize - remainingNodes, maxTreeHeight - parentLevel);
101        parent.InsertSubTree(childIndex, newFunctionTree);
102        Debug.Assert(gardener.IsValidTree(gpModel.FunctionTree));
103        // recalculate size and height
104        gpModel.Size = gpModel.FunctionTree.GetSize();
105        gpModel.Height = gpModel.FunctionTree.GetHeight();
106        // schedule an initialization operation for the new function-tree
107        return Util.CreateInitializationOperation(TreeGardener.GetAllSubTrees(newFunctionTree), scope);
108      }
109    }
110  }
111}
Note: See TracBrowser for help on using the repository browser.