Changeset 10388

Ignore:
Timestamp:
01/23/14 09:20:15 (6 years ago)
Message:

#2026 worked on code generator for brute force solver

Location:
branches/HeuristicLab.Problems.GPDL/CodeGenerator
Files:
4 edited

Unmodified
Removed
• branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs

 r10335 using System.Diagnostics; using System.Linq; using System.Text; using HeuristicLab.Grammars; namespace CodeGenerator { public class BruteForceCodeGen { private string solverTemplate = @" namespace ?PROBLEMNAME? { public sealed class ?IDENT?Solver { private static Dictionary transition = new Dictionary() { ?TRANSITIONTABLE? }; private static Dictionary subtreeCount = new Dictionary() { { -1, 0 }, // terminals ?SUBTREECOUNTTABLE? }; private static string[] symb = new string[] { ?SYMBOLNAMES? }; private static bool[] isTerminal = new bool[] { ?TERMINALTABLE? }; private static bool[] hasAlternatives = new bool[] {?HASALTERNATIVESTABLE? }; public sealed class SolverState : ISolverState { private class Node { public int state; public int count; public List nodes; public bool done; private int nextAlt; public Node(int state) { this.state = state; nodes = new List(transition[state].Length); if (!hasAlternatives[state]) { foreach (var t in transition[state]) { nodes.Add(new Node(t)); } } } public int GetNextAlternative() { System.Diagnostics.Debug.Assert(hasAlternatives[state]); if(nodes.Count == 0 && !isTerminal[state]) { foreach(var targetState in transition[state]) nodes.Add(new Node(targetState)); nextAlt = 0; // begin with a terminal if possible if(!isTerminal[nodes[nextAlt].state]) do { nextAlt = (nextAlt + 1) % nodes.Count; } while(nextAlt != 0 /* full circle*/ && !isTerminal[nodes[nextAlt].state]); } throw new NotImplementedException(); // TODO: handle terminal classes correctly return nextAlt; } public void Update() { count++; if(hasAlternatives[state] && !isTerminal[state]) { nodes[GetNextAlternative()].Update(); // check if all nodes done and set this node to done if(nodes.All(n=>n.done)) { this.done = true; } else { // must not walk nodes that are done do { nextAlt = (nextAlt + 1) % nodes.Count; } while (nodes[nextAlt].done); } } else { if(isTerminal[state]) { throw new NotImplementedException(); // TODO: handle terminal classes correctly done = (nextAlt + 1) >= GetAlternativesCount(symb[state]); } else { // update the smallest count. this basically means keeping all sub-trees the same and only altering the updated one Node minNode = nodes.First(); foreach(var node in nodes.Skip(1)) { if(node.count < minNode.count) { minNode = node; } } minNode.Update(); if(nodes.All(n=>n.done)) this.done = true; } } } } ?ALTERNATIVESCOUNTMETHOD? public int curDepth; public int steps; public int depth; private readonly Stack nodes; private readonly IGpdlProblem problem; private readonly Node searchTree; public SolverState(IGpdlProblem problem) { this.problem = problem; nodes = new Stack(); searchTree = new Node(0); nodes.Push(searchTree); } public void Reset() { System.Diagnostics.Debug.Assert(nodes.Count == 1); steps = 0; depth = 0; curDepth = 0; } public int PeekNextAlternative() { var curNode = nodes.Peek(); System.Diagnostics.Debug.Assert(hasAlternatives[curNode.state]); return curNode.GetNextAlternative(); } public void Follow(int idx) { steps++; curDepth++; depth = Math.Max(depth, curDepth); var curNode = nodes.Peek(); if(hasAlternatives[curNode.state]) { nodes.Push(curNode.nodes[curNode.GetNextAlternative()]); public class SearchTreeNode { public bool ready = false; public SearchTreeNode[] children; public int state; public int nextAltIdx; public SearchTreeNode(int state) { // do not initialize children yet to save mem nextAltIdx = 0; } public SearchTreeNode GetNextNode() { if(children == null) { int nChildren = Grammar.subtreeCount[state] == 1 ? Grammar.transitions[state].Length : Grammar.subtreeCount[state]; children = new SearchTreeNode[nChildren]; } if(children[nextAltIdx] == null) { children[nextAltIdx] = } } } private readonly ?IDENT?Problem problem; private readonly Random random; private SearchTreeNode searchTree = null; private IEnumerable GenerateTrees(int maxDepth) { if(searchTree==null) searchTree = new SearchTreeNode(0); } private Tree GenerateTree(SearchTreeNode node) { curDepth += 1; steps += 1; depth = Math.Max(depth, curDepth); Tree t = null; // terminals if(Grammar.subtreeCount[state] == 0) { t = CreateTerminalNode(state, random, problem); } else { // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case) if(Grammar.subtreeCount[state] == 1) { var targetStates = Grammar.transition[state]; var altIdx = SampleAlternative(random, state, curDepth); var alternative = SampleTree(targetStates[altIdx], ref steps, ref curDepth, ref depth); t = new Tree(altIdx, new Tree[] { alternative }); } else { nodes.Push(curNode.nodes[idx]); } } public void Unwind() { nodes.Pop(); curDepth--; } public void Update() { searchTree.Update(); } // if the symbol contains only one sequence we must use create sub-trees for each symbol in the sequence Tree[] subtrees = new Tree[Grammar.subtreeCount[state]]; for(int i = 0; i < Grammar.subtreeCount[state]; i++) { subtrees[i] = SampleTree(Grammar.transition[state][i], ref steps, ref curDepth, ref depth); } t = new Tree(-1, subtrees); // alternative index is ignored } } curDepth -=1; return t; } private static Tree CreateTerminalNode(int state, Random random, ?IDENT?Problem problem) { switch(state) { ?CREATETERMINALNODECODE? default: { throw new ArgumentException(""Unknown state index"" + state); } } } private int NextAlternative(SearchTreeNode node) { ?RETURNNEXTALTERNATIVECODE? } solver.Start(); } private readonly ?IDENT?Problem problem; public ?IDENT?Solver(?IDENT?Problem problem) { this.problem = problem; this.random = new Random(); } var sw = new System.Diagnostics.Stopwatch(); sw.Start(); var _state = new SolverState(problem); while (true) { var f = problem.Evaluate(_state); _state.Update(); n++; sumSize += _state.steps; sumDepth += _state.depth; sumF += f; if (IsBetter(f, bestF)) { // evaluate again with tracing to console // problem.Evaluate(new SolverState(_state.seed, true)); bestF = f; Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, _state.steps, _state.depth); } if (n % 1000 == 0) { sw.Stop(); 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); sw.Reset(); sumSize = 0; sumDepth = 0; sumF = 0.0; sw.Start(); } } } private bool IsBetter(double a, double b) { return ?MAXIMIZATION? ? a > b : a < b; for(int d = 1; d < 20; d++) { foreach(var t in GenerateTrees(d)) { var f = problem.Evaluate(t); n++; sumF += f; if (problem.IsBetter(f, bestF)) { bestF = f; Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, 0, 0); } if (n % 1000 == 0) { sw.Stop(); 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); sumSize = 0; sumDepth = 0; sumF = 0.0; sw.Restart(); } } } } } }"; public void Generate(IGrammar grammar, bool maximization, SourceBuilder problemSourceCode) { public void Generate(IGrammar grammar, IEnumerable terminals, bool maximization, SourceBuilder problemSourceCode) { var solverSourceCode = new SourceBuilder(); solverSourceCode.Append(solverTemplate) .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant()) .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", ")) .Replace("?TERMINALTABLE?", grammar.Symbols.Select(grammar.IsTerminal).Aggregate(string.Empty, (str, b) => str + b.ToString().ToLowerInvariant() + ", ")) .Replace("?HASALTERNATIVESTABLE?", grammar.Symbols.Select(s => grammar.IsNonTerminal(s) && (grammar.NumberOfAlternatives(s) > 1)).Aggregate(string.Empty, (str, b) => str + b.ToString().ToLowerInvariant() + ", ")) .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar)) .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar)) .Replace("?ALTERNATIVESCOUNTMETHOD?", GenerateAlternativesCountMethod(grammar)) .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar)) .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar, terminals)) ; } #region same as random search private string GenerateTransitionTable(IGrammar grammar) { private string GenerateSampleAlternativeSource(IGrammar grammar) { Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol)); var sb = new SourceBuilder(); // state idx = idx of the corresponding symbol in the grammar var allSymbols = grammar.Symbols.ToList(); var attributes = new List(); int stateCount = 0; foreach (var s in grammar.Symbols) { var targetStates = new List(); sb.AppendFormat("case {0}: ", stateCount++); if (grammar.IsTerminal(s)) { foreach (var att in s.Attributes) { targetStates.Add(allSymbols.Count + attributes.Count); attributes.Add(s.Name + "_" + att); } // ignore } else { if (grammar.NumberOfAlternatives(s) > 1) { foreach (var alt in grammar.GetAlternatives(s)) { // only single-symbol alternatives are supported Debug.Assert(alt.Count() == 1); targetStates.Add(allSymbols.IndexOf(alt.Single())); } var terminalAltIndexes = grammar.GetAlternatives(s) .Select((alt, idx) => new { alt, idx }) .Where((p) => p.alt.All(symb => grammar.IsTerminal(symb))) .Select(p => p.idx); var nonTerminalAltIndexes = grammar.GetAlternatives(s) .Select((alt, idx) => new { alt, idx }) .Where((p) => p.alt.Any(symb => grammar.IsNonTerminal(symb))) .Select(p => p.idx); var hasTerminalAlts = terminalAltIndexes.Any(); var hasNonTerminalAlts = nonTerminalAltIndexes.Any(); if (hasTerminalAlts && hasNonTerminalAlts) { sb.Append("if(random.NextDouble() < TerminalProbForDepth(depth)) {").BeginBlock(); GenerateReturnStatement(terminalAltIndexes, sb); sb.Append("} else {"); GenerateReturnStatement(nonTerminalAltIndexes, sb); sb.Append("}").EndBlock(); } else { // rule is a sequence of symbols var seq = grammar.GetAlternatives(s).Single(); targetStates.AddRange(seq.Select(symb => allSymbols.IndexOf(symb))); } } var targetStateString = targetStates.Aggregate(string.Empty, (str, state) => str + state + ", "); var idxOfSourceState = allSymbols.IndexOf(s); sb.AppendFormat("// {0}", s).AppendLine(); sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine(); } for (int attIdx = 0; attIdx < attributes.Count; attIdx++) { sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine(); sb.AppendFormat("{{ {0} , new int[] {{ }} }},", attIdx + allSymbols.Count).AppendLine(); GenerateReturnStatement(grammar.NumberOfAlternatives(s), sb); } } } return sb.ToString(); } private string GenerateSubtreeCountTable(IGrammar grammar) { private string GenerateCreateTerminalCode(IGrammar grammar, IEnumerable terminals) { Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol)); var sb = new SourceBuilder(); // state idx = idx of the corresponding symbol in the grammar var allSymbols = grammar.Symbols.ToList(); var attributes = new List(); foreach (var s in grammar.Symbols) { int subtreeCount; if (grammar.IsTerminal(s)) { subtreeCount = s.Attributes.Count(); attributes.AddRange(s.Attributes.Select(att => s.Name + "_" + att.Name)); } else { if (grammar.NumberOfAlternatives(s) > 1) { Debug.Assert(grammar.GetAlternatives(s).All(alt => alt.Count() == 1)); subtreeCount = 1; } else { subtreeCount = grammar.GetAlternative(s, 0).Count(); } } sb.AppendFormat("// {0}", s).AppendLine(); sb.AppendFormat("{{ {0} , {1} }},", allSymbols.IndexOf(s), subtreeCount).AppendLine(); } for (int attIdx = 0; attIdx < attributes.Count; attIdx++) { sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine(); sb.AppendFormat("{{ {0} , 1 }},", attIdx + allSymbols.Count).AppendLine(); sb.AppendFormat("case {0}: {{", allSymbols.IndexOf(s)).BeginBlock(); sb.AppendFormat("var t = new {0}Tree();", s.Name).AppendLine(); var terminal = terminals.Single(t => t.Ident == s.Name); foreach (var constr in terminal.Constraints) { if (constr.Type == ConstraintNodeType.Set) { sb.Append("{").BeginBlock(); sb.AppendLine("throw new NotImplementedException(\"Enumeration of terminal values is not implemented.\");"); sb.AppendFormat("//var elements = problem.GetAllowed{0}_{1}().ToArray();", terminal.Ident, constr.Ident).AppendLine(); sb.AppendFormat("//t.{0} = elements[random.Next(elements.Length)]; ", constr.Ident).EndBlock(); sb.AppendLine("}"); } else { sb.Append("{").BeginBlock(); sb.AppendLine("throw new NotSupportedException(\"The brute force solver does not support RANGE constraints\");"); sb.AppendLine("}"); } } sb.AppendLine("return t;").EndBlock(); sb.Append("}"); } } return sb.ToString(); } #endregion private string GenerateAlternativesCountMethod(IGrammar grammar) { Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol)); var sb = new SourceBuilder(); sb.Append("public int GetAlternativesCount(string symbol, string attribute = null) {").BeginBlock(); sb.AppendLine("switch(symbol) {"); foreach (var s in grammar.Symbols) { sb.AppendFormat("case \"{0}\":", s.Name).AppendLine(); int altCount; if (grammar.IsTerminal(s)) { if (s.Attributes.Any()) { sb.Append("switch(attribute) {").BeginBlock(); foreach (var att in s.Attributes) { sb.AppendFormat("case \"{1}\": return problem.GetCardinality(\"{0}\", \"{1}\");", s.Name, att.Name).AppendLine(); } sb.Append("} // switch").EndBlock(); } else { sb.AppendLine("return 0;"); } } else { sb.AppendFormat("return {0};", grammar.NumberOfAlternatives(s)).AppendLine(); } } sb.AppendLine("} // switch"); sb.Append("}").EndBlock(); return sb.ToString(); private void GenerateReturnStatement(IEnumerable idxs, SourceBuilder sb) { if (idxs.Count() == 1) { sb.AppendFormat("return {0};", idxs.Single()).AppendLine(); } else { var idxStr = idxs.Aggregate(string.Empty, (str, idx) => str + idx + ", "); sb.AppendFormat("return new int[] {{ {0} }}[random.Next({1})]; ", idxStr, idxs.Count()).AppendLine(); } } private void GenerateReturnStatement(int nAlts, SourceBuilder sb) { if (nAlts > 1) { sb.AppendFormat("return random.Next({0});", nAlts).AppendLine(); } else if (nAlts == 1) { sb.AppendLine("return 0; "); } else { sb.AppendLine("throw new InvalidProgramException();"); } } }
• branches/HeuristicLab.Problems.GPDL/CodeGenerator/CodeGenerator.csproj

 r10384
• branches/HeuristicLab.Problems.GPDL/CodeGenerator/ProblemCodeGen.cs

 r10387 private void GenerateSolvers(GPDefNode ast, SourceBuilder solverSourceCode) { var grammar = CreateGrammarFromAst(ast); var randomSearchCodeGen = new RandomSearchCodeGen(); randomSearchCodeGen.Generate(grammar, ast.Terminals.OfType(), ast.FitnessFunctionNode.Maximization, solverSourceCode); //var bruteForceSearchCodeGen = new BruteForceCodeGen(); //bruteForceSearchCodeGen.Generate(grammar, ast.FitnessFunctionNode.Maximization, solverSourceCode); // var randomSearchCodeGen = new RandomSearchCodeGen(); // randomSearchCodeGen.Generate(grammar, ast.Terminals.OfType(), ast.FitnessFunctionNode.Maximization, solverSourceCode); var bruteForceSearchCodeGen = new BruteForceCodeGen(); bruteForceSearchCodeGen.Generate(grammar, ast.Terminals.OfType(), ast.FitnessFunctionNode.Maximization, solverSourceCode); }
• branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs

 r10387 private readonly Random random; public Tree SampleTree(out int steps, out int depth) { private Tree SampleTree(out int steps, out int depth) { steps = 0; depth = 0; } public static Tree CreateTerminalNode(int state, Random random, ?IDENT?Problem problem) { private static Tree CreateTerminalNode(int state, Random random, ?IDENT?Problem problem) { switch(state) { ?CREATETERMINALNODECODE?
Note: See TracChangeset for help on using the changeset viewer.