Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSequenceProblem.cs @ 11792

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

#2283 work-in-progress commit (does not compile)

File size: 3.8 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 symbols and starting at the first symbol
11  // parameters
12  // - alphabetSize: number of different symbols (max=26)
13  // - sequenceLen: length of the correct subsequence
14  // - k: the number of correct symbols at each position
15  //
16  // this problem should be hard for GP and easy for MCTS (TD should not have an advantage compared to MCTS)
17  public class RoyalSequenceProblem : IProblem {
18
19    private readonly IGrammar grammar;
20    private readonly double correctReward;
21    private readonly double incorrectReward;
22    private readonly int sequenceLen;
23    private readonly SortedSet<char>[] optimalSymbolsForPos;
24
25    public RoyalSequenceProblem(Random rand, int alphabetSize, int sequenceLen, int k = 1, double correctReward = 1.0, double incorrectReward = 0.0) {
26      if (alphabetSize <= 0 || alphabetSize > 26) throw new ArgumentException();
27      if (sequenceLen <= 0) throw new ArgumentException();
28      if (k < 1 || k > alphabetSize) throw new ArgumentException();
29      if (correctReward <= incorrectReward) throw new ArgumentException();
30      this.sequenceLen = sequenceLen;
31      this.correctReward = correctReward;
32      this.incorrectReward = incorrectReward;
33      var sentenceSymbol = 'S';
34      var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray();
35      var nonTerminalSymbols = new char[] { 'S' };
36      var rules = terminalSymbols.Select(t => Tuple.Create('S', t.ToString()))
37        .Concat(terminalSymbols.Select(t => Tuple.Create('S', t + "S")));
38      //var rules = terminalSymbols.Select(t => Tuple.Create('S', t + "S"))
39      //  .Concat(terminalSymbols.Select(t => Tuple.Create('S', t.ToString())));
40      this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules);
41
42      this.optimalSymbolsForPos = new SortedSet<char>[sequenceLen];
43      for (int i = 0; i < sequenceLen; i++) {
44        optimalSymbolsForPos[i] = new SortedSet<char>();
45        for (int j = 0; j < k; j++) {
46          char ch;
47          do {
48            ch = terminalSymbols.SelectRandom(rand);
49          } while (optimalSymbolsForPos[i].Contains(ch));
50          optimalSymbolsForPos[i].Add(ch);
51        }
52      }
53    }
54
55    public double BestKnownQuality(int maxLen) {
56      return Math.Min(maxLen, sequenceLen) * correctReward;
57    }
58
59    public IGrammar Grammar {
60      get { return grammar; }
61    }
62
63    public double Evaluate(string sentence) {
64      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
65      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
66      // as long as only correct symbols are found we increase the reward by +1
67      // on the first incorrect symbol we return
68      var reward = 0.0;
69      for (int i = 0; i < Math.Min(sentence.Length, sequenceLen); i++) {
70        if (optimalSymbolsForPos[i].Contains(sentence[i])) {
71          reward += correctReward;
72        } else {
73          // alternatively reduce reward by number of remaining symbols
74          return Math.Max(0.0, reward + incorrectReward * (sentence.Length - i));
75          // stop on first incorrect symbol and return reward
76          //return reward;
77        }
78      }
79      return reward;
80    }
81
82    public string CanonicalRepresentation(string terminalPhrase) {
83      throw new NotImplementedException();
84      return terminalPhrase;
85    }
86  }
87}
Note: See TracBrowser for help on using the repository browser.