Changeset 15726

Timestamp:

02/06/18 22:11:56 (7 years ago)

Author:

lkammere

Message:

#2886: Overwrite long sentences when a shorter one with same hash was found.

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (6 diffs)
• Test/GrammarEnumerationTest.cs (modified) (4 diffs)

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

@@ -57 +57 @@
     public SymbolString BestTestSentence;
 
+    public List<Tuple<SymbolString, int>> DistinctGenerated;
+    public List<Tuple<SymbolString, int>> AllGenerated;
     #endregion
 
@@ -88 +90 @@
       BestTrainingSentence = null;
       BestTrainingSentence = null;
-
-      List<Tuple<SymbolString, int>> allGenerated = new List<Tuple<SymbolString, int>>();
-      List<SymbolString> distinctGenerated = new List<SymbolString>();
-
-      HashSet<int> evaluatedHashes = new HashSet<int>();
+      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());
@@ -105 +106 @@
 
         if (currSymbolString.IsSentence()) {
-          allGenerated.Add(new Tuple<SymbolString, int>(currSymbolString, Grammar.CalcHashCode(currSymbolString)));
-
-          if (evaluatedHashes.Add(Grammar.CalcHashCode(currSymbolString))) {
+          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);
-            distinctGenerated.Add(Grammar.PostfixToInfixParser(currSymbolString));
           }
-
-          UpdateView(allGenerated, distinctGenerated);
+          UpdateView(AllGenerated, DistinctGenerated);
 
         } else {
@@ -131 +135 @@
       }
 
-      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();
+      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)));
 
-      StringArray distinctSentences = new StringArray(distinctGenerated.Select(r => r.ToString()).ToArray());
-      Results.Add(new Result("Distinct generated sentences", distinctSentences));
-    }
-
-
-    private void UpdateView(List<Tuple<SymbolString, int>> allGenerated, List<SymbolString> distinctGenerated, bool force = false) {
+      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;
@@ -183 +193 @@
       } else {
         IRegressionSolution currBestTrainingSolution = (IRegressionSolution)currBestTrainingSolutionResult.Value;
-        if (currBestTrainingSolution.TrainingRSquared < newSolution.TrainingRSquared) {
+        if (currBestTrainingSolution.TrainingRSquared <= newSolution.TrainingRSquared) {
           BestTrainingSentence = symbolString;
           currBestTrainingSolutionResult.Value = newSolution;
@@ -190 +200 @@
 
         IRegressionSolution currBestTestSolution = (IRegressionSolution)currBestTestSolutionResult.Value;
-        if (currBestTestSolution.TestRSquared < newSolution.TestRSquared) {
+        if (currBestTestSolution.TestRSquared <= newSolution.TestRSquared) {
           BestTestSentence = symbolString;
           currBestTestSolutionResult.Value = newSolution;

branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

@@ -2 +2 @@
 using System.Linq;
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration;
+using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -43 +44 @@
 
 
-    private void TestGrammarEnumeration(IRegressionProblemData problemData) {
-      alg.Problem.ProblemData = problemData;
-
-      // Run
-      alg.Start();
-
+    private void EvaluateGrammarEnumeration() {
       // Evaluate results
       var eps = 1.0 - SuccessThreshold;
@@ -72 +68 @@
     public void MctsSymbReg_NoConstants_Nguyen1() {
       // x³ + x² + x
-      alg.MaxTreeSize = 15;
+      alg.MaxTreeSize = 30;
+      Console.WriteLine(alg.MaxTreeSize);
       var provider = new HeuristicLab.Problems.Instances.DataAnalysis.NguyenInstanceProvider(Seed);
       var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("F1 ")));
-      TestGrammarEnumeration(regProblem);
+      alg.Problem.ProblemData = regProblem;
+
+      alg.Start();
+
+      // Evaluate
+      // EvaluateGrammarEnumeration();
+
+      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, mulSymbol, mulSymbol,
+        varSymbol, varSymbol, mulSymbol, addSymbol,
+        varSymbol, addSymbol
+      });
+
+      int targetSolutionHash = alg.Grammar.CalcHashCode(targetSolution);
+      int actualSolutionHash = alg.Grammar.CalcHashCode(alg.BestTestSentence);
+
+      Assert.IsTrue(alg.DistinctGenerated.Select(tuple => tuple.Item2).Contains(actualSolutionHash));
+
+      // last because long sentences are overwritten by short ones.
+      Console.WriteLine(alg.Grammar.PostfixToInfixParser(alg.DistinctGenerated.Last(tuple => tuple.Item2 == targetSolutionHash).Item1));
+
+
+      Assert.AreEqual(targetSolutionHash, actualSolutionHash);
     }
 
@@ -82 +105 @@
     public void MctsSymbReg_NoConstants_Nguyen2() {
       // x^4 + x³ + x² + x
-      alg.MaxTreeSize = 20;
+      alg.MaxTreeSize = 30;
       var provider = new HeuristicLab.Problems.Instances.DataAnalysis.NguyenInstanceProvider(Seed);
       var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("F2 ")));
-      TestGrammarEnumeration(regProblem);
+      alg.Problem.ProblemData = regProblem;
+
+      alg.Start();
+
+      // Evaluate
+      EvaluateGrammarEnumeration();
     }