Changeset 11806 for branches/HeuristicLab.Problems.GrammaticalOptimization

Timestamp:

01/20/15 20:25:00 (9 years ago)

Author:

gkronber

Message:

#2283: separated value-states from done-states in GenericGrammarPolicy and removed disabling of actions from bandit policies

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization

Files:

• HeuristicLab.Algorithms.Bandits/BanditPolicies/ActiveLearningPolicy.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/BoltzmannExplorationPolicy.cs (modified) (1 diff)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/ChernoffIntervalEstimationPolicy.cs (modified) (3 diffs)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs (modified) (3 diffs)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/EpsGreedyPolicy.cs (modified) (1 diff)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/GenericThompsonSamplingPolicy.cs (modified) (1 diff)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs (modified) (1 diff)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/ModelPolicyActionInfo.cs (modified) (3 diffs)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/ModifiedUCTPolicy.cs (added)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/RandomPolicy.cs (modified) (1 diff)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs (modified) (4 diffs)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1Policy.cs (modified) (3 diffs)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs (modified) (1 diff)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs (modified) (1 diff)
• HeuristicLab.Algorithms.Bandits/BanditPolicies/UCTPolicy.cs (modified) (3 diffs)
• HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs (modified) (5 diffs)
• HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericTDPolicy.cs (added)
• HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj (modified) (3 diffs)
• HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs (modified) (1 diff)
• HeuristicLab.Algorithms.GrammaticalOptimization/ContextualMctsSampler.cs (deleted)
• HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj (modified) (1 diff)
• HeuristicLab.Algorithms.GrammaticalOptimization/MctsContextualSampler.cs (deleted)
• HeuristicLab.Algorithms.GrammaticalOptimization/MctsQLearningSampler.cs (deleted)
• HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs (deleted)
• HeuristicLab.Algorithms.GrammaticalOptimization/SequentialSearch.cs (modified) (1 diff)
• HeuristicLab.Algorithms.GrammaticalOptimization/TemporalDifferenceTreeSearchSampler.cs (deleted)
• HeuristicLab.Common/ConsoleEx.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs (modified) (2 diffs)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs (modified) (2 diffs)
• Main/Program.cs (modified) (8 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ActiveLearningPolicy.cs

@@ -11 +11 @@
     public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
       const double delta = 0.1;
-      int k = myActionInfos.Where(a => !a.Disabled).Count();
+      int k = myActionInfos.Count();
       var bestActions = new List<int>();
       var us = new List<double>();
@@ -20 +20 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         double u;

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BoltzmannExplorationPolicy.cs

@@ -37 +37 @@
 
       var w = from aInfo in myActionInfos
-              select aInfo.Disabled
-                ? 0.0
-                : Math.Exp(beta * valueFunction(aInfo));
+              select Math.Exp(beta * valueFunction(aInfo));
 
       var bestAction = Enumerable.Range(0, myActionInfos.Count()).SampleProportional(random, w);

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ChernoffIntervalEstimationPolicy.cs

@@ -21 +21 @@
       // select best
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
-      int k = myActionInfos.Count(a => !a.Disabled);
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int k = myActionInfos.Count();
+      int totalTries = myActionInfos.Sum(a => a.Tries);
       double bestQ = double.NegativeInfinity;
       var bestActions = new List<int>();
@@ -28 +28 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -46 +45 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs

@@ -9 +9 @@
   // stores information that is relevant for most of the policies
   public class DefaultPolicyActionInfo : IBanditPolicyActionInfo {
-    private double knownValue;
-    public bool Disabled { get { return Tries == -1; } }
     public double SumReward { get; private set; }
     public int Tries { get; private set; }
@@ -16 +14 @@
     public double Value {
       get {
-        if (Disabled) return knownValue;
-        else
           return Tries > 0 ? SumReward / Tries : 0.0;
       }
@@ -26 +22 @@
 
     public void UpdateReward(double reward) {
-      Debug.Assert(!Disabled);
-
       Tries++;
       SumReward += reward;
       MaxReward = Math.Max(MaxReward, reward);
     }
-    public void Disable(double reward) {
-      this.Tries = -1;
-      this.SumReward = 0.0;
-      this.knownValue = reward;
-    }
+
     public void Reset() {
       SumReward = 0.0;
       Tries = 0;
       MaxReward = 0.0;
-      knownValue = 0.0;
-    }
-    public void PrintStats() {
-      Console.WriteLine("avg reward {0,5:F2} disabled {1}", SumReward / Tries, Disabled);
     }
 

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EpsGreedyPolicy.cs

@@ -35 +35 @@
         foreach (var aInfo in myActionInfos) {
           aIdx++;
-          if (aInfo.Disabled) continue;
 
           var q = valueFunction(aInfo);

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GenericThompsonSamplingPolicy.cs

@@ -22 +22 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
-        //if (aInfo.Tries == 0) return aIdx;
         var q = aInfo.SampleExpectedReward(random);
         if (q > bestQ) {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs

@@ -39 +39 @@
       estimator.Reset();
     }
-
-    public void PrintStats() {
-      Console.WriteLine("avg reward {0,5:F2} disabled {1}", AvgReward, Disabled);
-    }
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModelPolicyActionInfo.cs

@@ -10 +10 @@
   public class ModelPolicyActionInfo : IBanditPolicyActionInfo {
     private readonly IModel model;
-    private double knownValue;
-    public bool Disabled { get { return Tries == -1; } }
     public double Value {
       get {
-        if (Disabled) return knownValue;
-        else
-          return model.SampleExpectedReward(new Random());
+        return model.SampleExpectedReward(new Random());
       }
     }
@@ -26 +22 @@
 
     public void UpdateReward(double reward) {
-      Debug.Assert(!Disabled);
       Tries++;
       model.Update(reward);
@@ -35 +30 @@
     }
 
-    public void Disable(double reward) {
-      this.Tries = -1;
-      this.knownValue = reward;
-    }
-
     public void Reset() {
       Tries = 0;
-      knownValue = 0.0;
       model.Reset();
     }
 
-    public void PrintStats() {
-      model.PrintStats();
-    }
-
     public override string ToString() {
-      return string.Format("disabled {0} model {1}", Disabled, model);
+      return string.Format("model {1}", model);
     }
   }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/RandomPolicy.cs

@@ -17 +17 @@
       return actionInfos
         .Select((aInfo, idx) => Tuple.Create(aInfo, idx))
-        .Where(p => !p.Item1.Disabled)
         .SelectRandom(random).Item2;
     }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs

@@ -28 +28 @@
       public int Tries { get; private set; }
       public int thresholdBin = 1;
-      private double knownValue;
 
       public double Value {
         get {
-          if (Disabled) return knownValue;
           if (Tries == 0.0) return 0.0;
           return rewardHistogram[thresholdBin] / (double)Tries;
         }
       }
-
-      public bool Disabled { get { return Tries == -1; } }
 
       public void UpdateReward(double reward) {
@@ -46 +42 @@
       }
 
-      public void Disable(double reward) {
-        this.knownValue = reward;
-        Tries = -1;
-      }
-
       public void Reset() {
         Tries = 0;
         thresholdBin = 1;
-        this.knownValue = 0.0;
         Array.Clear(rewardHistogram, 0, rewardHistogram.Length);
-      }
-
-      public void PrintStats() {
-        if (Tries >= 0) {
-          Console.Write("{0,6}", Tries);
-        } else {
-          Console.Write("{0,6}", "");
-        }
       }
 
@@ -101 +83 @@
       var bestActions = new List<int>();
       double bestQ = double.NegativeInfinity;
-      int k = myActionInfos.Count(a => !a.Disabled);
-      var totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int k = myActionInfos.Count();
+      var totalTries = myActionInfos.Sum(a => a.Tries);
       int aIdx = -1;
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -118 +99 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1Policy.cs

@@ -13 +13 @@
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
       double bestQ = double.NegativeInfinity;
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
 
       var bestActions = new List<int>();
@@ -19 +19 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -31 +30 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs

@@ -37 +37 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs

@@ -33 +33 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCTPolicy.cs

@@ -21 +21 @@
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
 
       int aIdx = -1;
@@ -27 +27 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -38 +37 @@
           bestQ = q;
           bestActions.Add(aIdx);
-        }
-        if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
@@ -9 +10 @@
 namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
   // this represents grammar policies that use one of the available bandit policies for state selection
-  public class GenericGrammarPolicy : IGrammarPolicy {
-    protected Dictionary<string, IBanditPolicyActionInfo> stateInfo; // stores the necessary information for bandit policies for each state 
-    private readonly bool useCanonicalState;
+  // any bandit policy can be used to select actions for states
+  // a separate datastructure is used to store visited states and to prevent revisiting of states
+  public sealed class GenericGrammarPolicy : IGrammarPolicy {
+    private Dictionary<string, IBanditPolicyActionInfo> stateInfo; // stores the necessary information for bandit policies for each state (=canonical phrase)
+    private HashSet<string> done;
+    private readonly bool useCanonicalPhrases;
     private readonly IProblem problem;
     private readonly IBanditPolicy banditPolicy;
 
-    public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalState = false) {
-      this.useCanonicalState = useCanonicalState;
+    public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalPhrases = false) {
+      this.useCanonicalPhrases = useCanonicalPhrases;
       this.problem = problem;
       this.banditPolicy = banditPolicy;
       this.stateInfo = new Dictionary<string, IBanditPolicyActionInfo>();
+      this.done = new HashSet<string>();
     }
+
+    private IBanditPolicyActionInfo[] activeAfterStates; // don't allocate each time
+    private int[] actionIndexMap; // don't allocate each time
 
     public bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
       // fail if all states are done (corresponding state infos are disabled)
-      if (afterStates.All(s => GetStateInfo(s).Disabled)) {
+      if (afterStates.All(s => Done(s))) {
         // fail because all follow states have already been visited => also disable the current state (if we can be sure that it has been fully explored)
+        MarkAsDone(curState);
 
-        GetStateInfo(curState).Disable(afterStates.Select(afterState => GetStateInfo(afterState).Value).Max());
         selectedStateIdx = -1;
         return false;
       }
 
-      selectedStateIdx = banditPolicy.SelectAction(random, afterStates.Select(s => GetStateInfo(s)));
+      // determine active actions (not done yet) and create an array to map the selected index back to original actions
+      if (activeAfterStates == null || activeAfterStates.Length < afterStates.Count()) {
+        activeAfterStates = new IBanditPolicyActionInfo[afterStates.Count()];
+        actionIndexMap = new int[afterStates.Count()];
+      }
+      var idx = 0; int originalIdx = 0;
+      foreach (var afterState in afterStates) {
+        if (!Done(afterState)) {
+          activeAfterStates[idx] = GetStateInfo(afterState);
+          actionIndexMap[idx] = originalIdx;
+          idx++;
+        }
+        originalIdx++;
+      }
+
+      selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))];
 
       return true;
     }
+
+
 
     private IBanditPolicyActionInfo GetStateInfo(string state) {
@@ -47 +72 @@
     }
 
-    public virtual void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
+    public void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
       foreach (var state in stateTrajectory) {
         GetStateInfo(state).UpdateReward(reward);
@@ -53 +78 @@
         // only the last state can be terminal
         if (problem.Grammar.IsTerminal(state)) {
-          GetStateInfo(state).Disable(reward);
+          MarkAsDone(state);
         }
       }
     }
 
-    public virtual void Reset() {
+
+    public void Reset() {
       stateInfo.Clear();
+      done.Clear();
     }
 
@@ -74 +101 @@
     }
 
-    protected string CanonicalState(string state) {
-      if (useCanonicalState) {
+    // the canonical states for the value function (banditInfos) and the done set must be distinguished
+    // sequences of different length could have the same canonical representation and can have the same value (banditInfo)
+    // however, if the canonical representation of a state is shorter than we must not mark the canonical state as done when all possible derivations from the initial state have been explored
+    // eg. in the ant problem the canonical representation for ...lllA is ...rA
+    // even though all possible derivations (of limited length) of lllA have been visited we must not mark the state rA as done
+    private void MarkAsDone(string state) {
+      var s = CanonicalState(state);
+      // when the lengths of the canonical string and the original string are the same we also disable the actions
+      // always disable terminals
+      Debug.Assert(s.Length <= state.Length);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        Debug.Assert(!done.Contains(s));
+        done.Add(s);
+      } else {
+        // for non-terminals where the canonical string is shorter than the original string we can only disable the canonical representation for all states in the same level
+        Debug.Assert(!done.Contains(s + state.Length));
+        done.Add(s + state.Length); // encode the original length of the state, states in the same level of the tree are treated as equivalent
+      }
+    }
+
+    // symmetric to MarkDone
+    private bool Done(string state) {
+      var s = CanonicalState(state);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        return done.Contains(s);
+      } else {
+        // it is not necessary to visit states if the canonical representation has already been fully explored
+        if (done.Contains(s)) return true;
+        if (done.Contains(s + state.Length)) return true;
+        for (int i = 1; i < state.Length; i++) {
+          if (done.Contains(s + i)) return true;
+        }
+        return false;
+      }
+    }
+
+    private string CanonicalState(string state) {
+      if (useCanonicalPhrases) {
         return problem.CanonicalRepresentation(state);
       } else

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj

@@ -49 +49 @@
     <Compile Include="BanditPolicies\ChernoffIntervalEstimationPolicy.cs" />
     <Compile Include="BanditPolicies\ActiveLearningPolicy.cs" />
+    <Compile Include="BanditPolicies\ModifiedUCTPolicy.cs" />
     <Compile Include="BanditPolicies\DefaultPolicyActionInfo.cs" />
     <Compile Include="BanditPolicies\EpsGreedyPolicy.cs" />
@@ -66 +67 @@
     <Compile Include="Bandits\IBandit.cs" />
     <Compile Include="Bandits\TruncatedNormalBandit.cs" />
+    <Compile Include="GrammarPolicies\GenericTDPolicy.cs" />
     <Compile Include="GrammarPolicies\GenericGrammarPolicy.cs">
       <SubType>Code</SubType>
@@ -72 +74 @@
       <SubType>Code</SubType>
     </Compile>
-    <Compile Include="GrammarPolicies\TDPolicy.cs" />
     <Compile Include="GrammarPolicies\GrammarPolicy.cs" />
     <Compile Include="GrammarPolicies\IGrammarPolicy.cs" />

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs

@@ -1 +1 @@
 namespace HeuristicLab.Algorithms.Bandits {
   public interface IBanditPolicyActionInfo {
-    bool Disabled { get; }
+    //bool Disabled { get; }
     double Value { get; }
     int Tries { get; }
     void UpdateReward(double reward);
-    void Disable(double reward);
+    //void Disable(double reward);
     // reset causes the state of the action to be reinitialized (as after constructor-call)
     void Reset();
-    void PrintStats();
   }
 }

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

@@ -46 +46 @@
     <Compile Include="AlternativesContextSampler.cs" />
     <Compile Include="SequentialSearch.cs" />
-    <Compile Include="TemporalDifferenceTreeSearchSampler.cs" />
     <Compile Include="ExhaustiveRandomFirstSearch.cs" />
-    <Compile Include="MctsContextualSampler.cs">
-      <SubType>Code</SubType>
-    </Compile>
-    <Compile Include="MctsSampler.cs" />
     <Compile Include="ExhaustiveDepthFirstSearch.cs" />
     <Compile Include="ExhaustiveBreadthFirstSearch.cs" />

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

@@ -77 +77 @@
           tries++;
           var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
+          if (double.IsNaN(quality)) quality = 0.0;
           Debug.Assert(quality >= 0 && quality <= 1.0);
           DistributeReward(quality);

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ConsoleEx.cs

@@ -49 +49 @@
       double startGreen = -1.41;
       double endGreen = 1.41;
-      
+
       double startBlue = -3;
       double endBlue = 1;
-      
+
       double startAlpha = 0;
-      double endAlpha =0;
+      double endAlpha = 0;
 
       // fire

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs

@@ -15 +15 @@
     private const string grammarString = @"
         G(E):
-        E -> V | V+E | V-E | V*E | (E)
+        E -> V | V+E | V-E | V*E | V/E | (E)
         V -> <variables>
         ";

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs

@@ -9 +9 @@
     IGrammar Grammar { get; }
     double Evaluate(string sentence);
-    string CanonicalRepresentation(string terminalPhrase);
+    string CanonicalRepresentation(string terminalPhrase); // canonical state must use correct syntax (must be a valid input for evaluate)
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs

@@ -115 +115 @@
     public string CanonicalRepresentation(string terminalPhrase) {
       if (phrasesAsSets) {
-        var phrases = new List<string>();
+        var sb = new StringBuilder();
         var numPhrases = terminalPhrase.Length / phraseLen;
         for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
@@ -121 +121 @@
           var phrase = terminalPhrase.Substring(sentenceIdx, phraseLen);
           phrase = CanonicalPhrase(phrase);
-          phrases.Add(phrase);
+          sb.Append(phrase);
         }
 
         var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
         remainder = CanonicalPhrase(remainder);
-        phrases.Add(remainder);
+        sb.Append(remainder);
 
-        return string.Join("", phrases);
+        return sb.ToString();
       } else
         return terminalPhrase;

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs

@@ -32 +32 @@
       // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
       Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
-      return regex.Matches(sentence.ToString()).Count;
+      return regex.Matches(sentence).Count;
     }
     public string CanonicalRepresentation(string terminalPhrase) {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs

@@ -111 +111 @@
         canonicalPhrase = sb.ToString();
       } while (canonicalPhrase != oldPhrase);
-      sb.Append(terminalPhrase.Length - canonicalPhrase.Length);
       return sb.ToString();
     }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs

@@ -92 +92 @@
 
         sb.Append(CanonicalTerm(terms[terms.Length - 1]));
-        sb.Append(phrase.Length - sb.Length);
         canonicalPhrase = sb.ToString();
         canonicalPhraseCache.Add(phrase, canonicalPhrase);
@@ -109 +108 @@
         var sb = new StringBuilder(chars.Length);
         // we want to have the up-case characters last
-        for (int i = chars.Length - 1; i >= 0; i--) {
-          if (chars[i] != '*') sb.Append(chars[i]);
+        for (int i = chars.Length - 1; i > 0; i--) {
+          if (chars[i] != '*') {
+            sb.Append(chars[i]);
+            if (chars[i - 1] != '*') sb.Append('*');
+          }
         }
+        if (chars[0] != '*') sb.Append(chars[0]); // last term
         canonicalTerm = sb.ToString();
         canonicalTermDictionary.Add(term, canonicalTerm);

branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs

@@ -24 +24 @@
       CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
 
-      //RunDemo();
-      RunGridTest();
+      RunDemo();
+      //RunGridTest();
     }
 
@@ -61 +61 @@
          () => new UCTPolicy( 5),
          () => new UCTPolicy( 10),
+         () => new ModifiedUCTPolicy(0.01),
+         () => new ModifiedUCTPolicy(0.05),
+         () => new ModifiedUCTPolicy(0.1),
+         () => new ModifiedUCTPolicy(0.5),
+         () => new ModifiedUCTPolicy(1),
+         () => new ModifiedUCTPolicy(2),
+         () => new ModifiedUCTPolicy( 5),
+         () => new ModifiedUCTPolicy( 10),
          () => new UCB1Policy(), 
          () => new UCB1TunedPolicy(), 
@@ -161 +169 @@
 
     private static void RunDemo() {
-      // TODO: move problem instances into a separate folder
       // TODO: implement bridge to HL-GP 
       // TODO: unify MCTS, TD and ContextMCTS Solvers (stateInfos)
@@ -170 +177 @@
       // TODO: warum funktioniert die alte Implementierung von GaussianThompson besser fÃŒr SantaFe als neue? Siehe Vergleich: alte vs. neue implementierung GaussianThompsonSampling
       // TODO: why does GaussianThompsonSampling work so well with MCTS for the artificial ant problem?
-      // TODO: wie kann ich sampler noch vergleichen bzw. was kann man messen um die qualitÀt des samplers abzuschÀtzen (bis auf qualitÀt und iterationen bis zur besten lösung) => ziel schnellere iterationen zu gutem ergebnis
       // TODO: research thompson sampling for max bandit?
       // TODO: ausfÃŒhrlicher test von strategien fÃŒr numCorrectPhrases-armed max bandit
@@ -192 +198 @@
 
 
-      var problem = new RoyalSequenceProblem(random, 10, 30, 2, 1, 0);
+      //var problem = new RoyalSequenceProblem(random, 10, 30, 2, 1, 0);
       //var phraseLen = 3;
       //var numPhrases = 5;
@@ -218 +224 @@
       //var problem = new SymbolicRegressionPoly10Problem();
 
-      //var problem = new SantaFeAntProblem();
+      var problem = new SantaFeAntProblem();
       //var problem = new SymbolicRegressionProblem("Tower"); 
       //var problem = new PalindromeProblem();
@@ -227 +233 @@
       //var alg = new MctsSampler(problem, 23, random, 0, new BoltzmannExplorationPolicy(100));
       //var alg = new MctsSampler(problem, 23, random, 0, new EpsGreedyPolicy(0.1));
-      var alg = new SequentialSearch(problem, 30, random, 0,
-        new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericGrammarPolicy(problem, new EpsGreedyPolicy(0.1), true));
+      //var alg = new SequentialSearch(problem, 23, random, 0,
+      //  new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericGrammarPolicy(problem, new ModifiedUCTPolicy(0.1), true));
+      var alg = new SequentialSearch(problem, 17, random, 0,
+        new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericTDPolicy(problem, true));
       //var alg = new MctsQLearningSampler(problem, sentenceLen, random, 0, null);
       //var alg = new MctsQLearningSampler(problem, 30, random, 0, new EpsGreedyPolicy(0.2));
@@ -248 +256 @@
         globalStatistics.AddSentence(sentence, quality);
         if (iterations % 1000 == 0) {
-          if (iterations % 1000 == 0) Console.Clear();
+          if (iterations % 10000 == 0) Console.Clear();
           Console.SetCursorPosition(0, 0);
           alg.PrintStats();