- Timestamp:
- 01/29/14 16:17:20 (10 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs
r10400 r10424 14 14 private static double baseTerminalProbability = 0.05; // 5% of all samples are only a terminal node 15 15 private static double terminalProbabilityInc = 0.05; // for each level the probability to sample a terminal grows by 5% 16 private static int maxDepth = 20; 16 17 17 18 private readonly ?IDENT?Problem problem; 18 19 private readonly Random random; 19 20 20 private Tree SampleTree( out int steps, out int depth) {21 private Tree SampleTree(int maxDepth, out int steps, out int depth) { 21 22 steps = 0; 22 23 depth = 0; 23 24 int curDepth = 0; 24 return SampleTree(0, ref steps, ref curDepth, ref depth);25 } 26 27 private Tree SampleTree(int state, ref int steps, ref int curDepth, ref int depth) {25 return SampleTree(0, maxDepth, ref steps, ref curDepth, ref depth); 26 } 27 28 private Tree SampleTree(int state, int maxDepth, ref int steps, ref int curDepth, ref int depth) { 28 29 curDepth += 1; 30 Debug.Assert(maxDepth > 0); 29 31 steps += 1; 30 32 depth = Math.Max(depth, curDepth); … … 38 40 if(Grammar.subtreeCount[state] == 1) { 39 41 var targetStates = Grammar.transition[state]; 40 var altIdx = SampleAlternative(random, state, curDepth);41 var alternative = SampleTree(targetStates[altIdx], ref steps, ref curDepth, ref depth);42 var altIdx = SampleAlternative(random, maxDepth - 1, state, curDepth); 43 var alternative = SampleTree(targetStates[altIdx], maxDepth - 1, ref steps, ref curDepth, ref depth); 42 44 t = new Tree(altIdx, new Tree[] { alternative }); 43 45 } else { … … 45 47 Tree[] subtrees = new Tree[Grammar.subtreeCount[state]]; 46 48 for(int i = 0; i < Grammar.subtreeCount[state]; i++) { 47 subtrees[i] = SampleTree(Grammar.transition[state][i], ref steps, ref curDepth, ref depth);49 subtrees[i] = SampleTree(Grammar.transition[state][i], maxDepth - 1, ref steps, ref curDepth, ref depth); 48 50 } 49 51 t = new Tree(-1, subtrees); // alternative index is ignored … … 57 59 switch(state) { 58 60 ?CREATETERMINALNODECODE? 59 default: { throw new ArgumentException(""Unknown state index "" + state); }60 } 61 } 62 63 private int SampleAlternative(Random random, int state, int depth) {61 default: { throw new ArgumentException(""Unknown state index "" + state); } 62 } 63 } 64 65 private int SampleAlternative(Random random, int maxDepth, int state, int depth) { 64 66 switch(state) { 65 67 … … 71 73 72 74 private double TerminalProbForDepth(int depth) { 75 if(depth>=maxDepth) return 1.0; 73 76 return baseTerminalProbability + depth * terminalProbabilityInc; 74 77 } … … 84 87 var baseTerminalProbabilityRegex = new Regex(@""--terminalProbBase=(?<prob>.+)""); 85 88 var terminalProbabilityIncRegex = new Regex(@""--terminalProbInc=(?<prob>.+)""); 89 var maxDepthRegex = new Regex(@""--maxDepth=(?<d>.+)""); 90 86 91 var helpRegex = new Regex(@""--help|/\?""); 87 92 … … 89 94 var baseTerminalProbabilityMatch = baseTerminalProbabilityRegex.Match(arg); 90 95 var terminalProbabilityIncMatch = terminalProbabilityIncRegex.Match(arg); 96 var maxDepthMatch = maxDepthRegex.Match(arg); 91 97 var helpMatch = helpRegex.Match(arg); 92 98 if(helpMatch.Success) { PrintUsage(); Environment.Exit(0); } … … 97 103 terminalProbabilityInc = double.Parse(terminalProbabilityIncMatch.Groups[""prob""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture); 98 104 if(terminalProbabilityInc < 0.0 || terminalProbabilityInc > 1.0) throw new ArgumentException(""terminal probability increment must lie in range [0.0 ... 1.0]""); 105 } else if(maxDepthMatch.Success) { 106 maxDepth = int.Parse(maxDepthMatch.Groups[""d""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture); 107 if(maxDepth < 1 || maxDepth > 100) throw new ArgumentException(""max depth must lie in range [1 ... 100]""); 99 108 } else { 100 109 Console.WriteLine(""Unknown switch {0}"", arg); PrintUsage(); Environment.Exit(0); … … 106 115 Console.WriteLine(); 107 116 Console.WriteLine(""Parameters:""); 117 Console.WriteLine(""\t--maxDepth=<depth>\tSets the maximal depth of sampled trees [Default: 20]""); 108 118 Console.WriteLine(""\t--terminalProbBase=<prob>\tSets the probability of sampling a terminal alternative in a rule [Default: 0.05]""); 109 119 Console.WriteLine(""\t--terminalProbInc=<prob>\tSets the increment for the probability of sampling a terminal alternative for each level in the syntax tree [Default: 0.05]""); … … 127 137 128 138 int steps, depth; 129 var _t = SampleTree(out steps, out depth); 139 var _t = SampleTree(maxDepth, out steps, out depth); 140 Debug.Assert(depth <= maxDepth); 141 // _t.PrintTree(0); Console.WriteLine(); 130 142 var f = problem.Evaluate(_t); 131 143 … … 185 197 var hasNonTerminalAlts = nonTerminalAltIndexes.Any(); 186 198 if (hasTerminalAlts && hasNonTerminalAlts) { 187 sb.Append("if( random.NextDouble() < TerminalProbForDepth(depth)) {").BeginBlock();188 Generate ReturnStatement(terminalAltIndexes, sb);199 sb.Append("if(maxDepth <= 1 || random.NextDouble() < TerminalProbForDepth(depth)) {").BeginBlock(); 200 GenerateSampleTerminalAlternativesStatement(terminalAltIndexes, sb); 189 201 sb.Append("} else {"); 190 Generate ReturnStatement(nonTerminalAltIndexes, sb);202 GenerateSampleNonterminalAlternativesStatement(nonTerminalAltIndexes, sb); 191 203 sb.Append("}").EndBlock(); 192 204 } else { … … 226 238 return sb.ToString(); 227 239 } 228 private void Generate ReturnStatement(IEnumerable<int> idxs, SourceBuilder sb) {240 private void GenerateSampleTerminalAlternativesStatement(IEnumerable<int> idxs, SourceBuilder sb) { 229 241 if (idxs.Count() == 1) { 230 242 sb.AppendFormat("return {0};", idxs.Single()).AppendLine(); … … 234 246 } 235 247 } 248 private void GenerateSampleNonterminalAlternativesStatement(IEnumerable<int> idxs, SourceBuilder sb) { 249 if (idxs.Count() == 1) { 250 sb.AppendFormat("return {0};", idxs.Single()).AppendLine(); 251 } else { 252 var idxStr = idxs.Aggregate(string.Empty, (str, idx) => str + idx + ", "); 253 sb.AppendLine("{"); 254 sb.AppendFormat("var allIdx = new int[] {{ {0} }}; ", idxStr).AppendLine(); 255 sb.AppendFormat( 256 "var allowedIdx = (from idx in allIdx let targetState = Grammar.transition[state][idx] where Grammar.minDepth[targetState] <= maxDepth select idx).ToArray();") 257 .AppendLine(); 258 sb.AppendLine( 259 "if(allowedIdx.Length==0) { allowedIdx = Enumerable.Range(0, Grammar.transition[state].Length).Except(allIdx).ToArray(); } ") 260 .AppendLine(); 261 sb.AppendLine("return allowedIdx[random.Next(allowedIdx.Length)];"); 262 sb.AppendLine("}"); 263 } 264 } 236 265 237 266 private void GenerateReturnStatement(int nAlts, SourceBuilder sb) { 238 if (nAlts > 1) { 239 sb.AppendFormat("return random.Next({0});", nAlts).AppendLine(); 267 if (nAlts > 1) 268 { 269 sb.AppendLine("{"); 270 sb.AppendFormat( 271 "var allowedIdx = (from idx in Enumerable.Range(0, {0}) let targetState = Grammar.transition[state][idx] where Grammar.minDepth[targetState] <= maxDepth select idx).ToArray();", nAlts) 272 .AppendLine(); 273 sb.AppendLine("return allowedIdx[random.Next(allowedIdx.Length)];"); 274 sb.AppendLine("}"); 240 275 } else if (nAlts == 1) { 241 276 sb.AppendLine("return 0; ");
Note: See TracChangeset
for help on using the changeset viewer.