source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs @ 12099

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using HeuristicLab.Common;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;

namespace HeuristicLab.Problems.GrammaticalOptimization {
  // must find one of numCorrectPhrases*sequenceLen sequences where the quality of a sequence is the length of the subsequence containing only correct _phrases_ (of length phraseLen) and starting at the first position
  // compared to the RoyalSequence problem this problem is harder because the number of different phrases starting at a position is much larger than the number of symbols (grows exponentially with the phrase-length)
  // if phraseLen = 1 this is the same as the RoyalSequence problem
  // parameters
  // - alphabetSize: number of different symbols (max=26)
  // - phraseLen: the length of a phrase in number of symbols
  // - sequenceLen: the number of phrases in the correct subsequence (total sequence length is n * phraseLen
  // - numCorrectPhrases: the number of correct phrases starting at each position
  // - phrasesAsSets: switch to determine if the ordering of symbols within a phrase is relevant
  // 
  // this problem should be hard for GP and easy for MCTS (TD should not have an advantage compared to MCTS)
  // for phraseLen > 1 this should be harder than RoyalSymbolProblem
  // when phrases are symbol sets instead of sequences then value-estimation routines should be better (TD)
  public class RoyalPhraseSequenceProblem : ISymbolicExpressionTreeProblem {

    private readonly IGrammar grammar;
    private readonly double correctReward;
    private readonly double incorrectReward;
    private readonly int sequenceLen;
    private readonly int phraseLen;
    private readonly bool phrasesAsSets;
    private readonly SortedSet<string>[] optimalPhrasesForPos;
    public string Name { get { return "RoyalPhraseSequence"; } }
    public RoyalPhraseSequenceProblem(Random rand, int alphabetSize, int sequenceLen, int phraseLen = 1, int numCorrectPhrases = 1, double correctReward = 1.0, double incorrectReward = 0.0, bool phrasesAsSets = false) {
      if (alphabetSize <= 0 || alphabetSize > 26) throw new ArgumentException();
      if (sequenceLen <= 0) throw new ArgumentException();
      if (numCorrectPhrases < 1 || numCorrectPhrases > alphabetSize) throw new ArgumentException();
      if (phraseLen < 1) throw new ArgumentException();
      if (correctReward <= incorrectReward) throw new ArgumentException();

      this.sequenceLen = sequenceLen;
      this.phraseLen = phraseLen;
      this.correctReward = correctReward;
      this.incorrectReward = incorrectReward;
      this.phrasesAsSets = phrasesAsSets;

      var sentenceSymbol = 'S';
      var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray();
      var nonTerminalSymbols = new char[] { sentenceSymbol };

      {
        // create grammar
        // S -> a..z | aS .. zS
        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
          .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString())));

        this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
      }
      {
        // create grammar for tree-based GP
        // S -> a..z | SS
        var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
          .Concat(new Tuple<char, string>[] { Tuple.Create(sentenceSymbol, sentenceSymbol.ToString() + sentenceSymbol) });

        this.TreeBasedGPGrammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
      }

      this.optimalPhrasesForPos = new SortedSet<string>[sequenceLen];
      for (int i = 0; i < sequenceLen; i++) {
        optimalPhrasesForPos[i] = new SortedSet<string>();
        for (int j = 0; j < numCorrectPhrases; j++) {
          string phrase = "";
          do {
            for (int l = 0; l < phraseLen; l++) {
              phrase += terminalSymbols.SelectRandom(rand);
            }
            phrase = CanonicalPhrase(phrase);
          } while (optimalPhrasesForPos[i].Contains(phrase)); // don't allow duplicate phrases
          optimalPhrasesForPos[i].Add(phrase);
        }
      }

      Debug.Assert(Evaluate(BestKnownSolution) / BestKnownQuality(phraseLen * sequenceLen) == 1.0);
    }

    public double BestKnownQuality(int maxLen) {
      return Math.Min(maxLen / phraseLen, sequenceLen) * correctReward; // integer division
    }

    public string BestKnownSolution {
      get {
        string solution = "";
        for (int i = 0; i < sequenceLen; i++) {
          solution += optimalPhrasesForPos[i].First();
        }
        return solution;
      }
    }

    public IGrammar Grammar {
      get { return grammar; }
    }

    public double Evaluate(string sentence) {
      // 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)));
      // as long as only correct symbols are found we increase the reward by +1
      // on the first incorrect symbol we return
      var reward = 0.0;
      for (int i = 0; i < Math.Min(sentence.Length / phraseLen, sequenceLen); i++) {
        var canonicalPhrase = CanonicalPhrase(sentence.Substring(i * phraseLen, phraseLen));
        if (optimalPhrasesForPos[i].Contains(canonicalPhrase)) {
          reward += correctReward;
        } else {
          // alternatively reduce reward by number of remaining phrases
          return Math.Max(0.0, reward + incorrectReward * (sentence.Length / phraseLen - i));
          // stop on first incorrect symbol and return reward
          //return reward;
        }
      }
      return reward;
    }

    // TODO: cache canonical phrases in most-recently used dictionary for increased performance (see symbolicregressionpoly10problem)
    private string CanonicalPhrase(string phrase) {
      if (phrasesAsSets) return string.Join("", phrase.OrderBy(ch => (byte)ch));
      else return phrase;
    }

    public string CanonicalRepresentation(string phrase) {
      if (phrasesAsSets) {
        var sb = new StringBuilder();
        var numPhrases = phrase.Length / phraseLen;
        for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
          var sentenceIdx = phraseIdx * phraseLen;
          var subphrase = phrase.Substring(sentenceIdx, phraseLen);
          subphrase = CanonicalPhrase(subphrase);
          sb.Append(subphrase);
        }

        var remainder = phrase.Substring(numPhrases * phraseLen, phrase.Length - (numPhrases * phraseLen));
        remainder = CanonicalPhrase(remainder);
        sb.Append(remainder);

        return sb.ToString();
      } else
        return phrase;
    }

    public IEnumerable<Feature> GetFeatures(string phrase) {
      throw new NotImplementedException();
    }

    public IGrammar TreeBasedGPGrammar { get; private set; }
    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
      var sb = new StringBuilder();
      foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) {
        if (s.Symbol.Name == "S") continue;
        sb.Append(s.Symbol.Name);
      }
      return sb.ToString();
    }
  }
}