Free cookie consent management tool by TermsFeed Policy Generator

Changeset 10386


Ignore:
Timestamp:
01/22/14 19:27:04 (10 years ago)
Author:
gkronber
Message:

#2026 refactoring

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

Legend:

Unmodified
Added
Removed

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

    r10385 r10386  
    1818    private const string problemTemplate = @"
    1919namespace ?PROBLEMNAME? {
    20 #region class definitions for tree
    21   public class Tree {
    22     public int altIdx;
    23     public List<Tree> subtrees;
    24     protected Tree() {
    25       // leave subtrees uninitialized
    26     }
    27     public Tree(int state, int altIdx, int numSubTrees) {
    28       subtrees = new List<Tree>();
    29       this.altIdx = altIdx;
    30     }
    31   }
    32 
    33   ?TERMINALNODECLASSDEFINITIONS?
    34 #endregion
    35 
    3620  public sealed class ?IDENT?Problem {
    3721   
    … …  
    5438#endregion
    5539    }
     40    public bool IsBetter(double a, double b) {
     41      return ?MAXIMIZATION? ? a > b : a < b;
     42    }
    5643
    5744// additional code from the problem definition (CODE section)
    … …  
    6855#endregion
    6956  }
     57
     58#region class definitions for tree
     59  public class Tree {
     60    public int altIdx;
     61    public Tree[] subtrees;
     62    protected Tree() {
     63      // leave subtrees uninitialized
     64    }
     65    public Tree(int altIdx, Tree[] subtrees) {
     66      this.altIdx = altIdx;
     67      this.subtrees = subtrees;
     68    }
     69  }
     70
     71  ?TERMINALNODECLASSDEFINITIONS?
     72#endregion
     73
     74#region helper class for the grammar representation
     75  public class Grammar {
     76    public static readonly Dictionary<int, int[]> transition = new Dictionary<int, int[]>() {
     77?TRANSITIONTABLE?
     78    };
     79    public static readonly Dictionary<int, int> subtreeCount = new Dictionary<int, int>() {
     80       { -1, 0 }, // terminals
     81?SUBTREECOUNTTABLE?
     82    };
     83    public static readonly string[] symb = new string[] { ?SYMBOLNAMES? };
     84   
     85    public static Tree CreateTerminalNode(int state, Random random, ?IDENT?Problem problem) {
     86      switch(state) {
     87        ?CREATETERMINALNODECODE?
     88        default: { throw new ArgumentException(""Unknown state index"" + state); }
     89      }
     90    }
     91  } 
     92#endregion
    7093}";
    7194
    … …  
    97120        .AppendLine(problemTemplate)
    98121        .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
     122        .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant())
    99123        .Replace("?INITSOURCE?", ast.InitCodeNode.SrcCode)
    100124        .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
    … …  
    102126        .Replace("?CONSTRAINTSSOURCE?", GenerateConstraintMethods(ast.Terminals))
    103127        .Replace("?TERMINALNODECLASSDEFINITIONS?", GenerateTerminalNodeClassDefinitions(ast.Terminals.OfType<TerminalNode>()))
     128        .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", "))
     129        .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar))
     130        .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar))
     131        .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
    104132       ;
    105133    }
    … …  
    190218          sb.AppendFormat("public {0} GetMax{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMaxExpression).AppendLine();
    191219          sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine();
    192           //sb.AppendFormat("public {0} Get{1}_{2}(ISolverState _state) {{ _state. }}", fieldType, t.Ident, c.Ident, )
    193220        } else if (c.Type == ConstraintNodeType.Set) {
    194221          sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
    … …  
    289316    }
    290317
    291     private void GenerateSwitchStatement(IEnumerable<Sequence> alts, SourceBuilder sb) {
     318    private void GenerateSwitchStatement(IEnumerable<Sequence> alts, SourceBuilder sb)
     319    {
    292320      sb.Append("switch(_t.altIdx) {").BeginBlock();
    293321      // generate a case for each alternative
    294       int i = 0;
     322      int altIdx = 0;
    295323      foreach (var alt in alts) {
    296         sb.AppendFormat("case {0}: {{ ", i).BeginBlock();
     324        sb.AppendFormat("case {0}: {{ ", altIdx).BeginBlock();
    297325
    298326        // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols)!
    … …  
    302330          GenerateSourceForAction(0, altSymb, sb); // index is always 0 because of the assertion above
    303331        }
    304         i++;
     332        altIdx++;
    305333        sb.AppendLine("break;").Append("}").EndBlock();
    306334      }
    … …  
    333361      sb.Append("}").EndBlock();
    334362    }
     363
     364    private string GenerateCreateTerminalCode(IGrammar grammar) {
     365      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
     366      var sb = new SourceBuilder();
     367      var allSymbols = grammar.Symbols.ToList();
     368      foreach (var s in grammar.Symbols) {
     369        if (grammar.IsTerminal(s)) {
     370          sb.AppendFormat("case {0}: {{ return new {1}Tree(random, problem); }}", allSymbols.IndexOf(s), s.Name).AppendLine();
     371        }
     372      }
     373      return sb.ToString();
     374    }
     375
     376    private string GenerateTransitionTable(IGrammar grammar) {
     377      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
     378      var sb = new SourceBuilder();
     379
     380      // state idx = idx of the corresponding symbol in the grammar
     381      var allSymbols = grammar.Symbols.ToList();
     382      foreach (var s in grammar.Symbols) {
     383        var targetStates = new List<int>();
     384        if (grammar.IsTerminal(s)) {
     385        } else {
     386          if (grammar.NumberOfAlternatives(s) > 1) {
     387            foreach (var alt in grammar.GetAlternatives(s)) {
     388              // only single-symbol alternatives are supported
     389              Debug.Assert(alt.Count() == 1);
     390              targetStates.Add(allSymbols.IndexOf(alt.Single()));
     391            }
     392          } else {
     393            // rule is a sequence of symbols
     394            var seq = grammar.GetAlternatives(s).Single();
     395            targetStates.AddRange(seq.Select(symb => allSymbols.IndexOf(symb)));
     396          }
     397        }
     398
     399        var targetStateString = targetStates.Aggregate(string.Empty, (str, state) => str + state + ", ");
     400
     401        var idxOfSourceState = allSymbols.IndexOf(s);
     402        sb.AppendFormat("// {0}", s).AppendLine();
     403        sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine();
     404      }
     405      return sb.ToString();
     406    }
     407    private string GenerateSubtreeCountTable(IGrammar grammar) {
     408      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
     409      var sb = new SourceBuilder();
     410
     411      // state idx = idx of the corresponding symbol in the grammar
     412      var allSymbols = grammar.Symbols.ToList();
     413      foreach (var s in grammar.Symbols) {
     414        int subtreeCount = 0;
     415        if (grammar.IsTerminal(s)) {
     416        } else {
     417          if (grammar.NumberOfAlternatives(s) > 1) {
     418            Debug.Assert(grammar.GetAlternatives(s).All(alt => alt.Count() == 1));
     419            subtreeCount = 1;
     420          } else {
     421            subtreeCount = grammar.GetAlternative(s, 0).Count();
     422          }
     423        }
     424
     425        sb.AppendFormat("// {0}", s).AppendLine();
     426        sb.AppendFormat("{{ {0} , {1} }},", allSymbols.IndexOf(s), subtreeCount).AppendLine();
     427      }
     428
     429      return sb.ToString();
     430    }
     431
    335432  }
    336433}

  • branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs

    r10385 r10386  
    1515    private static double terminalProbabilityInc = 0.05; // for each level the probability to sample a terminal grows by 5%
    1616
    17     private static Dictionary<int, int[]> transition = new Dictionary<int, int[]>() {
    18 ?TRANSITIONTABLE?
    19     };
    20     private static Dictionary<int, int> subtreeCount = new Dictionary<int, int>() {
    21        { -1, 0 }, // terminals
    22 ?SUBTREECOUNTTABLE?
    23     };
    24     private static string[] symb = new string[] { ?SYMBOLNAMES? };
    25 
    26    
    27     public sealed class SolverState  {
    28       public int curDepth;
    29       public int steps;
    30       public int depth;
    31       private readonly ?IDENT?Problem problem;
    32       private Random random;
    33 
    34       public SolverState(?IDENT?Problem problem, int seed) {
    35         this.problem = problem;
    36         this.random = new Random(seed);
    37       }
    38 
    39       public Tree SampleTree() {
    40         return SampleTree(0);
    41       }
    42 
    43       private Tree SampleTree(int state) {
    44         // Console.Write(state + "" "" );
    45         curDepth += 1;
    46         steps += 1;
    47         depth = Math.Max(depth, curDepth);
    48         Tree t = null;
    49 
    50         // terminals
    51         if(subtreeCount[state] == 0) {
    52           t = CreateTerminalNode(state);
     17    private readonly ?IDENT?Problem problem;
     18    private readonly Random random;
     19
     20    public Tree SampleTree(out int steps, out int depth) {
     21      steps = 0;
     22      depth = 0;
     23      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) {
     28      curDepth += 1;
     29      steps += 1;
     30      depth = Math.Max(depth, curDepth);
     31      Tree t = null;
     32
     33      // terminals
     34      if(Grammar.subtreeCount[state] == 0) {
     35        t = Grammar.CreateTerminalNode(state, random, problem);
     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 });
    5343        } else {
    54          
    55           t = new Tree(state, -1, subtreeCount[state]);
    56           if(subtreeCount[state] < 1) throw new ArgumentException();
    57           // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case)
    58           if(subtreeCount[state] == 1) {
    59             var targetStates = transition[state];
    60             var i = SampleAlternative(random, state);
    61             t.altIdx = i;
    62             t.subtrees.Add(SampleTree(targetStates[i]));
    63           } else {
    64             // if the symbol contains only one sequence we must use create sub-trees for each symbol in the sequence
    65             for(int i = 0; i < subtreeCount[state]; i++) {
    66               t.subtrees.Add(SampleTree(transition[state][i]));
    67             }
     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);
    6848          }
    69         }
    70         curDepth -=1;
    71         return t;
    72       }
    73 
    74       private Tree CreateTerminalNode(int state) {
    75         switch(state) {
    76           ?CREATETERMINALNODECODE?
    77           default: { throw new ArgumentException(""Unknown state index"" + state); }
    78         }
    79       }
    80 
    81       private int SampleAlternative(Random random, int state) {
    82         switch(state) {
     49          t = new Tree(-1, subtrees); // alternative index is ignored
     50        }
     51      }
     52      curDepth -=1;
     53      return t;
     54    }
     55
     56    private int SampleAlternative(Random random, int state, int depth) {
     57      switch(state) {
    8358
    8459?SAMPLEALTERNATIVECODE?
    8560
    86           default: throw new InvalidOperationException();
    87         }
    88       }
    89 
    90       private double TerminalProbForDepth(int depth) {
    91         return baseTerminalProbability + depth * terminalProbabilityInc;
    92       }
     61        default: throw new InvalidOperationException();
     62      }
     63    }
     64
     65    private double TerminalProbForDepth(int depth) {
     66      return baseTerminalProbability + depth * terminalProbabilityInc;
    9367    }
    9468
    … …  
    130104
    131105
    132     private readonly ?IDENT?Problem problem;
    133106    public ?IDENT?Solver(?IDENT?Problem problem) {
    134107      this.problem = problem;
     108      this.random = new Random();
    135109    }
    136110
    137111    private void Start() {
    138       var seedRandom = new Random();
    139112      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
    140113      int n = 0;
    … …  
    146119      while (n <= 10000) {
    147120
    148         var _state = new SolverState(problem, seedRandom.Next());
    149         var _t = _state.SampleTree();
     121        int steps, depth;
     122        var _t = SampleTree(out steps, out depth);
    150123        var f = problem.Evaluate(_t);
    151124 
    152125        n++;   
    153         // sumSize += _state.steps;
    154         // sumDepth += _state.depth;
     126        sumSize += steps;
     127        sumDepth += depth;
    155128        sumF += f;
    156         if (IsBetter(f, bestF)) {
     129        if (problem.IsBetter(f, bestF)) {
    157130          bestF = f;
    158           Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, 0, 0 /* _state.steps, _state.depth */);
     131          Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, steps, depth);
    159132        }
    160133        if (n % 1000 == 0) {
    … …  
    168141      }
    169142    }
    170 
    171     private bool IsBetter(double a, double b) {
    172       return ?MAXIMIZATION? ? a > b : a < b;
    173     }
    174143  }
    175144}";
    … …  
    179148      solverSourceCode.Append(solverTemplate)
    180149        .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
    181         .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", "))
    182         .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar))
    183         .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar))
    184         .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
    185150        .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar))
    186151      ;
    … …  
    190155
    191156
    192     private string GenerateCreateTerminalCode(IGrammar grammar) {
    193       Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
    194       var sb = new SourceBuilder();
    195       var allSymbols = grammar.Symbols.ToList();
    196       foreach (var s in grammar.Symbols) {
    197         if (grammar.IsTerminal(s)) {
    198           sb.AppendFormat("case {0}: {{ return new {1}Tree(random, problem); }}", allSymbols.IndexOf(s), s.Name).AppendLine();
    199         }
    200       }
    201       return sb.ToString();
    202     }
    203 
    204     private string GenerateTransitionTable(IGrammar grammar) {
    205       Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
    206       var sb = new SourceBuilder();
    207 
    208       // state idx = idx of the corresponding symbol in the grammar
    209       var allSymbols = grammar.Symbols.ToList();
    210       foreach (var s in grammar.Symbols) {
    211         var targetStates = new List<int>();
    212         if (grammar.IsTerminal(s)) {
    213         } else {
    214           if (grammar.NumberOfAlternatives(s) > 1) {
    215             foreach (var alt in grammar.GetAlternatives(s)) {
    216               // only single-symbol alternatives are supported
    217               Debug.Assert(alt.Count() == 1);
    218               targetStates.Add(allSymbols.IndexOf(alt.Single()));
    219             }
    220           } else {
    221             // rule is a sequence of symbols
    222             var seq = grammar.GetAlternatives(s).Single();
    223             targetStates.AddRange(seq.Select(symb => allSymbols.IndexOf(symb)));
    224           }
    225         }
    226 
    227         var targetStateString = targetStates.Aggregate(string.Empty, (str, state) => str + state + ", ");
    228 
    229         var idxOfSourceState = allSymbols.IndexOf(s);
    230         sb.AppendFormat("// {0}", s).AppendLine();
    231         sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine();
    232       }
    233       return sb.ToString();
    234     }
    235     private string GenerateSubtreeCountTable(IGrammar grammar) {
    236       Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
    237       var sb = new SourceBuilder();
    238 
    239       // state idx = idx of the corresponding symbol in the grammar
    240       var allSymbols = grammar.Symbols.ToList();
    241       foreach (var s in grammar.Symbols) {
    242         int subtreeCount = 0;
    243         if (grammar.IsTerminal(s)) {
    244         } else {
    245           if (grammar.NumberOfAlternatives(s) > 1) {
    246             Debug.Assert(grammar.GetAlternatives(s).All(alt => alt.Count() == 1));
    247             subtreeCount = 1;
    248           } else {
    249             subtreeCount = grammar.GetAlternative(s, 0).Count();
    250           }
    251         }
    252 
    253         sb.AppendFormat("// {0}", s).AppendLine();
    254         sb.AppendFormat("{{ {0} , {1} }},", allSymbols.IndexOf(s), subtreeCount).AppendLine();
    255       }
    256 
    257       return sb.ToString();
    258     }
    259157
    260158    private string GenerateSampleAlternativeSource(IGrammar grammar) {
Note: See TracChangeset for help on using the changeset viewer.