Changeset 15915

Timestamp:

04/24/18 13:11:59 (6 years ago)

Author:

lkammere

Message:

#2886: Add separate data structure for storing phrases in the queue.

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/RSquaredEvaluator.cs (modified) (1 diff)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (4 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs (modified) (4 diffs)
• Test/GrammarEnumerationTest.cs (modified) (6 diffs)

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/RSquaredEvaluator.cs

@@ -110 +110 @@
           problemData.TrainingIndices,
           applyLinearScaling: false,
-          maxIterations: 50,
+          maxIterations: 10,
           updateVariableWeights: true,
           updateConstantsInTree: true);

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

@@ -174 +174 @@
       int maxSentenceLength = GetMaxSentenceLength();
 
-      OpenPhrases.Store(phrase0Hash, 0.0, phrase0);
+      OpenPhrases.Store(new SearchNode(phrase0Hash, 0.0, 0.0, phrase0));
       while (OpenPhrases.Count > 0) {
         if (cancellationToken.IsCancellationRequested) break;
 
-        StoredSymbolString fetchedPhrase = OpenPhrases.GetNext();
-        SymbolString currPhrase = fetchedPhrase.SymbolString;
-
-        OnPhraseFetched(fetchedPhrase.Hash, currPhrase);
-
-        ArchivedPhrases.Add(fetchedPhrase.Hash);
+        SearchNode fetchedSearchNode = OpenPhrases.GetNext();
+        SymbolString currPhrase = fetchedSearchNode.SymbolString;
+
+        OnPhraseFetched(fetchedSearchNode.Hash, currPhrase);
+
+        ArchivedPhrases.Add(fetchedSearchNode.Hash);
 
         // expand next nonterminal symbols
@@ -199 +199 @@
             var phraseHash = Grammar.Hasher.CalcHashCode(newPhrase);
 
-            OnPhraseDerived(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
+            OnPhraseDerived(fetchedSearchNode.Hash, fetchedSearchNode.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
 
             if (newPhrase.IsSentence()) {
               AllGeneratedSentencesCount++;
 
-              OnSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
+              OnSentenceGenerated(fetchedSearchNode.Hash, fetchedSearchNode.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
 
               // Is the best solution found? (only if RSquaredEvaluator is activated)
@@ -219 +219 @@
 
                 DistinctSentencesComplexity[phraseHash] = newPhraseComplexity;
-                OnDistinctSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
+                OnDistinctSentenceGenerated(fetchedSearchNode.Hash, fetchedSearchNode.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
               }
               UpdateView();
 
             } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.Contains(phraseHash)) {
-              double phrasePriority = GetPriority(newPhrase, maxSentenceLength);
-              OpenPhrases.Store(phraseHash, phrasePriority, newPhrase);
+
+              double r2 = GetR2(newPhrase, fetchedSearchNode.R2);
+              double phrasePriority = GetPriority(newPhrase, r2, maxSentenceLength);
+
+              SearchNode newSearchNode = new SearchNode(phraseHash, phrasePriority, r2, newPhrase);
+              OpenPhrases.Store(newSearchNode);
             }
           }
@@ -233 +237 @@
     }
 
-    protected double GetPriority(SymbolString phrase, int maxSentenceLength) {
+    protected double GetPriority(SymbolString phrase, double r2, int maxSentenceLength) {
       double relLength = (double)phrase.Count() / maxSentenceLength;
-
-      double r2 = Grammar.EvaluatePhrase(phrase, Problem.ProblemData, OptimizeConstants);
       double error = 1.0 - r2;
 
       return relLength + ErrorWeight * error;
+    }
+
+    private double GetR2(SymbolString phrase, double parentR2) {
+      int length = phrase.Count();
+
+      // If the only nonterminal symbol is Expr, we can need to evaluate the sentence. Otherwise
+      // the phrase has the same r2 as its parent, from which it was derived.
+      for (int i = 0; i < length; i++) {
+        if (phrase[i] is NonterminalSymbol && phrase[i] != Grammar.Expr) {
+          return parentR2;
+        }
+      }
+
+      return Grammar.EvaluatePhrase(phrase, Problem.ProblemData, OptimizeConstants);
     }
 

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

@@ -5 +5 @@
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration {
 
-  public class StoredSymbolString {
+  public class SearchNode {
     public readonly int Hash;
     public readonly SymbolString SymbolString;
+    public readonly double Priority;
+    public readonly double R2;
 
-    public StoredSymbolString(int hash, SymbolString symbolString) {
+    public SearchNode(int hash, double priority, double r2, SymbolString symbolString) {
       Hash = hash;
+      Priority = priority;
       SymbolString = symbolString;
+      R2 = r2;
     }
   }
@@ -19 +23 @@
   }
 
-  class SearchDataStore : IEnumerable<SymbolString> {
+  class SearchDataStore : IEnumerable<SearchNode> {
 
-    private Dictionary<int, SymbolString> storedValues; // Store hash-references and associated, actual values 
+    private Dictionary<int, SearchNode> storedValues; // Store hash-references and associated, actual values 
     private Action<int, double> storeInternal; // Store hash-references 
     private Func<int> fetchInternal; // Fetch hash-reference
 
     public SearchDataStore(StorageType storageType) {
-      storedValues = new Dictionary<int, SymbolString>();
+      storedValues = new Dictionary<int, SearchNode>();
 
       switch (storageType) {
@@ -89 +93 @@
     #region Interface
 
-    public StoredSymbolString GetNext() {
+    public SearchNode GetNext() {
       int hash = fetchInternal.Invoke();
-      SymbolString result = storedValues[hash];
+      SearchNode result = storedValues[hash];
       storedValues.Remove(hash);
-      return new StoredSymbolString(hash, result);
+      return result;
     }
 
-    public void Store(int hash, double priority, SymbolString s) {
-      storeInternal(hash, priority);
-      storedValues[hash] = s;
+    public void Store(SearchNode sn) {
+      storeInternal(sn.Hash, sn.Priority);
+      storedValues[sn.Hash] = sn;
     }
 
@@ -113 +117 @@
     }
 
-    public IEnumerator<SymbolString> GetEnumerator() {
+    public IEnumerator<SearchNode> GetEnumerator() {
       return storedValues.Values.GetEnumerator();
     }

branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

@@ -210 +210 @@
     public void Constants_Nguyen7() {
       // log(x+1) + log(x*x + 1)
-      alg.MaxComplexity = 3;
+      alg.MaxComplexity = 4;
+      alg.OptimizeConstants = true;
       alg.Problem.ProblemData = new NguyenFunctionSeven().GenerateRegressionData();
 
@@ -242 +243 @@
       // x*x*x*x - x*x*x + y*y/2 -y
       alg.MaxComplexity = 10;
+      alg.OptimizeConstants = true;
       alg.Problem.ProblemData = new NguyenFunctionTwelve().GenerateRegressionData();
 
@@ -286 +288 @@
       // (30*x*z) / ((x - 10)*y*y)
       alg.MaxComplexity = 5;
+      alg.OptimizeConstants = true;
       alg.Problem.ProblemData = new KeijzerFunctionFive().GenerateRegressionData();
 
@@ -357 +360 @@
     [TestProperty("Goal", "structure search + const op")]
     public void Constants_Keijzer14() {
-      // 8 / (2 + x*x + y*y
+      // 8 / (2 + x*x + y*y)
       alg.MaxComplexity = 4;
+      alg.OptimizeConstants = true;
       alg.Problem.ProblemData = new KeijzerFunctionFourteen().GenerateRegressionData();
 
@@ -396 +400 @@
       // x*x*x / 5 + y*y*y / 2 - y - x
       alg.MaxComplexity = 8;
+      alg.OptimizeConstants = true;
       alg.Problem.ProblemData = new KeijzerFunctionFifteen().GenerateRegressionData();
 
@@ -428 +433 @@
     [TestProperty("Goal", "Poly-10 derivatives")]
     public void MctsSymbReg_NoConstants_Poly10_Part1() {
-      alg.MaxComplexity = 12; 
+      alg.MaxComplexity = 12;
       alg.OptimizeConstants = false;
       var regProblem = new PolyTen(123).GenerateRegressionData();