Changeset 12988

Timestamp:

10/09/15 00:16:03 (9 years ago)

Author:

bburlacu

Message:

#1772: Performance improvement changes

• QueryMatch.cs: eliminate unnecessary ToList() call and expensive GetBranchLevel calls
• Diversification: eliminated creation of shallow copies of the individual subscopes as it was either too slow (due to events being registered/deregistered when variables are added to the scope) or too leaky (if attempting to clear the scopes without clearing the variables then the code is leaking EventHandlers)
• Aggregated diversification statistics separately with the help of some parameters set up in the SchemaCreator and SchemaEvaluator
• Made code in the UpdateEstimatedValuesOperator perform exactly as in the evaluator (updating quality and estimated values)
• Removed no longer needed SchemaCleanupOperator
• Do not evaluate intermediate vertices in the genealogy analyzer if the TrimOlderGenerations flag is activated

New functionality:

• parameter to control the fraction of the population to be considered by the diversification strategy
• parameter to control whether individuals may be matched by any schema and mutated only once (exclusive matching)
• parameter to control whether linear scaling should be applied to the estimated values used for the calculation of phenotypic similarity (default: yes)

Location:

branches/HeuristicLab.EvolutionTracking

Files:

• HeuristicLab.EvolutionTracking/3.4/Analyzers/GenealogyAnalyzer.cs (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/DiversificationStatisticsOperator.cs (moved) (moved from branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaCleanupOperator.cs) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaCreator.cs (modified) (9 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaEvaluator.cs (modified) (11 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/UpdateEstimatedValuesOperator.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/QueryMatch.cs (modified) (1 diff)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/Analyzers/GenealogyAnalyzer.cs

@@ -314 +314 @@
       }
       // update qualities for intermediate vertices
-      EvaluateIntermediateChildren();
+      if (!TrimOlderGenerations)
+        EvaluateIntermediateChildren();
 
       // remove extra graph nodes (added by the instrumented operators in the case of offspring selection)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -316 +316 @@
     <Compile Include="Tracking\Analyzers\SymbolicDataAnalysisSubtreeSampleCountAnalyzer.cs" />
     <Compile Include="Tracking\Analyzers\SymbolicDataAnalysisTraceOverlapAnalyzer.cs" />
-    <Compile Include="Tracking\SchemaDiversification\SchemaCleanupOperator.cs" />
+    <Compile Include="Tracking\SchemaDiversification\DiversificationStatisticsOperator.cs" />
     <Compile Include="Tracking\SchemaDiversification\SchemaEvaluator.cs" />
     <Compile Include="Tracking\SchemaDiversification\SchemaCreator.cs" />

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/DiversificationStatisticsOperator.cs

@@ -20 +20 @@
 #endregion
 
-using System.Linq;
+using HeuristicLab.Analysis;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Data;
 using HeuristicLab.Operators;
+using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
@@ -29 +32 @@
   [Item("SchemaCleanupOperator", "Operator which removes the schemas from the global scope after they have been evaluated.")]
   [StorableClass]
-  public class SchemaCleanupOperator : SingleSuccessorOperator {
-    public SchemaCleanupOperator() { }
+  public class DiversificationStatisticsOperator : SingleSuccessorOperator {
+    private const string NumberOfChangedTreesParameterName = "NumberOfChangedTrees";
+    private const string NumberOfSchemasParameterName = "NumberOfSchemas";
+    private const string AverageSchemaLengthParameterName = "AverageSchemaLength";
+    private const string ResultCollectionParameterName = "Results";
 
-    protected SchemaCleanupOperator(SchemaCleanupOperator original, Cloner cloner) : base(original, cloner) { }
+    public ILookupParameter<IntValue> NumberOfChangedTreesParameter {
+      get { return (ILookupParameter<IntValue>)Parameters[NumberOfChangedTreesParameterName]; }
+    }
+    public ILookupParameter<IntValue> NumberOfSchemasParameter {
+      get { return (ILookupParameter<IntValue>)Parameters[NumberOfSchemasParameterName]; }
+    }
+    public ILookupParameter<DoubleValue> AverageSchemaLengthParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters[AverageSchemaLengthParameterName]; }
+    }
+    public ILookupParameter<ResultCollection> ResultCollectionParameter {
+      get { return (ILookupParameter<ResultCollection>)Parameters[ResultCollectionParameterName]; }
+    }
 
-    public override IDeepCloneable Clone(Cloner cloner) { return new SchemaCleanupOperator(this, cloner); }
+    public DiversificationStatisticsOperator() {
+      Parameters.Add(new LookupParameter<IntValue>(NumberOfChangedTreesParameterName));
+      Parameters.Add(new LookupParameter<IntValue>(NumberOfSchemasParameterName));
+      Parameters.Add(new LookupParameter<DoubleValue>(AverageSchemaLengthParameterName));
+      Parameters.Add(new LookupParameter<ResultCollection>(ResultCollectionParameterName));
+    }
+
+    protected DiversificationStatisticsOperator(DiversificationStatisticsOperator original, Cloner cloner) : base(original, cloner) { }
+
+    public override IDeepCloneable Clone(Cloner cloner) { return new DiversificationStatisticsOperator(this, cloner); }
 
     [StorableConstructor]
-    protected SchemaCleanupOperator(bool deserializing) : base(deserializing) { }
+    protected DiversificationStatisticsOperator(bool deserializing) : base(deserializing) { }
 
     public override IOperation Apply() {
-      foreach (var scope in ExecutionContext.Scope.SubScopes.Where(x => x.Name.Equals("Schema"))) {
-        foreach (var subscope in scope.SubScopes) { subscope.Variables.Clear(); }
-        scope.SubScopes.Clear();
-        scope.Variables.Clear();
+
+      var results = ResultCollectionParameter.ActualValue;
+      DataTable table;
+      if (!results.ContainsKey("NumberOfChangedTrees")) {
+        table = new DataTable();
+        results.Add(new Result("NumberOfChangedTrees", table));
+        var row = new DataRow("Changed trees");
+        table.Rows.Add(row);
       }
-      ExecutionContext.Scope.SubScopes.RemoveAll(x => x.Name.Equals("Schema"));
+      if (!results.ContainsKey("AverageSchemaLength")) {
+        table = new DataTable();
+        results.Add(new Result("AverageSchemaLength", table));
+        var row = new DataRow("Average schema length");
+        table.Rows.Add(row);
+      }
+      if (!results.ContainsKey("NumberOfSchemas")) {
+        table = new DataTable();
+        results.Add(new Result("NumberOfSchemas", table));
+        var row = new DataRow("Number of schemas");
+        table.Rows.Add(row);
+      }
+      ((DataTable)results["NumberOfChangedTrees"].Value).Rows["Changed trees"].Values.Add(NumberOfChangedTreesParameter.ActualValue.Value);
+      ((DataTable)results["AverageSchemaLength"].Value).Rows["Average schema length"].Values.Add(AverageSchemaLengthParameter.ActualValue.Value);
+      ((DataTable)results["NumberOfSchemas"].Value).Rows["Number of schemas"].Values.Add(NumberOfSchemasParameter.ActualValue.Value);
+
       return base.Apply();
     }

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaCreator.cs

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
 using System.Linq;
-using HeuristicLab.Analysis;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -28 +28 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.EvolutionTracking;
-using HeuristicLab.Operators;
-using HeuristicLab.Optimization.Operators;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -44 +42 @@
     private const string ExecuteInParallelParameterName = "ExecuteInParallel";
     private const string MaxDegreeOfParalellismParameterName = "MaxDegreeOfParallelism";
+    private const string PercentageOfPopulationParameterName = "PercentageOfPopulationToDiversify";
+    private const string ScaleEstimatedValuesParameterName = "ScaleEstimatedValues";
+    private const string ExclusiveMatchingParameterName = "ExclusiveMatching";
+    private const string NumberOfChangedTreesParameterName = "NumberOfChangedTrees";
+    private const string NumberOfSchemasParameterName = "NumberOfSchemas";
+    private const string AverageSchemaLengthParameterName = "AverageSchemaLength";
 
     #region parameters
+    public IFixedValueParameter<BoolValue> ExclusiveMatchingParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters[ExclusiveMatchingParameterName]; }
+    }
+    public IFixedValueParameter<BoolValue> ScaleEstimatedValuesParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters[ScaleEstimatedValuesParameterName]; }
+    }
+    public IFixedValueParameter<PercentValue> PercentageOfPopulationParameter {
+      get { return (IFixedValueParameter<PercentValue>)Parameters[PercentageOfPopulationParameterName]; }
+    }
     public IFixedValueParameter<IntValue> MinimumSchemaLengthParameter {
       get { return (IFixedValueParameter<IntValue>)Parameters[MinimumSchemaLengthParameterName]; }
     }
-
     public IFixedValueParameter<BoolValue> ExecuteInParallelParameter {
       get { return (IFixedValueParameter<BoolValue>)Parameters[ExecuteInParallelParameterName]; }
     }
-
     public IFixedValueParameter<IntValue> MaxDegreeOfParallelismParameter {
       get { return (IFixedValueParameter<IntValue>)Parameters[MaxDegreeOfParalellismParameterName]; }
     }
-
     public IFixedValueParameter<PercentValue> MinimumSchemaFrequencyParameter {
       get { return (IFixedValueParameter<PercentValue>)Parameters[MinimumSchemaFrequencyParameterName]; }
     }
-
     public IFixedValueParameter<PercentValue> MinimumPhenotypicSimilarityParameter {
       get { return (IFixedValueParameter<PercentValue>)Parameters[MinimumPhenotypicSimilarityParameterName]; }
     }
-
     public IFixedValueParameter<PercentValue> ReplacementRatioParameter {
       get { return (IFixedValueParameter<PercentValue>)Parameters[ReplacementRatioParameterName]; }
+    }
+    public IValueParameter<IntValue> NumberOfSchemasParameter {
+      get { return (IValueParameter<IntValue>)Parameters[NumberOfSchemasParameterName]; }
+    }
+    public IValueParameter<DoubleValue> AverageSchemaLengthParameter {
+      get { return (IValueParameter<DoubleValue>)Parameters[AverageSchemaLengthParameterName]; }
+    }
+    public IValueParameter<IntValue> NumberOfChangedTreesParameter {
+      get { return (IValueParameter<IntValue>)Parameters[NumberOfChangedTreesParameterName]; }
     }
     #endregion
@@ -75 +92 @@
     public int MaxDegreeOfParallelism { get { return MaxDegreeOfParallelismParameter.Value.Value; } }
     public bool ExecuteInParallel { get { return ExecuteInParallelParameter.Value.Value; } }
+    public double PercentageOfPopulation { get { return PercentageOfPopulationParameter.Value.Value; } }
     #endregion
 
-    private SchemaEvaluator schemaEvaluator;
-    private SchemaCleanupOperator schemaCleanupOperator;
-    private DataReducer changedTreesReducer;
-    private DataTableValuesCollector valuesCollector;
-    private ResultsCollector resultsCollector;
     private UpdateEstimatedValuesOperator updateEstimatedValuesOperator;
-
-    private void ParameterizeOperators() {
-      schemaEvaluator = new SchemaEvaluator();
-      schemaCleanupOperator = new SchemaCleanupOperator();
-
-      changedTreesReducer = new DataReducer();
-      changedTreesReducer.ParameterToReduce.ActualName = schemaEvaluator.ChangedTreesParameter.ActualName;
-      changedTreesReducer.ReductionOperation.Value = new ReductionOperation(ReductionOperations.Sum);
-      changedTreesReducer.TargetOperation.Value = new ReductionOperation(ReductionOperations.Assign); // asign the sum to the target parameter
-      changedTreesReducer.TargetParameter.ActualName = "NumberOfChangedTrees";
-
-      valuesCollector = new DataTableValuesCollector();
-      valuesCollector.CollectedValues.Add(new LookupParameter<IntValue>("NumberOfChangedTrees"));
-      valuesCollector.DataTableParameter.ActualName = "Diversification";
-
-      resultsCollector = new ResultsCollector();
-      resultsCollector.CollectedValues.Add(new LookupParameter<DataTable>("Diversification"));
-
-      updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
-    }
+    private DiversificationStatisticsOperator diversificationStatisticsOperator;
 
     public SchemaCreator() {
@@ -109 +103 @@
       Parameters.Add(new FixedValueParameter<PercentValue>(MinimumPhenotypicSimilarityParameterName, new PercentValue(0.9)));
       Parameters.Add(new FixedValueParameter<PercentValue>(ReplacementRatioParameterName, new PercentValue(0.9)));
+      Parameters.Add(new FixedValueParameter<PercentValue>(PercentageOfPopulationParameterName, new PercentValue(1)));
       Parameters.Add(new FixedValueParameter<BoolValue>(RandomReplacementParameterName, new BoolValue(false)));
       Parameters.Add(new FixedValueParameter<BoolValue>(ExecuteInParallelParameterName, new BoolValue(false)));
       Parameters.Add(new FixedValueParameter<IntValue>(MaxDegreeOfParalellismParameterName, new IntValue(-1)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(ScaleEstimatedValuesParameterName, new BoolValue(true)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(ExclusiveMatchingParameterName, new BoolValue(false)));
+      Parameters.Add(new ValueParameter<IntValue>(NumberOfChangedTreesParameterName, new IntValue(0)));
+      Parameters.Add(new ValueParameter<IntValue>(NumberOfSchemasParameterName, new IntValue(0)));
+      Parameters.Add(new ValueParameter<DoubleValue>(AverageSchemaLengthParameterName, new DoubleValue(0)));
+
+      NumberOfChangedTreesParameter.Hidden = true;
+      NumberOfSchemasParameter.Hidden = true;
+      AverageSchemaLengthParameter.Hidden = true;
 
       ExecuteInParallelParameter.Hidden = true;
       MaxDegreeOfParallelismParameter.Hidden = true;
-
-      ParameterizeOperators();
     }
 
@@ -133 +135 @@
       if (gen < 1 || GenealogyGraph == null)
         return base.Apply();
+
+      var n = (int)Math.Round(ExecutionContext.Scope.SubScopes.Count * PercentageOfPopulation);
+      var scopes = new ScopeList(ExecutionContext.Scope.SubScopes.Take(n));
+
       // for now, only consider crossover offspring
-
-      var scopes = new ScopeList(this.ExecutionContext.Scope.SubScopes);
-      var vertices = GenealogyGraph.GetByRank(gen).Where(x => x.InDegree == 2).Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>();
+      var vertices = from s in scopes
+                     let t = (ISymbolicExpressionTree)s.Variables["SymbolicExpressionTree"].Value
+                     let v = GenealogyGraph.GetByContent(t)
+                     where v.InDegree == 2
+                     select v;
+
       var groups = vertices.GroupBy(x => x.Parents.First()).OrderByDescending(g => g.Count()).ToList();
       var anySubtreeSymbol = new AnySubtreeSymbol();
 
-      if (schemaEvaluator == null || schemaCleanupOperator == null || changedTreesReducer == null || valuesCollector == null || resultsCollector == null)
-        ParameterizeOperators();
-
-      var reduceChangedTrees = ExecutionContext.CreateChildOperation(changedTreesReducer);
-      var collectValues = ExecutionContext.CreateChildOperation(valuesCollector);
-      var collectResults = ExecutionContext.CreateChildOperation(resultsCollector);
-
       var updateEstimatedValues = new OperationCollection { Parallel = true };
+      if (updateEstimatedValuesOperator == null)
+        updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
+
       foreach (var s in scopes) {
         if (!s.Variables.ContainsKey("EstimatedValues"))
@@ -153 +158 @@
         updateEstimatedValues.Add(ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, s));
       }
-      var oc = new OperationCollection { updateEstimatedValues };
-
+
+      var evaluateSchemas = new OperationCollection();
+      var schemas = new List<ISymbolicExpressionTree>();
+      var wildCardCounts = new List<double>();
       #region create schemas and add subscopes representing the individuals
       foreach (var g in groups) {
@@ -167 +174 @@
         Array.Sort(indices);
         var nodesToReplace = indices.Select(x => nodes[x]).ToList();
+        int w = 0;
         for (int i = nodesToReplace.Count - 1; i >= 0; --i) {
           var node = nodesToReplace[i];
@@ -177 +185 @@
           ReplaceSubtree(node, replacement, false);
           replaced = true;
+          ++w;
         }
         if (replaced) {
-          var scope = new Scope("Schema");
-          scope.Variables.Add(new Core.Variable("Schema", schema));
-          scope.SubScopes.AddRange(ShallowCopy(scopes));
-
-          oc.Add(ExecutionContext.CreateChildOperation(schemaEvaluator, scope));
-          ExecutionContext.Scope.SubScopes.Add(scope);
+          // store the schemas and the number of wildcards they contain in two lists
+          schemas.Add(schema);
+          wildCardCounts.Add(w);
         }
       }
+
+      for (int i = 0; i < schemas.Count; ++i) {
+        var schema = schemas[i];
+        evaluateSchemas.Add(ExecutionContext.CreateChildOperation(new SchemaEvaluator { Schema = schema }, ExecutionContext.Scope));
+      }
       #endregion
 
-      var cleanup = ExecutionContext.CreateChildOperation(schemaCleanupOperator);
+      if (diversificationStatisticsOperator == null)
+        diversificationStatisticsOperator = new DiversificationStatisticsOperator();
+
+      var calculateStatistics = ExecutionContext.CreateChildOperation(diversificationStatisticsOperator);
+
+      // set parameters for statistics
+      AverageSchemaLengthParameter.Value = new DoubleValue(schemas.Average(x => x.Length));
+      NumberOfSchemasParameter.Value = new IntValue(schemas.Count);
+      NumberOfChangedTreesParameter.Value = new IntValue(0);
+
       // return an operation collection containing all the scope operations + base.Apply()
-      return new OperationCollection { oc, reduceChangedTrees, collectValues, collectResults, cleanup, base.Apply() };
-    }
-
-    private static ScopeList ShallowCopy(ScopeList scopes) {
-      var scopeList = new ScopeList();
-      // shallow-copy means that we create a new scope but reuse the variables
-      foreach (var scope in scopes) {
-        var s = new Scope(scope.Name);
-        foreach (var v in scope.Variables)
-          s.Variables.Add(v);
-        scopeList.Add(s);
-      }
-      return scopeList;
+      return new OperationCollection { updateEstimatedValues, evaluateSchemas, calculateStatistics, base.Apply() };
     }
 

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaEvaluator.cs

@@ -50 +50 @@
     private const string MutatorParameterName = "Mutator";
     private const string RandomReplacementParameterName = "RandomReplacement";
-    private const string ChangedTreesParameterName = "ChangedTrees";
+    private const string NumberOfChangedTreesParameterName = "NumberOfChangedTrees";
     private const string ExecuteInParallelParameterName = "ExecuteInParallel";
     private const string MaxDegreeOfParalellismParameterName = "MaxDegreeOfParallelism";
+    private const string ExclusiveMatchingParameterName = "ExclusiveMatching";
     #endregion
 
     #region parameters
+    public ILookupParameter<BoolValue> ExclusiveMatchingParameter {
+      get { return (ILookupParameter<BoolValue>)Parameters[ExclusiveMatchingParameterName]; }
+    }
     public ILookupParameter<BoolValue> ExecuteInParallelParameter {
       get { return (ILookupParameter<BoolValue>)Parameters[ExecuteInParallelParameterName]; }
@@ -101 +105 @@
       get { return (ILookupParameter<PercentValue>)Parameters[MinimumPhenotypicSimilarityParameterName]; }
     }
-    public LookupParameter<IntValue> ChangedTreesParameter {
-      get { return (LookupParameter<IntValue>)Parameters[ChangedTreesParameterName]; }
+    public LookupParameter<IntValue> NumberOfChangedTreesParameter {
+      get { return (LookupParameter<IntValue>)Parameters[NumberOfChangedTreesParameterName]; }
     }
     #endregion
@@ -111 +115 @@
     public PercentValue MinimumPhenotypicSimilarity { get { return MinimumPhenotypicSimilarityParameter.ActualValue; } }
     public BoolValue RandomReplacement { get { return RandomReplacementParameter.ActualValue; } }
+    public IntValue NumberOfChangedTrees { get { return NumberOfChangedTreesParameter.ActualValue; } }
     #endregion
 
@@ -122 +127 @@
     };
 
+    public ISymbolicExpressionTree Schema { get; set; }
+
     [Storable]
     private readonly UpdateEstimatedValuesOperator updateEstimatedValuesOperator;
@@ -128 +135 @@
       qm = new QueryMatch(comp) { MatchParents = true };
       this.updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
-
+      #region add parameters
       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(SchemaParameterName, "The current schema to be evaluated"));
       Parameters.Add(new LookupParameter<PercentValue>(MinimumSchemaFrequencyParameterName));
@@ -142 +149 @@
       Parameters.Add(new LookupParameter<ISymbolicExpressionTreeManipulator>(MutatorParameterName));
       Parameters.Add(new LookupParameter<BoolValue>(RandomReplacementParameterName));
-      Parameters.Add(new LookupParameter<IntValue>(ChangedTreesParameterName));
+      Parameters.Add(new LookupParameter<IntValue>(NumberOfChangedTreesParameterName));
       Parameters.Add(new LookupParameter<BoolValue>(ExecuteInParallelParameterName));
       Parameters.Add(new LookupParameter<IntValue>(MaxDegreeOfParalellismParameterName));
+      Parameters.Add(new LookupParameter<BoolValue>(ExclusiveMatchingParameterName));
+      #endregion
     }
 
@@ -170 +179 @@
       var mutator = MutatorParameter.ActualValue;
 
-      var s = SchemaParameter.ActualValue;
+      var s = Schema;
       var sRoot = s.Root.GetSubtree(0).GetSubtree(0);
       int countThreshold = (int)Math.Max(2, Math.Round(MinimumSchemaFrequency.Value * individuals.Count));
 
       // first apply the length and root equality checks in order to filter the individuals
-      var filtered = (from ind in individuals
-                      let t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value
-                      where t.Length >= s.Length && qm.Comparer.Equals(t.Root.GetSubtree(0).GetSubtree(0), sRoot)
-                      select ind).ToList();
+      var exclusiveMatching = ExclusiveMatchingParameter.ActualValue.Value;
+      var filtered = exclusiveMatching ? (from ind in individuals
+                                          where !ind.Variables.ContainsKey("AlreadyMatched")
+                                          let t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value
+                                          where t.Length >= s.Length && qm.Comparer.Equals(t.Root.GetSubtree(0).GetSubtree(0), sRoot)
+                                          select ind).ToList()
+                                       : (from ind in individuals
+                                          let t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value
+                                          where t.Length >= s.Length && qm.Comparer.Equals(t.Root.GetSubtree(0).GetSubtree(0), sRoot)
+                                          select ind).ToList();
 
       // if we don't have enough filtered individuals, then we are done
       if (filtered.Count < countThreshold) {
-        ChangedTreesParameter.ActualValue = new IntValue(0);
         return base.Apply();
       }
@@ -210 +224 @@
       } else {
         for (int i = 0; i < filtered.Count; ++i) {
-
           // break early if it becomes impossible to reach the minimum threshold
           if (matchingIndividuals.Count + filtered.Count - i < countThreshold)
@@ -223 +236 @@
       }
 
+      // additional condition: the average schema quality should be equal or greater than the population average quality
       if (matchingIndividuals.Count < countThreshold) {
-        ChangedTreesParameter.ActualValue = new IntValue(0);
         return base.Apply();
       }
@@ -230 +243 @@
       var similarity = CalculatePhenotypicSimilarity(matchingIndividuals, calculator, executeInParallel, maxDegreeOfParallelism);
       if (similarity < MinimumPhenotypicSimilarity.Value) {
-        ChangedTreesParameter.ActualValue = new IntValue(0);
         return base.Apply();
       }
@@ -244 +256 @@
         mutationOc.Add(mutatorOp);
         updateEstimatedValues.Add(updateOp);
-      }
-      ChangedTreesParameter.ActualValue = new IntValue(individualsToReplace.Count);
+        if (exclusiveMatching)
+          ind.Variables.Add(new Core.Variable("AlreadyMatched"));
+      }
+
+      NumberOfChangedTrees.Value += individualsToReplace.Count; // a lock is not necessary here because the SchemaEvaluators cannot be executed in parallel
+
       return new OperationCollection(mutationOc, updateEstimatedValues, base.Apply());
     }

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/UpdateEstimatedValuesOperator.cs

@@ -38 +38 @@
     private const string EstimationLimitsParameterName = "EstimationLimits";
     private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
+    private const string ScaleEstimatedValuesParameterName = "ScaleEstimatedValues";
 
     public ILookupParameter<IRegressionProblemData> ProblemDataParameter {
@@ -51 +52 @@
       get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
     }
-
+    public ILookupParameter<BoolValue> ScaleEstimatedValuesParameter {
+      get { return (ILookupParameter<BoolValue>)Parameters[ScaleEstimatedValuesParameterName]; }
+    }
 
     public UpdateEstimatedValuesOperator() {
@@ -58 +61 @@
       Parameters.Add(new LookupParameter<DoubleLimit>(EstimationLimitsParameterName));
       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName));
+      Parameters.Add(new LookupParameter<BoolValue>(ScaleEstimatedValuesParameterName));
     }
 
@@ -100 +104 @@
       OnlineCalculatorError error;
       var r = OnlinePearsonsRCalculator.Calculate(targetValues, scaled, out error);
-      if (error != OnlineCalculatorError.None) r = 0;
+      if (error != OnlineCalculatorError.None) r = double.NaN;
 
       var r2 = r * r;
-      if (r2 > 1.0) r2 = 1.0;
 
       var variables = ExecutionContext.Scope.Variables;
       ((DoubleValue)variables["Quality"].Value).Value = r2;
+
+      var scaleEstimatedValues = ScaleEstimatedValuesParameter.ActualValue;
+      if (!scaleEstimatedValues.Value)
+        scaled = estimatedValues.LimitToRange(estimationLimits.Lower, estimationLimits.Upper).ToArray();
 
       if (variables.ContainsKey("EstimatedValues")) {

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/QueryMatch.cs

@@ -159 +159 @@
 
     internal static List<NodeInfo> InitializePostOrder(ISymbolicExpressionTreeNode node) {
-      var list = node.IterateNodesPostfix().ToList();
-      var nodes = list.Select((x, i) => new NodeInfo { Node = x, Index = i, Level = node.GetBranchLevel(x) }).ToList();
-      var map = Enumerable.Range(0, list.Count).ToDictionary(i => list[i], i => nodes[i]);
+      var nodes = node.IterateNodesPostfix().Select((x, i) => new NodeInfo { Node = x, Index = i, Level = 0 }).ToList();
+      var map = nodes.ToDictionary(x => x.Node, x => x);
 
       var inf = new NodeInfo { Node = null, Index = int.MaxValue, Previous = nodes.Last() };
       var nil = new NodeInfo { Node = null, Index = -1, Next = nodes.First() };
 
-      foreach (var n in nodes) {
+      for (int i = nodes.Count - 1; i >= 0; --i) {
+        var n = nodes[i];
         n.Parent = n.Node.Parent != null && map.ContainsKey(n.Node.Parent) ? map[n.Node.Parent] : null;
+        n.Level = n.Parent?.Level + 1 ?? -1;
         n.Next = n == nodes.Last() ? inf : nodes[n.Index + 1];
         n.Previous = n == nodes.First() ? nil : nodes[n.Index - 1];