Changeset 11793 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization

Timestamp:

01/18/15 18:24:58 (9 years ago)

Author:

gkronber

Message:

#2283 fixed compile errors and refactoring

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization

Files:

• ContextualMctsSampler.cs (added)
• ExhaustiveBreadthFirstSearch.cs (modified) (1 diff)
• MctsQLearningSampler.cs (added)
• RandomSearch.cs (modified) (1 diff)
• SequentialSearch.cs (modified) (9 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs

@@ -42 +42 @@
 
         char nt = phrase.FirstNonTerminal;
-        int ntIdx;
 
         var alts = grammar.GetAlternatives(nt);

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs

@@ -1 +1 @@
 using System;
-using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
 using HeuristicLab.Problems.GrammaticalOptimization;
 

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialSearch.cs

@@ -24 +24 @@
   // 3) Collect reward and update policy (feedback: state of visited rewards from step 2)
   public class SequentialSearch {
+    // only for storing states so that it is not necessary to allocate new state strings whenever we select a follow state using the policy
+    private class TreeNode {
+      public int randomTries;
+      public string phrase;
+      public Sequence alternative;
+      public TreeNode[] children;
+
+      public TreeNode(string phrase, Sequence alternative) {
+        this.alternative = alternative;
+        this.phrase = phrase;
+      }
+    }
+
 
     public event Action<string, double> FoundNewBestSolution;
@@ -34 +47 @@
     private readonly IGrammarPolicy behaviourPolicy;
     private readonly IGrammarPolicy greedyPolicy;
+    private TreeNode rootNode;
+
+    private int tries;
     private int maxSearchDepth;
 
     private double bestQuality;
     private string bestPhrase;
-    private int tries;
-    private readonly List<ReadonlySequence> stateChain;
+    private readonly List<string> stateChain;
 
     public SequentialSearch(IProblem problem, int maxLen, Random random, int randomTries, IGrammarPolicy behaviourPolicy) {
@@ -47 +62 @@
       this.randomTries = randomTries;
       this.behaviourPolicy = behaviourPolicy;
-      this.greedyPolicy = new GreedyPolicy(problem, false);
-      this.stateChain = new List<ReadonlySequence>();
-      this.cache = new Dictionary<ReadonlySequence, ReadonlySequence[]>();
+      this.greedyPolicy = new GenericGrammarPolicy(problem, new EpsGreedyPolicy(0.0), false);
+      this.stateChain = new List<string>();
     }
 
     public void Run(int maxIterations) {
       bestQuality = double.MinValue;
-      //InitPolicies(problem.Grammar);
       Reset();
 
@@ -79 +92 @@
 
 
-    private ReadonlySequence SampleSentence(IGrammar grammar) {
-      ReadonlySequence phrase;
+    private Sequence SampleSentence(IGrammar grammar) {
+      Sequence phrase;
       do {
         stateChain.Clear();
-        phrase = new ReadonlySequence(grammar.SentenceSymbol);
+        phrase = new Sequence(rootNode.phrase);
         //var startPhrase = new Sequence("a*b+c*d+e*f+E");
       } while (!Done() && !TryCompleteSentence(grammar, ref phrase));
@@ -89 +102 @@
     }
 
-    private bool TryCompleteSentence(IGrammar g, ref ReadonlySequence phrase) {
+    private bool TryCompleteSentence(IGrammar g, ref Sequence phrase) {
       if (phrase.Length > maxLen) throw new ArgumentException();
       if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
       var curDepth = 0;
-
-      stateChain.Add(phrase);
+      var n = rootNode;
+      stateChain.Add(n.phrase);
+
       while (!phrase.IsTerminal) {
 
-        var newPhrases = GenerateFollowStates(g, phrase);
-        
-        throw new NotImplementedException(); // TODO: reintroduce random-trie checking once the tree of all states has been reintroduced
+
         //if (n.randomTries < randomTries) {
         //  n.randomTries++;
-        //  treeDepth = Math.Max(treeDepth, curDepth);
-        //  lastNode = n;
-        //  return g.CompleteSentenceRandomly(random, phrase, maxLen);
+        //  curDepth = Math.Max(curDepth, curDepth);
+        //  g.CompleteSentenceRandomly(random, phrase, maxLen);
+        //  return true;
         //} else {
-
-
-          // => select using bandit policy
-          // failure means we simply restart
-          if (!behaviourPolicy.TrySelect(random, phrase, newPhrases, out phrase)) {
-            return false;
-          }
-        // }
-        stateChain.Add(phrase);
+        // => select using bandit policy
+        // failure means we simply restart
+        GenerateFollowStates(n); // creates child nodes for node n
+
+        int selectedChildIdx;
+        if (!behaviourPolicy.TrySelect(random, n.phrase, n.children.Select(ch => ch.phrase), out selectedChildIdx)) {
+          return false;
+        }
+        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, n.children[selectedChildIdx].alternative);
+
+        // prepare for next iteration
+        n = n.children[selectedChildIdx];
+        stateChain.Add(n.phrase);
         curDepth++;
+        //}
       } // while
 
@@ -123 +140 @@
 
 
-    private readonly Dictionary<ReadonlySequence, ReadonlySequence[]> cache;
-    private IEnumerable<ReadonlySequence> GenerateFollowStates(IGrammar g, ReadonlySequence phrase) {
-      throw new NotImplementedException();
-      // TODO: Replace caching by a tree of all states. tree is only used for easily retrieving the follow-states of a state
-      ReadonlySequence[] follow;
-      //if (!cache.TryGetValue(phrase, out follow)) {
+    private IEnumerable<string> GenerateFollowStates(TreeNode n) {
+      // create children on the first visit
+      if (n.children == null) {
+        var g = problem.Grammar;
+        // tree is only used for easily retrieving the follow-states of a state
+        var phrase = new Sequence(n.phrase);
         char nt = phrase.FirstNonTerminal;
 
@@ -137 +154 @@
         var alts = g.GetAlternatives(nt).Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement);
 
-        follow = new ReadonlySequence[alts.Count()];
+        var children = new TreeNode[alts.Count()];
         int idx = 0;
         foreach (var alt in alts) {
           var newPhrase = new Sequence(phrase); // clone
           newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
-          follow[idx++] = new ReadonlySequence(newPhrase);
-        }
-      //  cache[phrase] = follow;
-      //}
-      return follow;
+          children[idx++] = new TreeNode(newPhrase.ToString(), alt);
+        }
+        n.children = children;
+      }
+      return n.children.Select(ch => ch.phrase);
     }
 
@@ -161 +178 @@
       bestQuality = 0.0;
       tries = 0;
-      cache.Clear();
+      rootNode = new TreeNode(problem.Grammar.SentenceSymbol.ToString(), new ReadonlySequence("$"));
     }
 
     public bool Done() {
-      var g = problem.Grammar;
-      var startState = new ReadonlySequence(g.SentenceSymbol);
-      var follow = GenerateFollowStates(g, startState);
-      ReadonlySequence selectedState;
-      return !behaviourPolicy.TrySelect(random, startState, follow, out selectedState);
+      int selectedStateIdx;
+      return !behaviourPolicy.TrySelect(random, rootNode.phrase, GenerateFollowStates(rootNode), out selectedStateIdx);
     }
 
@@ -176 +190 @@
       Console.WriteLine("depth: {0,5} tries: {1,5} best phrase {2,50} bestQ {3:F3}", maxSearchDepth, tries, bestPhrase, bestQuality);
 
-      // use greedy strategy to generate the currently prefered sentence
-      var phrase = new ReadonlySequence(problem.Grammar.SentenceSymbol);
+      // use behaviour strategy to generate the currently prefered sentence
       var policy = behaviourPolicy;
-      while (!phrase.IsTerminal) {
+
+      var n = rootNode;
+
+      while (n != null) {
+        var phrase = n.phrase;
         Console.ForegroundColor = ConsoleColor.White;
         Console.WriteLine("{0,-30}", phrase);
-        var newPhrases = GenerateFollowStates(problem.Grammar, phrase);
-        if (!newPhrases.Any()) break;
-        var values = newPhrases.Select(p => policy.GetValue(p));
+        var children = n.children;
+        if (children == null || !children.Any()) break;
+        var values = children.Select(ch => policy.GetValue(ch.phrase));
         var maxValue = values.Max();
         if (maxValue == 0) maxValue = 1.0;
 
         // write phrases
-        foreach (var p in newPhrases) {
-          SetColorForValue(policy.GetValue(p) / maxValue);
-          Console.Write(" {0,-4}", p.Subsequence(Math.Max(0, p.Length - 3), Math.Min(3, p.Length)));
+        foreach (var ch in children) {
+          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
+          Console.Write(" {0,-4}", ch.phrase.Substring(Math.Max(0, ch.phrase.Length - 3), Math.Min(3, ch.phrase.Length)));
         }
         Console.WriteLine();
 
         // write values
-        foreach (var p in newPhrases) {
-          SetColorForValue(policy.GetValue(p) / maxValue);
-          Console.Write(" {0:F2}", policy.GetValue(p) * 10.0);
+        foreach (var ch in children) {
+          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
+          Console.Write(" {0:F2}", policy.GetValue(ch.phrase) * 10.0);
         }
         Console.WriteLine();
 
         // write tries
-        foreach (var p in newPhrases) {
-          SetColorForValue(policy.GetValue(p) / maxValue);
-          Console.Write(" {0,4}", policy.GetTries(p));
+        foreach (var ch in children) {
+          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
+          Console.Write(" {0,4}", policy.GetTries(ch.phrase));
         }
         Console.WriteLine();
-        if (!policy.TrySelect(random, phrase, newPhrases, out phrase)) {
+        int selectedChildIdx;
+        if (!policy.TrySelect(random, phrase, children.Select(ch => ch.phrase), out selectedChildIdx)) {
           break;
         }
+        n = n.children[selectedChildIdx];
       }