- Timestamp:
- 01/22/14 18:09:44 (10 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs
r10338 r10384 25 25 26 26 27 public sealed class SolverState : ISolverState{27 public sealed class SolverState { 28 28 public int curDepth; 29 29 public int steps; 30 30 public int depth; 31 private readonly Stack<Tree> nodes;31 // private readonly Stack<Tree> nodes; 32 32 private readonly ?IDENT?Problem problem; 33 private Random random; 33 34 34 35 public SolverState(?IDENT?Problem problem, int seed) { 35 36 this.problem = problem; 36 this.nodes = new Stack<Tree>();37 // this.nodes = new Stack<Tree>(); 37 38 38 // create a random tree 39 var tree = SampleTree(new Random(seed), 0, -1); // state 0 is the state for the start symbol 40 nodes.Push(tree); 41 } 42 43 public void Reset() { 44 // stack must contain only the root of the tree 45 System.Diagnostics.Debug.Assert(nodes.Count == 1); 46 } 47 48 private Tree SampleTree(Random random, int state, int altIdx) { 49 // Console.Write(state + "" ""); 39 this.random = new Random(seed); 40 // nodes.Push(tree); 41 } 42 43 // public void Reset() { 44 // // stack must contain only the root of the tree 45 // System.Diagnostics.Debug.Assert(nodes.Count == 1); 46 // } 47 48 public Tree SampleTree() { 49 return SampleTree(0); 50 } 51 52 private Tree SampleTree(int state) { 53 // Console.Write(state + "" "" ); 50 54 curDepth += 1; 51 55 steps += 1; 52 56 depth = Math.Max(depth, curDepth); 53 var t = new Tree(state, altIdx, subtreeCount[state]); 54 55 // t.symbol = symb.Length > state ? symb[state] : ""TERM""; 56 // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case) 57 if(subtreeCount[state] == 1) { 58 var targetStates = transition[state]; 59 var i = SampleAlternative(random, state); 60 if(targetStates.Length == 0) { 61 //terminal 62 t.subtrees.Add(SampleTree(random, -1, i)); 57 Tree t = null; 58 59 // terminals 60 if(subtreeCount[state] == 0) { 61 t = CreateTerminalNode(state); 62 } else { 63 64 t = new Tree(state, -1, subtreeCount[state]); 65 if(subtreeCount[state] < 1) throw new ArgumentException(); 66 // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case) 67 if(subtreeCount[state] == 1) { 68 var targetStates = transition[state]; 69 var i = SampleAlternative(random, state); 70 t.altIdx = i; 71 t.subtrees.Add(SampleTree(targetStates[i])); 63 72 } else { 64 t.subtrees.Add(SampleTree(random, targetStates[i], i)); 65 } 66 } else { 67 // if the symbol contains only one sequence we must use create sub-trees for each symbol in the sequence 68 for(int i = 0; i < subtreeCount[state]; i++) { 69 t.subtrees.Add(SampleTree(random, transition[state][i], i)); 73 // if the symbol contains only one sequence we must use create sub-trees for each symbol in the sequence 74 for(int i = 0; i < subtreeCount[state]; i++) { 75 t.subtrees.Add(SampleTree(transition[state][i])); 76 } 70 77 } 71 78 } … … 74 81 } 75 82 76 public int PeekNextAlternative() { 77 // this must only be called nodes that contain alternatives and therefore must only have single-symbols alternatives 78 System.Diagnostics.Debug.Assert(nodes.Peek().subtrees.Count == 1); 79 return nodes.Peek().subtrees[0].altIdx; 80 } 81 82 public void Follow(int idx) { 83 nodes.Push(nodes.Peek().subtrees[idx]); 84 } 85 86 public void Unwind() { 87 nodes.Pop(); 88 } 83 private Tree CreateTerminalNode(int state) { 84 switch(state) { 85 ?CREATETERMINALNODECODE? 86 default: { throw new ArgumentException(""Unknown state index"" + state); } 87 } 88 } 89 90 // public int PeekNextAlternative() { 91 // // this must only be called nodes that contain alternatives and therefore must only have single-symbols alternatives 92 // System.Diagnostics.Debug.Assert(nodes.Peek().subtrees.Count == 1); 93 // return nodes.Peek().subtrees[0].altIdx; 94 // } 95 // 96 // public void Follow(int idx) { 97 // nodes.Push(nodes.Peek().subtrees[idx]); 98 // } 99 // 100 // public void Unwind() { 101 // nodes.Pop(); 102 // } 89 103 90 104 private int SampleAlternative(Random random, int state) { … … 155 169 while (true) { 156 170 157 // must make sure that calling the start-symbol multiple times in the fitness function always leads to the same path through the grammar158 // so we use a PRNG for generating seeds for a separate PRNG that is reset each time the start symbol is called159 160 171 var _state = new SolverState(problem, seedRandom.Next()); 161 162 var f = problem.Evaluate(_ state);172 var _t = _state.SampleTree(); 173 var f = problem.Evaluate(_t); 163 174 164 n++; 165 sumSize += _state.steps;166 sumDepth += _state.depth;175 n++; 176 // sumSize += _state.steps; 177 // sumDepth += _state.depth; 167 178 sumF += f; 168 179 if (IsBetter(f, bestF)) { 169 180 bestF = f; 170 Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, _state.steps, _state.depth);181 Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, 0, 0 /* _state.steps, _state.depth */); 171 182 } 172 183 if (n % 1000 == 0) { … … 196 207 .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", ")) 197 208 .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar)) 209 .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar)) 198 210 .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar)) 199 211 .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar)) 200 // .Replace("?SAMPLETERMINALCODE?", GenerateSampleTerminalSource(grammar))212 // .Replace("?SAMPLETERMINALCODE?", GenerateSampleTerminalSource(grammar)) 201 213 ; 202 214 … … 217 229 // return sb.ToString(); 218 230 //} 219 231 private string GenerateCreateTerminalCode(IGrammar grammar) { 232 Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol)); 233 var sb = new SourceBuilder(); 234 var allSymbols = grammar.Symbols.ToList(); 235 foreach (var s in grammar.Symbols) { 236 if (grammar.IsTerminal(s)) { 237 sb.AppendFormat("case {0}: {{ return new {1}Tree(random, problem); }}", allSymbols.IndexOf(s), s.Name).AppendLine(); 238 } 239 } 240 return sb.ToString(); 241 } 220 242 221 243 private string GenerateTransitionTable(IGrammar grammar) { … … 225 247 // state idx = idx of the corresponding symbol in the grammar 226 248 var allSymbols = grammar.Symbols.ToList(); 227 var attributes = new List<string>();228 249 foreach (var s in grammar.Symbols) { 229 250 var targetStates = new List<int>(); 230 251 if (grammar.IsTerminal(s)) { 231 foreach (var att in s.Attributes) {232 targetStates.Add(allSymbols.Count + attributes.Count);233 attributes.Add(s.Name + "_" + att);234 }235 252 } else { 236 253 if (grammar.NumberOfAlternatives(s) > 1) { … … 253 270 sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine(); 254 271 } 255 for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {256 sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();257 sb.AppendFormat("{{ {0} , new int[] {{ }} }},", attIdx + allSymbols.Count).AppendLine();258 }259 272 return sb.ToString(); 260 273 } … … 265 278 // state idx = idx of the corresponding symbol in the grammar 266 279 var allSymbols = grammar.Symbols.ToList(); 267 var attributes = new List<string>();268 280 foreach (var s in grammar.Symbols) { 269 int subtreeCount ;281 int subtreeCount = 0; 270 282 if (grammar.IsTerminal(s)) { 271 subtreeCount = s.Attributes.Count();272 attributes.AddRange(s.Attributes.Select(att => s.Name + "_" + att.Name));273 283 } else { 274 284 if (grammar.NumberOfAlternatives(s) > 1) { … … 284 294 } 285 295 286 for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {287 sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();288 sb.AppendFormat("{{ {0} , 1 }},", attIdx + allSymbols.Count).AppendLine();289 }290 296 return sb.ToString(); 291 297 }
Note: See TracChangeset
for help on using the changeset viewer.