Index: branches/2886_SymRegGrammarEnumeration/ExpressionClustering/ExpressionClustering.csproj
===================================================================
--- branches/2886_SymRegGrammarEnumeration/ExpressionClustering/ExpressionClustering.csproj	(revision 15973)
+++ branches/2886_SymRegGrammarEnumeration/ExpressionClustering/ExpressionClustering.csproj	(revision 15974)
@@ -15,5 +15,5 @@
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
-    <PlatformTarget>x64</PlatformTarget>
+    <PlatformTarget>AnyCPU</PlatformTarget>
     <DebugSymbols>true</DebugSymbols>
     <DebugType>full</DebugType>
Index: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/RSquaredEvaluator.cs
===================================================================
--- branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/RSquaredEvaluator.cs	(revision 15973)
+++ branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/RSquaredEvaluator.cs	(revision 15974)
@@ -16,6 +16,8 @@
   public class RSquaredEvaluator : Item, IGrammarEnumerationAnalyzer {
     public static readonly string BestTrainingQualityResultName = "Best R² (Training)";
+    public static readonly string BestTestQualityResultName = "Best R² (Test)";
     public static readonly string BestTrainingModelResultName = "Best model (Training)";
     public static readonly string BestTrainingSolutionResultName = "Best solution (Training)";
+    public static readonly string BestComplexityResultName = "Best solution complexity";
 
     private static readonly ISymbolicDataAnalysisExpressionTreeInterpreter expressionTreeLinearInterpreter = new SymbolicDataAnalysisExpressionTreeLinearInterpreter();
@@ -42,5 +44,4 @@
       algorithm.Started -= OnStarted;
       algorithm.Stopped -= OnStopped;
-
       algorithm.DistinctSentenceGenerated -= AlgorithmOnDistinctSentenceGenerated;
     }
@@ -57,15 +58,16 @@
     }
 
-    private void OnStopped(object sender, EventArgs eventArgs) {
-      GrammarEnumerationAlgorithm algorithm = (GrammarEnumerationAlgorithm)sender;
-      if (algorithm.Results.ContainsKey(BestTrainingModelResultName)) {
-        SymbolicRegressionModel model = (SymbolicRegressionModel)algorithm.Results[BestTrainingModelResultName].Value;
-        IRegressionSolution bestTrainingSolution = new RegressionSolution(model, algorithm.Problem.ProblemData);
+    private void OnStopped(object sender, EventArgs eventArgs) { }
 
-        algorithm.Results.AddOrUpdateResult(BestTrainingSolutionResultName, bestTrainingSolution);
-      }
+    private T GetValue<T>(IItem value) where T : struct {
+      var v = value as ValueTypeValue<T>;
+      if (v == null)
+        throw new ArgumentException(string.Format("Item is not of type {0}", typeof(ValueTypeValue<T>)));
+      return v.Value;
     }
 
     private void EvaluateSentence(GrammarEnumerationAlgorithm algorithm, SymbolString symbolString) {
+      var results = algorithm.Results;
+      var grammar = algorithm.Grammar;
       var problemData = algorithm.Problem.ProblemData;
 
@@ -74,26 +76,20 @@
 
       double r2 = Evaluate(problemData, tree, OptimizeConstants);
+      double bestR2 = results.ContainsKey(BestTrainingQualityResultName) ? GetValue<double>(results[BestTrainingQualityResultName].Value) : 0.0;
+      if (r2 < bestR2)
+        return;
 
-      double bestR2 = 0.0;
-      if (algorithm.Results.ContainsKey(BestTrainingQualityResultName))
-        bestR2 = ((DoubleValue)algorithm.Results[BestTrainingQualityResultName].Value).Value;
-      bool better = r2 > bestR2;
-      bool equallyGood = r2.IsAlmost(bestR2);
-      bool shorter = false;
+      var bestComplexity = int.MaxValue;
+      if (results.ContainsKey(BestComplexityResultName)) {
+        bestComplexity = GetValue<int>(results[BestComplexityResultName].Value);
+      } else if (algorithm.BestTrainingSentence != null) {
+        bestComplexity = grammar.GetComplexity(algorithm.BestTrainingSentence);
+        results.AddOrUpdateResult(BestComplexityResultName, new IntValue(bestComplexity));
+      }
+      var complexity = grammar.GetComplexity(symbolString);
 
-      if (!better && equallyGood) {
-        shorter = algorithm.BestTrainingSentence != null &&
-          algorithm.Grammar.GetComplexity(algorithm.BestTrainingSentence) > algorithm.Grammar.GetComplexity(symbolString);
-      }
-      if (better || (equallyGood && shorter)) {
-        algorithm.Results.AddOrUpdateResult(BestTrainingQualityResultName, new DoubleValue(r2));
-
-        SymbolicRegressionModel model = new SymbolicRegressionModel(
-          problemData.TargetVariable,
-          tree,
-          expressionTreeLinearInterpreter);
-
-        algorithm.Results.AddOrUpdateResult(BestTrainingModelResultName, model);
-
+      if (r2 > bestR2 || (r2.IsAlmost(bestR2) && complexity < bestComplexity)) {
+        results.AddOrUpdateResult(BestTrainingQualityResultName, new DoubleValue(r2));
+        results.AddOrUpdateResult(BestComplexityResultName, new IntValue(complexity));
         algorithm.BestTrainingSentence = symbolString;
       }
@@ -121,22 +117,14 @@
           }
         }
-
-        r2 = double.IsNaN(r2) ? 0.0 : r2;
-
       } else {
-        var target = problemData.TargetVariableTrainingValues;
-
-        SymbolicRegressionModel model = new SymbolicRegressionModel(
-          problemData.TargetVariable,
+        r2 = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(expressionTreeLinearInterpreter,
           tree,
-          expressionTreeLinearInterpreter);
-
-        var estVals = model.GetEstimatedValues(problemData.Dataset, problemData.TrainingIndices);
-        OnlineCalculatorError error;
-        r2 = OnlinePearsonsRCalculator.Calculate(target, estVals, out error);
-        if (error != OnlineCalculatorError.None) r2 = 0.0;
+          double.MinValue,
+          double.MaxValue,
+          problemData,
+          problemData.TrainingIndices,
+          applyLinearScaling: true);
       }
-
-      return r2;
+      return double.IsNaN(r2) ? 0.0 : r2;
     }
   }
Index: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs
===================================================================
--- branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs	(revision 15973)
+++ branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs	(revision 15974)
@@ -22,6 +22,5 @@
   [StorableClass(StorableClassType.AllFieldsAndAllProperties)]
   public class Grammar : DeepCloneable {
-
-    public Symbol StartSymbol { get; }
+    public Symbol StartSymbol { get; private set; }
 
     public Hasher<int> Hasher { get; }
@@ -29,5 +28,5 @@
     #region Symbols
 
-    public IReadOnlyDictionary<Symbol, IReadOnlyList<Production>> Productions { get; }
+    public IReadOnlyDictionary<Symbol, IReadOnlyList<Production>> Productions { get; private set; }
 
     public NonterminalSymbol Var;
@@ -79,10 +78,10 @@
 
     protected Grammar(Grammar original, Cloner cloner) : base(original, cloner) {
-      VarTerminals = original.VarTerminals.Select(cloner.Clone).ToArray();
-      StartSymbol = cloner.Clone(original.StartSymbol);
-      Hasher = cloner.Clone(original.Hasher); // how to handle circular reference grammar <-> hasher? (the cloner *should* handle it)
+      infixExpressionFormatter = cloner.Clone(original.infixExpressionFormatter);
+
       Productions = original.Productions.ToDictionary(x => cloner.Clone(x.Key), x => (IReadOnlyList<Production>)x.Value.Select(cloner.Clone).ToList());
+      VarTerminals = original.VarTerminals.Select(cloner.Clone).ToList();
+
       Var = cloner.Clone(original.Var);
-      VarTerminals = original.VarTerminals.Select(cloner.Clone).ToList();
       Expr = cloner.Clone(original.Expr);
       Term = cloner.Clone(original.Term);
@@ -95,4 +94,5 @@
       InvExpr = cloner.Clone(original.InvExpr);
       InvTerm = cloner.Clone(original.InvTerm);
+
       Addition = cloner.Clone(original.Addition);
       Multiplication = cloner.Clone(original.Multiplication);
@@ -100,25 +100,14 @@
       Exp = cloner.Clone(original.Exp);
       Sin = cloner.Clone(original.Sin);
-      Sin = cloner.Clone(original.Sin);
       Inv = cloner.Clone(original.Inv);
       Const = cloner.Clone(original.Const);
 
-
-      constSy = cloner.Clone(original.constSy);
-      varSy = cloner.Clone(original.varSy);
-      addSy = cloner.Clone(original.addSy);
-      mulSy = cloner.Clone(original.mulSy);
-      logSy = cloner.Clone(original.logSy);
-      expSy = cloner.Clone(original.expSy);
-      divSy = cloner.Clone(original.divSy);
-      sinSy = cloner.Clone(original.sinSy);
-
-      rootSy = cloner.Clone(original.rootSy);
-      startSy = cloner.Clone(original.startSy);
-
-      infixExpressionFormatter = cloner.Clone(original.infixExpressionFormatter);
-    }
-
-    public Grammar(string[] variables, IEnumerable<GrammarRule> includedRules) {
+      StartSymbol = Expr;
+      Hasher = cloner.Clone(original.Hasher);
+
+      InitTreeParser(); // easier this way (and less typing)
+    }
+
+    private void InitProductions(string[] variables, IEnumerable<GrammarRule> includedRules) {
       #region Define Symbols
       Var = new NonterminalSymbol("Var");
@@ -210,5 +199,7 @@
       Productions = productions;
       #endregion
-
+    }
+
+    private void InitTreeParser() {
       #region Parsing to SymbolicExpressionTree
       var symbolicExpressionGrammar = new TypeCoherentExpressionGrammar();
@@ -229,4 +220,9 @@
       infixExpressionFormatter = new InfixExpressionFormatter();
       #endregion
+    }
+
+    public Grammar(string[] variables, IEnumerable<GrammarRule> includedRules) {
+      InitProductions(variables, includedRules);
+      InitTreeParser();
 
       Hasher = new IntHasher(this);
@@ -244,8 +240,5 @@
     public double EvaluatePhrase(SymbolString s, IRegressionProblemData problemData, bool optimizeConstants) {
       SymbolicExpressionTree tree = ParseSymbolicExpressionTree(s);
-
-      double r2 = RSquaredEvaluator.Evaluate(problemData, tree, optimizeConstants);
-
-      return r2;
+      return RSquaredEvaluator.Evaluate(problemData, tree, optimizeConstants);
     }
 
Index: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs
===================================================================
--- branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs	(revision 15973)
+++ branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs	(revision 15974)
@@ -12,4 +12,6 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.DataAnalysis;
+using HeuristicLab.Problems.DataAnalysis.Symbolic;
+using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
 
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
@@ -36,9 +38,16 @@
     private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval";
     private readonly string GrammarSymbolsParameterName = "Grammar Symbols";
+    private readonly string SearchCacheSizeParameterName = "Search Cache Size";
+    private readonly string SearchDataStructureSizeParameterName = "Search Data Structure Size";
+
+    // result names
+    public static readonly string BestTrainingModelResultName = "Best model (Training)";
+    public static readonly string BestTrainingSolutionResultName = "Best solution (Training)";
+    public static readonly string BestComplexityResultName = "Best solution complexity";
 
     public override bool SupportsPause { get { return true; } }
 
-    protected IValueParameter<DoubleValue> VariableImportanceWeightParameter {
-      get { return (IValueParameter<DoubleValue>)Parameters[VariableImportanceWeightName]; }
+    protected IFixedValueParameter<DoubleValue> VariableImportanceWeightParameter {
+      get { return (IFixedValueParameter<DoubleValue>)Parameters[VariableImportanceWeightName]; }
     }
 
@@ -47,6 +56,6 @@
     }
 
-    protected IValueParameter<BoolValue> OptimizeConstantsParameter {
-      get { return (IValueParameter<BoolValue>)Parameters[OptimizeConstantsParameterName]; }
+    protected IFixedValueParameter<BoolValue> OptimizeConstantsParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters[OptimizeConstantsParameterName]; }
     }
 
@@ -56,7 +65,8 @@
     }
 
-    protected IValueParameter<IntValue> MaxComplexityParameter {
-      get { return (IValueParameter<IntValue>)Parameters[MaxComplexityParameterName]; }
-    }
+    protected IFixedValueParameter<IntValue> MaxComplexityParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[MaxComplexityParameterName]; }
+    }
+
     public int MaxComplexity {
       get { return MaxComplexityParameter.Value.Value; }
@@ -64,7 +74,8 @@
     }
 
-    protected IValueParameter<DoubleValue> ErrorWeightParameter {
-      get { return (IValueParameter<DoubleValue>)Parameters[ErrorWeightParameterName]; }
-    }
+    protected IFixedValueParameter<DoubleValue> ErrorWeightParameter {
+      get { return (IFixedValueParameter<DoubleValue>)Parameters[ErrorWeightParameterName]; }
+    }
+
     public double ErrorWeight {
       get { return ErrorWeightParameter.Value.Value; }
@@ -72,7 +83,8 @@
     }
 
-    protected IValueParameter<IntValue> GuiUpdateIntervalParameter {
-      get { return (IValueParameter<IntValue>)Parameters[GuiUpdateIntervalParameterName]; }
-    }
+    protected IFixedValueParameter<IntValue> GuiUpdateIntervalParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[GuiUpdateIntervalParameterName]; }
+    }
+
     public int GuiUpdateInterval {
       get { return GuiUpdateIntervalParameter.Value.Value; }
@@ -80,7 +92,24 @@
     }
 
-    protected IValueParameter<EnumValue<StorageType>> SearchDataStructureParameter {
-      get { return (IValueParameter<EnumValue<StorageType>>)Parameters[SearchDataStructureParameterName]; }
-    }
+    protected IFixedValueParameter<EnumValue<StorageType>> SearchDataStructureParameter {
+      get { return (IFixedValueParameter<EnumValue<StorageType>>)Parameters[SearchDataStructureParameterName]; }
+    }
+
+    public IFixedValueParameter<IntValue> SearchDataStructureSizeParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[SearchDataStructureSizeParameterName]; }
+    }
+
+    public int SearchDataStructureSize {
+      get { return SearchDataStructureSizeParameter.Value.Value; }
+    }
+
+    public IFixedValueParameter<IntValue> SearchCacheSizeParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[SearchCacheSizeParameterName]; }
+    }
+
+    public int SearchCacheSize {
+      get { return SearchCacheSizeParameter.Value.Value; }
+    }
+
     public StorageType SearchDataStructure {
       get { return SearchDataStructureParameter.Value.Value; }
@@ -116,10 +145,18 @@
     internal SearchDataStore OpenPhrases { get; private set; }           // Stack/Queue/etc. for fetching the next node in the search tree.  
 
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      variableImportance = CalculateVariableImportances();
+    }
+
     #region execution stats
+    [Storable]
     public int AllGeneratedSentencesCount { get; private set; }
 
+    [Storable]
     public int OverwrittenSentencesCount { get; private set; } // It is not guaranteed that shorter solutions are found first. 
                                                                // When longer solutions are overwritten with shorter ones, 
                                                                // this counter is increased.
+    [Storable]
     public int PhraseExpansionCount { get; private set; }      // Number, how many times a nonterminal symbol is replaced with a production rule.
     #endregion
@@ -133,10 +170,16 @@
 
     public GrammarEnumerationAlgorithm() {
-      Parameters.Add(new ValueParameter<DoubleValue>(VariableImportanceWeightName, "Variable Weight.", new DoubleValue(1.0)));
-      Parameters.Add(new ValueParameter<BoolValue>(OptimizeConstantsParameterName, "Run constant optimization in sentence evaluation.", new BoolValue(false)));
-      Parameters.Add(new ValueParameter<DoubleValue>(ErrorWeightParameterName, "Defines, how much weight is put on a phrase's r² value when priorizing phrases during search.", new DoubleValue(0.8)));
-      Parameters.Add(new ValueParameter<IntValue>(MaxComplexityParameterName, "The maximum number of variable symbols in a sentence.", new IntValue(12)));
-      Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(5000)));
-      Parameters.Add(new ValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.PriorityQueue)));
+      Parameters.Add(new FixedValueParameter<DoubleValue>(VariableImportanceWeightName, "Variable Weight.", new DoubleValue(1.0)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(OptimizeConstantsParameterName, "Run constant optimization in sentence evaluation.", new BoolValue(false)));
+      Parameters.Add(new FixedValueParameter<DoubleValue>(ErrorWeightParameterName, "Defines, how much weight is put on a phrase's r² value when priorizing phrases during search.", new DoubleValue(0.8)));
+      Parameters.Add(new FixedValueParameter<IntValue>(MaxComplexityParameterName, "The maximum number of variable symbols in a sentence.", new IntValue(12)));
+      Parameters.Add(new FixedValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(5000)));
+      Parameters.Add(new FixedValueParameter<IntValue>(SearchCacheSizeParameterName, "The size of the search node cache.", new IntValue((int)1e5)));
+      Parameters.Add(new FixedValueParameter<IntValue>(SearchDataStructureSizeParameterName, "The size of the search data structure.", new IntValue((int)1e5)));
+      Parameters.Add(new FixedValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.PriorityQueue)));
+
+      SearchDataStructureParameter.Value.ValueChanged += (o, e) => Prepare();
+      SearchDataStructureSizeParameter.Value.ValueChanged += (o, e) => Prepare();
+      SearchCacheSizeParameter.Value.ValueChanged += (o, e) => Prepare();
 
       var availableAnalyzers = new IGrammarEnumerationAnalyzer[] {
@@ -145,4 +188,5 @@
         new RSquaredEvaluator()
       };
+
       Parameters.Add(new FixedValueParameter<ReadOnlyCheckedItemCollection<IGrammarEnumerationAnalyzer>>(
         AnalyzersParameterName,
@@ -170,5 +214,5 @@
       // set a default problem
       Problem = new RegressionProblem() {
-        ProblemData = new HeuristicLab.Problems.Instances.DataAnalysis.PolyTen(seed: 1234).GenerateRegressionData()
+        ProblemData = new Problems.Instances.DataAnalysis.PolyTen(seed: 1234).GenerateRegressionData()
       };
     }
@@ -182,9 +226,9 @@
       ArchivedPhrases = new HashSet<int>(original.ArchivedPhrases);
       OpenPhrases = cloner.Clone(original.OpenPhrases);
+      Grammar = cloner.Clone(original.Grammar);
 
       AllGeneratedSentencesCount = original.AllGeneratedSentencesCount;
       OverwrittenSentencesCount = original.OverwrittenSentencesCount;
       PhraseExpansionCount = original.PhraseExpansionCount;
-      Grammar = cloner.Clone(original.Grammar);
 
       if (original.variableImportance != null)
@@ -204,5 +248,5 @@
       Analyzers.OfType<RSquaredEvaluator>().First().OptimizeConstants = OptimizeConstants;
       Grammar = new Grammar(Problem.ProblemData.AllowedInputVariables.ToArray(), GrammarSymbols.CheckedItems.Select(v => v.Value));
-      OpenPhrases = new SearchDataStore(SearchDataStructure); // Select search strategy
+      OpenPhrases = new SearchDataStore(SearchDataStructure, SearchDataStructureSize, SearchCacheSize); // Select search strategy
 
       base.Prepare(); // this actually clears the results which will get reinitialized on Run()
@@ -237,4 +281,5 @@
         var phrase0 = new SymbolString(new[] { Grammar.StartSymbol });
         var phrase0Hash = Grammar.Hasher.CalcHashCode(phrase0);
+
         OpenPhrases.Store(new SearchNode(phrase0Hash, 0.0, 0.0, phrase0));
       }
@@ -249,4 +294,8 @@
 
         SearchNode fetchedSearchNode = OpenPhrases.GetNext();
+
+        if (fetchedSearchNode == null)
+          continue;
+
         SymbolString currPhrase = fetchedSearchNode.SymbolString;
 
@@ -380,4 +429,17 @@
     protected override void OnStopped() {
       previousExecutionState = this.ExecutionState;
+
+      if (BestTrainingSentence == null) {
+        base.OnStopped();
+        return;
+      }
+
+      var tree = Grammar.ParseSymbolicExpressionTree(BestTrainingSentence);
+      var model = new SymbolicRegressionModel(Problem.ProblemData.TargetVariable, tree, new SymbolicDataAnalysisExpressionTreeLinearInterpreter());
+      model.Scale(Problem.ProblemData);
+      var bestTrainingSolution = new SymbolicRegressionSolution(model, Problem.ProblemData);
+      Results.AddOrUpdateResult(BestTrainingModelResultName, model);
+      Results.AddOrUpdateResult(BestTrainingSolutionResultName, bestTrainingSolution);
+      Results.AddOrUpdateResult(BestComplexityResultName, new IntValue(Grammar.GetComplexity(BestTrainingSentence)));
       base.OnStopped();
     }
@@ -409,5 +471,7 @@
         ((IntValue)Results[DistinctSentencesName].Value).Value = DistinctSentencesComplexity.Count;
         ((IntValue)Results[PhraseExpansionsName].Value).Value = PhraseExpansionCount;
-        ((DoubleValue)Results[AverageSentenceComplexityName].Value).Value = DistinctSentencesComplexity.Select(pair => pair.Value).Average();
+        ((DoubleValue)Results[AverageSentenceComplexityName].Value).Value = DistinctSentencesComplexity.Count > 0
+          ? DistinctSentencesComplexity.Select(pair => pair.Value).Average()
+          : 0;
         ((IntValue)Results[OverwrittenSentencesName].Value).Value = OverwrittenSentencesCount;
         ((IntValue)Results[ExpansionsPerSecondName].Value).Value = (int)((PhraseExpansionCount /
Index: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/LruCache.cs
===================================================================
--- branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/LruCache.cs	(revision 15974)
+++ branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/LruCache.cs	(revision 15974)
@@ -0,0 +1,276 @@
+﻿using System;
+using System.Collections;
+using System.Collections.Generic;
+using System.Linq;
+using HeuristicLab.Common;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration {
+  /// <summary>
+  /// A least-recently-used cache stored like a dictionary.
+  /// </summary>
+  /// <typeparam name="TKey">
+  /// The type of the key to the cached item
+  /// </typeparam>
+  /// <typeparam name="TValue">
+  /// The type of the cached item.
+  /// </typeparam>
+  /// <remarks>
+  /// Derived from https://stackoverflow.com/a/3719378/240845
+  /// </remarks>
+  [StorableClass]
+  public class LruCache<TKey, TValue> : DeepCloneable, IDictionary<TKey, TValue> {
+    private Dictionary<TKey, LinkedListNode<LruCacheItem>> cacheMap = new Dictionary<TKey, LinkedListNode<LruCacheItem>>();
+    private LinkedList<LruCacheItem> lruList = new LinkedList<LruCacheItem>();
+    private readonly Action<TValue> dispose;
+
+    [Storable]
+    // since a linked list is not directly serializable we use a list of { key, value, index } tuples
+    // the index is necessary to be able to restore the linked list with the correct order of nodes
+    private List<Tuple<TKey, TValue, int>> cacheItems {
+      get {
+        var indexedNodes = lruList.Select((lruCacheItem, index) => new { lruCacheItem, index }).ToDictionary(x => x.lruCacheItem, x => x.index);
+        return cacheMap.Select(x => Tuple.Create(x.Key, x.Value.Value.Value, indexedNodes[x.Value.Value])).ToList();
+      }
+      set {
+        lruList = new LinkedList<LruCacheItem>();
+        cacheMap = new Dictionary<TKey, LinkedListNode<LruCacheItem>>();
+        foreach (var t in value.OrderBy(x => x.Item3)) {
+          var key = t.Item1;
+          var val = t.Item2;
+          var item = new LruCacheItem(key, val);
+          var node = new LinkedListNode<LruCacheItem>(item);
+          lruList.AddLast(node);
+          cacheMap.Add(key, node);
+        }
+      }
+    }
+
+    /// <summary>
+    /// Initializes a new instance of the <see cref="LruCache{TKey, TValue}"/>
+    /// class.
+    /// </summary>
+    /// <param name="capacity">
+    /// Maximum number of elements to cache.
+    /// </param>
+    /// <param name="dispose">
+    /// When elements cycle out of the cache, disposes them. May be null.
+    /// </param>
+    public LruCache(int capacity, Action<TValue> dispose = null) {
+      this.Capacity = capacity;
+      this.dispose = dispose;
+    }
+
+    [StorableConstructor]
+    protected LruCache(bool deserializing) { }
+
+    protected LruCache(LruCache<TKey, TValue> original, Cloner cloner) : base(original, cloner) {
+      cacheMap = new Dictionary<TKey, LinkedListNode<LruCacheItem>>();
+      lruList = new LinkedList<LruCacheItem>(original.lruList.Select(cloner.Clone));
+
+      var nodeMap = new Dictionary<LruCacheItem, LinkedListNode<LruCacheItem>>();
+      for (var node = lruList.First; node != null; node = node.Next) {
+        nodeMap.Add(node.Value, node);
+      }
+
+      foreach (var t in original.cacheMap) {
+        var node = t.Value;
+        var item = node.Value;
+        var clone = (LruCacheItem)cloner.GetClone(item);
+        cacheMap.Add(t.Key, nodeMap[clone]);
+      }
+      Capacity = original.Capacity;
+    }
+
+    /// <summary>
+    /// Gets the capacity of the cache.
+    /// </summary>
+    [Storable]
+    public int Capacity { get; private set; }
+
+    public ICollection<TKey> Keys => cacheMap.Keys;
+
+    public ICollection<TValue> Values => (ICollection<TValue>)Keys.Select(x => cacheMap[x].Value.Value);
+
+    public int Count => cacheMap.Count;
+
+    public bool IsReadOnly => false;
+
+    public TValue this[TKey key] { get => Get(key, null); set => Add(key, value); }
+
+    /// <summary>Gets the value associated with the specified key.</summary>
+    /// <param name="key">
+    /// The key of the value to get.
+    /// </param>
+    /// <param name="value">
+    /// When this method returns, contains the value associated with the specified
+    /// key, if the key is found; otherwise, the default value for the type of the 
+    /// <paramref name="value" /> parameter. This parameter is passed
+    /// uninitialized.
+    /// </param>
+    /// <returns>
+    /// true if the <see cref="T:System.Collections.Generic.Dictionary`2" /> 
+    /// contains an element with the specified key; otherwise, false.
+    /// </returns>
+    public bool TryGetValue(TKey key, out TValue value) {
+      lock (cacheMap) {
+        LinkedListNode<LruCacheItem> node;
+        if (cacheMap.TryGetValue(key, out node)) {
+          value = node.Value.Value;
+          lruList.Remove(node);
+          lruList.AddLast(node);
+          return true;
+        }
+
+        value = default(TValue);
+        return false;
+      }
+    }
+
+    /// <summary>
+    /// Looks for a value for the matching <paramref name="key"/>. If not found, 
+    /// calls <paramref name="valueGenerator"/> to retrieve the value and add it to
+    /// the cache.
+    /// </summary>
+    /// <param name="key">
+    /// The key of the value to look up.
+    /// </param>
+    /// <param name="valueGenerator">
+    /// Generates a value if one isn't found.
+    /// </param>
+    /// <returns>
+    /// The requested value.
+    /// </returns>
+    public TValue Get(TKey key, Func<TValue> valueGenerator) {
+      lock (cacheMap) {
+        LinkedListNode<LruCacheItem> node;
+        TValue value;
+        if (cacheMap.TryGetValue(key, out node)) {
+          value = node.Value.Value;
+          lruList.Remove(node);
+          lruList.AddLast(node);
+        } else {
+          value = valueGenerator();
+          if (cacheMap.Count >= Capacity) {
+            RemoveFirst();
+          }
+
+          LruCacheItem cacheItem = new LruCacheItem(key, value);
+          node = new LinkedListNode<LruCacheItem>(cacheItem);
+          lruList.AddLast(node);
+          cacheMap.Add(key, node);
+        }
+
+        return value;
+      }
+    }
+
+    /// <summary>
+    /// Adds the specified key and value to the dictionary.
+    /// </summary>
+    /// <param name="key">
+    /// The key of the element to add.
+    /// </param>throw new NotImplementedException()
+    /// <param name="value">
+    /// The value of the element to add. The value can be null for reference types.
+    /// </param>
+    public void Add(TKey key, TValue value) {
+      lock (cacheMap) {
+        if (cacheMap.Count >= Capacity) {
+          RemoveFirst();
+        }
+
+        LruCacheItem cacheItem = new LruCacheItem(key, value);
+        LinkedListNode<LruCacheItem> node = new LinkedListNode<LruCacheItem>(cacheItem);
+        lruList.AddLast(node);
+        cacheMap.Add(key, node);
+      }
+    }
+
+    public void Remove(TKey key) {
+      LinkedListNode<LruCacheItem> node;
+      if (cacheMap.TryGetValue(key, out node)) {
+        lruList.Remove(node);
+        cacheMap.Remove(key);
+      }
+      dispose?.Invoke(node.Value.Value);
+    }
+
+    private void RemoveFirst() {
+      // Remove from LRUPriority
+      LinkedListNode<LruCacheItem> node = lruList.First;
+      lruList.RemoveFirst();
+
+      // Remove from cache
+      cacheMap.Remove(node.Value.Key);
+
+      // dispose
+      dispose?.Invoke(node.Value.Value);
+    }
+
+    private class LruCacheItem : DeepCloneable {
+      public LruCacheItem(TKey k, TValue v) {
+        Key = k;
+        Value = v;
+      }
+
+      protected LruCacheItem(LruCacheItem original, Cloner cloner) : base(original, cloner) {
+        Key = original.Key;
+        Value = original.Value;
+      }
+
+      public TKey Key { get; }
+
+      public TValue Value { get; }
+
+      public override IDeepCloneable Clone(Cloner cloner) {
+        return new LruCacheItem(this, cloner);
+      }
+    }
+
+    #region implement DeepCloneable abstract methods
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new LruCache<TKey, TValue>(this, cloner);
+    }
+
+    public bool ContainsKey(TKey key) {
+      return cacheMap.ContainsKey(key);
+    }
+
+    bool IDictionary<TKey, TValue>.Remove(TKey key) {
+      return cacheMap.Remove(key);
+    }
+
+    public void Add(KeyValuePair<TKey, TValue> item) {
+      Add(item.Key, item.Value);
+    }
+
+    public void Clear() {
+      cacheMap.Clear();
+      lruList.Clear();
+    }
+
+    public bool Contains(KeyValuePair<TKey, TValue> item) {
+      return cacheMap.Select(x => new KeyValuePair<TKey, TValue>(x.Key, x.Value.Value.Value)).Contains(item);
+    }
+
+    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex) {
+      throw new NotImplementedException();
+    }
+
+    public bool Remove(KeyValuePair<TKey, TValue> item) {
+      var ret = cacheMap.ContainsKey(item.Key);
+      Remove(item.Key);
+      return ret;
+    }
+
+    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() {
+      return cacheMap.Select(x => new KeyValuePair<TKey, TValue>(x.Key, x.Value.Value.Value)).GetEnumerator();
+    }
+
+    IEnumerator IEnumerable.GetEnumerator() {
+      return GetEnumerator();
+    }
+    #endregion
+  }
+}
Index: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs
===================================================================
--- branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs	(revision 15973)
+++ branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs	(revision 15974)
@@ -11,8 +11,11 @@
     [Storable]
     public readonly int Hash;
+
     [Storable]
     public readonly SymbolString SymbolString;
+
     [Storable]
     public readonly double Priority;
+
     [Storable]
     public readonly double R2;
@@ -43,5 +46,5 @@
 
   public enum StorageType {
-    PriorityQueue, Stack, Queue, RandomList
+    PriorityQueue, Stack, Queue, RandomList, SortedSet
   }
 
@@ -49,9 +52,10 @@
   class SearchDataStore : DeepCloneable, IEnumerable<SearchNode> {
     [Storable]
-    private Dictionary<int, SearchNode> storedValues; // Store hash-references and associated, actual values 
+    private LruCache<int, SearchNode> storedValues;
+    //private Dictionary<int, SearchNode> storedValues; // Store hash-references and associated, actual values 
+
     [Storable]
     private StorageType storageType;
 
-    // private storage
     [Storable]
     private Queue<int> queue;
@@ -62,4 +66,13 @@
     [Storable]
     private List<int> list;
+
+    [Storable]
+    private SortedSet<Tuple<double, int>> sortedSet;
+
+    [Storable]
+    private int searchDataStructureSize; // storage size for search nodes 
+
+    [Storable]
+    private int cacheSize; // cache for already explored search nodes 
 
     [ExcludeFromObjectGraphTraversal]
@@ -74,7 +87,11 @@
     protected SearchDataStore(bool deserializing) : this() { }
 
-    public SearchDataStore(StorageType storageType) {
+    public SearchDataStore(StorageType storageType, int searchDataStructureSize = (int)1e5, int cacheSize = (int)1e5) {
       this.storageType = storageType;
-      storedValues = new Dictionary<int, SearchNode>();
+
+      this.searchDataStructureSize = searchDataStructureSize;
+      this.cacheSize = cacheSize;
+
+      storedValues = new LruCache<int, SearchNode>(this.cacheSize);
       InitStorage();
     }
@@ -94,4 +111,7 @@
           InitRandomList();
           break;
+        case StorageType.SortedSet:
+          InitSortedSet();
+          break;
       }
     }
@@ -102,6 +122,9 @@
 
     protected SearchDataStore(SearchDataStore original, Cloner cloner) : base(original, cloner) {
-      storedValues = original.storedValues.ToDictionary(x => x.Key, x => cloner.Clone(x.Value));
+      storedValues = cloner.Clone(original.storedValues);
       storageType = original.storageType;
+      cacheSize = original.cacheSize;
+      searchDataStructureSize = original.searchDataStructureSize;
+
       InitStorage();
       switch (storageType) {
@@ -122,4 +145,7 @@
         case StorageType.RandomList:
           list.AddRange(original.list);
+          break;
+        case StorageType.SortedSet:
+          sortedSet = new SortedSet<Tuple<double, int>>(original.sortedSet);
           break;
       }
@@ -153,4 +179,21 @@
           };
           break;
+        case StorageType.SortedSet:
+          storeInternal = (hash, prio) => {
+            if (sortedSet.Count >= searchDataStructureSize) {
+              var max = sortedSet.Max;
+              sortedSet.Remove(max);
+              storedValues.Remove(max.Item2);
+            }
+            sortedSet.Add(Tuple.Create(prio, hash));
+          };
+          fetchInternal = () => {
+            var elem = sortedSet.FirstOrDefault();
+            if (elem == null)
+              return 0;
+            sortedSet.Remove(elem);
+            return elem.Item2;
+          };
+          break;
       }
     }
@@ -158,10 +201,19 @@
 
     private void InitPriorityQueue() {
-      int capacity = 10000000;
+      int capacity = searchDataStructureSize;
       priorityQueue = new PriorityQueue<double, int>(double.MaxValue, double.MinValue, capacity);
-      storeInternal = (hash, prio) => priorityQueue.Insert(prio, hash);
+      storeInternal = (hash, prio) => {
+        // size is the 0-based index of the last used element
+        if (priorityQueue.Size == capacity - 1) {
+          // if the queue is at capacity we have to replace 
+          return;
+        }
+        priorityQueue.Insert(prio, hash);
+      };
       fetchInternal = () => {
         int ret = priorityQueue.PeekMinValue();
-        priorityQueue.RemoveMin();
+        if (priorityQueue.Size > 0) {
+          priorityQueue.RemoveMin();
+        }
         return ret;
       };
@@ -195,4 +247,23 @@
     }
 
+    private void InitSortedSet() {
+      sortedSet = new SortedSet<Tuple<double, int>>();
+      storeInternal = (hash, prio) => {
+        if (sortedSet.Count >= searchDataStructureSize) {
+          var max = sortedSet.Max;
+          sortedSet.Remove(max);
+          storedValues.Remove(max.Item2);
+        }
+        sortedSet.Add(Tuple.Create(prio, hash));
+      };
+      fetchInternal = () => {
+        var elem = sortedSet.FirstOrDefault();
+        if (elem == null)
+          return default(int);
+        sortedSet.Remove(elem);
+        return elem.Item2;
+      };
+    }
+
     #endregion
 
@@ -201,6 +272,8 @@
     public SearchNode GetNext() {
       int hash = fetchInternal.Invoke();
-      SearchNode result = storedValues[hash];
-      storedValues.Remove(hash);
+      SearchNode result = null;
+      if (storedValues.TryGetValue(hash, out result)) {
+        storedValues.Remove(hash);
+      }
       return result;
     }
@@ -212,5 +285,6 @@
 
     public bool Contains(int hash) {
-      return storedValues.ContainsKey(hash);
+      SearchNode result;
+      return storedValues.TryGetValue(hash, out result);
     }
 
@@ -220,9 +294,24 @@
 
     public int Count {
-      get { return storedValues.Count; }
+      get {
+        switch (storageType) {
+          case StorageType.PriorityQueue:
+            return priorityQueue.Size;
+          case StorageType.Queue:
+            return queue.Count;
+          case StorageType.RandomList:
+            return list.Count;
+          case StorageType.Stack:
+            return stack.Count;
+          case StorageType.SortedSet:
+            return sortedSet.Count;
+          default:
+            throw new InvalidOperationException("");
+        }
+      }
     }
 
     public IEnumerator<SearchNode> GetEnumerator() {
-      return storedValues.Values.GetEnumerator();
+      return storedValues.Select(x => x.Value).GetEnumerator();
     }
 
Index: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Sentence.cs
===================================================================
--- branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Sentence.cs	(revision 15973)
+++ branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Sentence.cs	(revision 15974)
@@ -29,5 +29,5 @@
 
     protected SymbolString(SymbolString original, Cloner cloner) : base(original, cloner) {
-      symbols = original.symbols.ToArray();
+      symbols = original.symbols.Select(cloner.Clone).ToArray();
     }
 
Index: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs
===================================================================
--- branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs	(revision 15973)
+++ branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs	(revision 15974)
@@ -10,6 +10,6 @@
     private readonly int stringRepresentationHash;
 
-    [Storable(AllowOneWay = true)]
-    public string StringRepresentation { get; }
+    [Storable]
+    public string StringRepresentation { get; private set; }
 
     protected Symbol(string representation) {
Index: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj
===================================================================
--- branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj	(revision 15973)
+++ branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj	(revision 15974)
@@ -122,4 +122,5 @@
     <Compile Include="GrammarEnumeration\Grammar.cs" />
     <Compile Include="GrammarEnumeration\GrammarEnumerationAlgorithm.cs" />
+    <Compile Include="GrammarEnumeration\LruCache.cs" />
     <Compile Include="Hashing\Hasher.cs" />
     <Compile Include="GrammarEnumeration\SearchDataStructure.cs" />
Index: branches/2886_SymRegGrammarEnumeration/Test/Test.csproj
===================================================================
--- branches/2886_SymRegGrammarEnumeration/Test/Test.csproj	(revision 15973)
+++ branches/2886_SymRegGrammarEnumeration/Test/Test.csproj	(revision 15974)
@@ -34,4 +34,10 @@
     <ErrorReport>prompt</ErrorReport>
     <WarningLevel>4</WarningLevel>
+  </PropertyGroup>
+  <PropertyGroup>
+    <SignAssembly>true</SignAssembly>
+  </PropertyGroup>
+  <PropertyGroup>
+    <AssemblyOriginatorKeyFile>HeuristicLab.snk</AssemblyOriginatorKeyFile>
   </PropertyGroup>
   <ItemGroup>
@@ -120,4 +126,7 @@
     </ProjectReference>
   </ItemGroup>
+  <ItemGroup>
+    <None Include="HeuristicLab.snk" />
+  </ItemGroup>
   <Choose>
     <When Condition="'$(VisualStudioVersion)' == '10.0' And '$(IsCodedUITest)' == 'True'">
