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

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

#2886: Add parsing to infix form for debugging purpose.

File size: 8.9 KB
Line 
1using System.Collections.Generic;
2using System.Linq;
3using System.Threading;
4using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
5using HeuristicLab.Common;
6using HeuristicLab.Core;
7using HeuristicLab.Data;
8using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
9using HeuristicLab.Optimization;
10using HeuristicLab.Parameters;
11using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
12using HeuristicLab.Problems.DataAnalysis;
13using HeuristicLab.Problems.DataAnalysis.Symbolic;
14using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
15
16namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
17  [Item("Grammar Enumeration Symbolic Regression", "Iterates all possible model structures for a fixed grammar.")]
18  [StorableClass]
19  [Creatable(CreatableAttribute.Categories.DataAnalysisRegression, Priority = 250)]
20  public class GrammarEnumerationAlgorithm : FixedDataAnalysisAlgorithm<IRegressionProblem> {
21    private readonly string BestTrainingSolution = "Best solution (training)";
22    private readonly string BestTrainingSolutionQuality = "Best solution quality (training)";
23    private readonly string BestTestSolution = "Best solution (test)";
24    private readonly string BestTestSolutionQuality = "Best solution quality (test)";
25
26    private readonly string MaxTreeSizeParameterName = "Max. Tree Nodes";
27    private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval";
28    private readonly string UseMemoizationParameterName = "Use Memoization?";
29
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<SymbolString> allGenerated = new List<SymbolString>();
92      List<SymbolString> distinctGenerated = new List<SymbolString>();
93
94      int expansions = 0;
95
96      HashSet<int> evaluatedHashes = new HashSet<int>();
97
98      Grammar = new Grammar(Problem.ProblemData.AllowedInputVariables.ToArray());
99
100      Stack<SymbolString> remainingTrees = new Stack<SymbolString>();
101      remainingTrees.Push(new SymbolString(new[] { Grammar.StartSymbol }));
102
103      while (remainingTrees.Any()) {
104        if (cancellationToken.IsCancellationRequested) break;
105
106        SymbolString currSymbolString = remainingTrees.Pop();
107
108        if (currSymbolString.IsSentence()) {
109          allGenerated.Add(Grammar.PostfixToInfixParser(currSymbolString));
110
111          //if (evaluatedHashes.Add(grammar.CalcHashCode(currSymbolString))) {
112          EvaluateSentence(currSymbolString);
113          distinctGenerated.Add(Grammar.PostfixToInfixParser(currSymbolString));
114          //}
115
116          UpdateView(allGenerated, distinctGenerated, expansions);
117
118        } else {
119          // expand next nonterminal symbols
120          int nonterminalSymbolIndex = currSymbolString.FindIndex(s => s is NonterminalSymbol);
121          NonterminalSymbol expandedSymbol = currSymbolString[nonterminalSymbolIndex] as NonterminalSymbol;
122
123          foreach (Production productionAlternative in expandedSymbol.Alternatives) {
124            SymbolString newSentence = new SymbolString(currSymbolString);
125            newSentence.RemoveAt(nonterminalSymbolIndex);
126            newSentence.InsertRange(nonterminalSymbolIndex, productionAlternative);
127
128            if (newSentence.Count <= MaxTreeSize) {
129              remainingTrees.Push(newSentence);
130            }
131          }
132        }
133      }
134
135      UpdateView(allGenerated, distinctGenerated, expansions, force: true);
136
137      StringArray sentences = new StringArray(allGenerated.Select(r => r.ToString()).ToArray());
138      Results.Add(new Result("All generated sentences", sentences));
139      StringArray distinctSentences = new StringArray(distinctGenerated.Select(r => r.ToString()).ToArray());
140      Results.Add(new Result("Distinct generated sentences", distinctSentences));
141    }
142
143
144    private void UpdateView(List<SymbolString> allGenerated, List<SymbolString> distinctGenerated, int expansions, bool force = false) {
145      int generatedSolutions = allGenerated.Count;
146      int distinctSolutions = distinctGenerated.Count;
147
148      if (force || generatedSolutions % GuiUpdateInterval == 0) {
149        Results.AddOrUpdateResult("Generated Solutions", new IntValue(generatedSolutions));
150        Results.AddOrUpdateResult("Distinct Solutions", new IntValue(distinctSolutions));
151
152        DoubleValue averageTreeLength = new DoubleValue(allGenerated.Select(r => r.Count).Average());
153        Results.AddOrUpdateResult("Average Tree Length of Solutions", averageTreeLength);
154
155        IntValue expansionsValue = new IntValue(expansions);
156        Results.AddOrUpdateResult("Expansions", expansionsValue);
157      }
158    }
159
160    private void EvaluateSentence(SymbolString symbolString) {
161      SymbolicExpressionTree tree = Grammar.ParseSymbolicExpressionTree(symbolString);
162      SymbolicRegressionModel model = new SymbolicRegressionModel(
163        Problem.ProblemData.TargetVariable,
164        tree,
165        new SymbolicDataAnalysisExpressionTreeLinearInterpreter());
166
167      IRegressionSolution newSolution = model.CreateRegressionSolution(Problem.ProblemData);
168
169      IResult currBestTrainingSolutionResult;
170      IResult currBestTestSolutionResult;
171      if (!Results.TryGetValue(BestTrainingSolution, out currBestTrainingSolutionResult)
172           || !Results.TryGetValue(BestTestSolution, out currBestTestSolutionResult)) {
173
174        BestTrainingSentence = symbolString;
175        Results.Add(new Result(BestTrainingSolution, newSolution));
176        Results.Add(new Result(BestTrainingSolutionQuality, new DoubleValue(newSolution.TrainingRSquared).AsReadOnly()));
177
178        BestTestSentence = symbolString;
179        Results.Add(new Result(BestTestSolution, newSolution));
180        Results.Add(new Result(BestTestSolutionQuality, new DoubleValue(newSolution.TestRSquared).AsReadOnly()));
181
182      } else {
183        IRegressionSolution currBestTrainingSolution = (IRegressionSolution)currBestTrainingSolutionResult.Value;
184        if (currBestTrainingSolution.TrainingRSquared < newSolution.TrainingRSquared) {
185          BestTrainingSentence = symbolString;
186          currBestTrainingSolutionResult.Value = newSolution;
187          Results.AddOrUpdateResult(BestTrainingSolutionQuality, new DoubleValue(newSolution.TrainingRSquared).AsReadOnly());
188        }
189
190        IRegressionSolution currBestTestSolution = (IRegressionSolution)currBestTestSolutionResult.Value;
191        if (currBestTestSolution.TestRSquared < newSolution.TestRSquared) {
192          BestTestSentence = symbolString;
193          currBestTestSolutionResult.Value = newSolution;
194          Results.AddOrUpdateResult(BestTestSolutionQuality, new DoubleValue(newSolution.TestRSquared).AsReadOnly());
195        }
196      }
197    }
198  }
199}
Note: See TracBrowser for help on using the repository browser.