Changeset 3369 for trunk/sources
- Timestamp:
- 04/16/10 12:12:29 (14 years ago)
- Location:
- trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3
- Files:
-
- 19 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/SubroutineDeleter.cs
r3360 r3369 68 68 69 69 // remove references to deleted function 70 foreach (var subtree in symbolicExpressionTree.Root.SubTrees ) {70 foreach (var subtree in symbolicExpressionTree.Root.SubTrees.OfType<SymbolicExpressionTreeTopLevelNode>()) { 71 71 var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>() 72 72 where symb.FunctionName == selectedDefunBranch.FunctionName … … 99 99 int minPossibleHeight = invocationCutPoint.Parent.Grammar.GetMinExpressionDepth(selectedSymbol); 100 100 int maxHeight = Math.Max(minPossibleHeight, invocationCutPoint.ReplacedChild.GetHeight()); 101 102 replacementTree = ProbabilisticTreeCreator.PTC2(random, invocationCutPoint.Parent.Grammar, selectedSymbol, maxSize, maxHeight, 0, 0); 101 replacementTree = selectedSymbol.CreateTreeNode(); 103 102 invocationCutPoint.Parent.RemoveSubTree(invocationCutPoint.ReplacedChildIndex); 104 103 invocationCutPoint.Parent.InsertSubTree(invocationCutPoint.ReplacedChildIndex, replacementTree); 104 105 ProbabilisticTreeCreator.PTC2(random, replacementTree, maxSize, maxHeight, 0, 0); 105 106 106 107 invocationCutPoint = (from node in symbolicExpressionTree.IterateNodesPrefix() -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/SubroutineDuplicater.cs
r3360 r3369 72 72 duplicatedDefunBranch.Grammar = (ISymbolicExpressionGrammar)selectedBranch.Grammar.Clone(); 73 73 // add an invoke symbol for each branch that is allowed to invoke the original function 74 foreach (var subtree in symbolicExpressionTree.Root.SubTrees ) {74 foreach (var subtree in symbolicExpressionTree.Root.SubTrees.OfType<SymbolicExpressionTreeTopLevelNode>()) { 75 75 var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>() 76 76 where symb.FunctionName == selectedBranch.FunctionName … … 79 79 GrammarModifier.AddDynamicSymbol(subtree.Grammar, subtree.Symbol, duplicatedDefunBranch.FunctionName, duplicatedDefunBranch.NumberOfArguments); 80 80 } 81 } 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; 81 // in the current subtree: 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 subtree.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 subtree.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 } 93 94 } 94 95 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Creators/ProbabilisticTreeCreator.cs
r3360 r3369 35 35 [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed size")] 36 36 public class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator { 37 private const int MAX_TRIES = 100; 37 38 38 39 public ProbabilisticTreeCreator() … … 53 54 ) { 54 55 SymbolicExpressionTree tree = new SymbolicExpressionTree(); 55 tree.Root = PTC2(random, grammar, grammar.StartSymbol, maxTreeSize, maxTreeHeight, maxFunctionDefinitions, maxFunctionArguments); 56 var rootNode = grammar.StartSymbol.CreateTreeNode(); 57 rootNode.Grammar = grammar; 58 tree.Root = PTC2(random, rootNode, maxTreeSize, maxTreeHeight, maxFunctionDefinitions, maxFunctionArguments); 56 59 return tree; 57 60 } … … 63 66 } 64 67 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 public static SymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionGrammar grammar, Symbol rootSymbol, 68 public static SymbolicExpressionTreeNode PTC2(IRandom random, SymbolicExpressionTreeNode seedNode, 77 69 int maxTreeSize, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) { 78 70 // 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); 97 return root; 98 } 99 100 private static void CreateFullTreeFromSeed(IRandom random, SymbolicExpressionTreeNode root, int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) { 71 int allowedMinSize = seedNode.Grammar.GetMinExpressionLength(seedNode.Symbol); 72 int allowedMaxSize = Math.Min(maxTreeSize, seedNode.Grammar.GetMaxExpressionLength(seedNode.Symbol)); 73 int tries = 0; 74 while (tries++ < MAX_TRIES) { 75 // select a target tree size uniformly in the possible range (as determined by explicit limits and limits of the grammar) 76 int treeSize = random.Next(allowedMinSize, allowedMaxSize + 1); 77 if (treeSize <= 1 || maxDepth <= 1) return seedNode; 78 79 bool success = CreateFullTreeFromSeed(random, seedNode, seedNode.Grammar, treeSize, maxDepth, maxFunctionDefinitions, maxFunctionArguments); 80 81 // if successfull => check constraints and return the tree if everything looks ok 82 if (success && seedNode.GetSize() <= maxTreeSize && seedNode.GetHeight() <= maxDepth) { 83 return seedNode; 84 } else { 85 // clean seedNode 86 while (seedNode.SubTrees.Count > 0) seedNode.RemoveSubTree(0); 87 } 88 // try a different size MAX_TRIES times 89 } 90 throw new ArgumentException("Couldn't create a valid tree with the specified constraints."); 91 } 92 93 private static bool CreateFullTreeFromSeed(IRandom random, SymbolicExpressionTreeNode root, ISymbolicExpressionGrammar globalGrammar, 94 int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) { 95 try { 96 TryCreateFullTreeFromSeed(random, root, globalGrammar, size, maxDepth, maxFunctionDefinitions, maxFunctionArguments); 97 return true; 98 } 99 catch (ArgumentException) { return false; } 100 } 101 102 private static void TryCreateFullTreeFromSeed(IRandom random, SymbolicExpressionTreeNode root, ISymbolicExpressionGrammar globalGrammar, 103 int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) { 101 104 List<TreeExtensionPoint> extensionPoints = new List<TreeExtensionPoint>(); 102 105 int currentSize = 1; 103 int totalListMinSize = root.Grammar.GetMinExpressionLength(root.Symbol) - 1;106 int totalListMinSize = globalGrammar.GetMinExpressionLength(root.Symbol) - 1; 104 107 int actualArity = SampleArity(random, root, size); 105 108 for (int i = 0; i < actualArity; i++) { … … 107 110 var dummy = new SymbolicExpressionTreeNode(); 108 111 root.AddSubTree(dummy); 109 dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone();112 // dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone(); 110 113 extensionPoints.Add(new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 2 }); 111 114 } … … 141 144 var dummy = new SymbolicExpressionTreeNode(); 142 145 newTree.AddSubTree(dummy); 143 if (IsTopLevelBranch(root, dummy))144 dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone();146 //if (IsTopLevelBranch(root, dummy)) 147 // dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone(); 145 148 extensionPoints.Add(new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 }); 146 149 } … … 175 178 var dummy = new SymbolicExpressionTreeNode(); 176 179 tree.AddSubTree(dummy); 177 dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone();180 // dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone(); 178 181 // replace the just inserted dummy by recursive application 179 182 ReplaceWithMinimalTree(random, root, tree, i, maxFunctionDefinitions, maxFunctionArguments); … … 185 188 // also assumes that newTree is already attached to root somewhere 186 189 if (IsTopLevelBranch(root, newTree)) { 187 newTree.Grammar = (ISymbolicExpressionGrammar) newTree.Grammar.Clone();190 newTree.Grammar = (ISymbolicExpressionGrammar)root.Grammar.Clone(); 188 191 189 192 // allow invokes of existing ADFs with higher index … … 225 228 226 229 private static bool IsTopLevelBranch(SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode branch) { 227 return root.SubTrees.IndexOf(branch) > -1; 230 //return root.SubTrees.IndexOf(branch) > -1; 231 return branch is SymbolicExpressionTreeTopLevelNode; 228 232 } 229 233 -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Crossovers/SubtreeCrossover.cs
r3338 r3369 61 61 SymbolicExpressionTreeNode crossoverPoint0; 62 62 int replacedSubtreeIndex; 63 SelectCrossoverPoint(random, parent0, internalCrossoverPointProbability, out crossoverPoint0, out replacedSubtreeIndex);63 SelectCrossoverPoint(random, parent0, internalCrossoverPointProbability, maxTreeSize - 1, maxTreeHeight - 1, out crossoverPoint0, out replacedSubtreeIndex); 64 64 65 65 // calculate the max size and height that the inserted branch can have … … 67 67 int maxInsertedBranchHeight = maxTreeHeight - GetBranchLevel(parent0.Root, crossoverPoint0); 68 68 69 var allowedBranches = from branch in parent1.Root.IterateNodesPrefix() 70 where branch.GetSize() < maxInsertedBranchSize 71 where branch.GetHeight() < maxInsertedBranchHeight 72 // where crossoverPoint0.GetAllowedSymbols(replacedSubtreeIndex).Contains(branch.Symbol) 73 where IsMatchingPointType(crossoverPoint0, replacedSubtreeIndex, branch) 74 select branch; 69 var allowedBranches = (from branch in parent1.Root.IterateNodesPrefix() 70 where branch.GetSize() < maxInsertedBranchSize 71 where branch.GetHeight() < maxInsertedBranchHeight 72 where IsMatchingPointType(crossoverPoint0, replacedSubtreeIndex, branch) 73 select branch).ToList(); 75 74 76 75 if (allowedBranches.Count() == 0) { … … 90 89 91 90 private static bool IsMatchingPointType(SymbolicExpressionTreeNode parent, int replacedSubtreeIndex, SymbolicExpressionTreeNode branch) { 92 // cannot compare dynamic symbols by reference because new instances of Invoke/Argument are created on demand 93 // instead we must check equality by names and number of arguments 94 var branchSymbols = (from node in branch.IterateNodesPrefix() 95 select new { FunctionName = node.Symbol.Name, SubtreeCount = node.SubTrees.Count }).Distinct(); 91 // check point type for the whole branch 92 foreach (var node in branch.IterateNodesPostfix()) { 93 if (!parent.Grammar.ContainsSymbol(node.Symbol)) return false; 94 else if (node.SubTrees.Count < parent.Grammar.GetMinSubtreeCount(node.Symbol)) return false; 95 else if (node.SubTrees.Count > parent.Grammar.GetMaxSubtreeCount(node.Symbol)) return false; 96 } 96 97 97 98 // check syntax constraints of direct parent - child relation 98 var matchingSymbolInParentGrammar = (from sym in parent.GetAllowedSymbols(replacedSubtreeIndex) 99 where sym.Name == branch.Symbol.Name 100 select sym).SingleOrDefault(); 101 if (matchingSymbolInParentGrammar == null || 102 branch.SubTrees.Count < parent.Grammar.GetMinSubtreeCount(matchingSymbolInParentGrammar) || 103 branch.SubTrees.Count > parent.Grammar.GetMaxSubtreeCount(matchingSymbolInParentGrammar)) return false; 104 105 // check point type for the whole branch 106 foreach (var branchSymbol in branchSymbols) { 107 matchingSymbolInParentGrammar = (from sym in parent.Grammar.Symbols 108 where sym.Name == branchSymbol.FunctionName 109 select sym).SingleOrDefault(); 110 if (matchingSymbolInParentGrammar == null || 111 branchSymbol.SubtreeCount < parent.Grammar.GetMinSubtreeCount(matchingSymbolInParentGrammar) || 112 branchSymbol.SubtreeCount > parent.Grammar.GetMaxSubtreeCount(matchingSymbolInParentGrammar)) return false; 113 } 99 if (!parent.Grammar.IsAllowedChild(parent.Symbol, branch.Symbol, replacedSubtreeIndex)) return false; 114 100 115 101 return true; 116 102 } 117 103 118 private static void SelectCrossoverPoint(IRandom random, SymbolicExpressionTree parent0, double internalNodeProbability, out SymbolicExpressionTreeNode crossoverPoint, out int subtreeIndex) {104 private static void SelectCrossoverPoint(IRandom random, SymbolicExpressionTree parent0, double internalNodeProbability, int maxBranchSize, int maxBranchHeight, out SymbolicExpressionTreeNode crossoverPoint, out int subtreeIndex) { 119 105 var crossoverPoints = from branch in parent0.Root.IterateNodesPrefix() 120 106 where branch.SubTrees.Count > 0 121 107 where branch != parent0.Root 108 where branch.GetSize() < maxBranchSize 109 where branch.GetHeight() < maxBranchHeight 122 110 from index in Enumerable.Range(0, branch.SubTrees.Count) 123 111 let p = new { CrossoverPoint = branch, SubtreeIndex = index, IsLeaf = branch.SubTrees[index].SubTrees.Count == 0 } … … 151 139 private static SymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<SymbolicExpressionTreeNode> branches, double internalNodeProbability) { 152 140 if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability"); 153 var groupedBranches = from branch in branches154 group branch by branch.SubTrees.Count into g155 select g;141 var groupedBranches = (from branch in branches 142 group branch by branch.SubTrees.Count into g 143 select g).ToList(); 156 144 var allowedInternalBranches = (from g in groupedBranches 157 145 where g.Key > 0 … … 163 151 select leaf).ToList(); 164 152 if (allowedInternalBranches.Count == 0) { 165 return allowedLeafBranches [random.Next(allowedLeafBranches.Count)];153 return allowedLeafBranches.SelectRandom(random); 166 154 } else if (allowedLeafBranches.Count == 0) { 167 return allowedInternalBranches [random.Next(allowedInternalBranches.Count)];155 return allowedInternalBranches.SelectRandom(random); 168 156 } else if (random.NextDouble() < internalNodeProbability) { 169 157 // when leaf and internal nodes are possible then choose either a leaf or internal node with internalNodeProbability 170 return allowedInternalBranches [random.Next(allowedInternalBranches.Count)];158 return allowedInternalBranches.SelectRandom(random); 171 159 } else { 172 return allowedLeafBranches [random.Next(allowedLeafBranches.Count)];160 return allowedLeafBranches.SelectRandom(random); 173 161 } 174 162 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/DefaultSymbolicExpressionGrammar.cs
r3360 r3369 30 30 31 31 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding { 32 /// <summary> 33 /// The default symbolic expression grammar stores symbols and syntactic constraints for symbols. 34 /// Symbols are treated as equvivalent if they have the same name. 35 /// Syntactic constraints limit the number of allowed sub trees for a node with a symbol and which symbols are allowed 36 /// in the sub-trees of a symbol (can be specified for each sub-tree index separately). 37 /// </summary> 32 38 [StorableClass] 33 39 [Item("DefaultSymbolicExpressionGrammar", "Represents a grammar that defines the syntax of symbolic expression trees.")] … … 40 46 private Dictionary<string, List<HashSet<string>>> allowedChildSymbols; 41 47 [Storable] 42 private HashSet<Symbol> allSymbols;48 private Dictionary<string, Symbol> allSymbols; 43 49 44 50 public DefaultSymbolicExpressionGrammar() … … 66 72 maxSubTreeCount = new Dictionary<string, int>(); 67 73 allowedChildSymbols = new Dictionary<string, List<HashSet<string>>>(); 68 allSymbols = new HashSet<Symbol>();74 allSymbols = new Dictionary<string, Symbol>(); 69 75 cachedMinExpressionLength = new Dictionary<string, int>(); 70 76 cachedMaxExpressionLength = new Dictionary<string, int>(); … … 74 80 75 81 public void AddSymbol(Symbol symbol) { 76 if ( allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Symbol " + symbol + " is already defined.");77 allSymbols.Add(symbol );82 if (ContainsSymbol(symbol)) throw new ArgumentException("Symbol " + symbol + " is already defined."); 83 allSymbols.Add(symbol.Name, symbol); 78 84 allowedChildSymbols[symbol.Name] = new List<HashSet<string>>(); 79 85 ClearCaches(); … … 86 92 allowedChildSymbols[parent.Name][i].Remove(symbol.Name); 87 93 } 88 allSymbols.Remove Where(s => s.Name ==symbol.Name);94 allSymbols.Remove(symbol.Name); 89 95 minSubTreeCount.Remove(symbol.Name); 90 96 maxSubTreeCount.Remove(symbol.Name); … … 94 100 95 101 public IEnumerable<Symbol> Symbols { 96 get { return allSymbols.AsEnumerable(); } 102 get { return allSymbols.Values.AsEnumerable(); } 103 } 104 105 public bool ContainsSymbol(Symbol symbol) { 106 return allSymbols.ContainsKey(symbol.Name); 97 107 } 98 108 99 109 public void SetAllowedChild(Symbol parent, Symbol child, int argumentIndex) { 100 if (! allSymbols.Any(s => s.Name == parent.Name)) throw new ArgumentException("Unknown symbol: " + parent, "parent");101 if (! allSymbols.Any(s => s.Name == child.Name)) throw new ArgumentException("Unknown symbol: " + child, "child");110 if (!ContainsSymbol(parent)) throw new ArgumentException("Unknown symbol: " + parent, "parent"); 111 if (!ContainsSymbol(child)) throw new ArgumentException("Unknown symbol: " + child, "child"); 102 112 if (argumentIndex >= GetMaxSubtreeCount(parent)) throw new ArgumentException("Symbol " + parent + " can have only " + GetMaxSubtreeCount(parent) + " subtrees."); 103 113 allowedChildSymbols[parent.Name][argumentIndex].Add(child.Name); … … 106 116 107 117 public bool IsAllowedChild(Symbol parent, Symbol child, int argumentIndex) { 108 if (! allSymbols.Any(s => s.Name == parent.Name)) throw new ArgumentException("Unknown symbol: " + parent, "parent");109 if (! allSymbols.Any(s => s.Name == child.Name)) throw new ArgumentException("Unknown symbol: " + child, "child");118 if (!ContainsSymbol(parent)) throw new ArgumentException("Unknown symbol: " + parent, "parent"); 119 if (!ContainsSymbol(child)) throw new ArgumentException("Unknown symbol: " + child, "child"); 110 120 if (argumentIndex >= GetMaxSubtreeCount(parent)) throw new ArgumentException("Symbol " + parent + " can have only " + GetMaxSubtreeCount(parent) + " subtrees."); 111 if (allowedChildSymbols.ContainsKey(parent.Name)) return allowedChildSymbols[parent.Name][argumentIndex].Contains(child.Name); 112 return false; 121 return allowedChildSymbols[parent.Name][argumentIndex].Contains(child.Name); 113 122 } 114 123 115 124 private Dictionary<string, int> cachedMinExpressionLength; 116 125 public int GetMinExpressionLength(Symbol symbol) { 117 if (! allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);126 if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol); 118 127 if (!cachedMinExpressionLength.ContainsKey(symbol.Name)) { 119 128 cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion 120 129 long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinSubtreeCount(symbol)) 121 let minForSlot = (long)(from s in allSymbols130 let minForSlot = (long)(from s in Symbols 122 131 where IsAllowedChild(symbol, s, argIndex) 123 132 select GetMinExpressionLength(s)).DefaultIfEmpty(0).Min() … … 131 140 private Dictionary<string, int> cachedMaxExpressionLength; 132 141 public int GetMaxExpressionLength(Symbol symbol) { 133 if (! allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);142 if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol); 134 143 if (!cachedMaxExpressionLength.ContainsKey(symbol.Name)) { 135 144 cachedMaxExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion 136 145 long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaxSubtreeCount(symbol)) 137 let maxForSlot = (long)(from s in allSymbols146 let maxForSlot = (long)(from s in Symbols 138 147 where IsAllowedChild(symbol, s, argIndex) 139 148 select GetMaxExpressionLength(s)).DefaultIfEmpty(0).Max() … … 147 156 private Dictionary<string, int> cachedMinExpressionDepth; 148 157 public int GetMinExpressionDepth(Symbol symbol) { 149 if (! allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);158 if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol); 150 159 if (!cachedMinExpressionDepth.ContainsKey(symbol.Name)) { 151 160 cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion 152 161 cachedMinExpressionDepth[symbol.Name] = 1 + (from argIndex in Enumerable.Range(0, GetMinSubtreeCount(symbol)) 153 let minForSlot = (from s in allSymbols162 let minForSlot = (from s in Symbols 154 163 where IsAllowedChild(symbol, s, argIndex) 155 164 select GetMinExpressionDepth(s)).DefaultIfEmpty(0).Min() … … 160 169 161 170 public void SetMaxSubtreeCount(Symbol symbol, int nSubTrees) { 162 if (! allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);171 if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol); 163 172 maxSubTreeCount[symbol.Name] = nSubTrees; 164 173 while (allowedChildSymbols[symbol.Name].Count <= nSubTrees) … … 171 180 172 181 public void SetMinSubtreeCount(Symbol symbol, int nSubTrees) { 173 if (! allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);182 if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol); 174 183 minSubTreeCount[symbol.Name] = nSubTrees; 175 184 ClearCaches(); … … 177 186 178 187 public int GetMinSubtreeCount(Symbol symbol) { 179 if (! allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);188 if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol); 180 189 return minSubTreeCount[symbol.Name]; 181 190 } 182 191 183 192 public int GetMaxSubtreeCount(Symbol symbol) { 184 if (! allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);193 if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol); 185 194 return maxSubTreeCount[symbol.Name]; 186 195 } … … 193 202 cachedMinExpressionDepth.Clear(); 194 203 } 195 196 //private void symbol_ToStringChanged(object sender, EventArgs e) {197 // OnToStringChanged();198 //}199 200 //private bool IsValidExpression(SymbolicExpressionTreeNode root) {201 // if (root.SubTrees.Count < root.GetMinSubtreeCount()) return false;202 // else if (root.SubTrees.Count > root.GetMaxSubtreeCount()) return false;203 // else for (int i = 0; i < root.SubTrees.Count; i++) {204 // if (!root.GetAllowedSymbols(i).Select(x => x.Name).Contains(root.SubTrees[i].Symbol.Name)) return false;205 // if (!IsValidExpression(root.SubTrees[i])) return false;206 // }207 // return true;208 //}209 204 210 205 public override IDeepCloneable Clone(Cloner cloner) { … … 220 215 } 221 216 } 222 clone.allSymbols = new HashSet<Symbol>(allSymbols);217 clone.allSymbols = new Dictionary<string, Symbol>(allSymbols); 223 218 return clone; 224 219 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.3.csproj
r3368 r3369 99 99 <Compile Include="GlobalSymbolicExpressionGrammar.cs" /> 100 100 <Compile Include="EnumerableExtensions.cs" /> 101 <Compile Include="Symbols\StartSymbolTreeNode.cs" />102 101 <Compile Include="DefaultSymbolicExpressionGrammar.cs"> 103 102 <SubType>Code</SubType> -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Interfaces/ISymbolicExpressionGrammar.cs
r3338 r3369 34 34 void RemoveSymbol(Symbol symbol); 35 35 IEnumerable<Symbol> Symbols { get; } 36 bool ContainsSymbol(Symbol symbol); 36 37 void SetAllowedChild(Symbol parent, Symbol child, int argumentIndex); 37 38 bool IsAllowedChild(Symbol parent, Symbol child, int argumentIndex); -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeCrossover.cs
r3338 r3369 81 81 if (!success) FailedCrossoverEvents.Value++; 82 82 83 Debug.Assert(result.Size <= MaxTreeSizeParameter.ActualValue.Value);84 Debug.Assert(result.Height <= MaxTreeHeightParameter.ActualValue.Value);85 // Debug.Assert(grammar.IsValidExpression(result));86 83 ChildParameter.ActualValue = result; 87 84 return base.Apply(); -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeNode.cs
r3360 r3369 37 37 [Storable] 38 38 private Symbol symbol; 39 //[Storable] 40 private SymbolicExpressionTreeNode parent; 39 41 40 42 public SymbolicExpressionTreeNode() { … … 51 53 symbol = original.symbol; 52 54 subTrees = new List<SymbolicExpressionTreeNode>(); 53 grammar = original.grammar;54 55 foreach (var subtree in original.SubTrees) { 55 SubTrees.Add((SymbolicExpressionTreeNode)subtree.Clone());56 AddSubTree((SymbolicExpressionTreeNode)subtree.Clone()); 56 57 } 57 58 } … … 70 71 } 71 72 72 private ISymbolicExpressionGrammar grammar;73 public virtual ISymbolicExpressionGrammar Grammar {74 get { return grammar; }75 set {76 grammar = value; 77 foreach (var subtree in subTrees)78 subtree.Grammar = value;79 }73 internal SymbolicExpressionTreeNode Parent { 74 get { return parent; } 75 set { parent = value; } 76 } 77 78 internal virtual ISymbolicExpressionGrammar Grammar { 79 get { return parent.Grammar; } 80 set { throw new NotSupportedException("Grammar can be set only for SymbolicExpressionTreeTopLevelNodes."); } 80 81 } 81 82 … … 96 97 97 98 public virtual void AddSubTree(SymbolicExpressionTreeNode tree) { 98 SubTrees.Add(tree); 99 //if (tree != null) 100 tree.Grammar = Grammar; 99 subTrees.Add(tree); 100 tree.Parent = this; 101 101 } 102 102 103 103 public virtual void InsertSubTree(int index, SymbolicExpressionTreeNode tree) { 104 SubTrees.Insert(index, tree); 105 //if (tree != null) 106 tree.Grammar = Grammar; 104 subTrees.Insert(index, tree); 105 tree.Parent = this; 107 106 } 108 107 109 108 public virtual void RemoveSubTree(int index) { 110 //if (SubTrees[index] != null) 111 SubTrees[index].Grammar = null; 112 SubTrees.RemoveAt(index); 109 subTrees[index].Parent = null; 110 subTrees.RemoveAt(index); 113 111 } 114 112 -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeTopLevelNode.cs
r3360 r3369 42 42 } 43 43 44 private ISymbolicExpressionGrammar grammar; 45 //internal virtual ISymbolicExpressionGrammar Grammar { 46 // get { return grammar; } 47 // set { 48 // grammar = value; 49 // //foreach (var subtree in subTrees) 50 // // subtree.Grammar = value; 51 // } 52 //} 53 internal override ISymbolicExpressionGrammar Grammar { 54 get { 55 return grammar; 56 } 57 set { 58 grammar = value; 59 } 60 } 61 44 62 // copy constructor 45 63 protected SymbolicExpressionTreeTopLevelNode(SymbolicExpressionTreeTopLevelNode original) 46 64 : base(original) { 47 Grammar = (ISymbolicExpressionGrammar)original.Grammar.Clone();65 grammar = (ISymbolicExpressionGrammar)original.Grammar.Clone(); 48 66 } 49 67 -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/ArgumentTreeNode.cs
r3338 r3369 25 25 [StorableClass] 26 26 public sealed class ArgumentTreeNode : SymbolicExpressionTreeNode { 27 publicnew Argument Symbol {27 internal new Argument Symbol { 28 28 get { return (Argument)base.Symbol; } 29 29 set { -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/DefunTreeNode.cs
r3360 r3369 39 39 } 40 40 41 private new Defun Symbol {42 get { return (Defun)base.Symbol; }43 }44 45 41 // copy constructor 46 42 private DefunTreeNode(DefunTreeNode original) -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/InvokeFunctionTreeNode.cs
r3360 r3369 27 27 public new InvokeFunction Symbol { 28 28 get { return (InvokeFunction)base.Symbol; } 29 set {29 internal set { 30 30 if (value == null) throw new ArgumentNullException(); 31 31 if (!(value is InvokeFunction)) throw new ArgumentNullException(); -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/ProgramRootSymbol.cs
r3294 r3369 31 31 } 32 32 } 33 34 public override SymbolicExpressionTreeNode CreateTreeNode() { 35 return new SymbolicExpressionTreeTopLevelNode(this); 36 } 33 37 } 34 38 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/StartSymbol.cs
r3338 r3369 33 33 34 34 public override SymbolicExpressionTreeNode CreateTreeNode() { 35 return new S tartSymbolTreeNode(this);35 return new SymbolicExpressionTreeTopLevelNode(this); 36 36 } 37 37 } -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/AllArchitectureAlteringOperatorsTest.cs
r3360 r3369 74 74 for (int g = 0; g < N_ITERATIONS; g++) { 75 75 for (int i = 0; i < POPULATION_SIZE; i++) { 76 var selectedTree = (SymbolicExpressionTree)trees.SelectRandom(random).Clone(); 77 var op = combinedAAOperator.Operators.SelectRandom(random); 78 bool success; 79 op.ModifyArchitecture(random, selectedTree, grammar, maxTreeSize, maxTreeHeigth, maxDefuns, maxArgs, out success); 80 if (!success) failedEvents++; 81 Util.IsValid(selectedTree); 82 newTrees.Add(selectedTree); 76 if (random.NextDouble() < 0.5) { 77 // manipulate 78 var selectedTree = (SymbolicExpressionTree)trees.SelectRandom(random).Clone(); 79 var op = combinedAAOperator.Operators.SelectRandom(random); 80 bool success; 81 op.ModifyArchitecture(random, selectedTree, grammar, maxTreeSize, maxTreeHeigth, maxDefuns, maxArgs, out success); 82 if (!success) failedEvents++; 83 Util.IsValid(selectedTree); 84 newTrees.Add(selectedTree); 85 } else { 86 // crossover 87 var par0 = (SymbolicExpressionTree)trees.SelectRandom(random).Clone(); 88 var par1 = (SymbolicExpressionTree)trees.SelectRandom(random).Clone(); 89 bool success; 90 newTrees.Add(SubtreeCrossover.Cross(random, par0, par1, 0.9, 100, 10, out success)); 91 if (!success) failedEvents++; 92 } 83 93 } 84 94 trees = newTrees; -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/Grammars.cs
r3360 r3369 97 97 98 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 allowed101 // we allow 3 ADF branches102 Assert.AreEqual(tree.Root.GetAllowedSymbols(1).Count(), 1); // only the defun branch is allowed103 Assert.AreEqual(tree.Root.GetAllowedSymbols(2).Count(), 1); // only the defun symbol is allowed104 Assert.AreEqual(tree.Root.GetAllowedSymbols(3).Count(), 1); // only the defun symbol is allowed105 foreach (var subtree in tree.Root.SubTrees) {106 // check consistency of each sub-tree grammar independently107 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.Symbols112 where subtree.Grammar.IsAllowedChild(parent, child, argIndex)113 select child;114 Assert.AreEqual(numberOfAllowedSymbols, allowedChildren.Count());115 }116 }117 }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 118 } 119 119 -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/ProbabilisticTreeCreaterTest.cs
r3360 r3369 54 54 var randomTrees = new List<SymbolicExpressionTree>(); 55 55 var grammar = Grammars.CreateSimpleArithmeticGrammar(); 56 var random = new MersenneTwister( );56 var random = new MersenneTwister(31415); 57 57 for (int i = 0; i < POPULATION_SIZE; i++) { 58 58 randomTrees.Add(ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 0, 0)); … … 75 75 var randomTrees = new List<SymbolicExpressionTree>(); 76 76 var grammar = Grammars.CreateArithmeticAndAdfGrammar(); 77 var random = new MersenneTwister( );77 var random = new MersenneTwister(31415); 78 78 for (int i = 0; i < POPULATION_SIZE; i++) { 79 79 var tree = ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3); -
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/Util.cs
r3360 r3369 117 117 public static void IsValid(SymbolicExpressionTree tree) { 118 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);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 122 IsValid(tree.Root); 123 123 } 124 124 125 125 public static void IsValid(SymbolicExpressionTreeNode treeNode) { 126 var matchingSymbol = (from symb in treeNode.Grammar.Symbols127 where symb.Name == treeNode.Symbol.Name128 select symb).SingleOrDefault();129 Assert.IsTrue(treeNode.SubTrees.Count >= treeNode.Grammar.GetMinSubtreeCount(matchingSymbol));130 Assert.IsTrue(treeNode.SubTrees.Count <= treeNode.Grammar.GetMaxSubtreeCount(matchingSymbol));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 131 for (int i = 0; i < treeNode.SubTrees.Count; i++) { 132 132 Assert.IsTrue(treeNode.GetAllowedSymbols(i).Select(x => x.Name).Contains(treeNode.SubTrees[i].Symbol.Name));
Note: See TracChangeset
for help on using the changeset viewer.