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

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

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 : IProblem {

    private readonly IGrammar grammar;
    private readonly double correctReward;
    private readonly double incorrectReward;
    private readonly int _numCorrectPhrases;
    private readonly int sequenceLen;
    private readonly int alphabetSize;
    private readonly int phraseLen;
    private readonly bool phrasesAsSets;
    private readonly SortedSet<string>[] optimalPhrasesForPos;

    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.alphabetSize = alphabetSize;
      this.sequenceLen = sequenceLen;
      this.phraseLen = phraseLen;
      this._numCorrectPhrases = numCorrectPhrases;
      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[] { 'S' };
      var rules = terminalSymbols.Select(t => Tuple.Create('S', t.ToString()))
        .Concat(terminalSymbols.Select(t => Tuple.Create('S', t + "S")));

      this.grammar = 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;
    }

    private string CanonicalPhrase(string phrase) {
      if (phrasesAsSets) return string.Join("", phrase.OrderBy(ch => (byte)ch));
      else return phrase;
    }

    public string CanonicalRepresentation(string terminalPhrase) {
      if (phrasesAsSets) {
        var phrases = new List<string>();
        var numPhrases = terminalPhrase.Length / phraseLen;
        for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
          var sentenceIdx = phraseIdx * phraseLen;
          var phrase = terminalPhrase.Substring(sentenceIdx, phraseLen);
          phrase = CanonicalPhrase(phrase);
          phrases.Add(phrase);
        }

        return string.Join("", phrases);
      } else
        return terminalPhrase;
    }
  }
}