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

Last change on this file since 11747 was 11747, checked in by gkronber, 7 years ago

#2283: implemented test problems for MCTS

File size: 4.9 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4using System.Linq;
5using System.Text;
6using System.Text.RegularExpressions;
7using HeuristicLab.Common;
8
9namespace 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}
Note: See TracBrowser for help on using the repository browser.