Changeset 15746

Timestamp:

02/09/18 15:32:44 (7 years ago)

Author:

lkammere

Message:

#2886: Refactor grammar enumeration alg.

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (8 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs (added)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj (modified) (1 diff)
• Test/GrammarEnumerationTest.cs (modified) (11 diffs)
• Test/TreeHashingTest.cs (modified) (1 diff)

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs

@@ -90 +90 @@
     }
 
-    /*
-    #region Memoize subtrees
-
-    public void MemoizeSubtrees(SymbolString sentence) {
-      Stack<TerminalSymbol> parseStack = new Stack<TerminalSymbol>(sentence.OfType<TerminalSymbol>());
-
-      // Parse root symbol "+"
-      MemoizeSubtreeExpression(parseStack);
-    }
-
-    private SymbolString MemoizeSubtreeExpression(Stack<TerminalSymbol> parseStack) {
-      SymbolString subtree = new SymbolString();
-
-      if (ReferenceEquals(parseStack.Peek(), Addition)) {
-        subtree.Add(parseStack.Pop());
-        subtree.InsertRange(0, MemoizeSubtreeExpression(parseStack));
-        subtree.InsertRange(0, MemoizeSubtreeTerm(parseStack));
-
-        Expr.Alternatives[0].GeneratedSentences.Add(subtree);
-      } else {
-        subtree.InsertRange(0, MemoizeSubtreeTerm(parseStack));
-
-        Expr.Alternatives[1].GeneratedSentences.Add(subtree);
-      }
-
-      return subtree;
-    }
-
-    private SymbolString MemoizeSubtreeTerm(Stack<TerminalSymbol> parseStack) {
-      SymbolString subtree = new SymbolString();
-
-      if (ReferenceEquals(parseStack.Peek(), Multiplication)) {
-        subtree.Add(parseStack.Pop());
-        subtree.InsertRange(0, MemoizeSubtreeTerm(parseStack));
-        subtree.InsertRange(0, MemoizeSubtreeFactor(parseStack));
-
-        Term.Alternatives[0].GeneratedSentences.Add(subtree);
-      } else {
-        subtree.InsertRange(0, MemoizeSubtreeFactor(parseStack));
-
-        Term.Alternatives[1].GeneratedSentences.Add(subtree);
-      }
-
-      return subtree;
-    }
-
-    private SymbolString MemoizeSubtreeFactor(Stack<TerminalSymbol> parseStack) {
-      SymbolString subtree = new SymbolString(MemoizeSubtreeVar(parseStack));
-
-      Factor.Alternatives[0].GeneratedSentences.Add(subtree);
-      return subtree;
-    }
-
-    private SymbolString MemoizeSubtreeVar(Stack<TerminalSymbol> parseStack) {
-      SymbolString subtree = new SymbolString(parseStack.Pop().ToEnumerable());
-
-      // ... not really
-      //Var.Alternatives[0].GeneratedSentences.Add(subtree);
-      return subtree;
-    }
-
-
-    #endregion
-    */
-
     #region Hashing
     public int CalcHashCode(SymbolString sentence) {
@@ -221 +156 @@
       }
 
-      // var
+      // var or nonterminal symbol
       return currentSymbol.StringRepresentation.GetHashCode().ToEnumerable().ToArray();
-
-
-      // throw new ArgumentException("Trying to hash malformed sentence!");
     }
 

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs

@@ -1 @@
-using System;
-using System.Collections.Generic;
+using System.Collections.Generic;
 using System.Linq;
 using System.Threading;
@@ -20 +19 @@
   [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)";
-
+    #region properties and result names
+    private readonly string BestTrainingQualityName = "Best R² (Training)";
+    private readonly string BestTrainingSolutionName = "Best solution (Training)";
+    private readonly string GeneratedSentencesName = "Generated Sentences";
+    private readonly string DistinctSentencesName = "Distinct Sentences";
+    private readonly string PhraseExpansionsName = "Phrase Expansions";
+    private readonly string AverageTreeLengthName = "Avg. Sentence Length among Distinct";
+    private readonly string GeneratedEqualSentencesName = "Generated equal sentences";
+
+
+    private readonly string SearchDataStructureParameterName = "Search Data Structure";
     private readonly string MaxTreeSizeParameterName = "Max. Tree Nodes";
     private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval";
-    private readonly string UseMemoizationParameterName = "Use Memoization?";
-
-    #region properties
+    
+    public override bool SupportsPause { get { return false; } }
+
     protected IValueParameter<IntValue> MaxTreeSizeParameter {
       get { return (IValueParameter<IntValue>)Parameters[MaxTreeSizeParameterName]; }
@@ -46 +51 @@
     }
 
-    protected IValueParameter<BoolValue> UseMemoizationParameter {
-      get { return (IValueParameter<BoolValue>)Parameters[UseMemoizationParameterName]; }
-    }
-    public bool UseMemoization {
-      get { return UseMemoizationParameter.Value.Value; }
-      set { UseMemoizationParameter.Value.Value = value; }
+    protected IValueParameter<EnumValue<StorageType>> SearchDataStructureParameter {
+      get { return (IValueParameter<EnumValue<StorageType>>)Parameters[SearchDataStructureParameterName]; }
+    }
+    public StorageType SearchDataStructure {
+      get { return SearchDataStructureParameter.Value.Value; }
+      set { SearchDataStructureParameter.Value.Value = value; }
     }
 
     public SymbolString BestTrainingSentence;
-    public SymbolString BestTestSentence;
-
-    public List<Tuple<SymbolString, int>> distinctSentences;
-    public List<Tuple<SymbolString, int>> sentences;
-    #endregion
-
+
+    #endregion
+
+    public Dictionary<int, SymbolString> DistinctSentences;   // Semantically distinct sentences in a run.
+    public Dictionary<int, List<SymbolString>> AllSentences;  // All sentences ever generated in a run.
+    public Dictionary<int, SymbolString> ArchivedPhrases;     // Nodes in the search tree
+    SearchDataStore OpenPhrases;                              // Stack/Queue/etc. for fetching the next node in the search tree.  
+
+    public int EqualGeneratedSentences; // It is not guaranteed that shorter solutions are found first. 
+                                        // When longer solutions are overwritten with shorter ones, 
+                                        // this counter is increased.
+    public int Expansions;              // Number, how many times a nonterminal symbol is replaced with a production rule.
     public Grammar Grammar;
-
 
     #region ctors
@@ -70 +80 @@
 
     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")));
@@ -80 +89 @@
       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
-
+
+      Parameters.Add(new ValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.RandomList)));
+    }
+
+    public 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>();
+      #region init
+      InitResults();
+
+      AllSentences = new Dictionary<int, List<SymbolString>>();
+      ArchivedPhrases = new Dictionary<int, SymbolString>(); // Nodes in the search tree
+      DistinctSentences = new Dictionary<int, SymbolString>();
+      Expansions = 0;
+      EqualGeneratedSentences = 0;
 
       Grammar = new Grammar(Problem.ProblemData.AllowedInputVariables.ToArray());
 
-      var phrases = new Dictionary<int, SymbolString>();
+      OpenPhrases = new SearchDataStore(SearchDataStructure); // Select search strategy
       var phrase0 = new SymbolString(new[] { Grammar.StartSymbol });
-      phrases.Add(Grammar.CalcHashCode(phrase0), phrase0);
-
-      while (phrases.Any()) {
+      #endregion
+
+      OpenPhrases.Store(Grammar.CalcHashCode(phrase0), phrase0);
+
+      while (OpenPhrases.Count > 0) {
         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);
+        StoredSymbolString fetchedPhrase = OpenPhrases.GetNext();
+        SymbolString currPhrase = fetchedPhrase.SymbolString;
+
+        ArchivedPhrases.Add(fetchedPhrase.Hash, currPhrase);
+
+        // 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 newPhrase = new SymbolString(currPhrase);
+          newPhrase.RemoveAt(nonterminalSymbolIndex);
+          newPhrase.InsertRange(nonterminalSymbolIndex, productionAlternative);
+
+          Expansions++;
+          if (newPhrase.Count <= MaxTreeSize) {
+            var phraseHash = Grammar.CalcHashCode(newPhrase);
+
+            if (newPhrase.IsSentence()) { // Sentence was generated.
+              SaveToAllSentences(phraseHash, newPhrase);
+
+              if (!DistinctSentences.ContainsKey(phraseHash) || DistinctSentences[phraseHash].Count > newPhrase.Count) {
+                if (DistinctSentences.ContainsKey(phraseHash)) EqualGeneratedSentences++; // for analysis only
+
+                DistinctSentences[phraseHash] = newPhrase;
+                EvaluateSentence(newPhrase);
+              }
+              UpdateView(AllSentences, DistinctSentences, Expansions);
+
+            } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.ContainsKey(phraseHash)) {
+              OpenPhrases.Store(phraseHash, newPhrase);
             }
           }
@@ -158 +153 @@
       }
 
-      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);
-      }
-    }
-
+      UpdateView(AllSentences, DistinctSentences, Expansions, force: true);
+      UpdateFinalResults();
+    }
+
+    // Store sentence to "MultiDictionary"
+    private void SaveToAllSentences(int hash, SymbolString sentence) {
+      if (AllSentences.ContainsKey(hash))
+        AllSentences[hash].Add(sentence);
+      else
+        AllSentences[hash] = new List<SymbolString> { sentence };
+    }
+
+    #region Evaluation of generated models.
+
+    // Evaluate sentence within an algorithm run.
     private void EvaluateSentence(SymbolString symbolString) {
       SymbolicExpressionTree tree = Grammar.ParseSymbolicExpressionTree(symbolString);
@@ -198 +174 @@
         tree,
         new SymbolicDataAnalysisExpressionTreeLinearInterpreter());
+
       var probData = Problem.ProblemData;
       var target = probData.TargetVariableTrainingValues;
@@ -205 +182 @@
       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());
-      //   }
-      // }
-    }
+      var bestR2 = ((DoubleValue)Results[BestTrainingQualityName].Value).Value;
+      if (r2 > bestR2) {
+        ((DoubleValue)Results[BestTrainingQualityName].Value).Value = r2;
+        BestTrainingSentence = symbolString;
+      }
+    }
+
+    #endregion
+
+    #region Visualization in HL
+    // Initialize entries in result set.
+    private void InitResults() {
+      BestTrainingSentence = null;
+
+      Results.Add(new Result(BestTrainingQualityName, new DoubleValue(-1.0)));
+
+      Results.Add(new Result(GeneratedSentencesName, new IntValue(0)));
+      Results.Add(new Result(DistinctSentencesName, new IntValue(0)));
+      Results.Add(new Result(PhraseExpansionsName, new IntValue(0)));
+      Results.Add(new Result(GeneratedEqualSentencesName, new IntValue(0)));
+      Results.Add(new Result(AverageTreeLengthName, new DoubleValue(1.0)));
+    }
+
+    // Update the view for intermediate results in an algorithm run.
+    private int updates;
+    private void UpdateView(Dictionary<int, List<SymbolString>> allGenerated,
+        Dictionary<int, SymbolString> distinctGenerated, int expansions, bool force = false) {
+      updates++;
+
+      if (force || updates % GuiUpdateInterval == 0) {
+        var allGeneratedEnum = allGenerated.Values.SelectMany(x => x).ToArray();
+        ((IntValue)Results[GeneratedSentencesName].Value).Value = allGeneratedEnum.Length;
+        ((IntValue)Results[DistinctSentencesName].Value).Value = distinctGenerated.Count;
+        ((IntValue)Results[PhraseExpansionsName].Value).Value = expansions;
+        ((IntValue)Results[GeneratedEqualSentencesName].Value).Value = EqualGeneratedSentences;
+        ((DoubleValue)Results[AverageTreeLengthName].Value).Value = allGeneratedEnum.Select(sentence => sentence.Count).Average();
+      }
+    }
+
+    // Generate all Results after an algorithm run.
+    private void UpdateFinalResults() {
+      SymbolicExpressionTree tree = Grammar.ParseSymbolicExpressionTree(BestTrainingSentence);
+      SymbolicRegressionModel model = new SymbolicRegressionModel(
+        Problem.ProblemData.TargetVariable,
+        tree,
+        new SymbolicDataAnalysisExpressionTreeLinearInterpreter());
+
+      IRegressionSolution bestTrainingSolution = new RegressionSolution(model, Problem.ProblemData);
+      Results.AddOrUpdateResult(BestTrainingSolutionName, bestTrainingSolution);
+
+      // Print generated sentences.
+      string[,] sentencesMatrix = new string[AllSentences.Values.SelectMany(x => x).Count(), 3];
+
+      int i = 0;
+      foreach (var sentenceSet in AllSentences) {
+        foreach (var sentence in sentenceSet.Value) {
+          sentencesMatrix[i, 0] = sentence.ToString();
+          sentencesMatrix[i, 1] = Grammar.PostfixToInfixParser(sentence).ToString();
+          sentencesMatrix[i, 2] = sentenceSet.Key.ToString();
+          i++;
+        }
+      }
+      Results.Add(new Result("All generated sentences", new StringMatrix(sentencesMatrix)));
+
+      string[,] distinctSentencesMatrix = new string[DistinctSentences.Count, 3];
+      i = 0;
+      foreach (KeyValuePair<int, SymbolString> distinctSentence in DistinctSentences) {
+        distinctSentencesMatrix[i, 0] = distinctSentence.Key.ToString();
+        distinctSentencesMatrix[i, 1] = Grammar.PostfixToInfixParser(distinctSentence.Value).ToString();
+        distinctSentencesMatrix[i, 2] = distinctSentence.Key.ToString();
+        i++;
+      }
+      Results.Add(new Result("Distinct generated sentences", new StringMatrix(distinctSentencesMatrix)));
+    }
+    #endregion
+ 
   }
 }

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj

@@ -93 +93 @@
     <Compile Include="GrammarEnumeration\Grammar.cs" />
     <Compile Include="GrammarEnumeration\GrammarEnumerationAlgorithm.cs" />
+    <Compile Include="GrammarEnumeration\SearchDataStructure.cs" />
     <Compile Include="GrammarEnumeration\Sentence.cs" />
     <Compile Include="Plugin.cs" />

branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

@@ -1 +1 @@
 using System;
+using System.Diagnostics;
 using System.Linq;
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration;
@@ -24 +25 @@
     [TestInitialize]
     public void InitTest() {
-      Console.Write("init called... ");
       rand = new FastRandom(Seed);
 
@@ -33 +33 @@
     }
 
-    [TestCleanup()]
+    [TestCleanup]
     public void Cleanup() {
       if (alg.BestTrainingSentence != null) {
         Console.WriteLine("Training: " + alg.Grammar.PostfixToInfixParser(alg.BestTrainingSentence));
       }
-      if (alg.BestTestSentence != null) {
-        Console.WriteLine("Test: " + alg.Grammar.PostfixToInfixParser(alg.BestTestSentence));
-      }
     }
 
@@ -49 +46 @@
 
       // Check if algorithm terminated correctly
-      Assert.IsTrue(alg.Results.ContainsKey("Best solution quality (training)"), "No training solution returned!");
-      Assert.IsTrue(alg.Results.ContainsKey("Best solution quality (test)"), "No test solution returned!");
+      Assert.IsTrue(alg.Results.ContainsKey("Best solution (Training)"), "No training solution returned!");
 
       // Check resultss
-      Assert.AreEqual(1.0, ((DoubleValue)alg.Results["Best solution quality (training)"].Value).Value, eps, "Training quality too low!");
-      Assert.AreEqual(1.0, ((DoubleValue)alg.Results["Best solution quality (test)"].Value).Value, eps, "Test quality too low!");
-
-      // Check overfitting
-      Assert.AreEqual(alg.Grammar.CalcHashCode(alg.BestTrainingSentence),
-                    alg.Grammar.CalcHashCode(alg.BestTestSentence),
-                    "Training and Test solution are not equal!");
+      Assert.AreEqual(1.0, ((IRegressionSolution)alg.Results["Best solution (Training)"].Value).TestRSquared, eps, "Test quality too low!");
     }
 
@@ -68 +58 @@
     public void MctsSymbReg_NoConstants_Nguyen1() {
       // x³ + x² + x
-      alg.MaxTreeSize = 3;
+      alg.MaxTreeSize = 15;
       Console.WriteLine(alg.MaxTreeSize);
       var provider = new HeuristicLab.Problems.Instances.DataAnalysis.NguyenInstanceProvider(Seed);
@@ -75 +65 @@
 
       alg.Start();
-
-      // Evaluate
-      // EvaluateGrammarEnumeration();
 
       TerminalSymbol varSymbol = alg.Grammar.Var.VariableTerminalSymbols.First();
@@ -90 +77 @@
 
       int targetSolutionHash = alg.Grammar.CalcHashCode(targetSolution);
-      int actualSolutionHash = alg.Grammar.CalcHashCode(alg.BestTestSentence);
-
-      Assert.IsTrue(alg.distinctSentences.Select(tuple => tuple.Item2).Contains(actualSolutionHash));
-
-      // last because long sentences are overwritten by short ones.
-      Console.WriteLine(alg.Grammar.PostfixToInfixParser(alg.distinctSentences.Last(tuple => tuple.Item2 == targetSolutionHash).Item1));
-
-
-      Assert.AreEqual(targetSolutionHash, actualSolutionHash);
+      int actualSolutionHash = alg.Grammar.CalcHashCode(alg.BestTrainingSentence);
+
+      Assert.IsTrue(alg.DistinctSentences.ContainsKey(actualSolutionHash), "Actual solution was not generated!");
+
+      Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
+
+      // Evaluate
+      EvaluateGrammarEnumeration();
     }
 
@@ -105 +91 @@
     public void MctsSymbReg_NoConstants_Nguyen2() {
       // x^4 + x³ + x² + x
-      alg.MaxTreeSize = 30;
+      alg.MaxTreeSize = 25;
       var provider = new HeuristicLab.Problems.Instances.DataAnalysis.NguyenInstanceProvider(Seed);
       var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("F2 ")));
@@ -111 +97 @@
 
       alg.Start();
+
+      TerminalSymbol varSymbol = alg.Grammar.Var.VariableTerminalSymbols.First();
+      TerminalSymbol mulSymbol = alg.Grammar.Multiplication;
+      TerminalSymbol addSymbol = alg.Grammar.Addition;
+
+      SymbolString targetSolution = new SymbolString(new[] {
+        varSymbol, varSymbol, varSymbol, varSymbol, mulSymbol, mulSymbol, mulSymbol,
+        varSymbol, varSymbol, varSymbol, mulSymbol, mulSymbol, addSymbol,
+        varSymbol, varSymbol, mulSymbol, addSymbol,
+        varSymbol, addSymbol
+      });
+
+      int targetSolutionHash = alg.Grammar.CalcHashCode(targetSolution);
+      int actualSolutionHash = alg.Grammar.CalcHashCode(alg.BestTrainingSentence);
+
+      var targetSolutionStr = alg.Grammar.PostfixToInfixParser(targetSolution).ToString();
+      var foundTargetSolutionStr = alg.Grammar.PostfixToInfixParser(alg.DistinctSentences[targetSolutionHash]).ToString();
+      var actualSolutionStr = alg.Grammar.PostfixToInfixParser(alg.DistinctSentences[targetSolutionHash]).ToString();
+
+      Assert.IsTrue(alg.DistinctSentences.ContainsKey(targetSolutionHash), "Target solution was not generated!");
+
+      Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
 
       // Evaluate
@@ -126 +134 @@
       alg.Start();
 
-      Assert.AreEqual(alg.distinctSentences.Count(), 110);
+      Assert.AreEqual(alg.DistinctSentences.Count(), 110);
 
       // Evaluate
@@ -142 +150 @@
       alg.Start();
 
-      Assert.AreEqual(alg.distinctSentences.Count(), 16);
+      Assert.AreEqual(alg.DistinctSentences.Count(), 16);
 
       // Evaluate

branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs

@@ -94 +94 @@
     }
 
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void NonterminalHashing() {
+      SymbolString s1 = new SymbolString(new Symbol[] { varA, varA, grammar.Expr, grammar.Addition, grammar.Addition });
+      SymbolString s2 = new SymbolString(new Symbol[] { varA, grammar.Expr, grammar.Addition });
+
+      int hash1 = grammar.CalcHashCode(s1);
+      int hash2 = grammar.CalcHashCode(s2);
+
+      Assert.AreEqual(hash1, hash2);
+    }
+
 
     #region parser