Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 11770 was 11770, checked in by gkronber, 9 years ago

#2283: worked on generic sequential search alg with bandit policy as parameter

File size: 6.2 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 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
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  // - numCorrectPhrases: the number of correct phrases starting at each position
18  // - phrasesAsSets: switch to determine if the ordering of symbols within a phrase is relevant
19  //
20  // this problem should be hard for GP and easy for MCTS (TD should not have an advantage compared to MCTS)
21  // for phraseLen > 1 this should be harder than RoyalSymbolProblem
22  // when phrases are symbol sets instead of sequences then value-estimation routines should be better (TD)
23  public class RoyalPhraseSequenceProblem : IProblem {
24
25    private readonly IGrammar grammar;
26    private readonly double correctReward;
27    private readonly double incorrectReward;
28    private readonly int sequenceLen;
29    private readonly int phraseLen;
30    private readonly bool phrasesAsSets;
31    private readonly SortedSet<string>[] optimalPhrasesForPos;
32
33    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) {
34      if (alphabetSize <= 0 || alphabetSize > 26) throw new ArgumentException();
35      if (sequenceLen <= 0) throw new ArgumentException();
36      if (numCorrectPhrases < 1 || numCorrectPhrases > alphabetSize) throw new ArgumentException();
37      if (phraseLen < 1) throw new ArgumentException();
38      if (correctReward <= incorrectReward) throw new ArgumentException();
39
40      this.sequenceLen = sequenceLen;
41      this.phraseLen = phraseLen;
42      this.correctReward = correctReward;
43      this.incorrectReward = incorrectReward;
44      this.phrasesAsSets = phrasesAsSets;
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 < numCorrectPhrases; j++) {
57          string phrase = "";
58          do {
59            for (int l = 0; l < phraseLen; l++) {
60              phrase += terminalSymbols.SelectRandom(rand);
61            }
62            phrase = CanonicalPhrase(phrase);
63          } while (optimalPhrasesForPos[i].Contains(phrase)); // don't allow duplicate phrases
64          optimalPhrasesForPos[i].Add(phrase);
65        }
66      }
67
68      Debug.Assert(Evaluate(BestKnownSolution) / BestKnownQuality(phraseLen * sequenceLen) == 1.0);
69    }
70
71    public double BestKnownQuality(int maxLen) {
72      return Math.Min(maxLen / phraseLen, sequenceLen) * correctReward; // integer division
73    }
74
75    public string BestKnownSolution {
76      get {
77        string solution = "";
78        for (int i = 0; i < sequenceLen; i++) {
79          solution += optimalPhrasesForPos[i].First();
80        }
81        return solution;
82      }
83    }
84
85    public IGrammar Grammar {
86      get { return grammar; }
87    }
88
89    public double Evaluate(string sentence) {
90      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
91      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
92      // as long as only correct symbols are found we increase the reward by +1
93      // on the first incorrect symbol we return
94      var reward = 0.0;
95      for (int i = 0; i < Math.Min(sentence.Length / phraseLen, sequenceLen); i++) {
96        var canonicalPhrase = CanonicalPhrase(sentence.Substring(i * phraseLen, phraseLen));
97        if (optimalPhrasesForPos[i].Contains(canonicalPhrase)) {
98          reward += correctReward;
99        } else {
100          // alternatively reduce reward by number of remaining phrases
101          return Math.Max(0.0, reward + incorrectReward * (sentence.Length / phraseLen - i));
102          // stop on first incorrect symbol and return reward
103          //return reward;
104        }
105      }
106      return reward;
107    }
108
109    private string CanonicalPhrase(string phrase) {
110      if (phrasesAsSets) return string.Join("", phrase.OrderBy(ch => (byte)ch));
111      else return phrase;
112    }
113
114    public string CanonicalRepresentation(string terminalPhrase) {
115      if (phrasesAsSets) {
116        var phrases = new List<string>();
117        var numPhrases = terminalPhrase.Length / phraseLen;
118        for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
119          var sentenceIdx = phraseIdx * phraseLen;
120          var phrase = terminalPhrase.Substring(sentenceIdx, phraseLen);
121          phrase = CanonicalPhrase(phrase);
122          phrases.Add(phrase);
123        }
124
125        var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
126        remainder = CanonicalPhrase(remainder);
127        phrases.Add(remainder);
128
129        return string.Join("", phrases);
130      } else
131        return terminalPhrase;
132    }
133  }
134}
Note: See TracBrowser for help on using the repository browser.