- Timestamp:
- 04/15/10 19:58:42 (14 years ago)
- Location:
- trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3
- Files:
-
- 6 added
- 25 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/ArgumentCreater.cs
r3338 r3360 96 96 // append a new argument branch after expanding all argument nodes 97 97 var clonedBranch = (SymbolicExpressionTreeNode)replacedBranch.Clone(); 98 ReplaceArgumentsInBranch(clonedBranch, invocationNode.SubTrees);98 clonedBranch = ReplaceArgumentsInBranch(clonedBranch, invocationNode.SubTrees); 99 99 invocationNode.InsertSubTree(newArgumentIndex, clonedBranch); 100 100 } … … 113 113 foreach (var subtree in symbolicExpressionTree.Root.SubTrees) { 114 114 // when the changed function is known in the branch then update the number of arguments 115 var matchingSymbol = subtree.Grammar.Symbols. Where(s => s.Name == selectedDefunBranch.FunctionName).SingleOrDefault();115 var matchingSymbol = subtree.Grammar.Symbols.OfType<InvokeFunction>().Where(s => s.FunctionName == selectedDefunBranch.FunctionName).SingleOrDefault(); 116 116 if (matchingSymbol != null) { 117 117 subtree.Grammar.SetMinSubtreeCount(matchingSymbol, selectedDefunBranch.NumberOfArguments); 118 118 subtree.Grammar.SetMaxSubtreeCount(matchingSymbol, selectedDefunBranch.NumberOfArguments); 119 foreach (var child in subtree.GetAllowedSymbols(0)) { 120 for (int i = 0; i < subtree.Grammar.GetMaxSubtreeCount(matchingSymbol); i++) { 121 subtree.Grammar.SetAllowedChild(matchingSymbol, child, i); 122 } 123 } 119 124 } 120 125 } … … 122 127 } 123 128 124 private static voidReplaceArgumentsInBranch(SymbolicExpressionTreeNode branch, IList<SymbolicExpressionTreeNode> argumentTrees) {125 // check if any subtree is an argument node126 for (int subtreeIndex = 0; subtreeIndex < branch.SubTrees.Count; subtreeIndex++) {127 var subtree = branch.SubTrees[subtreeIndex];128 var argNode = subtree as ArgumentTreeNode;129 if (argNode != null){130 // replace argument nodes by a clone of the original subtree that provided the result for the argument node131 branch.SubTrees[subtreeIndex] = (SymbolicExpressionTreeNode)argumentTrees[argNode.Symbol.ArgumentIndex].Clone();132 } else {133 // recursively replace arguments in all branches134 ReplaceArgumentsInBranch(subtree, argumentTrees);129 private static SymbolicExpressionTreeNode ReplaceArgumentsInBranch(SymbolicExpressionTreeNode branch, IList<SymbolicExpressionTreeNode> argumentTrees) { 130 if (branch is ArgumentTreeNode) { 131 var argNode = branch as ArgumentTreeNode; 132 // replace argument nodes by a clone of the original subtree that provided the result for the argument node 133 return (SymbolicExpressionTreeNode)argumentTrees[argNode.Symbol.ArgumentIndex].Clone(); 134 } else { 135 // call recursively for all subtree 136 List<SymbolicExpressionTreeNode> subtrees = new List<SymbolicExpressionTreeNode>(branch.SubTrees); 137 while (branch.SubTrees.Count > 0) branch.SubTrees.RemoveAt(0); 138 foreach (var subtree in subtrees) { 139 branch.AddSubTree(ReplaceArgumentsInBranch(subtree, argumentTrees)); 135 140 } 141 return branch; 136 142 } 137 143 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/ArgumentDeleter.cs
r3338 r3360 65 65 // argument deletion by consolidation is not possible => abort 66 66 return false; 67 // the argument to be removed is always the one with the largest index 68 // (otherwise we would have to decrement the index of the larger argument symbols) 67 69 var removedArgument = (from sym in selectedDefunBranch.Grammar.Symbols.OfType<Argument>() 68 select sym.ArgumentIndex).Distinct(). SelectRandom(random);70 select sym.ArgumentIndex).Distinct().OrderBy(x => x).Last(); 69 71 // find invocations of the manipulated funcion and remove the specified argument tree 70 var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()71 where node.Symbol.FunctionName == selectedDefunBranch.FunctionName72 select node;72 var invocationNodes = (from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>() 73 where node.Symbol.FunctionName == selectedDefunBranch.FunctionName 74 select node).ToList(); 73 75 foreach (var invokeNode in invocationNodes) { 74 76 invokeNode.RemoveSubTree(removedArgument); … … 78 80 79 81 // delete the dynamic argument symbol that matches the argument to be removed 80 var matchingSymbol = selectedDefunBranch.Grammar.Symbols.OfType<Argument>().Where(s => s.ArgumentIndex == removedArgument). First();82 var matchingSymbol = selectedDefunBranch.Grammar.Symbols.OfType<Argument>().Where(s => s.ArgumentIndex == removedArgument).Single(); 81 83 selectedDefunBranch.Grammar.RemoveSymbol(matchingSymbol); 84 selectedDefunBranch.NumberOfArguments--; 82 85 // reduce arity in known functions of all root branches 83 86 foreach (var subtree in symbolicExpressionTree.Root.SubTrees) { 84 var matchingInvokeSymbol = subtree.Grammar.Symbols.OfType<InvokeFunction>().Where(s => s.FunctionName == selectedDefunBranch.FunctionName). FirstOrDefault();87 var matchingInvokeSymbol = subtree.Grammar.Symbols.OfType<InvokeFunction>().Where(s => s.FunctionName == selectedDefunBranch.FunctionName).SingleOrDefault(); 85 88 if (matchingInvokeSymbol != null) { 86 subtree.Grammar.SetMinSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments - 1);87 subtree.Grammar.SetMaxSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments - 1);89 subtree.Grammar.SetMinSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments); 90 subtree.Grammar.SetMaxSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments); 88 91 } 89 92 } 90 selectedDefunBranch.NumberOfArguments--;91 93 return true; 92 94 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/ArgumentDuplicater.cs
r3338 r3360 64 64 return false; 65 65 66 var selectedDefunBranch = SelectRandomBranch(random, functionDefiningBranches); 67 var argumentNodes = from node in IterateNodesPrefix(selectedDefunBranch) 68 where node is ArgumentTreeNode 69 select (ArgumentTreeNode)node; 70 if (argumentNodes.Count() == 0 || argumentNodes.Count() >= maxFunctionArguments) 66 var selectedDefunBranch = functionDefiningBranches.SelectRandom(random); 67 var argumentSymbols = selectedDefunBranch.Grammar.Symbols.OfType<Argument>(); 68 if (argumentSymbols.Count() == 0 || argumentSymbols.Count() >= maxFunctionArguments) 71 69 // when no argument or number of arguments is already at max allowed value => abort 72 70 return false; 73 var distinctArgumentIndexes = (from node in argumentNodes 74 select node.ArgumentIndex).Distinct().ToList(); 75 var selectedArgumentIndex = distinctArgumentIndexes[random.Next(distinctArgumentIndexes.Count)]; 76 var newArgumentIndex = allowedArgumentIndexes.Except(from argNode in argumentNodes select argNode.ArgumentIndex).First(); 71 var selectedArgumentSymbol = argumentSymbols.SelectRandom(random); 72 var takenIndexes = argumentSymbols.Select(s => s.ArgumentIndex); 73 var newArgumentIndex = allowedArgumentIndexes.Except(takenIndexes).First(); 74 75 var newArgSymbol = new Argument(newArgumentIndex); 76 77 77 // replace existing references to the original argument with references to the new argument randomly in the selectedBranch 78 var argumentNodes = selectedDefunBranch.IterateNodesPrefix().OfType<ArgumentTreeNode>(); 78 79 foreach (var argNode in argumentNodes) { 79 if (argNode. ArgumentIndex == selectedArgumentIndex) {80 if (argNode.Symbol == selectedArgumentSymbol) { 80 81 if (random.NextDouble() < 0.5) { 81 argNode. ArgumentIndex = newArgumentIndex;82 argNode.Symbol = newArgSymbol; 82 83 } 83 84 } 84 85 } 85 86 // find invocations of the functions and duplicate the matching argument branch 86 var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix() 87 let invokeNode = node as InvokeFunctionTreeNode 88 where invokeNode != null 89 where invokeNode.InvokedFunctionName == selectedDefunBranch.Name 90 select invokeNode; 87 var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>() 88 where node.Symbol.FunctionName == selectedDefunBranch.FunctionName 89 select node; 91 90 foreach (var invokeNode in invocationNodes) { 92 var argumentBranch = invokeNode.SubTrees[selectedArgument Index];91 var argumentBranch = invokeNode.SubTrees[selectedArgumentSymbol.ArgumentIndex]; 93 92 var clonedArgumentBranch = (SymbolicExpressionTreeNode)argumentBranch.Clone(); 94 93 invokeNode.InsertSubTree(newArgumentIndex, clonedArgumentBranch); 95 94 } 96 // register the new argument node and increase the number of arguments of the ADF 97 selectedDefunBranch.AddDynamicSymbol("ARG" + newArgumentIndex); 95 // register the new argument symbol and increase the number of arguments of the ADF 96 selectedDefunBranch.Grammar.AddSymbol(newArgSymbol); 97 selectedDefunBranch.Grammar.SetMinSubtreeCount(newArgSymbol, 0); 98 selectedDefunBranch.Grammar.SetMaxSubtreeCount(newArgSymbol, 0); 99 // allow the argument as child of any other symbol 100 foreach (var symb in selectedDefunBranch.Grammar.Symbols) 101 for (int i = 0; i < selectedDefunBranch.Grammar.GetMaxSubtreeCount(symb); i++) { 102 selectedDefunBranch.Grammar.SetAllowedChild(symb, newArgSymbol, i); 103 } 98 104 selectedDefunBranch.NumberOfArguments++; 105 99 106 // increase the arity of the changed ADF in all branches that can use this ADF 100 107 foreach (var subtree in symbolicExpressionTree.Root.SubTrees) { 101 if (subtree.DynamicSymbols.Contains(selectedDefunBranch.Name)) { 102 subtree.SetDynamicSymbolArgumentCount(selectedDefunBranch.Name, selectedDefunBranch.NumberOfArguments); 108 var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>() 109 where symb.FunctionName == selectedDefunBranch.FunctionName 110 select symb).SingleOrDefault(); 111 if (matchingInvokeSymbol != null) { 112 subtree.Grammar.SetMinSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments); 113 subtree.Grammar.SetMaxSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments); 114 foreach (var child in subtree.GetAllowedSymbols(0)) { 115 for (int i = 0; i < subtree.Grammar.GetMaxSubtreeCount(matchingInvokeSymbol); i++) { 116 subtree.Grammar.SetAllowedChild(matchingInvokeSymbol, child, i); 117 } 118 } 103 119 } 104 120 } 105 Debug.Assert(grammar.IsValidExpression(symbolicExpressionTree));106 121 return true; 107 122 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/RandomArchitectureAlteringOperator.cs
r3294 r3360 65 65 66 66 public override void ModifyArchitecture(IRandom random, SymbolicExpressionTree tree, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight, IntValue maxFunctionDefiningBranches, IntValue maxFunctionArguments, out bool success) { 67 var selectedOperator = Operators [random.Next(Operators.Count)];67 var selectedOperator = Operators.SelectRandom(random); 68 68 selectedOperator.ModifyArchitecture(random, tree, grammar, maxTreeSize, maxTreeHeight, maxFunctionDefiningBranches, maxFunctionArguments, out success); 69 69 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/SubroutineCreater.cs
r3338 r3360 42 42 [StorableClass] 43 43 public sealed class SubroutineCreater : SymbolicExpressionTreeArchitectureAlteringOperator { 44 private const double ARGUMENT_CUTOFF_PROBABILITY = 0.05; 45 44 46 public override sealed void ModifyArchitecture( 45 47 IRandom random, … … 62 64 // allowed maximum number of ADF reached => abort 63 65 return false; 64 string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefiningBranches) + 1).ToString(); // >= 100 functions => ### 66 if (symbolicExpressionTree.Size + 4 > maxTreeSize) 67 // defining a new function causes an size increase by 4 nodes (max) if the max tree size is reached => abort 68 return false; 69 string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefiningBranches * 10 - 1)).ToString(); // >= 100 functions => ### 65 70 var allowedFunctionNames = from index in Enumerable.Range(0, maxFunctionDefiningBranches) 66 71 select "ADF" + index.ToString(formatString); 67 // find all body branches 68 var bodies = from node in symbolicExpressionTree.IterateNodesPrefix()69 where node.Symbol is Defun || node.Symbol is StartSymbol72 73 // select a random body (either the result producing branch or an ADF branch) 74 var bodies = from node in symbolicExpressionTree.Root.SubTrees 70 75 select new { Tree = node, Size = node.GetSize() }; 71 76 var totalNumberOfBodyNodes = bodies.Select(x => x.Size).Sum(); 72 // select a random body73 77 int r = random.Next(totalNumberOfBodyNodes); 74 78 int aggregatedNumberOfBodyNodes = 0; … … 81 85 // sanity check 82 86 if (selectedBody == null) throw new InvalidOperationException(); 83 // select a random node in the selected branch 84 var allCutPoints = (from parent in selectedBody.IterateNodesPrefix() 85 from subtree in parent.SubTrees 86 select new { Parent = parent, ReplacedBranchIndex = parent.SubTrees.IndexOf(subtree), ReplacedBranch = subtree }).ToList(); 87 if (allCutPoints.Count == 0) 87 88 // select a random cut point in the selected branch 89 var allCutPoints = from parent in selectedBody.IterateNodesPrefix() 90 from subtree in parent.SubTrees 91 select new { Parent = parent, ReplacedBranchIndex = parent.SubTrees.IndexOf(subtree), ReplacedBranch = subtree }; 92 if (allCutPoints.Count() == 0) 88 93 // no cut points => abort 89 94 return false; 90 var selectedCutPoint = allCutPoints[random.Next(allCutPoints.Count)]; 95 string newFunctionName = allowedFunctionNames.Except(functionDefiningBranches.Select(x => x.FunctionName)).First(); 96 var selectedCutPoint = allCutPoints.SelectRandom(random); 91 97 // select random branches as argument cut-off points (replaced by argument terminal nodes in the function) 92 List<SymbolicExpressionTreeNode> argumentBranches = SelectRandomArgumentBranches(selectedCutPoint.ReplacedBranch, random, 0.25, maxFunctionArguments); 93 string functionName = allowedFunctionNames.Except(functionDefiningBranches.Select(x => x.Name)).First(); 98 List<SymbolicExpressionTreeNode> argumentBranches = SelectRandomArgumentBranches(selectedCutPoint.ReplacedBranch, random, ARGUMENT_CUTOFF_PROBABILITY, maxFunctionArguments); 94 99 SymbolicExpressionTreeNode functionBody = selectedCutPoint.ReplacedBranch; 95 100 // disconnect the function body from the tree 96 101 selectedCutPoint.Parent.RemoveSubTree(selectedCutPoint.ReplacedBranchIndex); 97 102 // disconnect the argument branches from the function 98 DisconnectBranches(functionBody, argumentBranches); 99 // and insert a function invocation symbol instead 100 var invokeNode = (InvokeFunctionTreeNode)(new InvokeFunction()).CreateTreeNode(); 101 invokeNode.InvokedFunctionName = functionName; 103 functionBody = DisconnectBranches(functionBody, argumentBranches); 104 // insert a function invocation symbol instead 105 var invokeNode = (InvokeFunctionTreeNode)(new InvokeFunction(newFunctionName)).CreateTreeNode(); 102 106 selectedCutPoint.Parent.InsertSubTree(selectedCutPoint.ReplacedBranchIndex, invokeNode); 107 // add the branches selected as argument as subtrees of the function invocation node 103 108 foreach (var argumentBranch in argumentBranches) 104 109 invokeNode.AddSubTree(argumentBranch); … … 106 111 // insert a new function defining branch 107 112 var defunNode = (DefunTreeNode)(new Defun()).CreateTreeNode(); 108 defunNode. Name = functionName;113 defunNode.FunctionName = newFunctionName; 109 114 defunNode.AddSubTree(functionBody); 110 115 symbolicExpressionTree.Root.AddSubTree(defunNode); 111 // copy known symbols from originating branch into new branch 112 foreach (var knownSymbol in selectedBody.DynamicSymbols) { 113 defunNode.AddDynamicSymbol(knownSymbol, selectedBody.GetDynamicSymbolArgumentCount(knownSymbol)); 114 } 115 // add function arguments as known symbols to new branch 116 for (int i = 0; i < argumentBranches.Count; i++) { 117 defunNode.AddDynamicSymbol("ARG" + i); 118 } 119 // add new function name to original branch 120 selectedBody.AddDynamicSymbol(functionName, argumentBranches.Count); 116 // the grammar in the newly defined function is a clone of the grammar of the originating branch 117 defunNode.Grammar = (ISymbolicExpressionGrammar)selectedBody.Grammar.Clone(); 118 // remove all argument symbols from grammar 119 var oldArgumentSymbols = defunNode.Grammar.Symbols.OfType<Argument>().ToList(); 120 foreach (var oldArgSymb in oldArgumentSymbols) 121 defunNode.Grammar.RemoveSymbol(oldArgSymb); 122 // find unique argument indexes and matching symbols in the function defining branch 123 var newArgumentIndexes = (from node in defunNode.IterateNodesPrefix().OfType<ArgumentTreeNode>() 124 select node.Symbol.ArgumentIndex).Distinct(); 125 // add argument symbols to grammar of function defining branch 126 GrammarModifier.AddDynamicArguments(defunNode.Grammar, defunNode.Symbol, newArgumentIndexes); 127 defunNode.NumberOfArguments = newArgumentIndexes.Count(); 128 if (defunNode.NumberOfArguments != argumentBranches.Count) throw new InvalidOperationException(); 129 // add invoke symbol for newly defined function to the original branch 130 var allowedParents = from symb in selectedBody.Grammar.Symbols 131 where !(symb is ProgramRootSymbol) 132 select symb; 133 var allowedChildren = from symb in selectedBody.Grammar.Symbols 134 where selectedBody.Grammar.IsAllowedChild(selectedBody.Symbol, symb, 0) 135 select symb; 136 GrammarModifier.AddDynamicSymbol(selectedBody.Grammar, selectedBody.Symbol, defunNode.FunctionName, defunNode.NumberOfArguments); 137 138 // when the new function body was taken from another function definition 139 // add invoke symbol for newly defined function to all branches that are allowed to invoke the original branch 140 if (selectedBody.Symbol is Defun) { 141 var originalFunctionDefinition = selectedBody as DefunTreeNode; 142 foreach (var subtree in symbolicExpressionTree.Root.SubTrees) { 143 var originalBranchInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>() 144 where symb.FunctionName == originalFunctionDefinition.FunctionName 145 select symb).SingleOrDefault(); 146 // when the original branch can be invoked from the subtree then also allow invocation of the function 147 if (originalBranchInvokeSymbol != null) { 148 allowedParents = from symb in subtree.Grammar.Symbols 149 where !(symb is ProgramRootSymbol) 150 select symb; 151 allowedChildren = from symb in subtree.Grammar.Symbols 152 where subtree.Grammar.IsAllowedChild(subtree.Symbol, symb, 0) 153 select symb; 154 GrammarModifier.AddDynamicSymbol(subtree.Grammar, subtree.Symbol, defunNode.FunctionName, defunNode.NumberOfArguments); 155 } 156 } 157 } 121 158 return true; 122 159 } 123 160 124 private static void DisconnectBranches(SymbolicExpressionTreeNode node, List<SymbolicExpressionTreeNode> argumentBranches) { 161 private static SymbolicExpressionTreeNode DisconnectBranches(SymbolicExpressionTreeNode node, List<SymbolicExpressionTreeNode> argumentBranches) { 162 if (argumentBranches.Contains(node)) { 163 var argumentIndex = argumentBranches.IndexOf(node); 164 var argSymbol = new Argument(argumentIndex); 165 return argSymbol.CreateTreeNode(); 166 } 125 167 // remove the subtrees so that we can clone only the root node 126 168 List<SymbolicExpressionTreeNode> subtrees = new List<SymbolicExpressionTreeNode>(node.SubTrees); … … 128 170 // recursively apply function for subtrees or append a argument terminal node 129 171 foreach (var subtree in subtrees) { 130 if (argumentBranches.Contains(subtree)) { 131 node.AddSubTree(MakeArgumentNode(argumentBranches.IndexOf(subtree))); 132 } else { 133 DisconnectBranches(subtree, argumentBranches); 134 node.AddSubTree(subtree); 135 } 136 } 137 } 138 139 private static SymbolicExpressionTreeNode MakeArgumentNode(int argIndex) { 140 var node = (ArgumentTreeNode)(new Argument()).CreateTreeNode(); 141 node.ArgumentIndex = argIndex; 172 node.AddSubTree(DisconnectBranches(subtree, argumentBranches)); 173 } 142 174 return node; 143 175 } … … 145 177 private static List<SymbolicExpressionTreeNode> SelectRandomArgumentBranches(SymbolicExpressionTreeNode selectedRoot, 146 178 IRandom random, 147 double argumentProbability,179 double cutProbability, 148 180 int maxArguments) { 181 // breadth first determination of argument cut-off points 182 // we must make sure that we cut off all original argument nodes and that the number of new argument is smaller than the limit 149 183 List<SymbolicExpressionTreeNode> argumentBranches = new List<SymbolicExpressionTreeNode>(); 150 foreach (var subTree in selectedRoot.SubTrees) { 151 if (random.NextDouble() < argumentProbability) { 152 if (argumentBranches.Count < maxArguments) 153 argumentBranches.Add(subTree); 154 } else { 155 foreach (var argBranch in SelectRandomArgumentBranches(subTree, random, argumentProbability, maxArguments)) 156 if (argumentBranches.Count < maxArguments) 157 argumentBranches.Add(argBranch); 184 if (selectedRoot is ArgumentTreeNode) { 185 argumentBranches.Add(selectedRoot); 186 return argumentBranches; 187 } else { 188 // get the number of argument nodes (which must be cut-off) in the sub-trees 189 var numberOfArgumentsInSubtrees = (from subtree in selectedRoot.SubTrees 190 let nArgumentsInTree = subtree.IterateNodesPrefix().OfType<ArgumentTreeNode>().Count() 191 select nArgumentsInTree).ToList(); 192 // determine the minimal number of new argument nodes for each sub-tree 193 var minNewArgumentsForSubtrees = numberOfArgumentsInSubtrees.Select(x => x > 0 ? 1 : 0).ToList(); 194 if (minNewArgumentsForSubtrees.Sum() > maxArguments) { 195 argumentBranches.Add(selectedRoot); 196 return argumentBranches; 158 197 } 159 } 160 return argumentBranches; 161 } 162 163 private static IEnumerable<string> UsedFunctionNames(SymbolicExpressionTree symbolicExpressionTree) { 164 return from node in symbolicExpressionTree.IterateNodesPrefix() 165 where node.Symbol is Defun 166 select ((DefunTreeNode)node).Name; 198 // cut-off in the sub-trees in random order 199 var randomIndexes = (from index in Enumerable.Range(0, selectedRoot.SubTrees.Count) 200 select new { Index = index, OrderValue = random.NextDouble() }).OrderBy(x => x.OrderValue).Select(x => x.Index); 201 foreach (var subtreeIndex in randomIndexes) { 202 var subtree = selectedRoot.SubTrees[subtreeIndex]; 203 minNewArgumentsForSubtrees[subtreeIndex] = 0; 204 // => cut-off at 0..n points somewhere in the current sub-tree 205 // determine the maximum number of new arguments that should be created in the branch 206 // as the maximum for the whole branch minus already added arguments minus minimal number of arguments still left 207 int maxArgumentsFromBranch = maxArguments - argumentBranches.Count - minNewArgumentsForSubtrees.Sum(); 208 // when no argument is allowed from the current branch then we have to include the whole branch into the function 209 // otherwise: choose randomly wether to cut off immediately or wether to extend the function body into the branch 210 if (maxArgumentsFromBranch == 0) { 211 // don't cut at all => the whole sub-tree branch is included in the function body 212 // (we already checked ahead of time that there are no arguments left over in the subtree) 213 } else if (random.NextDouble() >= cutProbability) { 214 argumentBranches.AddRange(SelectRandomArgumentBranches(subtree, random, cutProbability, maxArgumentsFromBranch)); 215 } else { 216 // cut-off at current sub-tree 217 argumentBranches.Add(subtree); 218 } 219 } 220 return argumentBranches; 221 } 167 222 } 168 223 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/SubroutineDeleter.cs
r3338 r3360 41 41 [StorableClass] 42 42 public sealed class SubroutineDeleter : SymbolicExpressionTreeArchitectureAlteringOperator { 43 private const int MAX_TRIES = 100;44 43 public override sealed void ModifyArchitecture( 45 44 IRandom random, … … 68 67 symbolicExpressionTree.Root.RemoveSubTree(defunSubtreeIndex); 69 68 70 // get all cut points that contain an invokation of the deleted defun71 var invocationCutPoints = from node in symbolicExpressionTree.IterateNodesPrefix()72 where node.SubTrees.Count > 073 from argIndex in Enumerable.Range(0, node.SubTrees.Count)74 let subtree = node.SubTrees[argIndex] as InvokeFunctionTreeNode75 where subtree != null76 where subtree.InvokedFunctionName == selectedDefunBranch.Name77 select new { Parent = node, ReplacedChildIndex = argIndex, ReplacedChild = subtree };78 // deletion by random regeneration79 foreach (var cutPoint in invocationCutPoints) {80 SymbolicExpressionTreeNode replacementTree = null;81 int targetSize = random.Next(cutPoint.ReplacedChild.GetSize());82 int targetHeight = cutPoint.ReplacedChild.GetHeight();83 int tries = 0;84 do {85 try {86 replacementTree = ProbabilisticTreeCreator.PTC2(random, grammar, cutPoint.Parent.Symbol, targetSize, targetHeight);87 }88 catch (ArgumentException) {89 // try different size90 targetSize = random.Next(cutPoint.ReplacedChild.GetSize());91 if (tries++ > MAX_TRIES) throw;92 }93 } while (replacementTree == null);94 cutPoint.Parent.RemoveSubTree(cutPoint.ReplacedChildIndex);95 cutPoint.Parent.InsertSubTree(cutPoint.ReplacedChildIndex, replacementTree);96 }97 69 // remove references to deleted function 98 70 foreach (var subtree in symbolicExpressionTree.Root.SubTrees) { 99 if (subtree.DynamicSymbols.Contains(selectedDefunBranch.Name)) { 100 subtree.RemoveDynamicSymbol(selectedDefunBranch.Name); 71 var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>() 72 where symb.FunctionName == selectedDefunBranch.FunctionName 73 select symb).SingleOrDefault(); 74 if (matchingInvokeSymbol != null) { 75 subtree.Grammar.RemoveSymbol(matchingInvokeSymbol); 101 76 } 102 77 } 103 Debug.Assert(grammar.IsValidExpression(symbolicExpressionTree)); 78 79 DeletionByRandomRegeneration(random, symbolicExpressionTree, selectedDefunBranch); 104 80 return true; 81 } 82 83 private static void DeletionByRandomRegeneration(IRandom random, SymbolicExpressionTree symbolicExpressionTree, DefunTreeNode selectedDefunBranch) { 84 // find first invocation and replace it with a randomly generated tree 85 // can't find all invocations in one step because once we replaced a top level invocation 86 // the invocations below it are removed already 87 var invocationCutPoint = (from node in symbolicExpressionTree.IterateNodesPrefix() 88 from subtree in node.SubTrees.OfType<InvokeFunctionTreeNode>() 89 where subtree.Symbol.FunctionName == selectedDefunBranch.FunctionName 90 select new { Parent = node, ReplacedChildIndex = node.SubTrees.IndexOf(subtree), ReplacedChild = subtree }).FirstOrDefault(); 91 while (invocationCutPoint != null) { 92 // deletion by random regeneration 93 SymbolicExpressionTreeNode replacementTree = null; 94 // TODO: should weight symbols by tickets 95 var selectedSymbol = invocationCutPoint.Parent.GetAllowedSymbols(invocationCutPoint.ReplacedChildIndex).SelectRandom(random); 96 97 int minPossibleSize = invocationCutPoint.Parent.Grammar.GetMinExpressionLength(selectedSymbol); 98 int maxSize = Math.Max(minPossibleSize, invocationCutPoint.ReplacedChild.GetSize()); 99 int minPossibleHeight = invocationCutPoint.Parent.Grammar.GetMinExpressionDepth(selectedSymbol); 100 int maxHeight = Math.Max(minPossibleHeight, invocationCutPoint.ReplacedChild.GetHeight()); 101 102 replacementTree = ProbabilisticTreeCreator.PTC2(random, invocationCutPoint.Parent.Grammar, selectedSymbol, maxSize, maxHeight, 0, 0); 103 invocationCutPoint.Parent.RemoveSubTree(invocationCutPoint.ReplacedChildIndex); 104 invocationCutPoint.Parent.InsertSubTree(invocationCutPoint.ReplacedChildIndex, replacementTree); 105 106 invocationCutPoint = (from node in symbolicExpressionTree.IterateNodesPrefix() 107 from subtree in node.SubTrees.OfType<InvokeFunctionTreeNode>() 108 where subtree.Symbol.FunctionName == selectedDefunBranch.FunctionName 109 select new { Parent = node, ReplacedChildIndex = node.SubTrees.IndexOf(subtree), ReplacedChild = subtree }).FirstOrDefault(); 110 } 105 111 } 106 112 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/SubroutineDuplicater.cs
r3338 r3360 48 48 IntValue maxFunctionDefiningBranches, IntValue maxFunctionArguments, 49 49 out bool success) { 50 success = Duplicate RandomSubroutine(random, symbolicExpressionTree, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefiningBranches.Value, maxFunctionArguments.Value);50 success = DuplicateSubroutine(random, symbolicExpressionTree, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefiningBranches.Value, maxFunctionArguments.Value); 51 51 } 52 52 53 public static bool Duplicate RandomSubroutine(53 public static bool DuplicateSubroutine( 54 54 IRandom random, 55 55 SymbolicExpressionTree symbolicExpressionTree, … … 66 66 return false; 67 67 var selectedBranch = functionDefiningBranches.SelectRandom(random); 68 var clonedBranch = (DefunTreeNode)selectedBranch.Clone(); 69 clonedBranch.Name = allowedFunctionNames.Except(UsedFunctionNames(symbolicExpressionTree)).First(); 70 foreach (var node in symbolicExpressionTree.IterateNodesPrefix()) { 71 var invokeFunctionNode = node as InvokeFunctionTreeNode; 72 // find all invokations of the old function 73 if (invokeFunctionNode != null && invokeFunctionNode.InvokedFunctionName == selectedBranch.Name) { 74 // add the new function name to the list of known functions in the branches that used the originating function 75 var branch = symbolicExpressionTree.GetTopLevelBranchOf(invokeFunctionNode); 76 branch.AddDynamicSymbol(clonedBranch.Name, clonedBranch.NumberOfArguments); 77 // flip coin wether to replace with newly defined function 78 if (random.NextDouble() < 0.5) { 79 invokeFunctionNode.InvokedFunctionName = clonedBranch.Name; 80 } 68 var duplicatedDefunBranch = (DefunTreeNode)selectedBranch.Clone(); 69 string newFunctionName = allowedFunctionNames.Except(UsedFunctionNames(symbolicExpressionTree)).First(); 70 duplicatedDefunBranch.FunctionName = newFunctionName; 71 symbolicExpressionTree.Root.SubTrees.Add(duplicatedDefunBranch); 72 duplicatedDefunBranch.Grammar = (ISymbolicExpressionGrammar)selectedBranch.Grammar.Clone(); 73 // add an invoke symbol for each branch that is allowed to invoke the original function 74 foreach (var subtree in symbolicExpressionTree.Root.SubTrees) { 75 var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>() 76 where symb.FunctionName == selectedBranch.FunctionName 77 select symb).SingleOrDefault(); 78 if (matchingInvokeSymbol != null) { 79 GrammarModifier.AddDynamicSymbol(subtree.Grammar, subtree.Symbol, duplicatedDefunBranch.FunctionName, duplicatedDefunBranch.NumberOfArguments); 81 80 } 82 81 } 83 Debug.Assert(grammar.IsValidExpression(symbolicExpressionTree)); 82 // for all invoke nodes of the original function replace the invoke of the original function with an invoke of the new function randomly 83 var originalFunctionInvocations = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>() 84 where node.Symbol.FunctionName == selectedBranch.FunctionName 85 select node; 86 foreach (var originalFunctionInvokeNode in originalFunctionInvocations) { 87 var newInvokeSymbol = (from symb in originalFunctionInvokeNode.Grammar.Symbols.OfType<InvokeFunction>() 88 where symb.FunctionName == duplicatedDefunBranch.FunctionName 89 select symb).Single(); 90 // flip coin wether to replace with newly defined function 91 if (random.NextDouble() < 0.5) { 92 originalFunctionInvokeNode.Symbol = newInvokeSymbol; 93 } 94 } 84 95 return true; 85 }86 87 private static bool ContainsNode(SymbolicExpressionTreeNode branch, SymbolicExpressionTreeNode node) {88 if (branch == node) return true;89 else foreach (var subtree in branch.SubTrees) {90 if (ContainsNode(subtree, node)) return true;91 }92 return false;93 96 } 94 97 … … 96 99 return from node in symbolicExpressionTree.IterateNodesPrefix() 97 100 where node.Symbol is Defun 98 select ((DefunTreeNode)node). Name;101 select ((DefunTreeNode)node).FunctionName; 99 102 } 100 101 102 103 } 103 104 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Creators/ProbabilisticTreeCreator.cs
r3338 r3360 29 29 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols; 30 30 using System.Text; 31 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureAlteringOperators; 31 32 32 33 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding { … … 51 52 int maxFunctionDefinitions, int maxFunctionArguments 52 53 ) { 53 // tree size is limited by the grammar and by the explicit size constraints54 int allowedMinSize = grammar.GetMinExpressionLength(grammar.StartSymbol);55 int allowedMaxSize = Math.Min(maxTreeSize, grammar.GetMaxExpressionLength(grammar.StartSymbol));56 // select a target tree size uniformly in the possible range (as determined by explicit limits and limits of the grammar)57 int treeSize = random.Next(allowedMinSize, allowedMaxSize);58 54 SymbolicExpressionTree tree = new SymbolicExpressionTree(); 59 do { 60 try { 61 tree.Root = PTC2(random, grammar, grammar.StartSymbol, treeSize + 1, maxTreeHeight + 1, maxFunctionDefinitions, maxFunctionArguments); 62 } 63 catch (ArgumentException) { 64 // try a different size 65 treeSize = random.Next(allowedMinSize, allowedMaxSize); 66 } 67 } while (tree.Root == null || tree.Size > maxTreeSize || tree.Height > maxTreeHeight); 55 tree.Root = PTC2(random, grammar, grammar.StartSymbol, maxTreeSize, maxTreeHeight, maxFunctionDefinitions, maxFunctionArguments); 68 56 return tree; 69 57 } … … 74 62 public int ExtensionPointDepth { get; set; } 75 63 } 64 65 /// <summary> 66 /// Creates a random tree with <paramref name="maxTreeSize"/> and <paramref name="maxDepth"/>. 67 /// </summary> 68 /// <param name="random"></param> 69 /// <param name="grammar"></param> 70 /// <param name="rootSymbol"></param> 71 /// <param name="maxTreeSize"></param> 72 /// <param name="maxDepth"></param> 73 /// <param name="maxFunctionDefinitions"></param> 74 /// <param name="maxFunctionArguments"></param> 75 /// <returns></returns> 76 76 public static SymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionGrammar grammar, Symbol rootSymbol, 77 int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) { 78 SymbolicExpressionTreeNode root = rootSymbol.CreateTreeNode(); 79 root.Grammar = grammar; 80 if (size <= 1 || maxDepth <= 1) return root; 81 CreateFullTreeFromSeed(random, root, size, maxDepth, maxFunctionDefinitions, maxFunctionArguments); 77 int maxTreeSize, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) { 78 // tree size is limited by the grammar and by the explicit size constraints 79 int allowedMinSize = grammar.GetMinExpressionLength(rootSymbol); 80 int allowedMaxSize = Math.Min(maxTreeSize, grammar.GetMaxExpressionLength(rootSymbol)); 81 // select a target tree size uniformly in the possible range (as determined by explicit limits and limits of the grammar) 82 int treeSize = random.Next(allowedMinSize, allowedMaxSize + 1); 83 SymbolicExpressionTreeNode root = null; 84 do { 85 try { 86 root = rootSymbol.CreateTreeNode(); 87 root.Grammar = grammar; 88 if (treeSize <= 1 || maxDepth <= 1) return root; 89 CreateFullTreeFromSeed(random, root, treeSize, maxDepth, maxFunctionDefinitions, maxFunctionArguments); 90 } 91 catch (ArgumentException) { 92 // try a different size 93 root = null; 94 treeSize = random.Next(allowedMinSize, allowedMaxSize); 95 } 96 } while (root == null || root.GetSize() > maxTreeSize || root.GetHeight() > maxDepth); 82 97 return root; 83 98 } … … 105 120 if (extensionDepth + parent.Grammar.GetMinExpressionDepth(parent.Symbol) >= maxDepth) { 106 121 ReplaceWithMinimalTree(random, root, parent, argumentIndex, maxFunctionDefinitions, maxFunctionArguments); 107 //parent.RemoveSubTree(argumentIndex);108 //var allowedSymbols = from s in parent.Grammar.Symbols109 // where parent.Grammar.IsAllowedChild(parent.Symbol, s, argumentIndex)110 // select s;111 //SymbolicExpressionTreeNode branch = CreateMinimalTree(random, parent, allowedSymbols);112 //parent.InsertSubTree(argumentIndex, branch); // insert a smallest possible tree113 //currentSize += branch.GetSize();114 //totalListMinSize -= branch.GetSize();115 122 } else { 116 123 var allowedSymbols = from s in parent.Grammar.Symbols … … 118 125 where parent.Grammar.GetMinExpressionDepth(s) + extensionDepth - 1 < maxDepth 119 126 where parent.Grammar.GetMaxExpressionLength(s) > size - totalListMinSize - currentSize 120 /*||121 totalListMinSize + currentSize >= size * 0.9 // if the necessary size is almost reached then also allow122 // terminals or terminal-branches*/123 // where !IsDynamicSymbol(s) || IsDynamicSymbolAllowed(grammar, root, parent, s)124 127 select s; 125 128 Symbol selectedSymbol = SelectRandomSymbol(random, allowedSymbols); … … 172 175 var dummy = new SymbolicExpressionTreeNode(); 173 176 tree.AddSubTree(dummy); 174 dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone(); 177 dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone(); 175 178 // replace the just inserted dummy by recursive application 176 179 ReplaceWithMinimalTree(random, root, tree, i, maxFunctionDefinitions, maxFunctionArguments); 177 180 } 178 181 } 179 182 180 183 private static void InitializeNewTreeNode(IRandom random, SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode newTree, int maxFunctionDefinitions, int maxFunctionArguments) { 181 184 // NB it is assumed that defuns are only allowed as children of root and nowhere else 182 185 // also assumes that newTree is already attached to root somewhere 183 if (IsTopLevelBranch(root, newTree)) 186 if (IsTopLevelBranch(root, newTree)) { 184 187 newTree.Grammar = (ISymbolicExpressionGrammar)newTree.Grammar.Clone(); 188 189 // allow invokes of existing ADFs with higher index 190 int argIndex = root.SubTrees.IndexOf(newTree); 191 for (int i = argIndex + 1; i < root.SubTrees.Count; i++) { 192 var otherDefunNode = root.SubTrees[i] as DefunTreeNode; 193 if (otherDefunNode != null) { 194 GrammarModifier.AddDynamicSymbol(newTree.Grammar, newTree.Symbol, otherDefunNode.FunctionName, otherDefunNode.NumberOfArguments); 195 } 196 } 197 } 185 198 if (newTree.Symbol is Defun) { 186 199 var defunTree = newTree as DefunTreeNode; … … 197 210 defunTree.NumberOfArguments = nArgs; 198 211 if (nArgs > 0) { 199 AddDynamicArguments(defunTree.Grammar, nArgs); 200 } 212 GrammarModifier.AddDynamicArguments(defunTree.Grammar, defunTree.Symbol, Enumerable.Range(0, nArgs)); 213 } 214 // in existing branches with smaller index allow invoke of current function 201 215 int argIndex = root.SubTrees.IndexOf(newTree); 202 // allow invokes of ADFs with higher index203 for (int i = argIndex + 1; i < root.SubTrees.Count; i++) {204 var otherDefunNode = root.SubTrees[i] as DefunTreeNode;205 if (otherDefunNode != null) {206 var allowedParents = from sym in defunTree.Grammar.Symbols207 where defunTree.Grammar.IsAllowedChild(defunTree.Symbol, sym, 0)208 select sym;209 var allowedChildren = allowedParents;210 AddDynamicSymbol(defunTree.Grammar, allowedParents, allowedChildren, otherDefunNode.FunctionName, otherDefunNode.NumberOfArguments);211 }212 }213 // make the ADF available as symbol for other branches (with smaller index to prevent recursions)214 216 for (int i = 0; i < argIndex; i++) { 215 217 // if not dummy node 216 218 if (root.SubTrees[i].Symbol != null) { 217 var topLevelGrammar = root.SubTrees[i].Grammar; 218 var allowedParents = from sym in root.SubTrees[i].Grammar.Symbols 219 where root.SubTrees[i].Grammar.IsAllowedChild(root.SubTrees[i].Symbol, sym, 0) 220 select sym; 221 var allowedChildren = allowedParents; 222 223 AddDynamicSymbol(topLevelGrammar, allowedParents, allowedChildren, functionName, nArgs); 219 var existingBranch = root.SubTrees[i]; 220 GrammarModifier.AddDynamicSymbol(existingBranch.Grammar, existingBranch.Symbol, functionName, nArgs); 224 221 } 225 222 } 226 }227 }228 229 private static void AddDynamicSymbol(ISymbolicExpressionGrammar grammar, IEnumerable<Symbol> allowedParents, IEnumerable<Symbol> allowedChildren, string symbolName, int nArgs) {230 var invokeSym = new InvokeFunction(symbolName);231 grammar.AddSymbol(invokeSym);232 grammar.SetMinSubtreeCount(invokeSym, nArgs);233 grammar.SetMaxSubtreeCount(invokeSym, nArgs);234 foreach (var parent in allowedParents) {235 for (int arg = 0; arg < grammar.GetMaxSubtreeCount(parent); arg++) {236 grammar.SetAllowedChild(parent, invokeSym, arg);237 }238 }239 foreach (var child in allowedChildren) {240 for (int arg = 0; arg < grammar.GetMaxSubtreeCount(invokeSym); arg++) {241 grammar.SetAllowedChild(invokeSym, child, arg);242 }243 }244 }245 246 private static void AddDynamicArguments(ISymbolicExpressionGrammar grammar, int nArgs) {247 for (int argIndex = 0; argIndex < nArgs; argIndex++) {248 var argNode = new Argument(argIndex);249 grammar.AddSymbol(argNode);250 grammar.SetMinSubtreeCount(argNode, 0);251 grammar.SetMaxSubtreeCount(argNode, 0);252 // allow the argument as child of any other symbol253 foreach (var symb in grammar.Symbols)254 for (int i = 0; i < grammar.GetMaxSubtreeCount(symb); i++) {255 grammar.SetAllowedChild(symb, argNode, i);256 }257 223 } 258 224 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/DefaultSymbolicExpressionGrammar.cs
r3338 r3360 81 81 82 82 public void RemoveSymbol(Symbol symbol) { 83 foreach (var parent in Symbols) { 84 for (int i = 0; i < GetMaxSubtreeCount(parent); i++) 85 if (IsAllowedChild(parent, symbol, i)) 86 allowedChildSymbols[parent.Name][i].Remove(symbol.Name); 87 } 83 88 allSymbols.RemoveWhere(s => s.Name == symbol.Name); 84 89 minSubTreeCount.Remove(symbol.Name); … … 208 213 clone.minSubTreeCount = new Dictionary<string, int>(minSubTreeCount); 209 214 clone.startSymbol = startSymbol; 210 clone.allowedChildSymbols = new Dictionary<string, List<HashSet<string>>>(allowedChildSymbols); 215 clone.allowedChildSymbols = new Dictionary<string, List<HashSet<string>>>(); 216 foreach (var entry in allowedChildSymbols) { 217 clone.allowedChildSymbols[entry.Key] = new List<HashSet<string>>(); 218 foreach (var set in entry.Value) { 219 clone.allowedChildSymbols[entry.Key].Add(new HashSet<string>(set)); 220 } 221 } 211 222 clone.allSymbols = new HashSet<Symbol>(allSymbols); 212 223 return clone; -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/GlobalSymbolicExpressionGrammar.cs
r3338 r3360 82 82 } 83 83 84 private void Reset() {84 private new void Reset() { 85 85 base.Reset(); 86 86 Initialize(); -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.3.csproj
r3338 r3360 85 85 <Compile Include="ArchitectureAlteringOperators\ArgumentCreater.cs" /> 86 86 <Compile Include="ArchitectureAlteringOperators\ArgumentDeleter.cs" /> 87 <Compile Include="ArchitectureAlteringOperators\ArgumentDuplicater.cs" /> 88 <Compile Include="ArchitectureAlteringOperators\GrammarModifier.cs" /> 89 <Compile Include="ArchitectureAlteringOperators\RandomArchitectureAlteringOperator.cs" /> 90 <Compile Include="ArchitectureAlteringOperators\SubroutineCreater.cs"> 91 <SubType>Code</SubType> 92 </Compile> 93 <Compile Include="ArchitectureAlteringOperators\SubroutineDeleter.cs" /> 94 <Compile Include="ArchitectureAlteringOperators\SubroutineDuplicater.cs" /> 95 <Compile Include="SymbolicExpressionTreeTopLevelNode.cs" /> 87 96 <Compile Include="Crossovers\SubtreeCrossover.cs"> 88 97 <SubType>Code</SubType> -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTree.cs
r3338 r3360 77 77 } 78 78 79 public SymbolicExpressionTreeNode GetTopLevelBranchOf(SymbolicExpressionTreeNode node) {80 foreach (var branch in root.SubTrees) {81 if (branch.IterateNodesPrefix().Contains(node)) return branch;82 }83 throw new ArgumentException("Node was not found in tree.");84 }85 86 79 public override IDeepCloneable Clone(Cloner cloner) { 87 80 SymbolicExpressionTree clone = new SymbolicExpressionTree(); … … 91 84 return clone; 92 85 } 93 94 public bool IsValidExpression() {95 if (root.Symbol != root.Grammar.StartSymbol) return false;96 foreach (var subtree in root.SubTrees)97 if (subtree.Grammar == root.Grammar) return false;98 return root.IsValidTree();99 }100 86 } 101 87 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeNode.cs
r3338 r3360 128 128 yield return this; 129 129 } 130 //public int GetMinExpressionLength() {131 // return Grammar.GetMinExpressionLength(Symbol);132 //}133 //public int GetMaxExpressionLength() {134 // return Grammar.GetMaxExpressionLength(Symbol);135 //}136 //public int GetMinExpressionDepth() {137 // return Grammar.GetMinExpressionDepth(Symbol);138 //}139 130 public IEnumerable<Symbol> GetAllowedSymbols(int argumentIndex) { 140 131 return Grammar.Symbols.Where(s => Grammar.IsAllowedChild(Symbol, s, argumentIndex)); … … 146 137 return Grammar.GetMaxSubtreeCount(Symbol); 147 138 } 148 //public int GetMaxExpressionLength(Symbol s) {149 // return Grammar.GetMaxExpressionLength(s);150 //}151 //public int GetMinExpressionLength(Symbol s) {152 // return Grammar.GetMinExpressionLength(s);153 //}154 //public int GetMinExpressionDepth(Symbol s) {155 // return Grammar.GetMinExpressionDepth(s);156 //}157 139 158 140 #region ICloneable Members … … 165 147 166 148 167 public bool IsValidTree() {168 var matchingSymbol = (from symb in Grammar.Symbols169 where symb.Name == Symbol.Name170 select symb).SingleOrDefault();171 149 172 if (SubTrees.Count < Grammar.GetMinSubtreeCount(matchingSymbol)) return false;173 else if (SubTrees.Count > Grammar.GetMaxSubtreeCount(matchingSymbol)) return false;174 else for (int i = 0; i < SubTrees.Count; i++) {175 if (!GetAllowedSymbols(i).Select(x => x.Name).Contains(SubTrees[i].Symbol.Name)) return false;176 if (!SubTrees[i].IsValidTree()) return false;177 }178 return true;179 }180 150 } 181 151 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/DefunTreeNode.cs
r3338 r3360 25 25 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols { 26 26 [StorableClass] 27 public sealed class DefunTreeNode : SymbolicExpressionTree Node {27 public sealed class DefunTreeNode : SymbolicExpressionTreeTopLevelNode { 28 28 private int numberOfArguments; 29 29 [Storable] -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/InvokeFunctionTreeNode.cs
r3338 r3360 27 27 public new InvokeFunction Symbol { 28 28 get { return (InvokeFunction)base.Symbol; } 29 set { 30 if (value == null) throw new ArgumentNullException(); 31 if (!(value is InvokeFunction)) throw new ArgumentNullException(); 32 base.Symbol = value; 33 } 29 34 } 30 35 -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/StartSymbolTreeNode.cs
r3338 r3360 24 24 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols { 25 25 [StorableClass] 26 public sealed class StartSymbolTreeNode : SymbolicExpressionTree Node {26 public sealed class StartSymbolTreeNode : SymbolicExpressionTreeTopLevelNode { 27 27 // copy constructor 28 28 private StartSymbolTreeNode(StartSymbolTreeNode original) -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests
- Property svn:ignore
-
old new 1 1 bin 2 2 obj 3 *.user
-
- Property svn:ignore
-
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/ArgumentCreaterTest.cs
r3338 r3360 1 using System; 1 #region License Information 2 /* HeuristicLab 3 * Copyright (C) 2002-2010 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 22 using System; 2 23 using System.Text; 3 24 using System.Collections.Generic; … … 34 55 var trees = new List<SymbolicExpressionTree>(); 35 56 var grammar = Grammars.CreateArithmeticAndAdfGrammar(); 36 var random = new MersenneTwister(); 57 var random = new MersenneTwister(31415); 58 int failedEvents = 0; 37 59 for (int i = 0; i < POPULATION_SIZE; i++) { 38 60 var tree = ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3); 39 ArgumentCreater.CreateNewArgument(random, tree, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3); 40 Assert.IsTrue(tree.IsValidExpression()); 61 if (!ArgumentCreater.CreateNewArgument(random, tree, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3)) 62 failedEvents++; 63 Util.IsValid(tree); 41 64 trees.Add(tree); 42 65 } 43 66 Assert.Inconclusive("ArgumentCreator: " + Environment.NewLine + 44 Util.GetSizeDistributionString(trees, 105, 5) + Environment.NewLine + 67 "Failed events: " + failedEvents / (double)POPULATION_SIZE * 100 + " %" + Environment.NewLine + 68 Util.GetSizeDistributionString(trees, 200, 20) + Environment.NewLine + 45 69 Util.GetFunctionDistributionString(trees) + Environment.NewLine + 46 70 Util.GetNumberOfSubTreesDistributionString(trees) + Environment.NewLine + -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/ArgumentDeleterTest.cs
r3338 r3360 1 using System; 1 #region License Information 2 /* HeuristicLab 3 * Copyright (C) 2002-2010 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 22 using System; 2 23 using System.Text; 3 24 using System.Collections.Generic; … … 34 55 var trees = new List<SymbolicExpressionTree>(); 35 56 var grammar = Grammars.CreateArithmeticAndAdfGrammar(); 36 var random = new MersenneTwister(); 57 var random = new MersenneTwister(31415); 58 int failedEvents = 0; 37 59 for (int i = 0; i < POPULATION_SIZE; i++) { 38 60 var tree = ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3); 39 ArgumentDeleter.DeleteArgument(random, tree, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3); 40 Assert.IsTrue(tree.IsValidExpression()); 61 if (!ArgumentDeleter.DeleteArgument(random, tree, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3)) 62 failedEvents++; 63 Util.IsValid(tree); 41 64 trees.Add(tree); 42 65 } 43 66 Assert.Inconclusive("ArgumentDeleter: " + Environment.NewLine + 67 "Failed events: " + failedEvents / (double)POPULATION_SIZE * 100 + " %" + Environment.NewLine + 44 68 Util.GetSizeDistributionString(trees, 105, 5) + Environment.NewLine + 45 69 Util.GetFunctionDistributionString(trees) + Environment.NewLine + -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/Grammars.cs
r3338 r3360 1 using System; 1 #region License Information 2 /* HeuristicLab 3 * Copyright (C) 2002-2010 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 22 using System; 2 23 using System.Text; 3 24 using System.Collections.Generic; … … 74 95 return g; 75 96 } 97 98 public static void HasValidAdfGrammars(SymbolicExpressionTree tree) { 99 Assert.AreEqual(tree.Root.Grammar.Symbols.Count(), 8); 100 Assert.AreEqual(tree.Root.GetAllowedSymbols(0).Count(), 1); // only the start symbol is allowed 101 // we allow 3 ADF branches 102 Assert.AreEqual(tree.Root.GetAllowedSymbols(1).Count(), 1); // only the defun branch is allowed 103 Assert.AreEqual(tree.Root.GetAllowedSymbols(2).Count(), 1); // only the defun symbol is allowed 104 Assert.AreEqual(tree.Root.GetAllowedSymbols(3).Count(), 1); // only the defun symbol is allowed 105 foreach (var subtree in tree.Root.SubTrees) { 106 // check consistency of each sub-tree grammar independently 107 var allowedSymbols = subtree.GetAllowedSymbols(0); 108 int numberOfAllowedSymbols = allowedSymbols.Count(); 109 foreach (var parent in allowedSymbols) { 110 for (int argIndex = 0; argIndex < subtree.Grammar.GetMaxSubtreeCount(parent); argIndex++) { 111 var allowedChildren = from child in subtree.Grammar.Symbols 112 where subtree.Grammar.IsAllowedChild(parent, child, argIndex) 113 select child; 114 Assert.AreEqual(numberOfAllowedSymbols, allowedChildren.Count()); 115 } 116 } 117 } 118 } 119 76 120 } 77 121 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.3.Tests.csproj
r3338 r3360 41 41 <Compile Include="ArgumentCreaterTest.cs" /> 42 42 <Compile Include="ArgumentDeleterTest.cs" /> 43 <Compile Include="ArgumentDuplicaterTest.cs" /> 44 <Compile Include="AllArchitectureAlteringOperatorsTest.cs" /> 45 <Compile Include="SubroutineDeleterTest.cs" /> 46 <Compile Include="SubroutineDuplicaterTest.cs" /> 43 47 <Compile Include="Grammars.cs" /> 48 <Compile Include="SubroutineCreaterTest.cs"> 49 <SubType>Code</SubType> 50 </Compile> 44 51 <Compile Include="SubtreeCrossoverTest.cs"> 45 52 <SubType>Code</SubType> … … 50 57 </ItemGroup> 51 58 <ItemGroup> 59 <ProjectReference Include="..\..\..\HeuristicLab.Collections\3.3\HeuristicLab.Collections-3.3.csproj"> 60 <Project>{958B43BC-CC5C-4FA2-8628-2B3B01D890B6}</Project> 61 <Name>HeuristicLab.Collections-3.3</Name> 62 </ProjectReference> 52 63 <ProjectReference Include="..\..\..\HeuristicLab.Core\3.3\HeuristicLab.Core-3.3.csproj"> 53 64 <Project>{C36BD924-A541-4A00-AFA8-41701378DDC5}</Project> 54 65 <Name>HeuristicLab.Core-3.3</Name> 66 </ProjectReference> 67 <ProjectReference Include="..\..\..\HeuristicLab.Data\3.3\HeuristicLab.Data-3.3.csproj"> 68 <Project>{BBAB9DF5-5EF3-4BA8-ADE9-B36E82114937}</Project> 69 <Name>HeuristicLab.Data-3.3</Name> 55 70 </ProjectReference> 56 71 <ProjectReference Include="..\..\..\HeuristicLab.Operators\3.3\HeuristicLab.Operators-3.3.csproj"> -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/ProbabilisticTreeCreaterTest.cs
r3338 r3360 1 using System; 1 #region License Information 2 /* HeuristicLab 3 * Copyright (C) 2002-2010 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 22 using System; 2 23 using System.Text; 3 24 using System.Collections.Generic; … … 38 59 } 39 60 40 foreach (var tree in randomTrees) 41 Assert.IsTrue(tree.IsValidExpression()); 61 foreach (var tree in randomTrees) { 62 Util.IsValid(tree); 63 } 42 64 Assert.Inconclusive("ProbabilisticTreeCreator: " + Environment.NewLine + 43 65 Util.GetSizeDistributionString(randomTrees, 105, 5) + Environment.NewLine + … … 55 77 var random = new MersenneTwister(); 56 78 for (int i = 0; i < POPULATION_SIZE; i++) { 57 randomTrees.Add(ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3)); 79 var tree = ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3); 80 Grammars.HasValidAdfGrammars(tree); 81 Util.IsValid(tree); 82 randomTrees.Add(tree); 58 83 } 59 foreach (var tree in randomTrees)60 Assert.IsTrue(tree.IsValidExpression());61 84 Assert.Inconclusive("ProbabilisticTreeCreator: " + Environment.NewLine + 62 85 Util.GetSizeDistributionString(randomTrees, 105, 5) + Environment.NewLine + -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/SubroutineCreaterTest.cs
r3338 r3360 1 using System; 1 #region License Information 2 /* HeuristicLab 3 * Copyright (C) 2002-2010 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 22 using System; 2 23 using System.Text; 3 24 using System.Collections.Generic; … … 8 29 using System.Diagnostics; 9 30 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureAlteringOperators; 10 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols;11 31 12 32 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding_3._3.Tests { 13 33 [TestClass] 14 34 public class SubroutineCreaterTest { 15 private static ISymbolicExpressionGrammar grammar; 16 private static List<SymbolicExpressionTree> subroutineTrees; 17 private static int failedEvents; 18 35 private const int POPULATION_SIZE = 1000; 36 private const int MAX_TREE_SIZE = 100; 37 private const int MAX_TREE_HEIGHT = 10; 19 38 private TestContext testContextInstance; 20 39 … … 32 51 } 33 52 34 [ ClassInitialize()]35 public static void SubroutineCreaterTestInitialize(TestContext testContext) {36 var randomTrees = new List<SymbolicExpressionTree>();37 subroutineTrees = new List<SymbolicExpressionTree>();38 int populationSize = 1000;39 failedEvents = 0;40 grammar = Grammars.CreateArithmeticAndAdfGrammar();41 var random = new MersenneTwister();42 for (int i = 0; i < populationSize; i++) {43 var randTree = ProbabilisticTreeCreator.Create(random, grammar, 100, 10);44 // PTC create is tested separately45 randomTrees.Add(randTree);53 [TestMethod()] 54 public void SubroutineCreaterDistributionsTest() { 55 var trees = new List<SymbolicExpressionTree>(); 56 var grammar = Grammars.CreateArithmeticAndAdfGrammar(); 57 var random = new MersenneTwister(31415); 58 int failedEvents = 0; 59 for (int i = 0; i < POPULATION_SIZE; i++) { 60 var tree = ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3); 61 if (!SubroutineCreater.CreateSubroutine(random, tree, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3)) 62 failedEvents++; 63 Util.IsValid(tree); 64 trees.Add(tree); 46 65 } 47 var newPopulation = new List<SymbolicExpressionTree>(); 48 for (int i = 0; i < populationSize; i++) { 49 var par0 = (SymbolicExpressionTree)randomTrees[random.Next(populationSize)].Clone(); 50 bool success = SubroutineCreater.CreateSubroutine(random, par0, grammar, 100, 10, 3, 3); 51 if (!success) failedEvents++; 52 subroutineTrees.Add(par0); 53 } 54 } 55 56 57 [TestMethod()] 58 public void SubroutineCreaterCreateTest() { 59 foreach (var tree in subroutineTrees) 60 Assert.IsTrue(grammar.IsValidExpression(tree)); 61 } 62 63 [TestMethod()] 64 public void SubroutineCreaterSizeDistributionTest() { 65 Assert.Inconclusive("SubroutineCreater: " + Util.GetSizeDistributionString(subroutineTrees, 105, 5)); 66 } 67 68 [TestMethod()] 69 public void SubroutineCreaterFunctionDistributionTest() { 70 Assert.Inconclusive("SubroutineCreater: " + Util.GetFunctionDistributionString(subroutineTrees)); 71 } 72 73 [TestMethod()] 74 public void SubroutineCreaterNumberOfSubTreesDistributionTest() { 75 Assert.Inconclusive("SubroutineCreater: " + Util.GetNumberOfSubTreesDistributionString(subroutineTrees)); 76 } 77 78 79 [TestMethod()] 80 public void SubroutineCreaterTerminalDistributionTest() { 81 Assert.Inconclusive("SubroutineCreater: " + Util.GetTerminalDistributionString(subroutineTrees)); 66 Assert.Inconclusive("SubroutineCreator: " + Environment.NewLine + 67 "Failed events: " + failedEvents / (double)POPULATION_SIZE * 100 + " %" + Environment.NewLine + 68 Util.GetSizeDistributionString(trees, 105, 5) + Environment.NewLine + 69 Util.GetFunctionDistributionString(trees) + Environment.NewLine + 70 Util.GetNumberOfSubTreesDistributionString(trees) + Environment.NewLine + 71 Util.GetTerminalDistributionString(trees) + Environment.NewLine 72 ); 82 73 } 83 74 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/SubtreeCrossoverTest.cs
r3338 r3360 1 using System; 1 #region License Information 2 /* HeuristicLab 3 * Copyright (C) 2002-2010 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 22 using System; 2 23 using System.Text; 3 24 using System.Collections.Generic; … … 11 32 [TestClass] 12 33 public class SubtreeCrossoverTest { 13 private static ISymbolicExpressionGrammar grammar; 14 private static List<SymbolicExpressionTree> crossoverTrees; 15 private static double msPerCrossoverEvent; 16 34 private const int POPULATION_SIZE = 1000; 17 35 private TestContext testContextInstance; 18 36 … … 30 48 } 31 49 32 [ClassInitialize()] 33 public static void SubtreeCrossoverTestInitialize(TestContext testContext) { 34 crossoverTrees = new List<SymbolicExpressionTree>(); 35 int populationSize = 1000; 50 [TestMethod()] 51 public void SubtreeCrossoverDistributionsTest() { 36 52 int generations = 5; 53 var trees = new List<SymbolicExpressionTree>(); 54 var grammar = Grammars.CreateArithmeticAndAdfGrammar(); 55 var random = new MersenneTwister(); 37 56 int failedEvents = 0; 38 grammar = Grammars.CreateArithmeticAndAdfGrammar(); 39 var random = new MersenneTwister(); 40 for (int i = 0; i < populationSize; i++) { 41 crossoverTrees.Add(ProbabilisticTreeCreator.Create(random, grammar, 100, 10, 3, 3)); 57 List<SymbolicExpressionTree> crossoverTrees; 58 double msPerCrossoverEvent; 59 60 for (int i = 0; i < POPULATION_SIZE; i++) { 61 trees.Add(ProbabilisticTreeCreator.Create(random, grammar, 100, 10, 3, 3)); 42 62 } 43 63 Stopwatch stopwatch = new Stopwatch(); … … 45 65 for (int gCount = 0; gCount < generations; gCount++) { 46 66 var newPopulation = new List<SymbolicExpressionTree>(); 47 for (int i = 0; i < populationSize; i++) {48 var par0 = (SymbolicExpressionTree) crossoverTrees[random.Next(populationSize)].Clone();49 var par1 = (SymbolicExpressionTree) crossoverTrees[random.Next(populationSize)].Clone();67 for (int i = 0; i < POPULATION_SIZE; i++) { 68 var par0 = (SymbolicExpressionTree)trees.SelectRandom(random).Clone(); 69 var par1 = (SymbolicExpressionTree)trees.SelectRandom(random).Clone(); 50 70 bool success; 51 71 newPopulation.Add(SubtreeCrossover.Cross(random, par0, par1, 0.9, 100, 10, out success)); … … 55 75 } 56 76 stopwatch.Stop(); 57 foreach (var tree in crossoverTrees) 58 Assert.IsTrue(tree.IsValidExpression()); 59 msPerCrossoverEvent = stopwatch.ElapsedMilliseconds / (double)populationSize / (double)generations; 60 } 77 foreach (var tree in trees) 78 Util.IsValid(tree); 61 79 80 msPerCrossoverEvent = stopwatch.ElapsedMilliseconds / (double)POPULATION_SIZE / (double)generations; 62 81 63 64 [TestMethod()] 65 public void SubtreeCrossoverSpeed() { 66 67 Assert.Inconclusive(msPerCrossoverEvent + " ms per crossover event (~" + 68 Math.Round(1000.0 / (msPerCrossoverEvent)) + "crossovers / s)"); 69 } 70 71 [TestMethod()] 72 public void SubtreeCrossoverSizeDistributions() { 73 Assert.Inconclusive("SubtreeCrossover: " + Util.GetSizeDistributionString(crossoverTrees, 105, 5)); 74 } 75 76 [TestMethod()] 77 public void SubtreeCrossoverFunctionDistributionTest() { 78 Assert.Inconclusive("SubtreeCrossover: " + Util.GetFunctionDistributionString(crossoverTrees)); 79 } 80 81 [TestMethod()] 82 public void SubtreeCrossoverNumberOfSubTreesDistributionTest() { 83 Assert.Inconclusive("SubtreeCrossover: " + Util.GetNumberOfSubTreesDistributionString(crossoverTrees)); 84 } 85 86 87 [TestMethod()] 88 public void SubtreeCrossoverTerminalDistributionTest() { 89 Assert.Inconclusive("SubtreeCrossover: " + Util.GetTerminalDistributionString(crossoverTrees)); 82 Assert.Inconclusive("SubtreeCrossover: " + Environment.NewLine + 83 "Failed events: " + failedEvents / (double)POPULATION_SIZE * 100 + " %" + Environment.NewLine + 84 msPerCrossoverEvent + " ms per crossover event (~" + Math.Round(1000.0 / (msPerCrossoverEvent)) + "crossovers / s)" + Environment.NewLine + 85 Util.GetSizeDistributionString(trees, 105, 5) + Environment.NewLine + 86 Util.GetFunctionDistributionString(trees) + Environment.NewLine + 87 Util.GetNumberOfSubTreesDistributionString(trees) + Environment.NewLine + 88 Util.GetTerminalDistributionString(trees) + Environment.NewLine 89 ); 90 90 } 91 91 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/Util.cs
r3338 r3360 1 using System; 1 #region License Information 2 /* HeuristicLab 3 * Copyright (C) 2002-2010 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 22 using System; 2 23 using System.Text; 3 24 using System.Collections.Generic; … … 13 34 int[] histogram = new int[maxTreeSize / binSize]; 14 35 for (int i = 0; i < trees.Count; i++) { 15 histogram[trees[i].Size / binSize]++; 36 int binIndex = Math.Min(histogram.Length - 1, trees[i].Size / binSize); 37 histogram[binIndex]++; 16 38 } 17 39 StringBuilder strBuilder = new StringBuilder(); 18 for (int i = 0; i < histogram.Length ; i++) {40 for (int i = 0; i < histogram.Length - 1; i++) { 19 41 strBuilder.Append(Environment.NewLine); 20 42 strBuilder.Append("< "); strBuilder.Append((i + 1) * binSize); 21 43 strBuilder.Append(": "); strBuilder.AppendFormat("{0:#0.00%}", histogram[i] / (double)trees.Count); 22 44 } 45 strBuilder.Append(Environment.NewLine); 46 strBuilder.Append(">= "); strBuilder.Append(histogram.Length * binSize); 47 strBuilder.Append(": "); strBuilder.AppendFormat("{0:#0.00%}", histogram[histogram.Length - 1] / (double)trees.Count); 48 23 49 return "Size distribution: " + strBuilder; 24 50 } … … 88 114 return "Terminal distribution: " + strBuilder; 89 115 } 116 117 public static void IsValid(SymbolicExpressionTree tree) { 118 Grammars.HasValidAdfGrammars(tree); 119 Assert.AreEqual(tree.Root.Symbol, tree.Root.Grammar.StartSymbol); 120 foreach (var subtree in tree.Root.SubTrees) 121 Assert.AreNotSame(subtree.Grammar, tree.Root.Grammar); 122 IsValid(tree.Root); 123 } 124 125 public static void IsValid(SymbolicExpressionTreeNode treeNode) { 126 var matchingSymbol = (from symb in treeNode.Grammar.Symbols 127 where symb.Name == treeNode.Symbol.Name 128 select symb).SingleOrDefault(); 129 Assert.IsTrue(treeNode.SubTrees.Count >= treeNode.Grammar.GetMinSubtreeCount(matchingSymbol)); 130 Assert.IsTrue(treeNode.SubTrees.Count <= treeNode.Grammar.GetMaxSubtreeCount(matchingSymbol)); 131 for (int i = 0; i < treeNode.SubTrees.Count; i++) { 132 Assert.IsTrue(treeNode.GetAllowedSymbols(i).Select(x => x.Name).Contains(treeNode.SubTrees[i].Symbol.Name)); 133 IsValid(treeNode.SubTrees[i]); 134 } 135 } 90 136 } 91 137 }
Note: See TracChangeset
for help on using the changeset viewer.