Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
08/24/15 13:56:27 (9 years ago)
Author:
gkronber
Message:

#2283: experiments on grammatical optimization algorithms (maxreward instead of avg reward, ...)

Location:
branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization
Files:
18 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs

    r12391 r12893  
    184184        Debug.Assert(maxLenOfReplacement > 0);
    185185
    186         var alts = GetTerminalAlternatives(nt).Where(alt => MinPhraseLength(alt) <= maxLenOfReplacement);
     186
     187        IEnumerable<Sequence> alts;
     188        if (random.NextDouble() < 0.005) {
     189          alts = GetTerminalAlternatives(nt).Where(alt => MinPhraseLength(alt) <= maxLenOfReplacement);
     190        } else {
     191          alts = GetNonTerminalAlternatives(nt).Where(alt => MinPhraseLength(alt) <= maxLenOfReplacement);
     192          if (!alts.Any())
     193            alts = GetTerminalAlternatives(nt).Where(alt => MinPhraseLength(alt) <= maxLenOfReplacement);
     194        }
    187195        Debug.Assert(alts.Any());
    188196

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj

    r12876 r12893  
    3232    <WarningLevel>4</WarningLevel>
    3333    <Prefer32Bit>false</Prefer32Bit>
     34    <UseVSHostingProcess>true</UseVSHostingProcess>
    3435  </PropertyGroup>
    3536  <ItemGroup>

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Interfaces/IProblem.cs

    r12099 r12893  
    1212    IGrammar Grammar { get; }
    1313    double Evaluate(string sentence);
     14    bool IsOptimalPhrase(string phrase); // determines if the phrase can be derived to an optimal solution
    1415    string CanonicalRepresentation(string phrase); // canonical state must use correct syntax (must be a valid input for evaluate)
    1516    IEnumerable<Feature> GetFeatures(string phrase);

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs

    r12290 r12893  
    6363    }
    6464
     65    public bool IsOptimalPhrase(string phrase) {
     66      throw new NotImplementedException();
     67    }
     68
    6569    public string CanonicalRepresentation(string phrase) {
    6670      throw new NotImplementedException();
    … …  
    6872    }
    6973
    70     public IEnumerable<Feature> GetFeatures(string phrase)
    71     {
    72       return new[] {new Feature(phrase, 1.0)};
     74    public IEnumerable<Feature> GetFeatures(string phrase) {
     75      return new[] { new Feature(phrase, 1.0) };
    7376    }
    7477

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs

    r12391 r12893  
    169169      return new Feature[] {new Feature(phrase, 1.0),};
    170170    }
     171    public bool IsOptimalPhrase(string phrase) {
     172      throw new NotImplementedException();
     173    }
    171174
    172175    public override string ToString() {

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs

    r12099 r12893  
    5555      throw new NotImplementedException();
    5656    }
     57    public bool IsOptimalPhrase(string phrase) {
     58      throw new NotImplementedException();
     59    }
    5760
    5861    public IGrammar TreeBasedGPGrammar { get; private set; }

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs

    r12099 r12893  
    9696      throw new NotImplementedException();
    9797    }
     98    public bool IsOptimalPhrase(string phrase) {
     99      throw new NotImplementedException();
     100    }
    98101
    99102    public IGrammar TreeBasedGPGrammar { get; private set; }

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/PermutationProblem.cs

    r12099 r12893  
    4747      throw new NotImplementedException();
    4848    }
     49    public bool IsOptimalPhrase(string phrase) {
     50      throw new NotImplementedException();
     51    }
     52
    4953    public IGrammar TreeBasedGPGrammar { get; private set; }
    5054    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/PrimePolynomialProblem.cs

    r12291 r12893  
    215215      return sb.ToString();
    216216    }
     217    public bool IsOptimalPhrase(string phrase) {
     218      // throw new NotImplementedException();
     219      return false; // TODO
     220    }
    217221
    218222

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs

    r12391 r12893  
    7676
    7777    }
     78    public bool IsOptimalPhrase(string phrase) {
     79      throw new NotImplementedException();
     80    }
    7881
    7982    public IGrammar TreeBasedGPGrammar { get; private set; }

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs

    r12391 r12893  
    153153      return new Feature[] {new Feature(phrase, 1.0)};
    154154    }
     155    public bool IsOptimalPhrase(string phrase) {
     156      throw new NotImplementedException();
     157    }
    155158
    156159    public IGrammar TreeBasedGPGrammar { get; private set; }

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalRoadProblem.cs

    r12099 r12893  
    3333      return phrase;
    3434    }
     35    public bool IsOptimalPhrase(string phrase) {
     36      throw new NotImplementedException();
     37    }
    3538
    3639    public IEnumerable<Feature> GetFeatures(string phrase)

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs

    r12391 r12893  
    104104      throw new NotImplementedException();
    105105    }
     106    public bool IsOptimalPhrase(string phrase) {
     107      throw new NotImplementedException();
     108    }
    106109
    107110    public IGrammar TreeBasedGPGrammar { get; private set; }

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs

    r12099 r12893  
    5151      throw new NotImplementedException();
    5252    }
     53    public bool IsOptimalPhrase(string phrase) {
     54      throw new NotImplementedException();
     55    }
    5356
    5457    public IGrammar TreeBasedGPGrammar { get; private set; }

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs

    r12099 r12893  
    263263      throw new NotImplementedException();
    264264    }
     265    public bool IsOptimalPhrase(string phrase) {
     266      throw new NotImplementedException();
     267    }
    265268
    266269    public IGrammar TreeBasedGPGrammar { get; private set; }

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs

    r12876 r12893  
    3030    // here we use a modified grammar which has only one syntax tree for each sentence
    3131
     32    public IEnumerable<string> OptimalSentences {
     33      get {
     34        return new string[]
     35        {
     36          "?(m)(ll?(m)(r))mr",
     37          "?(m)(rr?(m)(l))ml",
     38          "r?(m)(ll?(m)(r))m",
     39          "l?(m)(rr?(m)(l))m",
     40          "mr?(m)(ll?(m)(r))",
     41          "ml?(m)(rr?(m)(l))",
     42          "?(m)(ll?(m)(l))ml",
     43          "?(m)(rr?(m)(r))mr",
     44          "l?(m)(ll?(m)(l))m",
     45          "r?(m)(rr?(m)(r))m",
     46          "ml?(m)(ll?(m)(l))",
     47          "mr?(m)(rr?(m)(r))",
     48        };
     49      }
     50    }
    3251
    3352    private readonly IGrammar grammar;
    … …  
    138157
    139158    public IEnumerable<Feature> GetFeatures(string phrase) {
    140       yield return new Feature(phrase, 1.0);
     159      for (int idx = 0; idx < 15; idx++) {
     160        foreach (var t in Grammar.TerminalSymbols)
     161          yield return new Feature(t.ToString(), phrase.Length > idx ? phrase[idx] == t ? 1 : 0 : 0);
     162      }
    141163      //var ant = new Ant(false);
    142164      //int p = 0;
    … …  
    166188      }
    167189    }
     190    public bool IsOptimalPhrase(string phrase) {
     191      var firstNonTerminalIdx = new Sequence(phrase).FirstNonTerminalIndex;
     192      if (firstNonTerminalIdx == -1) firstNonTerminalIdx = phrase.Length;
     193      return OptimalSentences.Any(s => s.Substring(0, firstNonTerminalIdx) == phrase.Substring(0, firstNonTerminalIdx));
     194    }
     195
    168196  }
    169197

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs

    r12391 r12893  
    66using System.Linq;
    77using System.Net;
     8using System.Runtime.InteropServices;
    89using System.Security;
    910using System.Security.AccessControl;
    … …  
    6061    public string Name { get { return "SymbolicRegressionPoly10"; } }
    6162
    62     public SymbolicRegressionPoly10Problem() {
     63    public SymbolicRegressionPoly10Problem(int n = 500) {
    6364      this.grammar = new Grammar(grammarString);
    6465      this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
    6566
    66       this.N = 500;
     67      this.N = n;
    6768      this.x = new double[N][];
    6869      this.y = new double[N];
    … …  
    99100    }
    100101
     102    private static double[] erc = new double[] { 0.0, 1.0 };
    101103    public double Evaluate(string sentence) {
    102104      var interpreter = new ExpressionInterpreter();
    103       return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])).ToArray());
     105      return Math.Round(HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i], erc)).ToArray()), 3);
    104106    }
    105107
    … …  
    166168
    167169
    168       if (phrase.EndsWith("E")) phrase = phrase.TrimEnd('*', '+', 'E');
     170      //if (phrase.EndsWith("E")) phrase = phrase.TrimEnd('*', '+', 'E');
    169171      //var len = 5;
    170172      //var start = Math.Max(0, phrase.Length - len);
    … …  
    174176      //
    175177
    176       var terms = phrase.Split('+');
    177       foreach (var t in terms.Distinct()) yield return new Feature(t, 1.0);
    178 
    179       for (int i = 0; i < terms.Length; i++) {
    180         for (int j = i + 1; j < terms.Length; j++) {
    181           yield return new Feature(terms[i] + " " + terms[j], 1.0);
     178      //var terms = phrase.Split('+');
     179      //foreach (var t in terms.Distinct()) yield return new Feature(t, 1.0);
     180      //
     181      //for (int i = 0; i < terms.Length; i++) {
     182      //  for (int j = i + 1; j < terms.Length; j++) {
     183      //    yield return new Feature(terms[i] + " " + terms[j], 1.0);
     184      //  }
     185      //}
     186      var t = new string[] { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j" };
     187      for (int t0Idx = 0; t0Idx < t.Length - 1; t0Idx++) {
     188        for (int t1Idx = t0Idx; t1Idx < t.Length; t1Idx++) {
     189          var a = t[t0Idx] + "*" + t[t1Idx];
     190          var b = t[t1Idx] + "*" + t[t0Idx];
     191          yield return new Feature(a, phrase.Contains(a) || phrase.Contains(b) ? 1 : 0);
    182192        }
    183193      }
    … …  
    225235    }
    226236
     237    private static string[][] optimalTerms = new string[][]
     238      {
     239        new string[] { "a*b","b*a",},
     240        new string[] { "c*d","d*c",},
     241        new string[] { "e*f","f*e",},
     242        new string[] { "a*g*i","a*i*g","g*a*i","g*i*a","i*a*g","i*g*a"},
     243        new string[] { "c*j*f","c*f*j","j*c*f","j*f*c","f*c*j","f*j*c"},
     244      };
     245
     246    private static int[][] permute5 = new int[][]
     247      {
     248        new int[] { 4, 3, 2, 0, 1 },
     249        new int[] { 4, 3, 2, 1, 0 },
     250        new int[] { 4, 3, 0, 2, 1 },
     251        new int[] { 4, 3, 1, 2, 0 },
     252        new int[] { 4, 3, 0, 1, 2 },
     253        new int[] { 4, 3, 1, 0, 2 },
     254        new int[] { 4, 2, 3, 0, 1 },
     255        new int[] { 4, 2, 3, 1, 0 },
     256        new int[] { 4, 0, 3, 2, 1 },
     257        new int[] { 4, 1, 3, 2, 0 },
     258        new int[] { 4, 0, 3, 1, 2 },
     259        new int[] { 4, 1, 3, 0, 2 },
     260        new int[] { 4, 2, 0, 3, 1 },
     261        new int[] { 4, 2, 1, 3, 0 },
     262        new int[] { 4, 0, 2, 3, 1 },
     263        new int[] { 4, 1, 2, 3, 0 },
     264        new int[] { 4, 0, 1, 3, 2 },
     265        new int[] { 4, 1, 0, 3, 2 },
     266        new int[] { 4, 2, 0, 1, 3 },
     267        new int[] { 4, 2, 1, 0, 3 },
     268        new int[] { 4, 0, 2, 1, 3 },
     269        new int[] { 4, 1, 2, 0, 3 },
     270        new int[] { 4, 0, 1, 2, 3 },
     271        new int[] { 4, 1, 0, 2, 3 },
     272        new int[] { 3, 4, 2, 0, 1 },
     273        new int[] { 3, 4, 2, 1, 0 },
     274        new int[] { 3, 4, 0, 2, 1 },
     275        new int[] { 3, 4, 1, 2, 0 },
     276        new int[] { 3, 4, 0, 1, 2 },
     277        new int[] { 3, 4, 1, 0, 2 },
     278        new int[] { 2, 4, 3, 0, 1 },
     279        new int[] { 2, 4, 3, 1, 0 },
     280        new int[] { 0, 4, 3, 2, 1 },
     281        new int[] { 1, 4, 3, 2, 0 },
     282        new int[] { 0, 4, 3, 1, 2 },
     283        new int[] { 1, 4, 3, 0, 2 },
     284        new int[] { 2, 4, 0, 3, 1 },
     285        new int[] { 2, 4, 1, 3, 0 },
     286        new int[] { 0, 4, 2, 3, 1 },
     287        new int[] { 1, 4, 2, 3, 0 },
     288        new int[] { 0, 4, 1, 3, 2 },
     289        new int[] { 1, 4, 0, 3, 2 },
     290        new int[] { 2, 4, 0, 1, 3 },
     291        new int[] { 2, 4, 1, 0, 3 },
     292        new int[] { 0, 4, 2, 1, 3 },
     293        new int[] { 1, 4, 2, 0, 3 },
     294        new int[] { 0, 4, 1, 2, 3 },
     295        new int[] { 1, 4, 0, 2, 3 },
     296        new int[] { 3, 2, 4, 0, 1 },
     297        new int[] { 3, 2, 4, 1, 0 },
     298        new int[] { 3, 0, 4, 2, 1 },
     299        new int[] { 3, 1, 4, 2, 0 },
     300        new int[] { 3, 0, 4, 1, 2 },
     301        new int[] { 3, 1, 4, 0, 2 },
     302        new int[] { 2, 3, 4, 0, 1 },
     303        new int[] { 2, 3, 4, 1, 0 },
     304        new int[] { 0, 3, 4, 2, 1 },
     305        new int[] { 1, 3, 4, 2, 0 },
     306        new int[] { 0, 3, 4, 1, 2 },
     307        new int[] { 1, 3, 4, 0, 2 },
     308        new int[] { 2, 0, 4, 3, 1 },
     309        new int[] { 2, 1, 4, 3, 0 },
     310        new int[] { 0, 2, 4, 3, 1 },
     311        new int[] { 1, 2, 4, 3, 0 },
     312        new int[] { 0, 1, 4, 3, 2 },
     313        new int[] { 1, 0, 4, 3, 2 },
     314        new int[] { 2, 0, 4, 1, 3 },
     315        new int[] { 2, 1, 4, 0, 3 },
     316        new int[] { 0, 2, 4, 1, 3 },
     317        new int[] { 1, 2, 4, 0, 3 },
     318        new int[] { 0, 1, 4, 2, 3 },
     319        new int[] { 1, 0, 4, 2, 3 },
     320        new int[] { 3, 2, 0, 4, 1 },
     321        new int[] { 3, 2, 1, 4, 0 },
     322        new int[] { 3, 0, 2, 4, 1 },
     323        new int[] { 3, 1, 2, 4, 0 },
     324        new int[] { 3, 0, 1, 4, 2 },
     325        new int[] { 3, 1, 0, 4, 2 },
     326        new int[] { 2, 3, 0, 4, 1 },
     327        new int[] { 2, 3, 1, 4, 0 },
     328        new int[] { 0, 3, 2, 4, 1 },
     329        new int[] { 1, 3, 2, 4, 0 },
     330        new int[] { 0, 3, 1, 4, 2 },
     331        new int[] { 1, 3, 0, 4, 2 },
     332        new int[] { 2, 0, 3, 4, 1 },
     333        new int[] { 2, 1, 3, 4, 0 },
     334        new int[] { 0, 2, 3, 4, 1 },
     335        new int[] { 1, 2, 3, 4, 0 },
     336        new int[] { 0, 1, 3, 4, 2 },
     337        new int[] { 1, 0, 3, 4, 2 },
     338        new int[] { 2, 0, 1, 4, 3 },
     339        new int[] { 2, 1, 0, 4, 3 },
     340        new int[] { 0, 2, 1, 4, 3 },
     341        new int[] { 1, 2, 0, 4, 3 },
     342        new int[] { 0, 1, 2, 4, 3 },
     343        new int[] { 1, 0, 2, 4, 3 },
     344        new int[] { 3, 2, 0, 1, 4 },
     345        new int[] { 3, 2, 1, 0, 4 },
     346        new int[] { 3, 0, 2, 1, 4 },
     347        new int[] { 3, 1, 2, 0, 4 },
     348        new int[] { 3, 0, 1, 2, 4 },
     349        new int[] { 3, 1, 0, 2, 4 },
     350        new int[] { 2, 3, 0, 1, 4 },
     351        new int[] { 2, 3, 1, 0, 4 },
     352        new int[] { 0, 3, 2, 1, 4 },
     353        new int[] { 1, 3, 2, 0, 4 },
     354        new int[] { 0, 3, 1, 2, 4 },
     355        new int[] { 1, 3, 0, 2, 4 },
     356        new int[] { 2, 0, 3, 1, 4 },
     357        new int[] { 2, 1, 3, 0, 4 },
     358        new int[] { 0, 2, 3, 1, 4 },
     359        new int[] { 1, 2, 3, 0, 4 },
     360        new int[] { 0, 1, 3, 2, 4 },
     361        new int[] { 1, 0, 3, 2, 4 },
     362        new int[] { 2, 0, 1, 3, 4 },
     363        new int[] { 2, 1, 0, 3, 4 },
     364        new int[] { 0, 2, 1, 3, 4 },
     365        new int[] { 1, 2, 0, 3, 4 },
     366        new int[] { 0, 1, 2, 3, 4 },
     367        new int[] { 1, 0, 2, 3, 4 },
     368      };
     369
     370
     371    private static HashSet<string>[] optimalSentences;
     372    static SymbolicRegressionPoly10Problem() {
     373      optimalSentences = Enumerable.Range(0, 24).Select(i => new HashSet<string>()).ToArray();
     374
     375      foreach (var t0Idx in new[] { 0, 1 })
     376        foreach (var t1Idx in new[] { 0, 1 })
     377          foreach (var t2Idx in new[] { 0, 1 })
     378            foreach (var t3Idx in new[] { 0, 1, 2, 3, 4, 5 })
     379              foreach (var t4Idx in new[] { 0, 1, 2, 3, 4, 5 }) {
     380                foreach (var p in permute5) {
     381                  int[] idx = new int[] { t0Idx, t1Idx, t2Idx, t3Idx, t4Idx };
     382                  optimalSentences[23].Add(string.Join("+", p.Select(pi => optimalTerms[pi][idx[pi]])));
     383                }
     384              }
     385      for (int i = 0; i < 23; i += 2) {
     386        var newElements = new HashSet<string>();
     387        foreach (var sentence in optimalSentences[23]) {
     388          newElements.Add(sentence.Substring(0, i) + "E");
     389        }
     390        foreach (var e in newElements) optimalSentences[i + 1].Add(e);
     391      }
     392    }
     393
     394    public bool IsOptimalPhrase(string phrase) {
     395      return optimalSentences[phrase.Length].Contains(phrase);
     396    }
     397
    227398    private void TreeToSentence(ISymbolicExpressionTreeNode treeNode, StringBuilder sb) {
    228399      if (treeNode.SubtreeCount == 0) {

  • branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/SentenceSetStatistics.cs

    r12298 r12893  
    2323    public SentenceSetStatistics(double bestKnownQuality = 1.0) {
    2424      this.bestKnownQuality = bestKnownQuality;
     25      Clear();
     26    }
     27
     28    public void Clear() {
    2529      BestSentenceQuality = double.NegativeInfinity;
    2630      BestSentence = string.Empty;
    … …  
    5559      BestSentenceIndex, TrimToSize(BestSentence, 30),
    5660      LastSentenceQuality, TrimToSize(LastSentence, 20)
    57       //LastSentenceQuality, TrimToSize(LastSentence, 20)
     61        //LastSentenceQuality, TrimToSize(LastSentence, 20)
    5862     );
    5963    }
Note: See TracChangeset for help on using the changeset viewer.