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

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)

File:

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

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