source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesContextSampler.cs @ 11727

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using HeuristicLab.Algorithms.Bandits;
using HeuristicLab.Common;
using HeuristicLab.Problems.GrammaticalOptimization;

namespace HeuristicLab.Algorithms.GrammaticalOptimization {
  public class AlternativesContextSampler {
    public event Action<string, double> FoundNewBestSolution;
    public event Action<string, double> SolutionEvaluated;

    private readonly int maxLen;
    private readonly IProblem problem;
    private readonly Random random;
    private readonly int contextLen;

    public AlternativesContextSampler(IProblem problem, int maxLen) {
      this.maxLen = maxLen;
      this.problem = problem;
      this.random = new Random(31415);
      this.contextLen = 25;
    }

    public void Run(int maxIterations) {
      double bestQuality = double.MinValue;
      InitPolicies(problem.Grammar);
      for (int i = 0; i < maxIterations; i++) {
        var sentence = SampleSentence(problem.Grammar);
        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 
        DistributeReward(quality);

        RaiseSolutionEvaluated(sentence, quality);

        if (quality > bestQuality) {
          bestQuality = quality;
          RaiseFoundNewBestSolution(sentence, quality);
        }
      }
    }


    private Dictionary<string, IPolicy> ntPolicy;
    private List<Tuple<string, int>> updateChain;
    private void InitPolicies(IGrammar grammar) {
      this.ntPolicy = new Dictionary<string, IPolicy>();
      this.updateChain = new List<Tuple<string, int>>();
    }

    private string SampleSentence(IGrammar grammar) {
      updateChain.Clear();
      return CompleteSentence(grammar, grammar.SentenceSymbol.ToString());
    }

    public string CompleteSentence(IGrammar g, string phrase) {
      if (phrase.Length > maxLen) throw new ArgumentException();
      if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
      bool done = phrase.All(g.IsTerminal); // terminal phrase means we are done
      while (!done) {
        int ntIdx; char nt;
        Grammar.FindFirstNonTerminal(g, phrase, out nt, out ntIdx);

        int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
        Debug.Assert(maxLenOfReplacement > 0);

        var alts = g.GetAlternatives(nt);
        string selectedAlt;
        // if the choice is restricted then one of the allowed alternatives is selected randomly
        if (alts.Any(alt => g.MinPhraseLength(alt) > maxLenOfReplacement)) {
          var allowedAlts = alts.Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement);
          Debug.Assert(allowedAlts.Any());
          // replace nt with random alternative
          selectedAlt = allowedAlts.SelectRandom(random);
        } else {
          // all alts are allowed => select using bandit policy
          var startIdx = Math.Max(0, ntIdx - contextLen);
          var endIdx = Math.Min(startIdx + contextLen, ntIdx);
          var lft = phrase.Substring(startIdx, endIdx - startIdx + 1);
          lft = problem.Hash(lft);
          if (!ntPolicy.ContainsKey(lft)) {
            ntPolicy.Add(lft, new UCB1TunedPolicy(g.GetAlternatives(nt).Count()));
          }
          var selectedAltIdx = ntPolicy[lft].SelectAction();
          selectedAlt = alts.ElementAt(selectedAltIdx);
          updateChain.Add(Tuple.Create(lft, selectedAltIdx));
        }

        // replace nt with alt
        phrase = phrase.Remove(ntIdx, 1);
        phrase = phrase.Insert(ntIdx, selectedAlt);

        done = phrase.All(g.IsTerminal); // terminal phrase means we are done
      }
      return phrase;
    }

    private void DistributeReward(double reward) {
      foreach (var e in updateChain) {
        var lft = e.Item1;
        var action = e.Item2;
        ntPolicy[lft].UpdateReward(action, reward);
      }
    }

    private void RaiseSolutionEvaluated(string sentence, double quality) {
      var handler = SolutionEvaluated;
      if (handler != null) handler(sentence, quality);
    }
    private void RaiseFoundNewBestSolution(string sentence, double quality) {
      var handler = FoundNewBestSolution;
      if (handler != null) handler(sentence, quality);
    }
  }
}