Changeset 11755 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPhraseSequenceProblem.cs

Timestamp:

01/13/15 20:02:29 (9 years ago)

Author:

gkronber

Message:

#2283: implemented synthetic benchmark problems (modeling symb-reg) with configurable hardness

File:

• branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPhraseSequenceProblem.cs (modified) (9 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPhraseSequenceProblem.cs

@@ -8 +8 @@
 
 namespace HeuristicLab.Problems.GrammaticalOptimization {
-  // 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
+  // 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
@@ -15 +15 @@
   // - 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
-  // - k: the number of correct phrases starting at each position
+  // - 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 {
 
@@ -24 +26 @@
     private readonly double correctReward;
     private readonly double incorrectReward;
-    private readonly int k;
+    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 k = 1, double correctReward = 1.0, double incorrectReward = 0.0) {
+    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 (k < 1 || k > alphabetSize) throw new ArgumentException();
+      if (numCorrectPhrases < 1 || numCorrectPhrases > alphabetSize) throw new ArgumentException();
       if (phraseLen < 1) throw new ArgumentException();
       if (correctReward <= incorrectReward) throw new ArgumentException();
@@ -40 +43 @@
       this.sequenceLen = sequenceLen;
       this.phraseLen = phraseLen;
-      this.k = k;
+      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();
@@ -54 +58 @@
       for (int i = 0; i < sequenceLen; i++) {
         optimalPhrasesForPos[i] = new SortedSet<string>();
-        for (int j = 0; j < k; j++) {
+        for (int j = 0; j < numCorrectPhrases; j++) {
           string phrase = "";
           do {
@@ -60 +64 @@
               phrase += terminalSymbols.SelectRandom(rand);
             }
+            phrase = CanonicalPhrase(phrase);
           } while (optimalPhrasesForPos[i].Contains(phrase)); // don't allow duplicate phrases
           optimalPhrasesForPos[i].Add(phrase);
@@ -65 +70 @@
       }
 
-      Debug.Assert(Evaluate(BestKnownSolution)/BestKnownQuality(phraseLen * sequenceLen) == 1.0);
+      Debug.Assert(Evaluate(BestKnownSolution) / BestKnownQuality(phraseLen * sequenceLen) == 1.0);
     }
 
@@ -93 +98 @@
       var reward = 0.0;
       for (int i = 0; i < Math.Min(sentence.Length / phraseLen, sequenceLen); i++) {
-        if (optimalPhrasesForPos[i].Contains(sentence.Substring(i * phraseLen, phraseLen))) {
+        var canonicalPhrase = CanonicalPhrase(sentence.Substring(i * phraseLen, phraseLen));
+        if (optimalPhrasesForPos[i].Contains(canonicalPhrase)) {
           reward += correctReward;
         } else {
@@ -105 +111 @@
     }
 
+    private string CanonicalPhrase(string phrase) {
+      if (phrasesAsSets) return string.Join("", phrase.OrderBy(ch => (byte)ch));
+      else return phrase;
+    }
+
     public string CanonicalRepresentation(string terminalPhrase) {
-      return 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;
     }
   }