Changeset 10384


Ignore:
Timestamp:
01/22/14 18:09:44 (6 years ago)
Author:
gkronber
Message:

#2026 fixed random search code generation

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

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.GPDL/CodeGenerator/CodeGenerator.csproj

    r10100 r10384  
    3636  </ItemGroup>
    3737  <ItemGroup>
    38     <Compile Include="BruteForceCodeGen.cs" />
    3938    <Compile Include="ProblemCodeGen.cs" />
    4039    <Compile Include="SourceBuilder.cs" />
  • branches/HeuristicLab.Problems.GPDL/CodeGenerator/ProblemCodeGen.cs

    r10338 r10384  
    3333
    3434  // generic interface for communication from problem interpretation to solver
    35   public interface ISolverState {
    36     void Reset();
    37     int PeekNextAlternative(); // in alternative nodes returns the index of the alternative that should be followed
    38     void Follow(int idx); // next: derive the NT symbol with index=idx;
    39     void Unwind(); // finished with deriving the NT symbol
    40   }
     35  // public interface ISolverState {
     36  //   void Reset();
     37  //   int PeekNextAlternative(); // in alternative nodes returns the index of the alternative that should be followed
     38  //   void Follow(int idx); // next: derive the NT symbol with index=idx;
     39  //   void Unwind(); // finished with deriving the NT symbol
     40  // }
    4141
    4242  public sealed class ?IDENT?Problem {
     
    5353    }
    5454
    55     private ISolverState _state;
    56     public double Evaluate(ISolverState _state) {
    57       this._state = _state;
     55    private Tree _t;
     56    public double Evaluate(Tree _t) {
     57      this._t = _t;
    5858#region objective function (MINIMIZE / MAXIMIZE section)
    5959?FITNESSFUNCTION?
     
    216216      sb.AppendFormat("public class {0}Tree : Tree {{", terminal.Ident).BeginBlock();
    217217      foreach (var att in terminal.FieldDefinitions) {
    218         sb.AppendFormat("{0} {1};", att.Type, att.Identifier).AppendLine();
     218        sb.AppendFormat("public {0} {1};", att.Type, att.Identifier).AppendLine();
    219219      }
    220220      sb.AppendFormat(" public {0}Tree(Random random, ?IDENT?Problem problem) : base() {{", terminal.Ident).BeginBlock();
     
    222222        if (constr.Type == ConstraintNodeType.Set) {
    223223          sb.AppendLine("{").BeginBlock();
    224           sb.AppendFormat(" var elements = problem.GetAllowed{0}_{1}().ToArray();", terminal.Ident, constr.Ident).AppendLine();
     224          sb.AppendFormat("var elements = problem.GetAllowed{0}_{1}().ToArray();", terminal.Ident, constr.Ident).AppendLine();
    225225          sb.AppendFormat("{0} = elements[random.Next(elements.Length)]; ", constr.Ident).AppendLine();
    226226          sb.AppendLine("}").EndBlock();
     
    229229          sb.AppendFormat(" var max = problem.GetMax{0}_{1}();", terminal.Ident, constr.Ident).AppendLine();
    230230          sb.AppendFormat(" var min = problem.GetMin{0}_{1}();", terminal.Ident, constr.Ident).AppendLine();
    231           sb.AppendFormat("{0} = random.NextDouble() * (max - min) + min ", constr.Ident).AppendLine();
     231          sb.AppendFormat("{0} = random.NextDouble() * (max - min) + min;", constr.Ident).AppendLine();
    232232          sb.AppendLine("}").EndBlock();
    233233        }
     
    268268      else
    269269        actualParameter = string.Empty;
    270       sb.AppendLine("_state.Reset();");
    271       sb.AppendFormat("{0}(_state, {1});", s.Name, actualParameter).AppendLine();
     270      sb.AppendFormat("{0}(_t, {1});", s.Name, actualParameter).AppendLine();
    272271      sb.AppendLine("}").EndBlock();
    273272    }
     
    275274    private void GenerateInterpreterMethod(AttributedGrammar g, ISymbol s, SourceBuilder sb) {
    276275      if (!s.Attributes.Any())
    277         sb.AppendFormat("private void {0}(ISolverState _state) {{", s.Name).BeginBlock();
     276        sb.AppendFormat("private void {0}(Tree _t) {{", s.Name).BeginBlock();
    278277      else
    279         sb.AppendFormat("private void {0}(ISolverState _state, {1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
     278        sb.AppendFormat("private void {0}(Tree _t, {1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
    280279
    281280      // generate local definitions
     
    297296
    298297    private void GenerateSwitchStatement(IEnumerable<Sequence> alts, SourceBuilder sb) {
    299       sb.Append("switch(_state.PeekNextAlternative()) {").BeginBlock();
     298      sb.Append("switch(_t.altIdx) {").BeginBlock();
    300299      // generate a case for each alternative
    301300      int i = 0;
     
    321320        sb.Append(action.Code + ";");
    322321      else if (!s.Attributes.Any())
    323         sb.AppendFormat("_state.Follow({0}); {1}(_state); _state.Unwind();", idx, s.Name);
    324       else sb.AppendFormat("_state.Follow({0}); {1}(_state, {2}); _state.Unwind();", idx, s.Name, s.GetAttributeString());
     322        sb.AppendFormat("{1}(_t.subtrees[{0}]);", idx, s.Name);
     323      else sb.AppendFormat("{1}(_t.subtrees[{0}], {2}); ", idx, s.Name, s.GetAttributeString());
    325324      sb.AppendLine();
    326325    }
     
    329328      // if the terminal symbol has attributes then we must samples values for these attributes
    330329      if (!s.Attributes.Any())
    331         sb.AppendFormat("private void {0}(ISolverState _state) {{", s.Name).BeginBlock();
     330        sb.AppendFormat("private void {0}(Tree _t) {{", s.Name).BeginBlock();
    332331      else
    333         sb.AppendFormat("private void {0}(ISolverState _state, {1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
     332        sb.AppendFormat("private void {0}(Tree _t, {1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
    334333
    335334      // each field must match a formal parameter, assign a value for each parameter
    336335      int i = 0;
    337336      foreach (var element in s.Attributes) {
    338         sb.AppendFormat("_state.Follow({0});", i++).AppendLine();
    339         sb.AppendFormat("{0} = Get{1}_{0}(_state);", element.Name, s.Name).AppendLine();
    340         sb.AppendFormat("_state.Unwind();").AppendLine();
     337        sb.AppendFormat("{0} = (_t as {1}Tree).{0};", element.Name, s.Name).AppendLine();
    341338      }
    342339      sb.Append("}").EndBlock();
  • branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs

    r10338 r10384  
    2525
    2626   
    27     public sealed class SolverState : ISolverState {
     27    public sealed class SolverState {
    2828      public int curDepth;
    2929      public int steps;
    3030      public int depth;
    31       private readonly Stack<Tree> nodes;
     31      // private readonly Stack<Tree> nodes;
    3232      private readonly ?IDENT?Problem problem;
     33      private Random random;
    3334
    3435      public SolverState(?IDENT?Problem problem, int seed) {
    3536        this.problem = problem;
    36         this.nodes = new Stack<Tree>();
     37        // this.nodes = new Stack<Tree>();
    3738       
    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 + "" "" );
    5054        curDepth += 1;
    5155        steps += 1;
    5256        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]));
    6372          } 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            }
    7077          }
    7178        }
     
    7481      }
    7582
    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      // }
    89103
    90104      private int SampleAlternative(Random random, int state) {
     
    155169      while (true) {
    156170
    157         // must make sure that calling the start-symbol multiple times in the fitness function always leads to the same path through the grammar
    158         // so we use a PRNG for generating seeds for a separate PRNG that is reset each time the start symbol is called
    159        
    160171        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);
    163174 
    164         n++;
    165         sumSize += _state.steps;
    166         sumDepth += _state.depth;
     175        n++;   
     176        // sumSize += _state.steps;
     177        // sumDepth += _state.depth;
    167178        sumF += f;
    168179        if (IsBetter(f, bestF)) {
    169180          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 */);
    171182        }
    172183        if (n % 1000 == 0) {
     
    196207        .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", "))
    197208        .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar))
     209        .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar))
    198210        .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
    199211        .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar))
    200 //        .Replace("?SAMPLETERMINALCODE?", GenerateSampleTerminalSource(grammar))
     212        //        .Replace("?SAMPLETERMINALCODE?", GenerateSampleTerminalSource(grammar))
    201213      ;
    202214
     
    217229    //  return sb.ToString();
    218230    //}
    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    }
    220242
    221243    private string GenerateTransitionTable(IGrammar grammar) {
     
    225247      // state idx = idx of the corresponding symbol in the grammar
    226248      var allSymbols = grammar.Symbols.ToList();
    227       var attributes = new List<string>();
    228249      foreach (var s in grammar.Symbols) {
    229250        var targetStates = new List<int>();
    230251        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           }
    235252        } else {
    236253          if (grammar.NumberOfAlternatives(s) > 1) {
     
    253270        sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine();
    254271      }
    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       }
    259272      return sb.ToString();
    260273    }
     
    265278      // state idx = idx of the corresponding symbol in the grammar
    266279      var allSymbols = grammar.Symbols.ToList();
    267       var attributes = new List<string>();
    268280      foreach (var s in grammar.Symbols) {
    269         int subtreeCount;
     281        int subtreeCount = 0;
    270282        if (grammar.IsTerminal(s)) {
    271           subtreeCount = s.Attributes.Count();
    272           attributes.AddRange(s.Attributes.Select(att => s.Name + "_" + att.Name));
    273283        } else {
    274284          if (grammar.NumberOfAlternatives(s) > 1) {
     
    284294      }
    285295
    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       }
    290296      return sb.ToString();
    291297    }
Note: See TracChangeset for help on using the changeset viewer.