Changeset 10228
 Timestamp:
 12/15/13 12:34:33 (6 years ago)
 Location:
 branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/DepthFirstMapper.cs
r10075 r10228 20 20 #endregion 21 21 22 using System; 23 using System.Collections.Generic; 22 24 using HeuristicLab.Common; 23 25 using HeuristicLab.Core; … … 63 65 tree.Root = rootNode; 64 66 65 int genotypeIndex = 0; 66 int currSubtreeCount = 1; 67 //int genotypeIndex = 0; 68 //int currSubtreeCount = 1; 69 //MapDepthFirstRecursively(startNode, genotype, 70 // grammar, genotype.Length, 71 // ref genotypeIndex, ref currSubtreeCount, 72 // new MersenneTwister()); 67 73 68 MapDepthFirstRecursively(startNode, genotype, 69 grammar, genotype.Length, 70 ref genotypeIndex, ref currSubtreeCount); 71 74 MapDepthFirstIteratively(startNode, genotype, grammar, 75 genotype.Length, new MersenneTwister()); 72 76 return tree; 73 77 } … … 85 89 /// <param name="currentNode">current parent node</param> 86 90 /// <param name="genotype">integer vector, which should be mapped to a tree</param> 87 /// <param name="grammar">grammar definitionto determine the allowed child symbols for currentNode </param>91 /// <param name="grammar">grammar to determine the allowed child symbols for currentNode </param> 88 92 /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param> 89 93 /// <param name="genotypeIndex">current index in integer vector</param> … … 94 98 int maxSubtreeCount, 95 99 ref int genotypeIndex, 96 ref int currSubtreeCount) { 100 ref int currSubtreeCount, 101 IRandom random) { 102 103 // TODO: check, if method calls of GetNewChildNode() and GetRandomTerminalNode() don't return null 97 104 if (currSubtreeCount < maxSubtreeCount) { 98 105 99 var newNode = GetNewChildNode(currentNode, genotype, grammar, genotypeIndex );106 var newNode = GetNewChildNode(currentNode, genotype, grammar, genotypeIndex, random); 100 107 101 108 if ((currSubtreeCount + newNode.Symbol.MinimumArity) > maxSubtreeCount) { 102 109 // TODO: maybe check, if there is any node, which fits in the tree yet 103 currentNode.AddSubtree(GetRandomTerminalNode(currentNode, grammar ));110 currentNode.AddSubtree(GetRandomTerminalNode(currentNode, grammar, random)); 104 111 } else { 105 112 currentNode.AddSubtree(newNode); … … 110 117 MapDepthFirstRecursively(newNode, genotype, 111 118 grammar, maxSubtreeCount, 112 ref genotypeIndex, ref currSubtreeCount );119 ref genotypeIndex, ref currSubtreeCount, random); 113 120 } 114 121 } … … 116 123 } else { 117 124 while (currentNode.Symbol.MinimumArity > currentNode.SubtreeCount) { 118 var newNode = GetNewChildNode(currentNode, genotype, grammar, genotypeIndex );125 var newNode = GetNewChildNode(currentNode, genotype, grammar, genotypeIndex, random); 119 126 currentNode.AddSubtree(newNode); 120 127 genotypeIndex++; 121 128 while (newNode.Symbol.MinimumArity > newNode.SubtreeCount) { 122 newNode.AddSubtree(GetRandomTerminalNode(newNode, grammar ));129 newNode.AddSubtree(GetRandomTerminalNode(newNode, grammar, random)); 123 130 } 124 131 } 125 132 } 126 133 } 134 135 136 /// <summary> 137 /// GenotypetoPhenotype mapper (iterative depthfirst approach). 138 /// </summary> 139 /// <param name="startNode">first node of the tree with arity 1</param> 140 /// <param name="genotype">integer vector, which should be mapped to a tree</param> 141 /// <param name="grammar">grammar to determine the allowed child symbols for each node</param> 142 /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param> 143 /// <param name="random">random number generator</param> 144 private void MapDepthFirstIteratively(ISymbolicExpressionTreeNode startNode, 145 IntegerVector genotype, 146 ISymbolicExpressionGrammar grammar, 147 int maxSubtreeCount, IRandom random) { 148 149 Stack<Tuple<ISymbolicExpressionTreeNode, int>> stack 150 = new Stack<Tuple<ISymbolicExpressionTreeNode, int>>(); // tuples of <node, arity> 151 152 int genotypeIndex = 0; 153 int currSubtreeCount = 1; 154 155 stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(startNode, 1)); 156 157 while ((currSubtreeCount < maxSubtreeCount) && (stack.Count > 0)) { 158 159 // get next node from stack and repush it, if this node still has unhandled subtrees ... 160 Tuple<ISymbolicExpressionTreeNode, int> current = stack.Pop(); 161 if (current.Item2 > 1) { 162 stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(current.Item1, current.Item2  1)); 163 } 164 165 var newNode = GetNewChildNode(current.Item1, genotype, grammar, genotypeIndex, random); 166 int arity = SampleArity(random, newNode, maxSubtreeCount  currSubtreeCount); 167 168 if (arity < 0) { 169 current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random)); 170 } else { 171 current.Item1.AddSubtree(newNode); 172 genotypeIndex++; 173 currSubtreeCount += arity; 174 if (arity > 0) { 175 // new node has subtrees so push it onto the stack 176 stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(newNode, arity)); 177 } 178 } 179 } 180 181 // maximum allowed subtree count was already reached, but there are still 182 // incomplete subtrees (nonterminal symbols) in the tree 183 // > fill them with terminal symbols 184 while (stack.Count > 0) { 185 Tuple<ISymbolicExpressionTreeNode, int> current = stack.Pop(); 186 if (current.Item2 > 1) { 187 stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(current.Item1, current.Item2  1)); 188 } 189 current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random)); 190 } 191 } 127 192 } 128 193 } 
branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/GenotypeToPhenotypeMapper.cs
r10075 r10228 23 23 using System.Linq; 24 24 using HeuristicLab.Common; 25 using HeuristicLab.Core; 25 26 using HeuristicLab.Encodings.IntegerVectorEncoding; 26 27 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding; 27 28 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 28 29 using HeuristicLab.Problems.GrammaticalEvolution.Mappers; 29 using HeuristicLab.Random;30 30 31 31 namespace HeuristicLab.Problems.GrammaticalEvolution { … … 48 48 /// </summary> 49 49 /// <param name="parentNode">parent node for which a child node is returned randomly</param> 50 /// <param name="grammar">grammar definition to determine the allowed child symbols for parentNode</param> 51 /// <returns>randomly chosen terminal node with arity 0</returns> 50 /// <param name="grammar">grammar to determine the allowed child symbols for parentNode</param> 51 /// <param name="random">random number generator</param> 52 /// <returns>randomly chosen terminal node with arity 0 or null, if no terminal node exists</returns> 52 53 protected ISymbolicExpressionTreeNode GetRandomTerminalNode(ISymbolicExpressionTreeNode parentNode, 53 ISymbolicExpressionGrammar grammar) { 54 ISymbolicExpressionGrammar grammar, 55 IRandom random) { 54 56 // only select specific symbols, which can be interpreted ... 55 57 var possibleSymbolsList = (from s in grammar.GetAllowedChildSymbols(parentNode.Symbol) … … 58 60 where s.MinimumArity == 0 59 61 select s).ToList(); 60 // TODO: Check, if symbol list is empty (no terminal nodes found)  what should happen? 61 var newNode = possibleSymbolsList.SelectRandom(new MersenneTwister()).CreateTreeNode(); 62 if (newNode.HasLocalParameters) newNode.ResetLocalParameters(new MersenneTwister()); 62 63 // no terminal node exists for the given parent node 64 if (possibleSymbolsList.Count() < 1) return null; 65 66 var newNode = possibleSymbolsList.SelectRandom(random).CreateTreeNode(); 67 if (newNode.HasLocalParameters) newNode.ResetLocalParameters(random); 63 68 return newNode; 64 69 } … … 70 75 /// <param name="parentNode">parent node to find a child node randomly for</param> 71 76 /// <param name="genotype">integer vector, which should be mapped to a tree</param> 72 /// <param name="grammar">grammar definitionused to define the allowed child symbols</param>77 /// <param name="grammar">grammar used to define the allowed child symbols</param> 73 78 /// <param name="genotypeIndex">index in the integer vector; can be greater than vector length</param> 74 /// <returns>randomly chosen child node for parentNode</returns> 79 /// <param name="random">random number generator</param> 80 /// <returns>randomly chosen child node or null, if no child node exits</returns> 75 81 protected ISymbolicExpressionTreeNode GetNewChildNode(ISymbolicExpressionTreeNode parentNode, 76 82 IntegerVector genotype, 77 83 ISymbolicExpressionGrammar grammar, 78 int genotypeIndex) { 84 int genotypeIndex, 85 IRandom random) { 79 86 80 87 // only select specific symbols, which can be interpreted ... … … 82 89 where s.InitialFrequency > 0.0 83 90 select s).ToList(); 91 84 92 int prodRuleCount = symbolList.Count(); 93 94 // no child node exists for the given parent node 95 if (prodRuleCount < 1) return null; 96 85 97 int prodRuleIndex = genotype[genotypeIndex % genotype.Length] % prodRuleCount; 86 98 87 99 var newNode = symbolList.ElementAt(prodRuleIndex).CreateTreeNode(); 88 if (newNode.HasLocalParameters) newNode.ResetLocalParameters( new MersenneTwister());100 if (newNode.HasLocalParameters) newNode.ResetLocalParameters(random); 89 101 return newNode; 102 } 103 104 105 /// <summary> 106 /// Randomly determines an arity for the given node. 107 /// </summary> 108 /// <param name="random">random number generator</param> 109 /// <param name="node">node, for which a random arity is determined</param> 110 /// <param name="maxAllowedArity">the resulting arity must not exceed this maximum arity</param> 111 /// <returns>random arity in the interval [minArity, maxArity] of the node or 112 /// 1, if minArity exceeds maxAllowedArity</returns> 113 protected int SampleArity(IRandom random, 114 ISymbolicExpressionTreeNode node, 115 int maxAllowedArity) { 116 int minArity = node.Symbol.MinimumArity; 117 int maxArity = node.Symbol.MaximumArity; 118 119 if (maxAllowedArity < maxArity) { 120 maxArity = maxAllowedArity; 121 } 122 123 if (maxAllowedArity < minArity) { 124 return 1; 125 } 126 127 if (minArity == maxArity) { 128 return minArity; 129 } 130 131 return random.Next(minArity, maxArity); 90 132 } 91 133 }
Note: See TracChangeset
for help on using the changeset viewer.