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

Timestamp:

10/02/15 01:08:30 (9 years ago)

Author:

bburlacu

Message:

#1772:

• added parameters to the SchemaCreator for calculating things in parallel
• added parallel code to the SchemaEvaluator
• implemented quality calculation and saving of estimated values in the scope in the UpdateEstimatedValuesOperator
• small refactoring of QueryMatch (added some useful methods and made NodeInfo internal)
• updated query match unit test

File:

• branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaEvaluator.cs (modified) (9 diffs)

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

@@ -22 +22 @@
 using System;
 using System.Linq;
+using System.Threading.Tasks;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -50 +51 @@
     private const string RandomReplacementParameterName = "RandomReplacement";
     private const string ChangedTreesParameterName = "ChangedTrees";
+    private const string ExecuteInParallelParameterName = "ExecuteInParallel";
+    private const string MaxDegreeOfParalellismParameterName = "MaxDegreeOfParallelism";
     #endregion
 
     #region parameters
+    public ILookupParameter<BoolValue> ExecuteInParallelParameter {
+      get { return (ILookupParameter<BoolValue>)Parameters[ExecuteInParallelParameterName]; }
+    }
+    public ILookupParameter<IntValue> MaxDegreeOfParallelismParameter {
+      get { return (ILookupParameter<IntValue>)Parameters[MaxDegreeOfParalellismParameterName]; }
+    }
     public ILookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>> EvaluatorParameter {
       get { return (ILookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>>)Parameters[EvaluatorParameterName]; }
@@ -98 +107 @@
 
     #region parameter properties
-    public PercentValue MinimumSchemaFrequency {
-      get { return MinimumSchemaFrequencyParameter.ActualValue; }
-    }
-
-    public PercentValue ReplacementRatio {
-      get { return ReplacementRatioParameter.ActualValue; }
-    }
-
-    public PercentValue MinimumPhenotypicSimilarity {
-      get { return MinimumPhenotypicSimilarityParameter.ActualValue; }
-    }
-
-    public BoolValue RandomReplacement {
-      get { return RandomReplacementParameter.ActualValue; }
-    }
+    public PercentValue MinimumSchemaFrequency { get { return MinimumSchemaFrequencyParameter.ActualValue; } }
+    public PercentValue ReplacementRatio { get { return ReplacementRatioParameter.ActualValue; } }
+    public PercentValue MinimumPhenotypicSimilarity { get { return MinimumPhenotypicSimilarityParameter.ActualValue; } }
+    public BoolValue RandomReplacement { get { return RandomReplacementParameter.ActualValue; } }
     #endregion
 
@@ -124 +122 @@
     };
 
-
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      if (!Parameters.ContainsKey(ChangedTreesParameterName))
-        Parameters.Add(new LookupParameter<IntValue>(ChangedTreesParameterName));
-    }
+    [Storable]
+    private readonly UpdateEstimatedValuesOperator updateEstimatedValuesOperator;
 
     public SchemaEvaluator() {
       qm = new QueryMatch(comp) { MatchParents = true };
+      this.updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
 
       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(SchemaParameterName, "The current schema to be evaluated"));
@@ -148 +143 @@
       Parameters.Add(new LookupParameter<BoolValue>(RandomReplacementParameterName));
       Parameters.Add(new LookupParameter<IntValue>(ChangedTreesParameterName));
-    }
-
+      Parameters.Add(new LookupParameter<BoolValue>(ExecuteInParallelParameterName));
+      Parameters.Add(new LookupParameter<IntValue>(MaxDegreeOfParalellismParameterName));
+    }
 
     [StorableConstructor]
@@ -155 +151 @@
 
     protected SchemaEvaluator(SchemaEvaluator original, Cloner cloner) : base(original, cloner) {
-      this.comp = (ISymbolicExpressionTreeNodeEqualityComparer)original.comp.Clone();
-      this.qm = new QueryMatch(comp) { MatchParents = original.qm.MatchParents };
+      this.comp = original.comp == null ? new SymbolicExpressionTreeNodeEqualityComparer {
+        MatchConstantValues = false,
+        MatchVariableWeights = false,
+        MatchVariableNames = true
+      } : (ISymbolicExpressionTreeNodeEqualityComparer)original.comp.Clone();
+      this.qm = new QueryMatch(comp) { MatchParents = original.qm?.MatchParents ?? true };
+      this.updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
     }
 
@@ -163 +164 @@
     }
 
-    private static double CalculatePhenotypicSimilarity(ScopeList individuals, SymbolicExpressionTreePhenotypicSimilarityCalculator calculator) {
-      double similarity = 0;
-      int count = individuals.Count;
-      for (int i = 0; i < count - 1; ++i) {
-        for (int j = i + 1; j < count; ++j) {
-          similarity += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
-        }
-      }
-      return similarity / (count * (count - 1) / 2.0);
-    }
-
     public override IOperation Apply() {
       var individuals = ExecutionContext.Scope.SubScopes; // the scopes represent the individuals
@@ -179 +169 @@
       var random = RandomParameter.ActualValue;
       var mutator = MutatorParameter.ActualValue;
-      var evaluator = EvaluatorParameter.ActualValue;
-      var updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
 
       var s = SchemaParameter.ActualValue;
-      var matchingIndividuals = new ScopeList();
-      foreach (var ind in individuals) {
-        var t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value;
-        if (t.Length >= s.Length && qm.Match(t, s))
-          matchingIndividuals.Add(ind);
-      }
-
-      if (matchingIndividuals.Count < (int)Math.Max(2, Math.Round(MinimumSchemaFrequency.Value * individuals.Count))) {
+      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();
+
+      // if we don't have enough filtered individuals, then we are done
+      if (filtered.Count < countThreshold) {
         ChangedTreesParameter.ActualValue = new IntValue(0);
         return base.Apply();
       }
 
-      var similarity = CalculatePhenotypicSimilarity(matchingIndividuals, calculator);
+      // check if the filtered individuals match the schema
+      var sNodes = QueryMatch.InitializePostOrder(sRoot);
+      var matchingIndividuals = new ScopeList();
+      bool executeInParallel = ExecuteInParallelParameter.ActualValue.Value;
+      int maxDegreeOfParallelism = MaxDegreeOfParallelismParameter.ActualValue.Value;
+
+      if (executeInParallel) {
+        var matching = new bool[filtered.Count];
+
+        Parallel.For(0, filtered.Count, new ParallelOptions { MaxDegreeOfParallelism = maxDegreeOfParallelism },
+          i => {
+            var t = (ISymbolicExpressionTree)filtered[i].Variables["SymbolicExpressionTree"].Value;
+            var tNodes = QueryMatch.InitializePostOrder(t.Root.GetSubtree(0).GetSubtree(0));
+            if (qm.Match(tNodes, sNodes)) {
+              matching[i] = true;
+            }
+          });
+
+        for (int i = 0; i < matching.Length; ++i) {
+          if (matching[i])
+            matchingIndividuals.Add(filtered[i]);
+        }
+      } 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)
+            break;
+
+          var ind = filtered[i];
+          var t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value;
+          var tNodes = QueryMatch.InitializePostOrder(t.Root.GetSubtree(0).GetSubtree(0));
+          if (qm.Match(tNodes, sNodes))
+            matchingIndividuals.Add(ind);
+        }
+      }
+
+      if (matchingIndividuals.Count < countThreshold) {
+        ChangedTreesParameter.ActualValue = new IntValue(0);
+        return base.Apply();
+      }
+
+      var similarity = CalculatePhenotypicSimilarity(matchingIndividuals, calculator, executeInParallel, maxDegreeOfParallelism);
       if (similarity < MinimumPhenotypicSimilarity.Value) {
         ChangedTreesParameter.ActualValue = new IntValue(0);
@@ -201 +234 @@
       }
 
-      var oc = new OperationCollection();
       int n = (int)Math.Floor(matchingIndividuals.Count * ReplacementRatio.Value);
       var individualsToReplace = RandomReplacement.Value ? matchingIndividuals.SampleRandomWithoutRepetition(random, n).ToList()
                                                          : matchingIndividuals.OrderBy(x => (DoubleValue)x.Variables["Quality"].Value).Take(n).ToList();
+      var mutationOc = new OperationCollection { Parallel = false }; // cannot be parallel due to the before/after operators which insert vertices in the genealogy graph
+      var updateEstimatedValues = new OperationCollection { Parallel = true }; // evaluation should be done in parallel when possible
       foreach (var ind in individualsToReplace) {
         var mutatorOp = ExecutionContext.CreateChildOperation(mutator, ind);
-        var evaluatorOp = ExecutionContext.CreateChildOperation(evaluator, ind);
-        var updateEstimatedValuesOp = ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, ind);
-        oc.Add(mutatorOp);
-        oc.Add(evaluatorOp);
-        oc.Add(updateEstimatedValuesOp);
+        var updateOp = ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, ind);
+        mutationOc.Add(mutatorOp);
+        updateEstimatedValues.Add(updateOp);
       }
       ChangedTreesParameter.ActualValue = new IntValue(individualsToReplace.Count);
-      return new OperationCollection(oc, base.Apply());
+      return new OperationCollection(mutationOc, updateEstimatedValues, base.Apply());
+    }
+
+    private static double CalculatePhenotypicSimilarity(ScopeList individuals, SymbolicExpressionTreePhenotypicSimilarityCalculator calculator, bool parallel = false, int nThreads = -1) {
+      double similarity = 0;
+      int count = individuals.Count;
+      if (parallel) {
+        var parallelOptions = new ParallelOptions { MaxDegreeOfParallelism = nThreads };
+        var simArray = new double[count - 1];
+        Parallel.For(0, count - 1, parallelOptions, i => {
+          double innerSim = 0;
+          for (int j = i + 1; j < count; ++j) {
+            innerSim += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
+          }
+          simArray[i] = innerSim;
+        });
+        similarity = simArray.Sum();
+      } else {
+        for (int i = 0; i < count - 1; ++i) {
+          for (int j = i + 1; j < count; ++j) {
+            similarity += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
+          }
+        }
+      }
+      return similarity / (count * (count - 1) / 2.0);
     }
   }