Changeset 15915


Ignore:
Timestamp:
04/24/18 13:11:59 (19 months ago)
Author:
lkammere
Message:

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

Location:
branches/2886_SymRegGrammarEnumeration
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/RSquaredEvaluator.cs

    r15910 r15915  
    110110          problemData.TrainingIndices,
    111111          applyLinearScaling: false,
    112           maxIterations: 50,
     112          maxIterations: 10,
    113113          updateVariableWeights: true,
    114114          updateConstantsInTree: true);
  • branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs

    r15910 r15915  
    174174      int maxSentenceLength = GetMaxSentenceLength();
    175175
    176       OpenPhrases.Store(phrase0Hash, 0.0, phrase0);
     176      OpenPhrases.Store(new SearchNode(phrase0Hash, 0.0, 0.0, phrase0));
    177177      while (OpenPhrases.Count > 0) {
    178178        if (cancellationToken.IsCancellationRequested) break;
    179179
    180         StoredSymbolString fetchedPhrase = OpenPhrases.GetNext();
    181         SymbolString currPhrase = fetchedPhrase.SymbolString;
    182 
    183         OnPhraseFetched(fetchedPhrase.Hash, currPhrase);
    184 
    185         ArchivedPhrases.Add(fetchedPhrase.Hash);
     180        SearchNode fetchedSearchNode = OpenPhrases.GetNext();
     181        SymbolString currPhrase = fetchedSearchNode.SymbolString;
     182
     183        OnPhraseFetched(fetchedSearchNode.Hash, currPhrase);
     184
     185        ArchivedPhrases.Add(fetchedSearchNode.Hash);
    186186
    187187        // expand next nonterminal symbols
     
    199199            var phraseHash = Grammar.Hasher.CalcHashCode(newPhrase);
    200200
    201             OnPhraseDerived(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
     201            OnPhraseDerived(fetchedSearchNode.Hash, fetchedSearchNode.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
    202202
    203203            if (newPhrase.IsSentence()) {
    204204              AllGeneratedSentencesCount++;
    205205
    206               OnSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
     206              OnSentenceGenerated(fetchedSearchNode.Hash, fetchedSearchNode.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
    207207
    208208              // Is the best solution found? (only if RSquaredEvaluator is activated)
     
    219219
    220220                DistinctSentencesComplexity[phraseHash] = newPhraseComplexity;
    221                 OnDistinctSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
     221                OnDistinctSentenceGenerated(fetchedSearchNode.Hash, fetchedSearchNode.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
    222222              }
    223223              UpdateView();
    224224
    225225            } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.Contains(phraseHash)) {
    226               double phrasePriority = GetPriority(newPhrase, maxSentenceLength);
    227               OpenPhrases.Store(phraseHash, phrasePriority, newPhrase);
     226
     227              double r2 = GetR2(newPhrase, fetchedSearchNode.R2);
     228              double phrasePriority = GetPriority(newPhrase, r2, maxSentenceLength);
     229
     230              SearchNode newSearchNode = new SearchNode(phraseHash, phrasePriority, r2, newPhrase);
     231              OpenPhrases.Store(newSearchNode);
    228232            }
    229233          }
     
    233237    }
    234238
    235     protected double GetPriority(SymbolString phrase, int maxSentenceLength) {
     239    protected double GetPriority(SymbolString phrase, double r2, int maxSentenceLength) {
    236240      double relLength = (double)phrase.Count() / maxSentenceLength;
    237 
    238       double r2 = Grammar.EvaluatePhrase(phrase, Problem.ProblemData, OptimizeConstants);
    239241      double error = 1.0 - r2;
    240242
    241243      return relLength + ErrorWeight * error;
     244    }
     245
     246    private double GetR2(SymbolString phrase, double parentR2) {
     247      int length = phrase.Count();
     248
     249      // If the only nonterminal symbol is Expr, we can need to evaluate the sentence. Otherwise
     250      // the phrase has the same r2 as its parent, from which it was derived.
     251      for (int i = 0; i < length; i++) {
     252        if (phrase[i] is NonterminalSymbol && phrase[i] != Grammar.Expr) {
     253          return parentR2;
     254        }
     255      }
     256
     257      return Grammar.EvaluatePhrase(phrase, Problem.ProblemData, OptimizeConstants);
    242258    }
    243259
  • branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs

    r15907 r15915  
    55namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration {
    66
    7   public class StoredSymbolString {
     7  public class SearchNode {
    88    public readonly int Hash;
    99    public readonly SymbolString SymbolString;
     10    public readonly double Priority;
     11    public readonly double R2;
    1012
    11     public StoredSymbolString(int hash, SymbolString symbolString) {
     13    public SearchNode(int hash, double priority, double r2, SymbolString symbolString) {
    1214      Hash = hash;
     15      Priority = priority;
    1316      SymbolString = symbolString;
     17      R2 = r2;
    1418    }
    1519  }
     
    1923  }
    2024
    21   class SearchDataStore : IEnumerable<SymbolString> {
     25  class SearchDataStore : IEnumerable<SearchNode> {
    2226
    23     private Dictionary<int, SymbolString> storedValues; // Store hash-references and associated, actual values
     27    private Dictionary<int, SearchNode> storedValues; // Store hash-references and associated, actual values
    2428    private Action<int, double> storeInternal; // Store hash-references
    2529    private Func<int> fetchInternal; // Fetch hash-reference
    2630
    2731    public SearchDataStore(StorageType storageType) {
    28       storedValues = new Dictionary<int, SymbolString>();
     32      storedValues = new Dictionary<int, SearchNode>();
    2933
    3034      switch (storageType) {
     
    8993    #region Interface
    9094
    91     public StoredSymbolString GetNext() {
     95    public SearchNode GetNext() {
    9296      int hash = fetchInternal.Invoke();
    93       SymbolString result = storedValues[hash];
     97      SearchNode result = storedValues[hash];
    9498      storedValues.Remove(hash);
    95       return new StoredSymbolString(hash, result);
     99      return result;
    96100    }
    97101
    98     public void Store(int hash, double priority, SymbolString s) {
    99       storeInternal(hash, priority);
    100       storedValues[hash] = s;
     102    public void Store(SearchNode sn) {
     103      storeInternal(sn.Hash, sn.Priority);
     104      storedValues[sn.Hash] = sn;
    101105    }
    102106
     
    113117    }
    114118
    115     public IEnumerator<SymbolString> GetEnumerator() {
     119    public IEnumerator<SearchNode> GetEnumerator() {
    116120      return storedValues.Values.GetEnumerator();
    117121    }
  • branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

    r15907 r15915  
    210210    public void Constants_Nguyen7() {
    211211      // log(x+1) + log(x*x + 1)
    212       alg.MaxComplexity = 3;
     212      alg.MaxComplexity = 4;
     213      alg.OptimizeConstants = true;
    213214      alg.Problem.ProblemData = new NguyenFunctionSeven().GenerateRegressionData();
    214215
     
    242243      // x*x*x*x - x*x*x + y*y/2 -y
    243244      alg.MaxComplexity = 10;
     245      alg.OptimizeConstants = true;
    244246      alg.Problem.ProblemData = new NguyenFunctionTwelve().GenerateRegressionData();
    245247
     
    286288      // (30*x*z) / ((x - 10)*y*y)
    287289      alg.MaxComplexity = 5;
     290      alg.OptimizeConstants = true;
    288291      alg.Problem.ProblemData = new KeijzerFunctionFive().GenerateRegressionData();
    289292
     
    357360    [TestProperty("Goal", "structure search + const op")]
    358361    public void Constants_Keijzer14() {
    359       // 8 / (2 + x*x + y*y
     362      // 8 / (2 + x*x + y*y)
    360363      alg.MaxComplexity = 4;
     364      alg.OptimizeConstants = true;
    361365      alg.Problem.ProblemData = new KeijzerFunctionFourteen().GenerateRegressionData();
    362366
     
    396400      // x*x*x / 5 + y*y*y / 2 - y - x
    397401      alg.MaxComplexity = 8;
     402      alg.OptimizeConstants = true;
    398403      alg.Problem.ProblemData = new KeijzerFunctionFifteen().GenerateRegressionData();
    399404
     
    428433    [TestProperty("Goal", "Poly-10 derivatives")]
    429434    public void MctsSymbReg_NoConstants_Poly10_Part1() {
    430       alg.MaxComplexity = 12; 
     435      alg.MaxComplexity = 12;
    431436      alg.OptimizeConstants = false;
    432437      var regProblem = new PolyTen(123).GenerateRegressionData();
Note: See TracChangeset for help on using the changeset viewer.