Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialSearch.cs @ 11846

Last change on this file since 11846 was 11846, checked in by gkronber, 8 years ago

#2283 implemented bridge to HL (solve grammatical optimization problem instances with StandardGP and OffspringSelectionGP)

File size: 8.9 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4using System.Linq;
5using System.Resources;
6using System.Runtime.InteropServices;
7using System.Text;
8using HeuristicLab.Algorithms.Bandits;
9using HeuristicLab.Algorithms.Bandits.BanditPolicies;
10using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
11using HeuristicLab.Common;
12using HeuristicLab.Problems.GrammaticalOptimization;
13
14namespace HeuristicLab.Algorithms.GrammaticalOptimization {
15  // a search procedure that uses a policy to generate sentences and updates the policy (online RL)
16  // 1) Start with phrase = sentence symbol of grammar
17  // 2) Repeat
18  //    a) generate derived phrases using left-canonical derivation and grammar rules
19  //    b) keep only the phrases which are allowed (sentence length limit)
20  //    c) if the set of phrases is empty restart with 1)
21  //    d) otherwise use policy to select one of the possible derived phrases as active phrase
22  //       the policy has the option to fail (for instance if all derived phrases are terminal and should not be visited again), in this case we restart at 1
23  //    ... until phrase is terminal
24  // 3) Collect reward and update policy (feedback: state of visited rewards from step 2)
25  public class SequentialSearch : SolverBase {
26    // only for storing states so that it is not necessary to allocate new state strings whenever we select a follow state using the policy
27    private class TreeNode {
28      public int randomTries;
29      public string phrase;
30      public Sequence alternative;
31      public TreeNode[] children;
32
33      public TreeNode(string phrase, Sequence alternative) {
34        this.alternative = alternative;
35        this.phrase = phrase;
36      }
37    }
38
39
40    private readonly int maxLen;
41    private readonly IProblem problem;
42    private readonly Random random;
43    private readonly int randomTries;
44    private readonly IGrammarPolicy behaviourPolicy;
45    private readonly IGrammarPolicy greedyPolicy;
46    private TreeNode rootNode;
47
48    private int tries;
49    private int maxSearchDepth;
50
51    private string bestPhrase;
52    private readonly List<string> stateChain;
53
54    public SequentialSearch(IProblem problem, int maxLen, Random random, int randomTries, IGrammarPolicy behaviourPolicy) {
55      this.maxLen = maxLen;
56      this.problem = problem;
57      this.random = random;
58      this.randomTries = randomTries;
59      this.behaviourPolicy = behaviourPolicy;
60      this.greedyPolicy = new GenericGrammarPolicy(problem, new EpsGreedyPolicy(0.0), false);
61      this.stateChain = new List<string>();
62    }
63
64    public override void Run(int maxIterations) {
65      Reset();
66
67      for (int i = 0; /*!bestQuality.IsAlmost(1.0) && */!Done() && i < maxIterations; i++) {
68        var phrase = SampleSentence(problem.Grammar);
69        // can fail on the last sentence
70        if (phrase.IsTerminal) {
71          var sentence = phrase.ToString();
72          tries++;
73          var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
74          if (double.IsNaN(quality)) quality = 0.0;
75          Debug.Assert(quality >= 0 && quality <= 1.0);
76
77          if (quality > bestQuality) {
78            bestPhrase = sentence;
79          }
80
81          OnSolutionEvaluated(sentence, quality);
82          DistributeReward(quality);
83
84        }
85      }
86    }
87
88
89    private Sequence SampleSentence(IGrammar grammar) {
90      Sequence phrase;
91      do {
92        stateChain.Clear();
93        phrase = new Sequence(rootNode.phrase);
94      } while (!Done() && !TryCompleteSentence(grammar, ref phrase));
95      return phrase;
96    }
97
98    private bool TryCompleteSentence(IGrammar g, ref Sequence phrase) {
99      if (phrase.Length > maxLen) throw new ArgumentException();
100      if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
101      var curDepth = 0;
102      var n = rootNode;
103      stateChain.Add(n.phrase);
104
105      while (!phrase.IsTerminal) {
106        if (n.randomTries < randomTries) {
107          n.randomTries++;
108          maxSearchDepth = Math.Max(maxSearchDepth, curDepth);
109          g.CompleteSentenceRandomly(random, phrase, maxLen);
110          return true;
111        } else {
112          // => select using bandit policy
113          // failure means we simply restart
114          GenerateFollowStates(n); // creates child nodes for node n
115
116          int selectedChildIdx;
117          if (!behaviourPolicy.TrySelect(random, n.phrase, n.children.Select(ch => ch.phrase), out selectedChildIdx)) {
118            return false;
119          }
120          phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, n.children[selectedChildIdx].alternative);
121
122          // prepare for next iteration
123          n = n.children[selectedChildIdx];
124          stateChain.Add(n.phrase);
125          curDepth++;
126        }
127      } // while
128
129      maxSearchDepth = Math.Max(maxSearchDepth, curDepth);
130      return true;
131    }
132
133
134    private IEnumerable<string> GenerateFollowStates(TreeNode n) {
135      // create children on the first visit
136      if (n.children == null) {
137        var g = problem.Grammar;
138        // tree is only used for easily retrieving the follow-states of a state
139        var phrase = new Sequence(n.phrase);
140        char nt = phrase.FirstNonTerminal;
141
142        int maxLenOfReplacement = maxLen - (phrase.Length - 1);
143        // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
144        Debug.Assert(maxLenOfReplacement > 0);
145
146        var alts = g.GetAlternatives(nt).Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement);
147
148        var children = new TreeNode[alts.Count()];
149        int idx = 0;
150        foreach (var alt in alts) {
151          // var newPhrase = new Sequence(phrase); // clone
152          // newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
153          // children[idx++] = new TreeNode(newPhrase.ToString(), alt);
154
155          // since we are not using a sequence later on we might directly transform the current sequence to a string and replace there
156          var phraseStr = phrase.ToString();
157          var sb = new StringBuilder(phraseStr);
158          sb.Remove(phrase.FirstNonTerminalIndex, 1).Insert(phrase.FirstNonTerminalIndex, alt.ToString());
159          children[idx++] = new TreeNode(sb.ToString(), alt);
160        }
161        n.children = children;
162      }
163      return n.children.Select(ch => ch.phrase);
164    }
165
166    private void DistributeReward(double reward) {
167      behaviourPolicy.UpdateReward(stateChain, reward);
168      greedyPolicy.UpdateReward(stateChain, reward);
169    }
170
171
172    private void Reset() {
173      behaviourPolicy.Reset();
174      greedyPolicy.Reset();
175      maxSearchDepth = 0;
176      bestQuality = 0.0;
177      tries = 0;
178      rootNode = new TreeNode(problem.Grammar.SentenceSymbol.ToString(), new ReadonlySequence("$"));
179    }
180
181    public bool Done() {
182      int selectedStateIdx;
183      return !behaviourPolicy.TrySelect(random, rootNode.phrase, GenerateFollowStates(rootNode), out selectedStateIdx);
184    }
185
186    #region introspection
187    public void PrintStats() {
188      Console.WriteLine("depth: {0,5} tries: {1,5} best phrase {2,50} bestQ {3:F3}", maxSearchDepth, tries, bestPhrase, bestQuality);
189
190      // use behaviour strategy to generate the currently prefered sentence
191      var policy = behaviourPolicy;
192
193      var n = rootNode;
194
195      while (n != null) {
196        var phrase = n.phrase;
197        Console.ForegroundColor = ConsoleColor.White;
198        Console.WriteLine("{0,-30}", phrase);
199        var children = n.children;
200        if (children == null || !children.Any()) break;
201        var values = children.Select(ch => policy.GetValue(ch.phrase));
202        var maxValue = values.Max();
203        if (maxValue == 0) maxValue = 1.0;
204
205        // write phrases
206        foreach (var ch in children) {
207          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
208          Console.Write(" {0,-4}", ch.phrase.Substring(Math.Max(0, ch.phrase.Length - 3), Math.Min(3, ch.phrase.Length)));
209        }
210        Console.WriteLine();
211
212        // write values
213        foreach (var ch in children) {
214          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
215          Console.Write(" {0:F2}", policy.GetValue(ch.phrase) * 10.0);
216        }
217        Console.WriteLine();
218
219        // write tries
220        foreach (var ch in children) {
221          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
222          Console.Write(" {0,4}", policy.GetTries(ch.phrase));
223        }
224        Console.WriteLine();
225        int selectedChildIdx;
226        if (!policy.TrySelect(random, phrase, children.Select(ch => ch.phrase), out selectedChildIdx)) {
227          break;
228        }
229        n = n.children[selectedChildIdx];
230      }
231
232      Console.ForegroundColor = ConsoleColor.White;
233      Console.WriteLine("-------------------");
234    }
235
236    private void SetColorForValue(double v) {
237      Console.ForegroundColor = ConsoleEx.ColorForValue(v);
238    }
239    #endregion
240 
241  }
242}
Note: See TracBrowser for help on using the repository browser.