Free cookie consent management tool by TermsFeed Policy Generator

source: branches/FunctionsAndStructIdRefactoring/HeuristicLab.StructureIdentification/Manipulation/DeleteSubTreeManipulation.cs @ 148

Last change on this file since 148 was 143, checked in by gkronber, 17 years ago

worked on #112 in the refactoring branch

File size: 5.8 KB
RevLine 
[2]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 HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Operators;
27using HeuristicLab.Random;
[143]28using HeuristicLab.Functions;
[2]29
30namespace HeuristicLab.StructureIdentification {
31  public class DeleteSubTreeManipulation : OperatorBase {
32    public override string Description {
33      get {
34        return @"Deletes a random sub-tree of the input tree. If the remaining tree is not valid
35the operator tries to fix the tree by generating random subtrees where necessary.";
36      }
37    }
38
39    public DeleteSubTreeManipulation()
40      : base() {
41      AddVariableInfo(new VariableInfo("Random", "Uniform random number generator", typeof(MersenneTwister), VariableKind.In));
42      AddVariableInfo(new VariableInfo("OperatorLibrary", "The operator library containing all available operators", typeof(GPOperatorLibrary), VariableKind.In));
43      AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
44      AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
[143]45      AddVariableInfo(new VariableInfo("FunctionTree", "The tree to mutate", typeof(IFunctionTree), VariableKind.In | VariableKind.Out));
[2]46      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
47      AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.In | VariableKind.Out));
48    }
49
50
51    public override IOperation Apply(IScope scope) {
[143]52      IFunctionTree root = GetVariableValue<IFunctionTree>("FunctionTree", scope, true);
[2]53      MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);
54      GPOperatorLibrary library = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
55      TreeGardener gardener = new TreeGardener(random, library);
[143]56      IFunctionTree parent = gardener.GetRandomParentNode(root);
[2]57
58      // parent==null means the whole tree should be deleted.
59      // => return a new minimal random tree
60      if(parent == null) {
[143]61        IFunctionTree newTree = gardener.CreateRandomTree(1, 1, true);
[2]62
63        // check if the tree is ok
64        if(!gardener.IsValidTree(newTree)) {
65          throw new InvalidOperationException();
66        }
67
68        // update sizes to match the new tree
69        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(newTree);
70        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(newTree);
[143]71        scope.GetVariable(scope.TranslateName("FunctionTree")).Value = newTree;
[2]72
73        // schedule an operation to initialize the newly created operator
[143]74        return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newTree), scope);
[2]75      }
76
[143]77      int childIndex = random.Next(parent.SubTrees.Count);
[2]78
79      int min;
80      int max;
[143]81      gardener.GetMinMaxArity(parent.Function, out min, out max);
82      if(parent.SubTrees.Count > min) {
83        parent.RemoveSubTree(childIndex);
84        // actually since the next sub-trees are shifted in the place of the removed branch
85        // it might be possible that these sub-trees are not allowed in the place of the old branch
[2]86        // we ignore this problem for now.
[143]87        // when this starts to become a problem a possible solution is to go through the shifted branches from the place of the shifted
[2]88        // and find the first one that doesn't fit. At this position we insert a new randomly initialized subtree of matching type (gkronber 25.12.07)
89
[143]90        if(!gardener.IsValidTree(root)) {
[2]91          throw new InvalidOperationException();
92        }
93
[143]94        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
95        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
96        // root hasn't changed so don't need to update 'FunctionTree' variable
[2]97        return null;
98      } else {
99        // replace with a minimal random seedling
[143]100        parent.RemoveSubTree(childIndex);
[2]101
[143]102        IList<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
103        IFunctionTree newFunctionTree = gardener.CreateRandomTree(allowedFunctions, 1, 1, true);
[2]104
[143]105        parent.InsertSubTree(childIndex, newFunctionTree);
[2]106
[143]107        if(!gardener.IsValidTree(root)) {
[2]108          throw new InvalidProgramException();
109        }
110
[143]111        GetVariableValue<IntData>("TreeSize", scope, true).Data = gardener.GetTreeSize(root);
112        GetVariableValue<IntData>("TreeHeight", scope, true).Data = gardener.GetTreeHeight(root);
113        // again the root hasn't changed so we don't need to update the 'FunctionTree' variable
114        return gardener.CreateInitializationOperation(gardener.GetAllSubTrees(newFunctionTree), scope);
[2]115      }
116    }
117  }
118}
Note: See TracBrowser for help on using the repository browser.