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

Timestamp:

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

Author:

lkammere

Message:

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

File:

• branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (4 diffs)

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);
     }