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

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>> DistinctGenerated;
    public List<Tuple<SymbolString, int>> AllGenerated;
    #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) {
      BestTrainingSentence = null;
      BestTrainingSentence = null;
      AllGenerated = new List<Tuple<SymbolString, int>>();
      DistinctGenerated = new List<Tuple<SymbolString, int>>();

      Dictionary<int, SymbolString> evaluatedHashes = new Dictionary<int, SymbolString>();

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

      Stack<SymbolString> remainingTrees = new Stack<SymbolString>();
      remainingTrees.Push(new SymbolString(new[] { Grammar.StartSymbol }));

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

        SymbolString currSymbolString = remainingTrees.Pop();

        if (currSymbolString.IsSentence()) {
          AllGenerated.Add(new Tuple<SymbolString, int>(currSymbolString, Grammar.CalcHashCode(currSymbolString)));

          int currSymbolStringHash = Grammar.CalcHashCode(currSymbolString);
          if (!evaluatedHashes.ContainsKey(currSymbolStringHash)
              || evaluatedHashes[currSymbolStringHash].Count > currSymbolString.Count) {
            evaluatedHashes[currSymbolStringHash] = currSymbolString;

            DistinctGenerated.Add(new Tuple<SymbolString, int>(currSymbolString, Grammar.CalcHashCode(currSymbolString)));
            EvaluateSentence(currSymbolString);
          }
          UpdateView(AllGenerated, DistinctGenerated);

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

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

            if (newSentence.Count <= MaxTreeSize) {
              remainingTrees.Push(newSentence);
            }
          }
        }
      }

      UpdateView(AllGenerated, DistinctGenerated, force: true);

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

      string[,] distinctSentences = new string[DistinctGenerated.Count, 3];
      for (int i = 0; i < DistinctGenerated.Count; i++) {
        distinctSentences[i, 0] = DistinctGenerated[i].Item1.ToString();
        distinctSentences[i, 1] = Grammar.PostfixToInfixParser(DistinctGenerated[i].Item1).ToString();
        distinctSentences[i, 2] = DistinctGenerated[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());

      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());
        }
      }
    }
  }
}