source: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs @ 15734

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.DataAnalysis;
using HeuristicLab.Problems.DataAnalysis.Symbolic;
using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;

namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
  [Item("Grammar Enumeration Symbolic Regression", "Iterates all possible model structures for a fixed grammar.")]
  [StorableClass]
  [Creatable(CreatableAttribute.Categories.DataAnalysisRegression, Priority = 250)]
  public class GrammarEnumerationAlgorithm : FixedDataAnalysisAlgorithm<IRegressionProblem> {
    private readonly string BestTrainingSolution = "Best solution (training)";
    private readonly string BestTrainingSolutionQuality = "Best solution quality (training)";
    private readonly string BestTestSolution = "Best solution (test)";
    private readonly string BestTestSolutionQuality = "Best solution quality (test)";

    private readonly string MaxTreeSizeParameterName = "Max. Tree Nodes";
    private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval";
    private readonly string UseMemoizationParameterName = "Use Memoization?";

    #region properties
    protected IValueParameter<IntValue> MaxTreeSizeParameter {
      get { return (IValueParameter<IntValue>)Parameters[MaxTreeSizeParameterName]; }
    }
    public int MaxTreeSize {
      get { return MaxTreeSizeParameter.Value.Value; }
      set { MaxTreeSizeParameter.Value.Value = value; }
    }

    protected IValueParameter<IntValue> GuiUpdateIntervalParameter {
      get { return (IValueParameter<IntValue>)Parameters[GuiUpdateIntervalParameterName]; }
    }
    public int GuiUpdateInterval {
      get { return GuiUpdateIntervalParameter.Value.Value; }
      set { GuiUpdateIntervalParameter.Value.Value = value; }
    }

    protected IValueParameter<BoolValue> UseMemoizationParameter {
      get { return (IValueParameter<BoolValue>)Parameters[UseMemoizationParameterName]; }
    }
    public bool UseMemoization {
      get { return UseMemoizationParameter.Value.Value; }
      set { UseMemoizationParameter.Value.Value = value; }
    }

    public SymbolString BestTrainingSentence;
    public SymbolString BestTestSentence;

    public List<Tuple<SymbolString, int>> distinctSentences;
    public List<Tuple<SymbolString, int>> sentences;
    #endregion

    public Grammar Grammar;


    #region ctors
    public override IDeepCloneable Clone(Cloner cloner) {
      return new GrammarEnumerationAlgorithm(this, cloner);
    }

    public GrammarEnumerationAlgorithm() {

      var provider = new HeuristicLab.Problems.Instances.DataAnalysis.VariousInstanceProvider(seed: 1234);
      var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("Poly-10")));

      Problem = new RegressionProblem() {
        ProblemData = regProblem
      };

      Parameters.Add(new ValueParameter<IntValue>(MaxTreeSizeParameterName, "The number of clusters.", new IntValue(6)));
      Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(4000)));
      Parameters.Add(new ValueParameter<BoolValue>(UseMemoizationParameterName, "Should already subtrees be reused within a run.", new BoolValue(true)));
    }

    private GrammarEnumerationAlgorithm(GrammarEnumerationAlgorithm original, Cloner cloner) : base(original, cloner) { }
    #endregion


    protected override void Run(CancellationToken cancellationToken) {
      Results.Add(new Result("Best R²", new DoubleValue(0.0)));
      var rand = new System.Random(1234);
      BestTrainingSentence = null;
      BestTrainingSentence = null;
      this.sentences = new List<Tuple<SymbolString, int>>();
      this.distinctSentences = new List<Tuple<SymbolString, int>>();
      var archivedPhrases = new Dictionary<int, SymbolString>();
      int expansions = 0;
      Dictionary<int, SymbolString> evaluatedHashes = new Dictionary<int, SymbolString>();

      Grammar = new Grammar(Problem.ProblemData.AllowedInputVariables.ToArray());

      var phrases = new Dictionary<int, SymbolString>();
      var phrase0 = new SymbolString(new[] { Grammar.StartSymbol });
      phrases.Add(Grammar.CalcHashCode(phrase0), phrase0);

      while (phrases.Any()) {
        if (cancellationToken.IsCancellationRequested) break;

        // FIFO
        // SymbolString currSymbolString = phrases.First();
        // phrases.RemoveAt(0);

        
        // LIFO
        // SymbolString currSymbolString = phrases.Last();
        // phrases.RemoveAt(phrases.Count - 1);
        

        // RANDOM
        int idx = rand.Next(phrases.Count);
        var selectedEntry = phrases.ElementAt(idx);  // TODO: Perf von ElementAt ist schlecht.
        phrases.Remove(selectedEntry.Key);
        var currPhrase = selectedEntry.Value;

        archivedPhrases.Add(selectedEntry.Key, selectedEntry.Value);

        if (currPhrase.IsSentence()) {
          int currSymbolStringHash = Grammar.CalcHashCode(currPhrase);
          this.sentences.Add(new Tuple<SymbolString, int>(currPhrase, currSymbolStringHash));

          if (!evaluatedHashes.ContainsKey(currSymbolStringHash)) {
            evaluatedHashes[currSymbolStringHash] = currPhrase;

            this.distinctSentences.Add(new Tuple<SymbolString, int>(currPhrase, currSymbolStringHash));
            EvaluateSentence(currPhrase);
          }
          UpdateView(this.sentences, this.distinctSentences);

        } else {
          // expand next nonterminal symbols
          int nonterminalSymbolIndex = currPhrase.FindIndex(s => s is NonterminalSymbol);
          NonterminalSymbol expandedSymbol = currPhrase[nonterminalSymbolIndex] as NonterminalSymbol;

          foreach (Production productionAlternative in expandedSymbol.Alternatives) {
            SymbolString newSentence = new SymbolString(currPhrase);
            newSentence.RemoveAt(nonterminalSymbolIndex);
            newSentence.InsertRange(nonterminalSymbolIndex, productionAlternative);

            expansions++;
            if (newSentence.Count <= MaxTreeSize) {
              var phraseHash = Grammar.CalcHashCode(newSentence);
              if(!phrases.ContainsKey(phraseHash) &&
                !archivedPhrases.ContainsKey(phraseHash))
              phrases.Add(phraseHash, newSentence);
            }
          }
        }
      }

      UpdateView(this.sentences, this.distinctSentences, force: true);

      string[,] sentences = new string[this.sentences.Count, 3];
      for (int i = 0; i < this.sentences.Count; i++) {
        sentences[i, 0] = this.sentences[i].Item1.ToString();
        sentences[i, 1] = Grammar.PostfixToInfixParser(this.sentences[i].Item1).ToString();
        sentences[i, 2] = this.sentences[i].Item2.ToString();
      }
      Results.Add(new Result("All generated sentences", new StringMatrix(sentences)));

      string[,] distinctSentences = new string[this.distinctSentences.Count, 3];
      for (int i = 0; i < this.distinctSentences.Count; i++) {
        distinctSentences[i, 0] = this.distinctSentences[i].Item1.ToString();
        distinctSentences[i, 1] = Grammar.PostfixToInfixParser(this.distinctSentences[i].Item1).ToString();
        distinctSentences[i, 2] = this.distinctSentences[i].Item2.ToString();
      }
      Results.Add(new Result("Distinct generated sentences", new StringMatrix(distinctSentences)));
    }


    private void UpdateView(List<Tuple<SymbolString, int>> allGenerated,
        List<Tuple<SymbolString, int>> distinctGenerated, bool force = false) {
      int generatedSolutions = allGenerated.Count;
      int distinctSolutions = distinctGenerated.Count;

      if (force || generatedSolutions % GuiUpdateInterval == 0) {
        Results.AddOrUpdateResult("Generated Solutions", new IntValue(generatedSolutions));
        Results.AddOrUpdateResult("Distinct Solutions", new IntValue(distinctSolutions));

        DoubleValue averageTreeLength = new DoubleValue(allGenerated.Select(r => r.Item1.Count).Average());
        Results.AddOrUpdateResult("Average Tree Length of Solutions", averageTreeLength);
      }
    }

    private void EvaluateSentence(SymbolString symbolString) {
      SymbolicExpressionTree tree = Grammar.ParseSymbolicExpressionTree(symbolString);
      SymbolicRegressionModel model = new SymbolicRegressionModel(
        Problem.ProblemData.TargetVariable,
        tree,
        new SymbolicDataAnalysisExpressionTreeLinearInterpreter());
      var probData = Problem.ProblemData;
      var target = probData.TargetVariableTrainingValues;
      var estVals = model.GetEstimatedValues(probData.Dataset, probData.TrainingIndices);
      OnlineCalculatorError error;
      var r2 = OnlinePearsonsRSquaredCalculator.Calculate(target, estVals, out error);
      if (error != OnlineCalculatorError.None) r2 = 0.0;

      var bestR2 = ((DoubleValue)(Results["Best R²"]).Value).Value;
      ((DoubleValue)(Results["Best R²"].Value)).Value = Math.Max(r2, bestR2);

      // IRegressionSolution newSolution = model.CreateRegressionSolution(Problem.ProblemData);
      // 
      // IResult currBestTrainingSolutionResult;
      // IResult currBestTestSolutionResult;
      // if (!Results.TryGetValue(BestTrainingSolution, out currBestTrainingSolutionResult)
      //      || !Results.TryGetValue(BestTestSolution, out currBestTestSolutionResult)) {
      // 
      //   BestTrainingSentence = symbolString;
      //   Results.Add(new Result(BestTrainingSolution, newSolution));
      //   Results.Add(new Result(BestTrainingSolutionQuality, new DoubleValue(newSolution.TrainingRSquared).AsReadOnly()));
      // 
      //   BestTestSentence = symbolString;
      //   Results.Add(new Result(BestTestSolution, newSolution));
      //   Results.Add(new Result(BestTestSolutionQuality, new DoubleValue(newSolution.TestRSquared).AsReadOnly()));
      // 
      // } else {
      //   IRegressionSolution currBestTrainingSolution = (IRegressionSolution)currBestTrainingSolutionResult.Value;
      //   if (currBestTrainingSolution.TrainingRSquared <= newSolution.TrainingRSquared) {
      //     BestTrainingSentence = symbolString;
      //     currBestTrainingSolutionResult.Value = newSolution;
      //     Results.AddOrUpdateResult(BestTrainingSolutionQuality, new DoubleValue(newSolution.TrainingRSquared).AsReadOnly());
      //   }
      // 
      //   IRegressionSolution currBestTestSolution = (IRegressionSolution)currBestTestSolutionResult.Value;
      //   if (currBestTestSolution.TestRSquared <= newSolution.TestRSquared) {
      //     BestTestSentence = symbolString;
      //     currBestTestSolutionResult.Value = newSolution;
      //     Results.AddOrUpdateResult(BestTestSolutionQuality, new DoubleValue(newSolution.TestRSquared).AsReadOnly());
      //   }
      // }
    }
  }
}