Changeset 3512
- Timestamp:
- 04/23/10 14:27:06 (15 years ago)
- Location:
- trunk/sources
- Files:
-
- 8 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.3.csproj
r3462 r3512 98 98 <Compile Include="Creators\SymbolicExpressionTreeCreator.cs" /> 99 99 <Compile Include="Crossovers\SymbolicExpressionTreeCrossover.cs" /> 100 <Compile Include="Manipulators\ChangeNodeTypeManipulation.cs" /> 101 <Compile Include="Manipulators\FullTreeShaker.cs" /> 102 <Compile Include="Manipulators\OnePointShaker.cs" /> 100 103 <Compile Include="Manipulators\SymbolicExpressionTreeManipulator.cs" /> 101 104 <Compile Include="SymbolicExpressionTreeTopLevelNode.cs" /> -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Manipulators/ChangeNodeTypeManipulation.cs
r3219 r3512 1 1 #region License Information 2 2 /* HeuristicLab 3 * Copyright (C) 2002-20 08Heuristic and Evolutionary Algorithms Laboratory (HEAL)3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL) 4 4 * 5 5 * This file is part of HeuristicLab. … … 20 20 #endregion 21 21 22 using System.Collections.Generic;23 22 using System.Linq; 24 23 using HeuristicLab.Core; 24 using HeuristicLab.Operators; 25 25 using HeuristicLab.Random; 26 using System.Diagnostics;27 using HeuristicLab. GP.Interfaces;26 using HeuristicLab.Data; 27 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 28 28 29 namespace HeuristicLab.Encodings.SymbolicExpressionTree { 30 public class ChangeNodeTypeManipulation : GPManipulatorBase { 31 32 public override string Description { 33 get { 34 return @"This manipulation operator selects a random tree-node and changes the function type. 35 If this leads to a constraint-violation (wrong number or type of sub-trees) the sub-trees are repaired 36 resulting in a valid tree again."; 37 } 38 } 29 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Manipulators { 30 [StorableClass] 31 [Item("ChangeNodeTypeManipulation", "Selects a random tree node and changes the symbol size.")] 32 public class ChangeNodeTypeManipulation : SymbolicExpressionTreeManipulator { 39 33 40 34 public ChangeNodeTypeManipulation() … … 42 36 } 43 37 44 internal override IOperation Manipulate(MersenneTwister random, IGeneticProgrammingModel gpModel, FunctionLibrary library, int maxTreeSize, int maxTreeHeight, IScope scope) { 45 TreeGardener gardener = new TreeGardener(random, library); 46 IFunctionTree parent = gardener.GetRandomParentNode(gpModel.FunctionTree); 47 IFunctionTree selectedChild; 48 int selectedChildIndex; 49 if (parent == null) { 50 selectedChildIndex = 0; 51 selectedChild = gpModel.FunctionTree; 52 } else { 53 selectedChildIndex = random.Next(parent.SubTrees.Count); 54 selectedChild = parent.SubTrees[selectedChildIndex]; 38 protected override void Manipulate(IRandom random, SymbolicExpressionTree symbolicExpressionTree, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight, out bool success) { 39 40 // select any node except the with a parent where the parent is not the root node) 41 var manipulationPoint = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1) 42 from subtree in parent.SubTrees 43 select new { Parent = parent, Node = subtree, Index = parent.SubTrees.IndexOf(subtree) }).SelectRandom(random); 44 // find possible symbols for the node (also considering the existing branches below it) 45 var allowedSymbols = from symbol in manipulationPoint.Parent.GetAllowedSymbols(manipulationPoint.Index) 46 where manipulationPoint.Node.SubTrees.Count <= manipulationPoint.Node.Grammar.GetMaxSubtreeCount(symbol) 47 where manipulationPoint.Node.SubTrees.Count >= manipulationPoint.Node.Grammar.GetMinSubtreeCount(symbol) 48 select symbol; 49 50 if (allowedSymbols.Count() <= 1) { 51 success = false; 52 return; 55 53 } 54 var node = manipulationPoint.Node; 55 // keep only symbols that are still possible considering the existing sub-trees 56 var constrainedSymbols = from symbol in allowedSymbols 57 let disallowedSubtrees = 58 from subtree in node.SubTrees 59 where !node.Grammar.IsAllowedChild(symbol, subtree.Symbol, node.SubTrees.IndexOf(subtree)) 60 select subtree 61 where disallowedSubtrees.Count() == 0 62 select symbol; 63 if (constrainedSymbols.Count() <= 1) { 64 success = false; 65 return; 66 } 67 var newSymbol = constrainedSymbols.SelectRandom(random); 56 68 57 if (selectedChild.SubTrees.Count == 0) { 58 IFunctionTree newTerminal = ChangeTerminalType(parent, selectedChild, selectedChildIndex, gardener, random); 59 if (parent == null) { 60 // no parent means the new child is the initial operator 61 gpModel.FunctionTree = newTerminal; 62 } else { 63 parent.RemoveSubTree(selectedChildIndex); 64 parent.InsertSubTree(selectedChildIndex, newTerminal); 65 // updating the variable is not necessary because it stays the same 66 } 67 Debug.Assert(gardener.IsValidTree(gpModel.FunctionTree)); 68 // size and height stays the same when changing a terminal so no need to update the variables 69 // schedule an operation to initialize the new terminal 70 return Util.CreateInitializationOperation(TreeGardener.GetAllSubTrees(newTerminal), scope); 71 } else { 72 List<IFunctionTree> uninitializedBranches; 73 IFunctionTree newFunctionTree = ChangeFunctionType(parent, selectedChild, selectedChildIndex, gardener, random, out uninitializedBranches); 74 // in rare cases the function creates a tree that breaks the size limits 75 // calculate the height and size difference and 76 // check if the size of the new tree is still in the allowed bounds 77 int oldChildSize = selectedChild.GetSize(); 78 int oldChildHeight = selectedChild.GetHeight(); 79 int newChildSize = newFunctionTree.GetSize(); 80 int newChildHeight = newFunctionTree.GetHeight(); 81 if ((gpModel.Height - oldChildHeight) + newChildHeight > maxTreeHeight || 82 (gpModel.Size - oldChildSize) + newChildSize > maxTreeSize) { 83 // if size-constraints are violated don't change anything 84 return null; 85 } 86 if (parent == null) { 87 // no parent means the new function is the initial operator 88 gpModel.FunctionTree = newFunctionTree; 89 } else { 90 // remove the old child 91 parent.RemoveSubTree(selectedChildIndex); 92 // add the new child as sub-tree of parent 93 parent.InsertSubTree(selectedChildIndex, newFunctionTree); 94 } 95 // update size and height 96 gpModel.Size = gpModel.Size - oldChildSize + newChildSize; 97 gpModel.Height = gpModel.FunctionTree.GetHeight(); // must recalculate height because we can't know wether the manipulated branch was the deepest branch 98 // check if whole tree is ok 99 Debug.Assert(gardener.IsValidTree(gpModel.FunctionTree)); 100 // return a composite operation that initializes all created sub-trees 101 return Util.CreateInitializationOperation(uninitializedBranches, scope); 102 } 103 } 104 105 private IFunctionTree ChangeTerminalType(IFunctionTree parent, IFunctionTree child, int childIndex, TreeGardener gardener, MersenneTwister random) { 106 IList<IFunction> allowedTerminals; 107 if (parent == null) { 108 allowedTerminals = gardener.Terminals; 109 } else { 110 allowedTerminals = new List<IFunction>(); 111 var allAllowedChildren = gardener.GetAllowedSubFunctions(parent.Function, childIndex); 112 foreach (IFunction c in allAllowedChildren) { 113 if (TreeGardener.IsTerminal(c)) allowedTerminals.Add(c); 114 } 115 } 116 // selecting from the terminals should always work since the current child was also a terminal 117 // so in the worst case we will just create a new terminal of the same type again. 118 return gardener.CreateRandomTree(allowedTerminals, 1, 1); 119 } 120 121 private IFunctionTree ChangeFunctionType(IFunctionTree parent, IFunctionTree child, int childIndex, TreeGardener gardener, MersenneTwister random, 122 out List<IFunctionTree> uninitializedBranches) { 123 // since there are subtrees, we have to check which 124 // and how many of the existing subtrees we can reuse. 125 // first let's choose the function we want to use instead of the old child. For this we have to determine the 126 // pool of allowed functions based on constraints of the parent if there is one. 127 List<IFunction> allowedFunctions = new List<IFunction>(gardener.GetAllowedSubFunctions(parent != null ? parent.Function : null, childIndex)); 128 // try to make a tree with the same arity as the old child. 129 int actualArity = child.SubTrees.Count; 130 // create a new tree-node for a randomly selected function 131 IFunction selectedFunction = allowedFunctions[random.Next(allowedFunctions.Count)]; 132 // arity of the selected operator 133 int minArity = selectedFunction.MinSubTrees; 134 int maxArity = selectedFunction.MaxSubTrees; 135 // if the old child had too many sub-trees then the new child should keep as many sub-trees as possible 136 if (actualArity > maxArity) 137 actualArity = maxArity; 138 if (actualArity < minArity) 139 actualArity = minArity; 140 // create a list that holds old sub-trees that we can reuse in the new tree 141 List<IFunctionTree> availableSubTrees = new List<IFunctionTree>(child.SubTrees); 142 List<IFunctionTree> freshSubTrees = new List<IFunctionTree>(); 143 IFunctionTree newTree = selectedFunction.GetTreeNode(); 144 // randomly select the sub-trees that we keep 145 for (int i = 0; i < actualArity; i++) { 146 // fill all sub-tree slots of the new tree 147 // if for a given slot i there are multiple existing sub-trees that can be used in that slot 148 // then use a random existing sub-tree. When there are no existing sub-trees 149 // that fit in the given slot then create a new random tree and use it for the slot 150 ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(selectedFunction, i); 151 var matchingSubTrees = availableSubTrees.Where(subTree => allowedSubFunctions.Contains(subTree.Function)); 152 if (matchingSubTrees.Count() > 0) { 153 IFunctionTree selectedSubTree = matchingSubTrees.ElementAt(random.Next(matchingSubTrees.Count())); 154 // we can just add it as subtree 155 newTree.InsertSubTree(i, selectedSubTree); 156 availableSubTrees.Remove(selectedSubTree); // the branch shouldn't be available for the following slots 157 } else { 158 // no existing matching tree found => create a new tree of minimal size 159 IFunctionTree freshTree = gardener.CreateRandomTree(allowedSubFunctions, 1, 1); 160 freshSubTrees.AddRange(TreeGardener.GetAllSubTrees(freshTree)); 161 newTree.InsertSubTree(i, freshTree); 162 } 163 } 164 freshSubTrees.Add(newTree); 165 uninitializedBranches = freshSubTrees; 166 return newTree; 69 // replace the old node with the new node 70 var newNode = newSymbol.CreateTreeNode(); 71 if (newNode.HasLocalParameters) 72 newNode.ResetLocalParameters(random); 73 foreach (var subtree in node.SubTrees) 74 newNode.AddSubTree(subtree); 75 manipulationPoint.Parent.RemoveSubTree(manipulationPoint.Index); 76 manipulationPoint.Parent.InsertSubTree(manipulationPoint.Index, newNode); 77 success = true; 167 78 } 168 79 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Manipulators/FullTreeShaker.cs
r3219 r3512 1 1 #region License Information 2 2 /* HeuristicLab 3 * Copyright (C) 2002-20 08Heuristic and Evolutionary Algorithms Laboratory (HEAL)3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL) 4 4 * 5 5 * This file is part of HeuristicLab. … … 25 25 using HeuristicLab.Random; 26 26 using HeuristicLab.Data; 27 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 27 28 28 namespace HeuristicLab.Encodings.SymbolicExpressionTree { 29 public class FullTreeShaker : DelegatingOperator { 30 public override string Description { 31 get { return "Manipulates all tree nodes for which a manipulator is defined."; } 32 } 29 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Manipulators { 30 [StorableClass] 31 [Item("FullTreeShaker", "Manipulates all nodes that have local parameters.")] 32 public class FullTreeShaker : SymbolicExpressionTreeManipulator { 33 33 34 34 public FullTreeShaker() 35 35 : base() { 36 AddVariableInfo(new VariableInfo("Random", "A random generator (uniform)", typeof(MersenneTwister), VariableKind.In));37 AddVariableInfo(new VariableInfo("FunctionLibrary", "Function library that defines function mutations", typeof(FunctionLibrary), VariableKind.In));38 AddVariableInfo(new VariableInfo("ShakingFactor", "Variable that determines the force of the shaking operation", typeof(DoubleData), VariableKind.In));39 AddVariableInfo(new VariableInfo("FunctionTree", "The function tree that should be mutated", typeof(IGeneticProgrammingModel), VariableKind.In | VariableKind.Out));40 36 } 41 37 42 public override IOperation Apply(IScope scope) { 43 FunctionLibrary library = GetVariableValue<FunctionLibrary>("FunctionLibrary", scope, true); 44 IGeneticProgrammingModel gpModel = GetVariableValue<IGeneticProgrammingModel>("FunctionTree", scope, false); 45 MersenneTwister mt = GetVariableValue<MersenneTwister>("Random", scope, true); 46 47 // save all existing sub-scopes in a backup scope 48 Scope backupScope = new Scope("backup"); 49 foreach (Scope subScope in scope.SubScopes) { 50 backupScope.AddSubScope(subScope); 38 protected override void Manipulate(IRandom random, SymbolicExpressionTree symbolicExpressionTree, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight, out bool success) { 39 foreach (var node in symbolicExpressionTree.IterateNodesPrefix()) { 40 if (node.HasLocalParameters) { 41 node.ShakeLocalParameters(random, 1.0); 42 } 51 43 } 52 53 // create a scope for all shaking operations 54 Scope tempScope = new Scope("Temp. manipulation scope"); 55 scope.AddSubScope(tempScope); // scope containing a subscope for each manipulation 56 scope.AddSubScope(backupScope); // scope containing the old subscopes 57 58 // create a composite operation for all shaking operations 59 CompositeOperation next = new CompositeOperation(); 60 next.ExecuteInParallel = false; 61 62 // enqueue all shaking operations 63 foreach (IFunctionTree subTree in TreeGardener.GetAllSubTrees(gpModel.FunctionTree).Where(x=>x.HasLocalParameters)) { 64 IOperation shakingOperation = subTree.CreateShakingOperation(tempScope); 65 next.AddOperation(shakingOperation); 66 } 67 68 // schedule a reducer operation to delete all temporary scopes and restore 69 // the subscopes of the backup scope after all manipulations are finished. 70 next.AddOperation(new AtomicOperation(new RightReducer(), scope)); 71 return next; 44 success = true; 72 45 } 73 46 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Manipulators/OnePointShaker.cs
r3219 r3512 1 1 #region License Information 2 2 /* HeuristicLab 3 * Copyright (C) 2002-20 08Heuristic and Evolutionary Algorithms Laboratory (HEAL)3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL) 4 4 * 5 5 * This file is part of HeuristicLab. … … 25 25 using HeuristicLab.Random; 26 26 using HeuristicLab.Data; 27 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 27 28 28 namespace HeuristicLab.Encodings.SymbolicExpressionTree { 29 public class OnePointShaker : DelegatingOperator { 30 public override string Description { 31 get { return "Selects a random node of all tree-nodes that have a manipulator defined and manipulates the selected node."; } 32 } 29 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Manipulators { 30 [StorableClass] 31 [Item("OnePointShaker", "Selects a random node with local parameters and manipulates the selected node.")] 32 public class OnePointShaker : SymbolicExpressionTreeManipulator { 33 33 34 34 public OnePointShaker() 35 35 : base() { 36 AddVariableInfo(new VariableInfo("FunctionLibrary", "Function library that defines mutation operations for functions", typeof(FunctionLibrary), VariableKind.In));37 AddVariableInfo(new VariableInfo("Random", "A random generator (uniform)", typeof(MersenneTwister), VariableKind.In));38 AddVariableInfo(new VariableInfo("ShakingFactor", "Factor that determines the force of the shaking operation", typeof(DoubleData), VariableKind.In));39 AddVariableInfo(new VariableInfo("FunctionTree", "The function tree that should be mutated", typeof(IGeneticProgrammingModel), VariableKind.In | VariableKind.Out));40 36 } 41 37 42 public override IOperation Apply(IScope scope) { 43 FunctionLibrary library = GetVariableValue<FunctionLibrary>("FunctionLibrary", scope, true); 44 IGeneticProgrammingModel gpModel = GetVariableValue<IGeneticProgrammingModel>("FunctionTree", scope, false); 45 MersenneTwister mt = GetVariableValue<MersenneTwister>("Random", scope, true); 38 protected override void Manipulate(IRandom random, SymbolicExpressionTree symbolicExpressionTree, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight, out bool success) { 46 39 47 // get all nodes with local parameters 48 var parametricBranches = TreeGardener.GetAllSubTrees(gpModel.FunctionTree).Where(branch => branch.HasLocalParameters); 49 if (parametricBranches.Count() == 0) return null; // don't manipulate anything if there are no nodes with a manipulation operator 50 IFunctionTree selectedBranch = parametricBranches.ElementAt(mt.Next(parametricBranches.Count())); 40 SymbolicExpressionTreeNode selectedPoint = (from node in symbolicExpressionTree.IterateNodesPrefix() 41 where node.HasLocalParameters 42 select node).SelectRandom(random); 51 43 52 // save the exising sub-scopes in a backup scope 53 Scope backupScope = new Scope("backup"); 54 foreach (Scope subScope in scope.SubScopes) { 55 backupScope.AddSubScope(subScope); 56 } 57 58 // create a scope for all shaking operations 59 Scope tempScope = new Scope("Temp. manipulation scope"); 60 61 // add the new sub-scopes 62 scope.AddSubScope(tempScope); 63 scope.AddSubScope(backupScope); 64 65 CompositeOperation next = new CompositeOperation(); 66 next.ExecuteInParallel = false; 67 // the next operation should first manipulate and then restore the sub-scopes from the backup scope 68 next.AddOperation(selectedBranch.CreateShakingOperation(tempScope)); 69 next.AddOperation(new AtomicOperation(new RightReducer(), scope)); 70 71 return next; 44 selectedPoint.ShakeLocalParameters(random, 1.0); 45 success = true; 72 46 } 73 47 } -
trunk/sources/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/Symbols/Constant.cs
r3485 r3512 28 28 using HeuristicLab.Parameters; 29 29 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols; 30 using System; 30 31 namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols { 31 32 [StorableClass] … … 45 46 set { maxValue = value; } 46 47 } 48 [Storable] 49 private double manipulatorNu; 50 public double ManipulatorNu { 51 get { return manipulatorNu; } 52 set { manipulatorNu = value; } 53 } 54 [Storable] 55 private double manipulatorSigma; 56 public double ManipulatorSigma { 57 get { return manipulatorSigma; } 58 set { 59 if (value < 0) throw new ArgumentException(); 60 manipulatorSigma = value; 61 } 62 } 47 63 #endregion 48 64 public Constant() 49 65 : base() { 66 manipulatorNu = 0.0; 67 manipulatorSigma = 1.0; 68 minValue = -20.0; 69 maxValue = 20.0; 50 70 } 51 71 … … 55 75 56 76 public override IDeepCloneable Clone(Cloner cloner) { 57 Constant clone = (Constant) 77 Constant clone = (Constant)base.Clone(cloner); 58 78 clone.minValue = minValue; 59 79 clone.maxValue = maxValue; 80 clone.manipulatorNu = manipulatorNu; 81 clone.manipulatorSigma = manipulatorSigma; 60 82 return clone; 61 83 } -
trunk/sources/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/Symbols/ConstantTreeNode.cs
r3485 r3512 63 63 } 64 64 65 public override void ShakeLocalParameters(IRandom random, double shakingFactor) { 66 base.ShakeLocalParameters(random, shakingFactor); 67 var normalDistributedRNG = new NormalDistributedRandom(random, Symbol.ManipulatorNu, Symbol.ManipulatorSigma); 68 double x = normalDistributedRNG.NextDouble(); 69 Value = Value + x * shakingFactor; 70 } 71 65 72 public override object Clone() { 66 73 return new ConstantTreeNode(this); -
trunk/sources/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/Symbols/Variable.cs
r3485 r3512 52 52 } 53 53 [Storable] 54 private double weightManipulatorNu; 55 public double WeightManipulatorNu { 56 get { return weightManipulatorNu; } 57 set { weightManipulatorNu = value; } 58 } 59 [Storable] 60 private double weightManipulatorSigma; 61 public double WeightManipulatorSigma { 62 get { return weightManipulatorSigma; } 63 set { 64 if (weightManipulatorSigma < 0.0) throw new ArgumentException("Negative sigma is not allowed."); 65 weightManipulatorSigma = value; 66 } 67 } 68 [Storable] 54 69 private List<string> variableNames; 55 70 public IEnumerable<string> VariableNames { … … 66 81 weightNu = 1.0; 67 82 weightSigma = 1.0; 83 weightManipulatorNu = 0.0; 84 weightManipulatorSigma = 1.0; 68 85 variableNames = new List<string>(); 69 86 } … … 78 95 clone.weightSigma = weightSigma; 79 96 clone.variableNames = new List<string>(variableNames); 97 clone.weightManipulatorNu = weightManipulatorNu; 98 clone.weightManipulatorSigma = weightManipulatorSigma; 80 99 return clone; 81 100 } -
trunk/sources/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/Symbols/VariableTreeNode.cs
r3485 r3512 69 69 var normalDistributedRNG = new NormalDistributedRandom(random, Symbol.WeightNu, Symbol.WeightSigma); 70 70 weight = normalDistributedRNG.NextDouble(); 71 var variableList = new List<string>(Symbol.VariableNames); 72 int variableIndex = random.Next(0, variableList.Count); 73 variableName = variableList[variableIndex]; 71 variableName = Symbol.VariableNames.SelectRandom(random); 74 72 } 73 74 public override void ShakeLocalParameters(IRandom random, double shakingFactor) { 75 base.ShakeLocalParameters(random, shakingFactor); 76 var normalDistributedRNG = new NormalDistributedRandom(random, Symbol.WeightManipulatorNu, Symbol.WeightManipulatorSigma); 77 double x = normalDistributedRNG.NextDouble(); 78 weight = weight + x * shakingFactor; 79 variableName = Symbol.VariableNames.SelectRandom(random); 80 } 81 75 82 76 83 public override object Clone() {
Note: See TracChangeset
for help on using the changeset viewer.