[11747] | 1 | using System;
|
---|
| 2 | using System.Collections.Generic;
|
---|
| 3 | using System.Diagnostics;
|
---|
| 4 | using System.Linq;
|
---|
| 5 | using System.Text;
|
---|
| 6 | using System.Text.RegularExpressions;
|
---|
| 7 | using HeuristicLab.Common;
|
---|
| 8 |
|
---|
| 9 | namespace HeuristicLab.Problems.GrammaticalOptimization {
|
---|
| 10 | // must find one of k*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
|
---|
| 11 | // 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)
|
---|
| 12 | // if phraseLen = 1 this is the same as the RoyalSequence problem
|
---|
| 13 | // parameters
|
---|
| 14 | // - alphabetSize: number of different symbols (max=26)
|
---|
| 15 | // - phraseLen: the length of a phrase in number of symbols
|
---|
| 16 | // - sequenceLen: the number of phrases in the correct subsequence (total sequence length is n * phraseLen
|
---|
| 17 | // - k: the number of correct phrases starting at each position
|
---|
| 18 | //
|
---|
| 19 | // this problem should be hard for GP and easy for MCTS (TD should not have an advantage compared to MCTS)
|
---|
| 20 | // for phraseLen > 1 this should be harder than RoyalSymbolProblem
|
---|
| 21 | public class RoyalPhraseSequenceProblem : IProblem {
|
---|
| 22 |
|
---|
| 23 | private readonly IGrammar grammar;
|
---|
| 24 | private readonly double correctReward;
|
---|
| 25 | private readonly double incorrectReward;
|
---|
| 26 | private readonly int k;
|
---|
| 27 | private readonly int sequenceLen;
|
---|
| 28 | private readonly int alphabetSize;
|
---|
| 29 | private readonly int phraseLen;
|
---|
| 30 | private readonly SortedSet<string>[] optimalPhrasesForPos;
|
---|
| 31 |
|
---|
| 32 | public RoyalPhraseSequenceProblem(Random rand, int alphabetSize, int sequenceLen, int phraseLen = 1, int k = 1, double correctReward = 1.0, double incorrectReward = 0.0) {
|
---|
| 33 | if (alphabetSize <= 0 || alphabetSize > 26) throw new ArgumentException();
|
---|
| 34 | if (sequenceLen <= 0) throw new ArgumentException();
|
---|
| 35 | if (k < 1 || k > alphabetSize) throw new ArgumentException();
|
---|
| 36 | if (phraseLen < 1) throw new ArgumentException();
|
---|
| 37 | if (correctReward <= incorrectReward) throw new ArgumentException();
|
---|
| 38 |
|
---|
| 39 | this.alphabetSize = alphabetSize;
|
---|
| 40 | this.sequenceLen = sequenceLen;
|
---|
| 41 | this.phraseLen = phraseLen;
|
---|
| 42 | this.k = k;
|
---|
| 43 | this.correctReward = correctReward;
|
---|
| 44 | this.incorrectReward = incorrectReward;
|
---|
| 45 | var sentenceSymbol = 'S';
|
---|
| 46 | var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray();
|
---|
| 47 | var nonTerminalSymbols = new char[] { 'S' };
|
---|
| 48 | var rules = terminalSymbols.Select(t => Tuple.Create('S', t.ToString()))
|
---|
| 49 | .Concat(terminalSymbols.Select(t => Tuple.Create('S', t + "S")));
|
---|
| 50 |
|
---|
| 51 | this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
|
---|
| 52 |
|
---|
| 53 | this.optimalPhrasesForPos = new SortedSet<string>[sequenceLen];
|
---|
| 54 | for (int i = 0; i < sequenceLen; i++) {
|
---|
| 55 | optimalPhrasesForPos[i] = new SortedSet<string>();
|
---|
| 56 | for (int j = 0; j < k; j++) {
|
---|
| 57 | string phrase = "";
|
---|
| 58 | do {
|
---|
| 59 | for (int l = 0; l < phraseLen; l++) {
|
---|
| 60 | phrase += terminalSymbols.SelectRandom(rand);
|
---|
| 61 | }
|
---|
| 62 | } while (optimalPhrasesForPos[i].Contains(phrase)); // don't allow duplicate phrases
|
---|
| 63 | optimalPhrasesForPos[i].Add(phrase);
|
---|
| 64 | }
|
---|
| 65 | }
|
---|
| 66 |
|
---|
| 67 | Debug.Assert(Evaluate(BestKnownSolution)/BestKnownQuality(phraseLen * sequenceLen) == 1.0);
|
---|
| 68 | }
|
---|
| 69 |
|
---|
| 70 | public double BestKnownQuality(int maxLen) {
|
---|
| 71 | return Math.Min(maxLen / phraseLen, sequenceLen) * correctReward; // integer division
|
---|
| 72 | }
|
---|
| 73 |
|
---|
| 74 | public string BestKnownSolution {
|
---|
| 75 | get {
|
---|
| 76 | string solution = "";
|
---|
| 77 | for (int i = 0; i < sequenceLen; i++) {
|
---|
| 78 | solution += optimalPhrasesForPos[i].First();
|
---|
| 79 | }
|
---|
| 80 | return solution;
|
---|
| 81 | }
|
---|
| 82 | }
|
---|
| 83 |
|
---|
| 84 | public IGrammar Grammar {
|
---|
| 85 | get { return grammar; }
|
---|
| 86 | }
|
---|
| 87 |
|
---|
| 88 | public double Evaluate(string sentence) {
|
---|
| 89 | // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
|
---|
| 90 | Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
|
---|
| 91 | // as long as only correct symbols are found we increase the reward by +1
|
---|
| 92 | // on the first incorrect symbol we return
|
---|
| 93 | var reward = 0.0;
|
---|
| 94 | for (int i = 0; i < Math.Min(sentence.Length / phraseLen, sequenceLen); i++) {
|
---|
| 95 | if (optimalPhrasesForPos[i].Contains(sentence.Substring(i * phraseLen, phraseLen))) {
|
---|
| 96 | reward += correctReward;
|
---|
| 97 | } else {
|
---|
| 98 | // alternatively reduce reward by number of remaining phrases
|
---|
| 99 | return Math.Max(0.0, reward + incorrectReward * (sentence.Length / phraseLen - i));
|
---|
| 100 | // stop on first incorrect symbol and return reward
|
---|
| 101 | //return reward;
|
---|
| 102 | }
|
---|
| 103 | }
|
---|
| 104 | return reward;
|
---|
| 105 | }
|
---|
| 106 |
|
---|
| 107 | public string CanonicalRepresentation(string terminalPhrase) {
|
---|
| 108 | return terminalPhrase;
|
---|
| 109 | }
|
---|
| 110 | }
|
---|
| 111 | }
|
---|