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

Last change on this file since 15725 was 15725, checked in by lkammere, 20 months ago

#2886: Refactor tree hash function.

File size: 9.1 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Threading;
5using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
6using HeuristicLab.Common;
7using HeuristicLab.Core;
8using HeuristicLab.Data;
9using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
10using HeuristicLab.Optimization;
11using HeuristicLab.Parameters;
12using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
13using HeuristicLab.Problems.DataAnalysis;
14using HeuristicLab.Problems.DataAnalysis.Symbolic;
15using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
16
17namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
18  [Item("Grammar Enumeration Symbolic Regression", "Iterates all possible model structures for a fixed grammar.")]
19  [StorableClass]
20  [Creatable(CreatableAttribute.Categories.DataAnalysisRegression, Priority = 250)]
21  public class GrammarEnumerationAlgorithm : FixedDataAnalysisAlgorithm<IRegressionProblem> {
22    private readonly string BestTrainingSolution = "Best solution (training)";
23    private readonly string BestTrainingSolutionQuality = "Best solution quality (training)";
24    private readonly string BestTestSolution = "Best solution (test)";
25    private readonly string BestTestSolutionQuality = "Best solution quality (test)";
26
27    private readonly string MaxTreeSizeParameterName = "Max. Tree Nodes";
28    private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval";
29    private readonly string UseMemoizationParameterName = "Use Memoization?";
30
31    #region properties
32    protected IValueParameter<IntValue> MaxTreeSizeParameter {
33      get { return (IValueParameter<IntValue>)Parameters[MaxTreeSizeParameterName]; }
34    }
35    public int MaxTreeSize {
36      get { return MaxTreeSizeParameter.Value.Value; }
37      set { MaxTreeSizeParameter.Value.Value = value; }
38    }
39
40    protected IValueParameter<IntValue> GuiUpdateIntervalParameter {
41      get { return (IValueParameter<IntValue>)Parameters[GuiUpdateIntervalParameterName]; }
42    }
43    public int GuiUpdateInterval {
44      get { return GuiUpdateIntervalParameter.Value.Value; }
45      set { GuiUpdateIntervalParameter.Value.Value = value; }
46    }
47
48    protected IValueParameter<BoolValue> UseMemoizationParameter {
49      get { return (IValueParameter<BoolValue>)Parameters[UseMemoizationParameterName]; }
50    }
51    public bool UseMemoization {
52      get { return UseMemoizationParameter.Value.Value; }
53      set { UseMemoizationParameter.Value.Value = value; }
54    }
55
56    public SymbolString BestTrainingSentence;
57    public SymbolString BestTestSentence;
58
59    #endregion
60
61    public Grammar Grammar;
62
63
64    #region ctors
65    public override IDeepCloneable Clone(Cloner cloner) {
66      return new GrammarEnumerationAlgorithm(this, cloner);
67    }
68
69    public GrammarEnumerationAlgorithm() {
70
71      var provider = new HeuristicLab.Problems.Instances.DataAnalysis.VariousInstanceProvider(seed: 1234);
72      var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("Poly-10")));
73
74      Problem = new RegressionProblem() {
75        ProblemData = regProblem
76      };
77
78      Parameters.Add(new ValueParameter<IntValue>(MaxTreeSizeParameterName, "The number of clusters.", new IntValue(6)));
79      Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(4000)));
80      Parameters.Add(new ValueParameter<BoolValue>(UseMemoizationParameterName, "Should already subtrees be reused within a run.", new BoolValue(true)));
81    }
82
83    private GrammarEnumerationAlgorithm(GrammarEnumerationAlgorithm original, Cloner cloner) : base(original, cloner) { }
84    #endregion
85
86
87    protected override void Run(CancellationToken cancellationToken) {
88      BestTrainingSentence = null;
89      BestTrainingSentence = null;
90
91      List<Tuple<SymbolString, int>> allGenerated = new List<Tuple<SymbolString, int>>();
92      List<SymbolString> distinctGenerated = new List<SymbolString>();
93
94      HashSet<int> evaluatedHashes = new HashSet<int>();
95
96      Grammar = new Grammar(Problem.ProblemData.AllowedInputVariables.ToArray());
97
98      Stack<SymbolString> remainingTrees = new Stack<SymbolString>();
99      remainingTrees.Push(new SymbolString(new[] { Grammar.StartSymbol }));
100
101      while (remainingTrees.Any()) {
102        if (cancellationToken.IsCancellationRequested) break;
103
104        SymbolString currSymbolString = remainingTrees.Pop();
105
106        if (currSymbolString.IsSentence()) {
107          allGenerated.Add(new Tuple<SymbolString, int>(currSymbolString, Grammar.CalcHashCode(currSymbolString)));
108
109          if (evaluatedHashes.Add(Grammar.CalcHashCode(currSymbolString))) {
110            EvaluateSentence(currSymbolString);
111            distinctGenerated.Add(Grammar.PostfixToInfixParser(currSymbolString));
112          }
113
114          UpdateView(allGenerated, distinctGenerated);
115
116        } else {
117          // expand next nonterminal symbols
118          int nonterminalSymbolIndex = currSymbolString.FindIndex(s => s is NonterminalSymbol);
119          NonterminalSymbol expandedSymbol = currSymbolString[nonterminalSymbolIndex] as NonterminalSymbol;
120
121          foreach (Production productionAlternative in expandedSymbol.Alternatives) {
122            SymbolString newSentence = new SymbolString(currSymbolString);
123            newSentence.RemoveAt(nonterminalSymbolIndex);
124            newSentence.InsertRange(nonterminalSymbolIndex, productionAlternative);
125
126            if (newSentence.Count <= MaxTreeSize) {
127              remainingTrees.Push(newSentence);
128            }
129          }
130        }
131      }
132
133      UpdateView(allGenerated, distinctGenerated, force: true);
134
135      string[,] sentences = new string[allGenerated.Count, 3];
136      for (int i = 0; i < allGenerated.Count; i++) {
137        sentences[i, 0] = allGenerated[i].Item1.ToString();
138        sentences[i, 1] = Grammar.PostfixToInfixParser(allGenerated[i].Item1).ToString();
139        sentences[i, 2] = allGenerated[i].Item2.ToString();
140      }
141      Results.Add(new Result("All generated sentences", new StringMatrix(sentences)));
142
143      StringArray distinctSentences = new StringArray(distinctGenerated.Select(r => r.ToString()).ToArray());
144      Results.Add(new Result("Distinct generated sentences", distinctSentences));
145    }
146
147
148    private void UpdateView(List<Tuple<SymbolString, int>> allGenerated, List<SymbolString> distinctGenerated, bool force = false) {
149      int generatedSolutions = allGenerated.Count;
150      int distinctSolutions = distinctGenerated.Count;
151
152      if (force || generatedSolutions % GuiUpdateInterval == 0) {
153        Results.AddOrUpdateResult("Generated Solutions", new IntValue(generatedSolutions));
154        Results.AddOrUpdateResult("Distinct Solutions", new IntValue(distinctSolutions));
155
156        DoubleValue averageTreeLength = new DoubleValue(allGenerated.Select(r => r.Item1.Count).Average());
157        Results.AddOrUpdateResult("Average Tree Length of Solutions", averageTreeLength);
158      }
159    }
160
161    private void EvaluateSentence(SymbolString symbolString) {
162      SymbolicExpressionTree tree = Grammar.ParseSymbolicExpressionTree(symbolString);
163      SymbolicRegressionModel model = new SymbolicRegressionModel(
164        Problem.ProblemData.TargetVariable,
165        tree,
166        new SymbolicDataAnalysisExpressionTreeLinearInterpreter());
167
168      IRegressionSolution newSolution = model.CreateRegressionSolution(Problem.ProblemData);
169
170      IResult currBestTrainingSolutionResult;
171      IResult currBestTestSolutionResult;
172      if (!Results.TryGetValue(BestTrainingSolution, out currBestTrainingSolutionResult)
173           || !Results.TryGetValue(BestTestSolution, out currBestTestSolutionResult)) {
174
175        BestTrainingSentence = symbolString;
176        Results.Add(new Result(BestTrainingSolution, newSolution));
177        Results.Add(new Result(BestTrainingSolutionQuality, new DoubleValue(newSolution.TrainingRSquared).AsReadOnly()));
178
179        BestTestSentence = symbolString;
180        Results.Add(new Result(BestTestSolution, newSolution));
181        Results.Add(new Result(BestTestSolutionQuality, new DoubleValue(newSolution.TestRSquared).AsReadOnly()));
182
183      } else {
184        IRegressionSolution currBestTrainingSolution = (IRegressionSolution)currBestTrainingSolutionResult.Value;
185        if (currBestTrainingSolution.TrainingRSquared < newSolution.TrainingRSquared) {
186          BestTrainingSentence = symbolString;
187          currBestTrainingSolutionResult.Value = newSolution;
188          Results.AddOrUpdateResult(BestTrainingSolutionQuality, new DoubleValue(newSolution.TrainingRSquared).AsReadOnly());
189        }
190
191        IRegressionSolution currBestTestSolution = (IRegressionSolution)currBestTestSolutionResult.Value;
192        if (currBestTestSolution.TestRSquared < newSolution.TestRSquared) {
193          BestTestSentence = symbolString;
194          currBestTestSolutionResult.Value = newSolution;
195          Results.AddOrUpdateResult(BestTestSolutionQuality, new DoubleValue(newSolution.TestRSquared).AsReadOnly());
196        }
197      }
198    }
199  }
200}
Note: See TracBrowser for help on using the repository browser.