Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericFunctionApproximationGrammarPolicy.cs @ 12509

Last change on this file since 12509 was 12027, checked in by gkronber, 10 years ago

#2283: comment regarding the last commit

File size: 7.3 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4using System.Linq;
5using System.Runtime.ExceptionServices;
6using System.Text;
7using System.Text.RegularExpressions;
8using System.Threading;
9using System.Threading.Tasks;
10using HeuristicLab.Common;
11using HeuristicLab.Problems.GrammaticalOptimization;
12
13namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
14  public sealed class GenericFunctionApproximationGrammarPolicy : IGrammarPolicy {
15    private Dictionary<string, double> featureWeigths; // stores the necessary information for bandit policies for each state (=canonical phrase)
16    private Dictionary<string, int> featureTries;
17    private HashSet<string> done;
18    private readonly bool useCanonicalPhrases;
19    private readonly IProblem problem;
20
21
22
23    public GenericFunctionApproximationGrammarPolicy(IProblem problem, bool useCanonicalPhrases = false) {
24      this.useCanonicalPhrases = useCanonicalPhrases;
25      this.problem = problem;
26      this.featureWeigths = new Dictionary<string, double>();
27      this.featureTries = new Dictionary<string, int>();
28      this.done = new HashSet<string>();
29    }
30
31    private double[] activeAfterStates; // don't allocate each time
32    private int[] actionIndexMap; // don't allocate each time
33
34    public bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
35      // fail if all states are done (corresponding state infos are disabled)
36      if (afterStates.All(s => Done(s))) {
37        // 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)
38        MarkAsDone(curState);
39
40        selectedStateIdx = -1;
41        return false;
42      }
43
44      // determine active actions (not done yet) and create an array to map the selected index back to original actions
45      if (activeAfterStates == null || activeAfterStates.Length < afterStates.Count()) {
46        activeAfterStates = new double[afterStates.Count()];
47        actionIndexMap = new int[afterStates.Count()];
48      }
49      var maxIdx = 0; int originalIdx = 0;
50      foreach (var afterState in afterStates) {
51        if (!Done(afterState)) {
52          activeAfterStates[maxIdx] = 0.0;
53          actionIndexMap[maxIdx] = originalIdx;
54
55
56          activeAfterStates[maxIdx] = GetValue(afterState);
57
58          maxIdx++;
59        }
60        originalIdx++;
61      }
62     
63     
64      // TODO: policy should be a parameter of the function approximation policy
65      if (random.NextDouble() < 0.2) {
66        selectedStateIdx = actionIndexMap[random.Next(maxIdx)];
67      } else {
68        // find max
69        var bestQ = double.NegativeInfinity;
70        var bestIdxs = new List<int>();
71        for (int i = 0; i < maxIdx; i++) {
72          if (activeAfterStates[i] > bestQ) {
73            bestIdxs.Clear();
74            bestIdxs.Add(i);
75            bestQ = activeAfterStates[i];
76          } else if (activeAfterStates[i].IsAlmost(bestQ)) {
77            bestIdxs.Add(i);
78          }
79        }
80        selectedStateIdx = actionIndexMap[bestIdxs[random.Next(bestIdxs.Count)]];
81      }
82     
83      return true;
84    }
85
86
87    public void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
88      foreach (var state in stateTrajectory) {
89        UpdateWeights(state, reward);
90
91        // only the last state can be terminal
92        if (problem.Grammar.IsTerminal(state)) {
93          MarkAsDone(state);
94        }
95      }
96    }
97
98
99    private IEnumerable<KeyValuePair<string, double>> Values {
100      get { return featureWeigths.OrderByDescending(p => p.Value); }
101    }
102
103    public void Reset() {
104      featureWeigths.Clear();
105      done.Clear();
106    }
107
108    public int GetTries(string state) {
109      return 0;
110    }
111
112    public int GetFeatureTries(string featureId) {
113      int t;
114      if (featureTries.TryGetValue(featureId, out t)) {
115        return t;
116      } else return 0;
117    }
118
119    public double GetValue(string state) {
120      return problem.GetFeatures(state).Sum(feature => GetWeight(feature));
121    }
122
123    private double GetWeight(Feature feature) {
124      double w;
125      if (featureWeigths.TryGetValue(feature.Id, out w)) return w * feature.Value;
126      else return 0.0;
127    }
128    private void UpdateWeights(string state, double reward) {
129      double delta = reward - GetValue(state);
130      foreach (var feature in problem.GetFeatures(state)) {
131        //featureTries[feature.Id] = GetFeatureTries(feature.Id) + 1;
132        //Debug.Assert(GetFeatureTries(feature.Id) >= 1);
133        //double alpha = 1.0 / GetFeatureTries(feature.Id);
134        //alpha = Math.Max(alpha, 0.001);
135       
136        // simple setting of constant alpha = 0.01 works very well for poly-10 (100% success rate for 20 runs within 40000 evaluations))
137        var alpha = 0.01;
138
139        double w;
140        if (!featureWeigths.TryGetValue(feature.Id, out w)) {
141          featureWeigths[feature.Id] = alpha * delta * feature.Value;
142        } else {
143          featureWeigths[feature.Id] += alpha * delta * feature.Value;
144        }
145      }
146    }
147
148
149
150    // the canonical states for the value function (banditInfos) and the done set must be distinguished
151    // sequences of different length could have the same canonical representation and can have the same value (banditInfo)
152    // 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
153    // eg. in the ant problem the canonical representation for ...lllA is ...rA
154    // even though all possible derivations (of limited length) of lllA have been visited we must not mark the state rA as done
155    private void MarkAsDone(string state) {
156      var s = CanonicalState(state);
157      // when the lengths of the canonical string and the original string are the same we also disable the actions
158      // always disable terminals
159      Debug.Assert(s.Length <= state.Length);
160      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
161        Debug.Assert(!done.Contains(s));
162        done.Add(s);
163      } else {
164        // 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
165        Debug.Assert(!done.Contains(s + state.Length));
166        done.Add(s + state.Length); // encode the original length of the state, states in the same level of the tree are treated as equivalent
167      }
168    }
169
170    // symmetric to MarkDone
171    private bool Done(string state) {
172      var s = CanonicalState(state);
173      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
174        return done.Contains(s);
175      } else {
176        // it is not necessary to visit states if the canonical representation has already been fully explored
177        if (done.Contains(s)) return true;
178        if (done.Contains(s + state.Length)) return true;
179        for (int i = 1; i < state.Length; i++) {
180          if (done.Contains(s + i)) return true;
181        }
182        return false;
183      }
184    }
185
186    private string CanonicalState(string state) {
187      if (useCanonicalPhrases) {
188        return problem.CanonicalRepresentation(state);
189      } else
190        return state;
191    }
192  }
193}
Note: See TracBrowser for help on using the repository browser.