Changeset 12893 for branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers

Timestamp:

08/24/15 13:56:27 (9 years ago)

Author:

gkronber

Message:

#2283: experiments on grammatical optimization algorithms (maxreward instead of avg reward, ...)

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers

Files:

• ExhaustiveRandomFirstSearch.cs (modified) (1 diff)
• RandomSearch.cs (modified) (1 diff)
• SequentialSearch.cs (modified) (9 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/ExhaustiveRandomFirstSearch.cs

@@ -13 +13 @@
     private readonly System.Collections.Generic.SortedList<double, Sequence> sortedList = new SortedList<double, Sequence>();
     private readonly IProblem problem;
-    private readonly Random random;
+    private readonly System.Random random;
 
-    public ExhaustiveRandomFirstSearch(IProblem problem, Random random, int maxLen) {
+    public ExhaustiveRandomFirstSearch(IProblem problem, System.Random random, int maxLen) {
       this.maxLen = maxLen;
       this.problem = problem;
-      this.random = new Random();
+      this.random = new System.Random();
     }
 

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/RandomSearch.cs

@@ -5 +5 @@
   public class RandomSearch : SolverBase {
     private readonly int maxLen;
-    private readonly Random random;
+    private readonly System.Random random;
     private readonly IProblem problem;
 
-    public RandomSearch(IProblem problem, Random random, int maxLen) {
+    public RandomSearch(IProblem problem, System.Random random, int maxLen) {
       this.maxLen = maxLen;
       this.random = random;

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/SequentialSearch.cs

@@ -6 +6 @@
 using System.Runtime.InteropServices;
 using System.Text;
+using System.Windows.Markup;
 using HeuristicLab.Algorithms.Bandits;
 using HeuristicLab.Algorithms.Bandits.BanditPolicies;
@@ -40 +41 @@
     private readonly int maxLen;
     private readonly IProblem problem;
-    private readonly Random random;
+    private readonly System.Random random;
     private readonly int randomTries;
     private readonly IGrammarPolicy behaviourPolicy;
@@ -51 +52 @@
     private readonly List<string> stateChain;
 
-    public SequentialSearch(IProblem problem, int maxLen, Random random, int randomTries, IGrammarPolicy behaviourPolicy) {
+    public SequentialSearch(IProblem problem, int maxLen, System.Random random, int randomTries, IGrammarPolicy behaviourPolicy) {
       this.maxLen = maxLen;
       this.problem = problem;
@@ -117 +118 @@
           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);
 
@@ -167 +170 @@
     }
 
+
+
     private void DistributeReward(double reward) {
       behaviourPolicy.UpdateReward(stateChain, reward);
     }
+
 
 
@@ -178 +184 @@
       bestQuality = 0.0;
       tries = 0;
+      //rootNode = new TreeNode("a*b+c*d+e*f+E", new ReadonlySequence("$"));
       rootNode = new TreeNode(problem.Grammar.SentenceSymbol.ToString(), new ReadonlySequence("$"));
     }
@@ -194 +201 @@
 
       var n = rootNode;
-
+      int lvl = 0;
       while (n != null) {
         var phrase = n.phrase;
         Console.ForegroundColor = ConsoleColor.White;
+        
+        if (lvl++ > 10) return;
+
         Console.WriteLine("{0,-30}", phrase);
         var children = n.children;
         if (children == null || !children.Any()) break;
-        var triesEnumerable = children.Select(ch => policy.GetTries(ch.phrase));
-        double maxTries = triesEnumerable.Where(v => !double.IsInfinity(v)).DefaultIfEmpty(1).Max();
-        maxTries = Math.Max(maxTries, 1.0);
+        var valuesEnumerable = children.Select(ch => policy.GetValue(ch.phrase));
+        double maxValue = valuesEnumerable.Where(v => !double.IsInfinity(v)).DefaultIfEmpty(0).Max();
+        maxValue = Math.Max(maxValue, 1.0);
         // write phrases
         foreach (var ch in children) {
-          SetColorForValue(policy.GetTries(ch.phrase) / maxTries);
+          //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)));
         }
@@ -213 +223 @@
         // write values
         foreach (var ch in children) {
-          SetColorForValue(policy.GetTries(ch.phrase) / maxTries);
+          //SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
           if (!double.IsInfinity(policy.GetValue(ch.phrase)))
             Console.Write(" {0:F2}", policy.GetValue(ch.phrase) * 10.0);
@@ -223 +233 @@
         // write tries
         foreach (var ch in children) {
-          SetColorForValue(policy.GetTries(ch.phrase) / maxTries);
+          //SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
           Console.Write(" {0,4}", policy.GetTries(ch.phrase));
         }
         Console.WriteLine();
-        int selectedChildIdx;
-        if (!policy.TrySelect(random, phrase, children.Select(ch => ch.phrase), out selectedChildIdx)) {
-          break;
-        }
+        var triesArr = valuesEnumerable.ToArray();
+        //var selectedChildIdx = Array.IndexOf(triesArr, triesArr.Max());
+        var valuesArr = children.Select(ch => policy.GetValue(ch.phrase)).ToArray();
+        int selectedChildIdx = Enumerable.Range(0, children.Length).OrderByDescending(i => valuesArr[i]).ThenByDescending(i => triesArr[i]).First();
+
+        //int selectedChildIdx;
+        //if (!policy.TrySelect(random, phrase, children.Select(ch => ch.phrase), out selectedChildIdx)) {
+        //  break;
+        //}
         n = n.children[selectedChildIdx];
       }