[10062] | 1 | using System;
|
---|
| 2 | using System.Collections.Generic;
|
---|
[10067] | 3 | using System.Diagnostics;
|
---|
[10062] | 4 | using System.Linq;
|
---|
[10335] | 5 | using System.Text;
|
---|
[10067] | 6 | using HeuristicLab.Grammars;
|
---|
[10062] | 7 |
|
---|
| 8 | namespace CodeGenerator {
|
---|
[10080] | 9 | public class RandomSearchCodeGen {
|
---|
[10062] | 10 |
|
---|
| 11 | private string solverTemplate = @"
|
---|
| 12 | namespace ?PROBLEMNAME? {
|
---|
| 13 | public sealed class ?IDENT?Solver {
|
---|
[10100] | 14 | private static double baseTerminalProbability = 0.05; // 5% of all samples are only a terminal node
|
---|
| 15 | private static double terminalProbabilityInc = 0.05; // for each level the probability to sample a terminal grows by 5%
|
---|
[10335] | 16 |
|
---|
[10386] | 17 | private readonly ?IDENT?Problem problem;
|
---|
| 18 | private readonly Random random;
|
---|
[10335] | 19 |
|
---|
[10388] | 20 | private Tree SampleTree(out int steps, out int depth) {
|
---|
[10386] | 21 | steps = 0;
|
---|
| 22 | depth = 0;
|
---|
| 23 | int curDepth = 0;
|
---|
| 24 | return SampleTree(0, ref steps, ref curDepth, ref depth);
|
---|
| 25 | }
|
---|
[10100] | 26 |
|
---|
[10386] | 27 | private Tree SampleTree(int state, ref int steps, ref int curDepth, ref int depth) {
|
---|
| 28 | curDepth += 1;
|
---|
| 29 | steps += 1;
|
---|
| 30 | depth = Math.Max(depth, curDepth);
|
---|
| 31 | Tree t = null;
|
---|
[10062] | 32 |
|
---|
[10386] | 33 | // terminals
|
---|
| 34 | if(Grammar.subtreeCount[state] == 0) {
|
---|
[10387] | 35 | t = CreateTerminalNode(state, random, problem);
|
---|
[10386] | 36 | } else {
|
---|
| 37 | // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case)
|
---|
| 38 | if(Grammar.subtreeCount[state] == 1) {
|
---|
| 39 | 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 | t = new Tree(altIdx, new Tree[] { alternative });
|
---|
[10384] | 43 | } else {
|
---|
[10386] | 44 | // if the symbol contains only one sequence we must use create sub-trees for each symbol in the sequence
|
---|
| 45 | Tree[] subtrees = new Tree[Grammar.subtreeCount[state]];
|
---|
| 46 | for(int i = 0; i < Grammar.subtreeCount[state]; i++) {
|
---|
| 47 | subtrees[i] = SampleTree(Grammar.transition[state][i], ref steps, ref curDepth, ref depth);
|
---|
[10100] | 48 | }
|
---|
[10386] | 49 | t = new Tree(-1, subtrees); // alternative index is ignored
|
---|
[10100] | 50 | }
|
---|
[10086] | 51 | }
|
---|
[10386] | 52 | curDepth -=1;
|
---|
| 53 | return t;
|
---|
| 54 | }
|
---|
[10100] | 55 |
|
---|
[10388] | 56 | private static Tree CreateTerminalNode(int state, Random random, ?IDENT?Problem problem) {
|
---|
[10387] | 57 | switch(state) {
|
---|
| 58 | ?CREATETERMINALNODECODE?
|
---|
| 59 | default: { throw new ArgumentException(""Unknown state index"" + state); }
|
---|
| 60 | }
|
---|
| 61 | }
|
---|
| 62 |
|
---|
[10386] | 63 | private int SampleAlternative(Random random, int state, int depth) {
|
---|
| 64 | switch(state) {
|
---|
[10100] | 65 |
|
---|
| 66 | ?SAMPLEALTERNATIVECODE?
|
---|
| 67 |
|
---|
[10386] | 68 | default: throw new InvalidOperationException();
|
---|
[10100] | 69 | }
|
---|
[10386] | 70 | }
|
---|
[10100] | 71 |
|
---|
[10386] | 72 | private double TerminalProbForDepth(int depth) {
|
---|
| 73 | return baseTerminalProbability + depth * terminalProbabilityInc;
|
---|
[10086] | 74 | }
|
---|
| 75 |
|
---|
[10062] | 76 | public static void Main(string[] args) {
|
---|
[10100] | 77 | if(args.Length >= 1) ParseArguments(args);
|
---|
| 78 |
|
---|
| 79 | var problem = new ?IDENT?Problem();
|
---|
| 80 | var solver = new ?IDENT?Solver(problem);
|
---|
[10062] | 81 | solver.Start();
|
---|
| 82 | }
|
---|
[10100] | 83 | private static void ParseArguments(string[] args) {
|
---|
| 84 | var baseTerminalProbabilityRegex = new Regex(@""--terminalProbBase=(?<prob>.+)"");
|
---|
| 85 | var terminalProbabilityIncRegex = new Regex(@""--terminalProbInc=(?<prob>.+)"");
|
---|
| 86 | var helpRegex = new Regex(@""--help|/\?"");
|
---|
| 87 |
|
---|
| 88 | foreach(var arg in args) {
|
---|
| 89 | var baseTerminalProbabilityMatch = baseTerminalProbabilityRegex.Match(arg);
|
---|
| 90 | var terminalProbabilityIncMatch = terminalProbabilityIncRegex.Match(arg);
|
---|
| 91 | var helpMatch = helpRegex.Match(arg);
|
---|
| 92 | if(helpMatch.Success) { PrintUsage(); Environment.Exit(0); }
|
---|
| 93 | else if(baseTerminalProbabilityMatch.Success) {
|
---|
| 94 | baseTerminalProbability = double.Parse(baseTerminalProbabilityMatch.Groups[""prob""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture);
|
---|
| 95 | if(baseTerminalProbability < 0.0 || baseTerminalProbability > 1.0) throw new ArgumentException(""base terminal probability must lie in range [0.0 ... 1.0]"");
|
---|
| 96 | } else if(terminalProbabilityIncMatch.Success) {
|
---|
| 97 | terminalProbabilityInc = double.Parse(terminalProbabilityIncMatch.Groups[""prob""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture);
|
---|
| 98 | if(terminalProbabilityInc < 0.0 || terminalProbabilityInc > 1.0) throw new ArgumentException(""terminal probability increment must lie in range [0.0 ... 1.0]"");
|
---|
| 99 | } else {
|
---|
| 100 | Console.WriteLine(""Unknown switch {0}"", arg); PrintUsage(); Environment.Exit(0);
|
---|
| 101 | }
|
---|
| 102 | }
|
---|
[10062] | 103 | }
|
---|
[10100] | 104 | private static void PrintUsage() {
|
---|
| 105 | Console.WriteLine(""Find a solution using random tree search."");
|
---|
| 106 | Console.WriteLine();
|
---|
| 107 | Console.WriteLine(""Parameters:"");
|
---|
| 108 | Console.WriteLine(""\t--terminalProbBase=<prob>\tSets the probability of sampling a terminal alternative in a rule [Default: 0.05]"");
|
---|
| 109 | 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]"");
|
---|
[10062] | 110 | }
|
---|
| 111 |
|
---|
[10100] | 112 |
|
---|
| 113 | public ?IDENT?Solver(?IDENT?Problem problem) {
|
---|
| 114 | this.problem = problem;
|
---|
[10386] | 115 | this.random = new Random();
|
---|
[10086] | 116 | }
|
---|
[10067] | 117 |
|
---|
[10062] | 118 | private void Start() {
|
---|
| 119 | var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
|
---|
[10067] | 120 | int n = 0;
|
---|
[10100] | 121 | long sumDepth = 0;
|
---|
| 122 | long sumSize = 0;
|
---|
| 123 | var sumF = 0.0;
|
---|
[10074] | 124 | var sw = new System.Diagnostics.Stopwatch();
|
---|
| 125 | sw.Start();
|
---|
[10385] | 126 | while (n <= 10000) {
|
---|
[10074] | 127 |
|
---|
[10386] | 128 | int steps, depth;
|
---|
| 129 | var _t = SampleTree(out steps, out depth);
|
---|
[10384] | 130 | var f = problem.Evaluate(_t);
|
---|
[10100] | 131 |
|
---|
[10384] | 132 | n++;
|
---|
[10386] | 133 | sumSize += steps;
|
---|
| 134 | sumDepth += depth;
|
---|
[10100] | 135 | sumF += f;
|
---|
[10386] | 136 | if (problem.IsBetter(f, bestF)) {
|
---|
[10086] | 137 | bestF = f;
|
---|
[10386] | 138 | Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, steps, depth);
|
---|
[10086] | 139 | }
|
---|
| 140 | if (n % 1000 == 0) {
|
---|
[10074] | 141 | sw.Stop();
|
---|
[10100] | 142 | Console.WriteLine(""{0}\tbest: {1:0.000}\t(avg: {2:0.000})\t(avg size: {3:0.0})\t(avg. depth: {4:0.0})\t({5:0.00} sols/ms)"", n, bestF, sumF/1000.0, sumSize/1000.0, sumDepth/1000.0, 1000.0 / sw.ElapsedMilliseconds);
|
---|
| 143 | sumSize = 0;
|
---|
| 144 | sumDepth = 0;
|
---|
| 145 | sumF = 0.0;
|
---|
[10385] | 146 | sw.Restart();
|
---|
[10074] | 147 | }
|
---|
[10062] | 148 | }
|
---|
| 149 | }
|
---|
| 150 | }
|
---|
| 151 | }";
|
---|
| 152 |
|
---|
[10387] | 153 | public void Generate(IGrammar grammar, IEnumerable<TerminalNode> terminals, bool maximization, SourceBuilder problemSourceCode) {
|
---|
[10100] | 154 | var solverSourceCode = new SourceBuilder();
|
---|
| 155 | solverSourceCode.Append(solverTemplate)
|
---|
| 156 | .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
|
---|
| 157 | .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar))
|
---|
[10387] | 158 | .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar, terminals))
|
---|
[10100] | 159 | ;
|
---|
[10062] | 160 |
|
---|
[10100] | 161 | problemSourceCode.Append(solverSourceCode.ToString());
|
---|
[10062] | 162 | }
|
---|
| 163 |
|
---|
| 164 |
|
---|
[10335] | 165 |
|
---|
[10100] | 166 | private string GenerateSampleAlternativeSource(IGrammar grammar) {
|
---|
| 167 | Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
|
---|
| 168 | var sb = new SourceBuilder();
|
---|
| 169 | int stateCount = 0;
|
---|
| 170 | foreach (var s in grammar.Symbols) {
|
---|
| 171 | sb.AppendFormat("case {0}: ", stateCount++);
|
---|
| 172 | if (grammar.IsTerminal(s)) {
|
---|
[10335] | 173 | // ignore
|
---|
[10100] | 174 | } else {
|
---|
| 175 | var terminalAltIndexes = grammar.GetAlternatives(s)
|
---|
| 176 | .Select((alt, idx) => new { alt, idx })
|
---|
| 177 | .Where((p) => p.alt.All(symb => grammar.IsTerminal(symb)))
|
---|
| 178 | .Select(p => p.idx);
|
---|
| 179 | var nonTerminalAltIndexes = grammar.GetAlternatives(s)
|
---|
| 180 | .Select((alt, idx) => new { alt, idx })
|
---|
| 181 | .Where((p) => p.alt.Any(symb => grammar.IsNonTerminal(symb)))
|
---|
| 182 | .Select(p => p.idx);
|
---|
| 183 | var hasTerminalAlts = terminalAltIndexes.Any();
|
---|
| 184 | var hasNonTerminalAlts = nonTerminalAltIndexes.Any();
|
---|
| 185 | if (hasTerminalAlts && hasNonTerminalAlts) {
|
---|
| 186 | sb.Append("if(random.NextDouble() < TerminalProbForDepth(depth)) {").BeginBlock();
|
---|
| 187 | GenerateReturnStatement(terminalAltIndexes, sb);
|
---|
| 188 | sb.Append("} else {");
|
---|
| 189 | GenerateReturnStatement(nonTerminalAltIndexes, sb);
|
---|
| 190 | sb.Append("}").EndBlock();
|
---|
| 191 | } else {
|
---|
| 192 | GenerateReturnStatement(grammar.NumberOfAlternatives(s), sb);
|
---|
| 193 | }
|
---|
[10062] | 194 | }
|
---|
| 195 | }
|
---|
| 196 | return sb.ToString();
|
---|
| 197 | }
|
---|
[10387] | 198 | private string GenerateCreateTerminalCode(IGrammar grammar, IEnumerable<TerminalNode> terminals) {
|
---|
| 199 | Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
|
---|
| 200 | var sb = new SourceBuilder();
|
---|
| 201 | var allSymbols = grammar.Symbols.ToList();
|
---|
| 202 | foreach (var s in grammar.Symbols) {
|
---|
| 203 | if (grammar.IsTerminal(s)) {
|
---|
| 204 | sb.AppendFormat("case {0}: {{", allSymbols.IndexOf(s)).BeginBlock();
|
---|
| 205 | sb.AppendFormat("var t = new {0}Tree();", s.Name).AppendLine();
|
---|
| 206 | var terminal = terminals.Single(t => t.Ident == s.Name);
|
---|
| 207 | foreach (var constr in terminal.Constraints) {
|
---|
| 208 | if (constr.Type == ConstraintNodeType.Set) {
|
---|
| 209 | sb.Append("{").BeginBlock();
|
---|
| 210 | sb.AppendFormat("var elements = problem.GetAllowed{0}_{1}().ToArray();", terminal.Ident, constr.Ident).AppendLine();
|
---|
| 211 | sb.AppendFormat("t.{0} = elements[random.Next(elements.Length)]; ", constr.Ident).EndBlock();
|
---|
| 212 | sb.AppendLine("}");
|
---|
| 213 | } else {
|
---|
| 214 | sb.Append("{").BeginBlock();
|
---|
| 215 | sb.AppendFormat(" var max = problem.GetMax{0}_{1}();", terminal.Ident, constr.Ident).AppendLine();
|
---|
| 216 | sb.AppendFormat(" var min = problem.GetMin{0}_{1}();", terminal.Ident, constr.Ident).AppendLine();
|
---|
| 217 | sb.AppendFormat("t.{0} = random.NextDouble() * (max - min) + min;", constr.Ident).EndBlock();
|
---|
| 218 | sb.AppendLine("}");
|
---|
| 219 | }
|
---|
| 220 | }
|
---|
| 221 | sb.AppendLine("return t;").EndBlock();
|
---|
| 222 | sb.Append("}");
|
---|
| 223 | }
|
---|
| 224 | }
|
---|
| 225 | return sb.ToString();
|
---|
| 226 | }
|
---|
[10100] | 227 | private void GenerateReturnStatement(IEnumerable<int> idxs, SourceBuilder sb) {
|
---|
| 228 | if (idxs.Count() == 1) {
|
---|
| 229 | sb.AppendFormat("return {0};", idxs.Single()).AppendLine();
|
---|
[10062] | 230 | } else {
|
---|
[10100] | 231 | var idxStr = idxs.Aggregate(string.Empty, (str, idx) => str + idx + ", ");
|
---|
| 232 | sb.AppendFormat("return new int[] {{ {0} }}[random.Next({1})]; ", idxStr, idxs.Count()).AppendLine();
|
---|
[10062] | 233 | }
|
---|
| 234 | }
|
---|
| 235 |
|
---|
[10100] | 236 | private void GenerateReturnStatement(int nAlts, SourceBuilder sb) {
|
---|
| 237 | if (nAlts > 1) {
|
---|
| 238 | sb.AppendFormat("return random.Next({0});", nAlts).AppendLine();
|
---|
| 239 | } else if (nAlts == 1) {
|
---|
| 240 | sb.AppendLine("return 0; ");
|
---|
[10067] | 241 | } else {
|
---|
[10100] | 242 | sb.AppendLine("throw new InvalidProgramException();");
|
---|
[10062] | 243 | }
|
---|
| 244 | }
|
---|
| 245 | }
|
---|
| 246 | }
|
---|