source: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs @ 13791

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;

namespace HeuristicLab.Problems.GrammaticalOptimization {
  public class RoyalTreeProblem : ISymbolicExpressionTreeProblem {
    // Punch: "How Effective Are Multiple Populations in Genetic Programming", 1998
    // In fact, for a new GP system it is dicult to judge whether it is performing
    // as intended or not, since the programs it generates are not necessarily identical to
    // those generated by other GP systems. This raised two questions: what constitutes
    // a "standard" problem in GP, and how do we rate the performance of a system on
    // such a problem.
    // One of the goals of this research was to create a benchmark problem to test how
    // well a particular GP configuration would perform as compared to other configurations.
    // ...
    // We were interested in addressing the same issues, showing how GP could address
    // difficult problems as well as providing a tunable benchmark for comparing GP con-
    // figurations. Furthermore, we were interested in creating and using this benchmark
    // to test the effectiveness of coarse-grain parallel GP's as compared to single population
    // GP's.
    // ...
    // A suitable benchmark problem which has only a single, unique tree as an answer can remove this obstruction.

    private readonly IGrammar grammar;
    private readonly char targetRootSymbol;
    public string Name { get { return "RoyalTree"; } }
    // the number of levels determines the number of non-terminal symbols
    // non-terminal A has only one argument, non-terminal B has two arguments ...
    // optimal level-e tree has quality 122880, 
    // level-a (a) tree has 
    // level-f (6) tree "is extremely difficult"
    // level-g (7) tree "never succeeded"
    public RoyalTreeProblem(int levels) {
      if (levels < 1 || levels > 7) throw new ArgumentException();
      var sentenceSymbol = 'S';
      var terminalSymbols = new char[] { 'x', 'y', 'z' };
      // originally non-terminal-symbols (but for the sequential search grammar these are only alternatives
      var nonTerminalSymbols = Enumerable.Range(0, levels).Select(lvl => (char)(lvl + (byte)'A')).ToArray(); // [A, B ... ]
      var arities = Enumerable.Range(1, levels).ToArray(); // [1, 2, ... levels]
      this.targetRootSymbol = char.ToLower(nonTerminalSymbols.Last());
      {
        // grammar for sequential search
        // S -> x | y | z | aS | bSS | cSSS ...

        var rules = new List<Tuple<char, string>>();
        foreach (var symb in terminalSymbols) {
          rules.Add(Tuple.Create('S', symb.ToString()));
        }
        for (int ntIdx = 0; ntIdx < nonTerminalSymbols.Length; ntIdx++) {
          var opSymb = char.ToLower(nonTerminalSymbols[ntIdx]);
          var remChain = string.Join("", Enumerable.Repeat('S', arities[ntIdx]));
          rules.Add(Tuple.Create('S', opSymb + remChain));
        }

        this.grammar = new Grammar(sentenceSymbol, terminalSymbols.Concat(nonTerminalSymbols.Select(char.ToLower)), new char[] { 'S' }, rules);
      }

      {
        // grammar for tree-based GP
        // S -> x | y | z | A | B | C ...
        // A -> S
        // B -> SS
        // C -> SSS
        var rules = new List<Tuple<char, string>>();
        foreach (var symb in terminalSymbols.Concat(nonTerminalSymbols)) {
          rules.Add(Tuple.Create('S', symb.ToString()));
        }

        for (int ntIdx = 0; ntIdx < nonTerminalSymbols.Length; ntIdx++) {
          var ntSymb = nonTerminalSymbols[ntIdx];
          var alt = string.Join("", Enumerable.Repeat('S', arities[ntIdx]));
          rules.Add(Tuple.Create(ntSymb, alt));
        }
        this.TreeBasedGPGrammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols.Concat(new char[] { 'S' }), rules);
      }

      maxSizeForLevel = new int[8];
      optimalSentencesForLevel = new string[8];
      optimalQualityForLevel = new double[8];
      maxSizeForLevel[0] = 1; // lvl-0 (x | y)
      maxSizeForLevel[1] = 2; // lvl-1 (e.g. ax)
      optimalSentencesForLevel[0] = "x";
      optimalQualityForLevel[0] = 1;
      //optimalSentencesForLevel[1] = "ax";
      //optimalQualityForLevel[1] = 4;

      for (int i = 1; i < levels; i++) {
        maxSizeForLevel[i] = i * maxSizeForLevel[i - 1] + 1; // e.g. lvl-2: baxax

        var opSymb = char.ToLower(nonTerminalSymbols[i - 1]);
        optimalSentencesForLevel[i] = opSymb +
                                       string.Join("",
                                         Enumerable.Repeat(optimalSentencesForLevel[i - 1], arities[i - 1]));

        optimalQualityForLevel[i] = Evaluate(optimalSentencesForLevel[i]);
      }

      // from the paper
      Debug.Assert(maxSizeForLevel[5] == 326);
      Debug.Assert(maxSizeForLevel[6] == 1957);
    }

    private readonly string[] optimalSentencesForLevel;
    private readonly double[] optimalQualityForLevel;
    private readonly int[] maxSizeForLevel;

    public double BestKnownQuality(int maxLen) {
      // search for corresponding level
      int level = 0;
      while (level+1 < maxSizeForLevel.Length && maxSizeForLevel[level + 1] < maxLen) level++;
      // ASSERT: maxSizeForLevel[level + 1] >= maxLen
      return optimalQualityForLevel[level];
    }

    public IGrammar Grammar {
      get { return grammar; }
    }

    public double Evaluate(string sentence) {
      int pos = 0;
      bool perfect;
      return Evaluate(sentence, ref pos, out perfect);
    }

    private double Evaluate(string sentence, ref int pos, out bool perfect) {
      const double completeBonus = 2.0;
      double t = 0.0;
      double weight = 0.0;
      double sum = 0.0;
      bool correctRoot = false;
      bool allPerfect = true, tPerfect;
      int arity;
      switch (sentence[pos]) {
        case 'a':
          pos++;
          correctRoot = (sentence[pos] == 'x');
          t = Evaluate(sentence, ref pos, out tPerfect); // ignores the perfect flag (false for terminals)
          weight = GetWeight(correctRoot, true);
          sum = weight * t;
          perfect = correctRoot;
          if (correctRoot) sum *= completeBonus;
          return sum;
        case 'b': {
            arity = 2;
            pos++;
            for (int i = 0; i < arity; i++) {
              correctRoot = (sentence[pos] == 'a');
              t = Evaluate(sentence, ref pos, out tPerfect);
              weight = GetWeight(correctRoot, tPerfect);
              allPerfect &= correctRoot & tPerfect;
              sum += weight * t;
            }
            perfect = allPerfect;
            if (allPerfect) sum *= completeBonus;
            return sum;
          }
        case 'c': {
            arity = 3;
            sum = 0.0;
            pos++;
            for (int i = 0; i < arity; i++) {
              correctRoot = (sentence[pos] == 'b');
              t = Evaluate(sentence, ref pos, out tPerfect);
              weight = GetWeight(correctRoot, tPerfect);
              allPerfect &= correctRoot & tPerfect;
              sum += weight * t;
            }
            perfect = allPerfect;
            if (allPerfect) sum *= completeBonus;
            return sum;
          }
        case 'd': {
            arity = 4;
            sum = 0.0;
            pos++;
            for (int i = 0; i < arity; i++) {
              correctRoot = (sentence[pos] == 'c');
              t = Evaluate(sentence, ref pos, out tPerfect);
              weight = GetWeight(correctRoot, tPerfect);
              allPerfect &= correctRoot & tPerfect;
              sum += weight * t;
            }
            perfect = allPerfect;
            if (allPerfect) sum *= completeBonus;
            return sum;
          }
        case 'e': {
            arity = 5;
            sum = 0.0;
            pos++;
            for (int i = 0; i < arity; i++) {
              correctRoot = (sentence[pos] == 'd');
              t = Evaluate(sentence, ref pos, out tPerfect);
              weight = GetWeight(correctRoot, tPerfect);
              allPerfect &= correctRoot & tPerfect;
              sum += weight * t;
            }
            perfect = allPerfect;
            if (allPerfect) sum *= completeBonus;
            return sum;
          }
        case 'f': {
            arity = 6;
            sum = 0.0;
            pos++;
            for (int i = 0; i < arity; i++) {
              correctRoot = (sentence[pos] == 'e');
              t = Evaluate(sentence, ref pos, out tPerfect);
              weight = GetWeight(correctRoot, tPerfect);
              allPerfect &= correctRoot & tPerfect;
              sum += weight * t;
            }
            perfect = allPerfect;
            if (allPerfect) sum *= completeBonus;
            return sum;
          }
        case 'g': {
            arity = 7;
            sum = 0.0;
            pos++;
            for (int i = 0; i < arity; i++) {
              correctRoot = (sentence[pos] == 'f');
              t = Evaluate(sentence, ref pos, out tPerfect);
              weight = GetWeight(correctRoot, tPerfect);
              allPerfect &= correctRoot & tPerfect;
              sum += weight * t;
            }
            perfect = allPerfect;
            if (allPerfect) sum *= completeBonus;
            return sum;
          }
        case 'x':
          pos++;
          perfect = false;
          return 1.0;
        case 'y':
        case 'z':
          pos++;
          perfect = false;
          return 0.0;
        default: throw new ArgumentException();
      }
    }

    private double GetWeight(bool correctRoot, bool perfect) {
      const double fullBonus = 2.0;
      const double partialBonus = 1.0;
      const double penalty = 0.33;
      if (correctRoot && perfect) return fullBonus;
      else if (correctRoot) return partialBonus;
      else return penalty;
    }

    public string CanonicalRepresentation(string phrase) {
      throw new NotImplementedException();
      return phrase;
    }

    public IEnumerable<Feature> GetFeatures(string phrase) {
      throw new NotImplementedException();
    }
    public bool IsOptimalPhrase(string phrase) {
      throw new NotImplementedException();
    }

    public IGrammar TreeBasedGPGrammar { get; private set; }
    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
      var sb = new StringBuilder();
      foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) {
        if (s.Symbol.Name == "S") continue;
        sb.Append(s.Symbol.Name.ToLower());
      }
      return sb.ToString();
    }
  }
}