Changeset 15906 for branches/HeuristicLab.EvolutionTracking

Timestamp:

04/16/18 08:35:59 (6 years ago)

Author:

bburlacu

Message:

#1772: Refactoring and speed optimization of diversification operators

Location:

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking

Files:

• Analyzers/SymbolicDataAnalysisSchemaFrequencyAnalyzer.cs (modified) (5 diffs)
• SchemaDiversification/SchemaCreator.cs (modified) (16 diffs)
• SchemaDiversification/SchemaEvaluator.cs (modified) (15 diffs)
• SchemaDiversification/UpdateQualityOperator.cs (modified) (6 diffs)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/Analyzers/SymbolicDataAnalysisSchemaFrequencyAnalyzer.cs

@@ -43 +43 @@
     private const string ExecuteInParallelParameterName = "ExecuteInParallel";
     private const string MaximumDegreeOfParallelismParameterName = "MaximumDegreeOfParallelism";
+    private const string SchemaDefinitionParameterName = "SchemaDefinition";
 
     private static readonly Dictionary<string, string> ShortNames = new Dictionary<string, string> {
-    { "Addition", "+" },
-    { "Subtraction", "-" },
-    { "Multiplication", "*" },
-    { "Division", "/" },
-    { "Exponential", "exp" },
-    { "Logarithm", "log" }
-  };
+      { "Addition", "+" },
+      { "Subtraction", "-" },
+      { "Multiplication", "*" },
+      { "Division", "/" },
+      { "Exponential", "exp" },
+      { "Logarithm", "log" }
+    };
 
     [Storable]
@@ -63 +64 @@
     private QueryMatch qm;
 
+
+    public IConstrainedValueParameter<StringValue> SchemaDefinitionParameter {
+      get { return (IConstrainedValueParameter<StringValue>)Parameters[SchemaDefinitionParameterName]; }
+    }
     public IFixedValueParameter<BoolValue> ExecuteInParallelParameter {
       get { return (IFixedValueParameter<BoolValue>)Parameters[ExecuteInParallelParameterName]; }
@@ -122 +127 @@
       Parameters.Add(new LookupParameter<IRegressionProblemData>(ProblemDataParameterName));
       Parameters.Add(new LookupParameter<ISymbolicDataAnalysisExpressionTreeInterpreter>(InterpreterParameterName));
+
+      var schemaDefinitions = new ItemSet<StringValue>(new[] {
+         new StringValue("="),
+         new StringValue("#"),
+         new StringValue("=,#")
+      });
+      var schemaDefinitionParameter = new ConstrainedValueParameter<StringValue>(SchemaDefinitionParameterName, schemaDefinitions);
+      schemaDefinitionParameter.Value = schemaDefinitions.First();
+      Parameters.Add(schemaDefinitionParameter);
     }
 
@@ -185 +199 @@
       }
 
-      var schemas = SchemaCreator.GenerateCombinedSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
+      List<ISymbolicExpressionTree> schemas;
+      var def = SchemaDefinitionParameter.Value.Value;
+      switch (def) {
+        case "=":
+          schemas = SchemaCreator.GenerateAnyNodeSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
+          break;
+        case "#":
+          schemas = SchemaCreator.GenerateAnySubtreeSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
+          break;
+        case "=,#":
+          schemas = SchemaCreator.GenerateCombinedSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
+          break;
+        default:
+          return base.Apply();
+      }
       var schemaStrings = schemas.Select(x => x.Root.GetSubtree(0).GetSubtree(0).FormatToString(StrictSchemaMatching)).ToList();
-      int[][] matchingIndices;
+      int[][] matchingIndices = new int[schemas.Count][];
+
+      var tNodes = trees.Select(x => QueryMatch.InitializePostOrder(x.Root.GetSubtree(0).GetSubtree(0))).ToList();
       if (ExecuteInParallel) {
-        matchingIndices = new int[schemas.Count][];
         Parallel.For(0, schemas.Count, new ParallelOptions { MaxDegreeOfParallelism = MaximumDegreeOfParallelism }, i => {
           var schema = schemas[i];
-          matchingIndices[i] = Enumerable.Range(0, trees.Count).Where(v => qm.Match(trees[v], schema)).ToArray();
+          var sNodes = QueryMatch.InitializePostOrder(schema.Root.GetSubtree(0).GetSubtree(0));
+          matchingIndices[i] = Enumerable.Range(0, trees.Count).Where(idx => qm.Match(tNodes[idx], sNodes)).ToArray();
         });
       } else {
-        matchingIndices = schemas.Select(x => Enumerable.Range(0, trees.Count).Where(v => qm.Match(trees[v], x)).ToArray()).ToArray();
+        for (int i = 0; i < schemas.Count; ++i) {
+          var schema = schemas[i];
+          var sNodes = QueryMatch.InitializePostOrder(schema.Root.GetSubtree(0).GetSubtree(0));
+          matchingIndices[i] = Enumerable.Range(0, trees.Count).Where(idx => qm.Match(tNodes[idx], sNodes)).ToArray();
+        }
       }
 
@@ -203 +237 @@
       if (ExecuteInParallel) {
         var locker = new object();
-        Parallel.For(0, schemas.Count, new ParallelOptions { MaxDegreeOfParallelism = MaximumDegreeOfParallelism }, i => {
+        Parallel.For(0, schemas.Count, new ParallelOptions {
+          MaxDegreeOfParallelism = MaximumDegreeOfParallelism
+        }, i => {
           var indices = matchingIndices[i];
           if (indices.Length > 1) {

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

@@ -39 +39 @@
   public class SchemaCreator : EvolutionTrackingOperator<ISymbolicExpressionTree> {
     #region parameter names
+    // criteria to trigger schema-based diversification
     private const string MinimumSchemaLengthParameterName = "MinimumSchemaLength";
     private const string MinimumSchemaFrequencyParameterName = "MinimumSchemaFrequency";
     private const string MinimumPhenotypicSimilarityParameterName = "MinimumPhenotypicSimilarity";
-    private const string ReplacementRatioParameterName = "ReplacementRatio";
-    private const string RandomReplacementParameterName = "RandomReplacement";
+    // parameters controlling the diversification strategy
+    private const string UseAdaptiveMutationRateParameterName = "UseAdaptiveMutationRate"; // dynamically control mutation rate
+    private const string MutationRateUpdateRuleParameterName = "ReplacementRatioUpdateRule";
+    private const string MutationRateParameterName = "MutationRate"; // fixed mutation rate when not using adaptive update
+    private const string ExclusiveMatchingParameterName = "ExclusiveMatching"; // an individual can belong to only 1 schema 
+    private const string ParentsRatio = "ParentsRatio"; // use best % parents to generate schemas from
+    private const string StrictSchemaMatchingParameterName = "StrictSchemaMatching"; // use strict node comparison (for constant values and variable weights)
+    private const string SchemaDefinitionParameterName = "SchemaDefinition"; // which schema definition to use: {=}, {#} or {=,#}
+    private const string SchemaManipulatorParameterName = "SchemaManipulator"; // mutation operator to apply within schemas
+
+    // control parallel behaviour
     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 UpdateCounterParameterName = "UpdateCounter";
+    private const string UpdateIntervalParameterName = "UpdateInterval";
+
+    #region information parameters 
     private const string NumberOfChangedTreesParameterName = "NumberOfChangedTrees";
     private const string NumberOfSchemasParameterName = "NumberOfSchemas";
     private const string AverageSchemaLengthParameterName = "AverageSchemaLength";
-    private const string UseAdaptiveReplacementRatioParameterName = "UseAdaptiveReplacementRatio";
-    private const string ReplacementRatioUpdateRuleParameterName = "ReplacementRatioUpdateRule";
-    private const string StrictSchemaMatchingParameterName = "StrictSchemaMatching";
-    private const string SchemaDefinitionParameterName = "SchemaDefinition";
-    private const string SchemaManipulatorParameterName = "SchemaManipulator";
+    #endregion
     #endregion
 
@@ -66 +75 @@
       get { return (IConstrainedValueParameter<StringValue>)Parameters[SchemaDefinitionParameterName]; }
     }
-    public IConstrainedValueParameter<StringValue> ReplacementRatioUpdateRuleParameter {
-      get { return (IConstrainedValueParameter<StringValue>)Parameters[ReplacementRatioUpdateRuleParameterName]; }
-    }
-    public IFixedValueParameter<BoolValue> UseAdaptiveReplacementRatioParameter {
-      get { return (IFixedValueParameter<BoolValue>)Parameters[UseAdaptiveReplacementRatioParameterName]; }
+    public IConstrainedValueParameter<StringValue> MutationRateUpdateRuleParameter {
+      get { return (IConstrainedValueParameter<StringValue>)Parameters[MutationRateUpdateRuleParameterName]; }
+    }
+    public IFixedValueParameter<BoolValue> UseAdaptiveMutationRateParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters[UseAdaptiveMutationRateParameterName]; }
     }
     public IFixedValueParameter<BoolValue> StrictSchemaMatchingParameter {
@@ -81 +90 @@
       get { return (IFixedValueParameter<BoolValue>)Parameters[ScaleEstimatedValuesParameterName]; }
     }
-    public IFixedValueParameter<PercentValue> PercentageOfPopulationParameter {
-      get { return (IFixedValueParameter<PercentValue>)Parameters[PercentageOfPopulationParameterName]; }
+    public IFixedValueParameter<PercentValue> ParentsRatioParameter {
+      get { return (IFixedValueParameter<PercentValue>)Parameters[ParentsRatio]; }
     }
     public IFixedValueParameter<IntValue> MinimumSchemaLengthParameter {
@@ -99 +108 @@
       get { return (IFixedValueParameter<PercentValue>)Parameters[MinimumPhenotypicSimilarityParameterName]; }
     }
-    public IFixedValueParameter<PercentValue> ReplacementRatioParameter {
-      get { return (IFixedValueParameter<PercentValue>)Parameters[ReplacementRatioParameterName]; }
+    public IFixedValueParameter<PercentValue> MutationRateParameter {
+      get { return (IFixedValueParameter<PercentValue>)Parameters[MutationRateParameterName]; }
     }
     public IValueParameter<IntValue> NumberOfSchemasParameter {
@@ -110 +119 @@
     public IValueParameter<IntValue> NumberOfChangedTreesParameter {
       get { return (IValueParameter<IntValue>)Parameters[NumberOfChangedTreesParameterName]; }
+    }
+    public IFixedValueParameter<IntValue> UpdateCounterParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[UpdateCounterParameterName]; }
+    }
+    public IFixedValueParameter<IntValue> UpdateIntervalParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[UpdateIntervalParameterName]; }
     }
     #endregion
@@ -117 +132 @@
     public int MaxDegreeOfParallelism { get { return MaxDegreeOfParallelismParameter.Value.Value; } }
     public bool ExecuteInParallel { get { return ExecuteInParallelParameter.Value.Value; } }
-    public double PercentageOfPopulation { get { return PercentageOfPopulationParameter.Value.Value; } }
+    public double PercentageOfPopulation { get { return ParentsRatioParameter.Value.Value; } }
     public bool StrictSchemaMatching { get { return StrictSchemaMatchingParameter.Value.Value; } }
+    public IntValue UpdateCounter { get { return UpdateCounterParameter.Value; } }
+    public IntValue UpdateInterval { get { return UpdateIntervalParameter.Value; } }
+
     #endregion
 
     private UpdateQualityOperator updateQualityOperator;
     private DiversificationStatisticsOperator diversificationStatisticsOperator;
+
+    public override void InitializeState() {
+      base.InitializeState();
+      NumberOfChangedTreesParameter.Value.Value = 0;
+      NumberOfChangedTreesParameter.Value.Value = 0;
+      AverageSchemaLengthParameter.Value.Value = 0;
+      UpdateCounter.Value = 0;
+    }
 
     public override void ClearState() {
@@ -128 +154 @@
       NumberOfChangedTreesParameter.Value.Value = 0;
       AverageSchemaLengthParameter.Value.Value = 0;
+      UpdateCounter.Value = 0;
       base.ClearState();
     }
@@ -136 +163 @@
       Parameters.Add(new FixedValueParameter<PercentValue>(MinimumSchemaFrequencyParameterName, new PercentValue(0.01)));
       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<PercentValue>(MutationRateParameterName, new PercentValue(0.9)));
+      Parameters.Add(new FixedValueParameter<PercentValue>(ParentsRatio, new PercentValue(1)));
       Parameters.Add(new FixedValueParameter<BoolValue>(ExecuteInParallelParameterName, new BoolValue(false)));
       Parameters.Add(new FixedValueParameter<IntValue>(MaxDegreeOfParalellismParameterName, new IntValue(-1)));
@@ -147 +173 @@
       Parameters.Add(new ValueParameter<IntValue>(NumberOfSchemasParameterName, new IntValue(0)));
       Parameters.Add(new ValueParameter<DoubleValue>(AverageSchemaLengthParameterName, new DoubleValue(0)));
-      Parameters.Add(new FixedValueParameter<BoolValue>(UseAdaptiveReplacementRatioParameterName, new BoolValue(true)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(UseAdaptiveMutationRateParameterName, new BoolValue(true)));
+      Parameters.Add(new FixedValueParameter<IntValue>(UpdateCounterParameterName, new IntValue(0)));
+      Parameters.Add(new FixedValueParameter<IntValue>(UpdateIntervalParameterName, new IntValue(1)));
 
       // add update rules
-      var replacementRatioUpdateRules = new ItemSet<StringValue>(new[] {
+      var mutationRateUpdateRules = new ItemSet<StringValue>(new[] {
         new StringValue("f(x) = x"),
         new StringValue("f(x) = tanh(x)"),
@@ -158 +186 @@
         new StringValue("f(x) = 1-sqrt(1-x)")
       });
-      var replacementRatioUpdateRuleParameter = new ConstrainedValueParameter<StringValue>(ReplacementRatioUpdateRuleParameterName, replacementRatioUpdateRules);
-      replacementRatioUpdateRuleParameter.Value = replacementRatioUpdateRules.First();
-      Parameters.Add(replacementRatioUpdateRuleParameter);
+      var mutationRateUpdateRuleParameter = new ConstrainedValueParameter<StringValue>(MutationRateUpdateRuleParameterName, mutationRateUpdateRules);
+      mutationRateUpdateRuleParameter.Value = mutationRateUpdateRules.First();
+      Parameters.Add(mutationRateUpdateRuleParameter);
 
       // add schema definitions
@@ -208 +236 @@
 
     public override IOperation Apply() {
+      UpdateCounter.Value++;
+      if (UpdateCounter.Value != UpdateInterval.Value)
+        return base.Apply();
+      UpdateCounter.Value = 0;
+
       // apply only when at least one generation has passed
       var gen = Generations.Value;
@@ -213 +246 @@
         return base.Apply();
 
-      var n = (int)Math.Round(ExecutionContext.Scope.SubScopes.Count * PercentageOfPopulation);
 
       var updateEstimatedValues = new OperationCollection { Parallel = true };
@@ -219 +251 @@
         updateQualityOperator = new UpdateQualityOperator();
 
-      foreach (var s in ExecutionContext.Scope.SubScopes.Where(s => !s.Variables.ContainsKey("EstimatedValues"))) {
+      var scope = ExecutionContext.Scope;
+
+      foreach (var s in scope.SubScopes.Where(s => !s.Variables.ContainsKey("EstimatedValues"))) {
         updateEstimatedValues.Add(ExecutionContext.CreateChildOperation(updateQualityOperator, s));
       }
 
-      var replacementRule = ReplacementRatioUpdateRuleParameter.Value.Value;
+      var updateRule = MutationRateUpdateRuleParameter.Value.Value;
       var schemaManipulator = SchemaManipulatorParameter.Value;
 
       var evaluateSchemas = new OperationCollection();
 
+      Func<IScope, double> getQuality = s => ((DoubleValue)s.Variables["Quality"].Value).Value;
+
+      var bestN = (int)Math.Round(scope.SubScopes.Count * PercentageOfPopulation);
+      var scopes = new ScopeList(scope.SubScopes.OrderByDescending(getQuality).Take(bestN));
       // for now, only consider crossover offspring
-      var scopes = new ScopeList(ExecutionContext.Scope.SubScopes.OrderByDescending(x => ((DoubleValue)x.Variables["Quality"].Value).Value).Take(n));
       var vertices = from s in scopes
                      let t = (ISymbolicExpressionTree)s.Variables["SymbolicExpressionTree"].Value
@@ -236 +273 @@
                      select v;
 
-      List<ISymbolicExpressionTree> schemas;
+      IEnumerable<ISymbolicExpressionTree> schemas;
       switch (SchemaDefinitionParameter.Value.Value) {
         case "=":
-          schemas = GenerateAnyNodeSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
+          schemas = GenerateAnyNodeSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching);
           break;
         case "#":
-          schemas = GenerateAnySubtreeSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
+          schemas = GenerateAnySubtreeSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching);
           break;
         case "=,#":
-          schemas = GenerateCombinedSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
+          schemas = GenerateCombinedSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching);
           break;
         default:
@@ -255 +292 @@
 
       #region create schemas and add subscopes representing the individuals
+      double avgLength = 0;
+      int count = 0;
       foreach (var schema in schemas) {
-        evaluateSchemas.Add(ExecutionContext.CreateChildOperation(new SchemaEvaluator { Schema = schema, ReplacementRule = replacementRule, SchemaManipulator = schemaManipulator }, ExecutionContext.Scope));
+        avgLength += schema.Length;
+        ++count;
+        evaluateSchemas.Add(ExecutionContext.CreateChildOperation(new SchemaEvaluator { Schema = schema, MutationRateUpdateRule = updateRule, SchemaManipulator = schemaManipulator }, scope));
       }
+      avgLength /= count;
       #endregion
+
+      // set parameters for statistics
+      AverageSchemaLengthParameter.Value = new DoubleValue(avgLength);
+      NumberOfSchemasParameter.Value = new IntValue(count);
+      NumberOfChangedTreesParameter.Value = new IntValue(0);
 
       if (diversificationStatisticsOperator == null)
@@ -264 +311 @@
 
       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()

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

@@ -21 +21 @@
 
 using System;
+using System.Collections.Concurrent;
 using System.Collections.Generic;
 using System.Linq;
@@ -41 +42 @@
     private const string MinimumSchemaFrequencyParameterName = "MinimumSchemaFrequency";
     private const string MinimumPhenotypicSimilarityParameterName = "MinimumPhenotypicSimilarity";
-    private const string ReplacementRatioParameterName = "ReplacementRatio";
+    private const string MutationRateParameterName = "MutationRate";
     private const string SchemaParameterName = "Schema";
     private const string PopulationSizeParameterName = "PopulationSize";
@@ -52 +53 @@
     private const string MutatorParameterName = "Mutator";
     private const string CrossoverParameterName = "Crossover";
-    private const string RandomReplacementParameterName = "RandomReplacement";
     private const string NumberOfChangedTreesParameterName = "NumberOfChangedTrees";
     private const string ExecuteInParallelParameterName = "ExecuteInParallel";
     private const string MaxDegreeOfParalellismParameterName = "MaxDegreeOfParallelism";
     private const string ExclusiveMatchingParameterName = "ExclusiveMatching";
-    private const string UseAdaptiveReplacementRatioParameterName = "UseAdaptiveReplacementRatio";
+    private const string UseAdaptiveMutationRateParameterName = "UseAdaptiveMutationRate";
     private const string StrictSchemaMatchingParameterName = "StrictSchemaMatching";
     #endregion
 
     #region parameters
-    public ILookupParameter<BoolValue> UseAdaptiveReplacementRatioParameter {
-      get { return (ILookupParameter<BoolValue>)Parameters[UseAdaptiveReplacementRatioParameterName]; }
+    public ILookupParameter<BoolValue> UseAdaptiveMutationRateParameter {
+      get { return (ILookupParameter<BoolValue>)Parameters[UseAdaptiveMutationRateParameterName]; }
     }
     public ILookupParameter<BoolValue> ExclusiveMatchingParameter {
@@ -89 +89 @@
       get { return (ILookupParameter<BoolValue>)Parameters[ApplyLinearScalingParameterName]; }
     }
-    public ILookupParameter<BoolValue> RandomReplacementParameter {
-      get { return (ILookupParameter<BoolValue>)Parameters[RandomReplacementParameterName]; }
-    }
     public ILookupParameter<ISymbolicExpressionTreeCrossover> CrossoverParameter {
       get { return (ILookupParameter<ISymbolicExpressionTreeCrossover>)Parameters[CrossoverParameterName]; }
@@ -107 +104 @@
       get { return (ILookupParameter<PercentValue>)Parameters[MinimumSchemaFrequencyParameterName]; }
     }
-    public ILookupParameter<PercentValue> ReplacementRatioParameter {
-      get { return (ILookupParameter<PercentValue>)Parameters[ReplacementRatioParameterName]; }
+    public ILookupParameter<PercentValue> MutationRateParameter {
+      get { return (ILookupParameter<PercentValue>)Parameters[MutationRateParameterName]; }
     }
     public ILookupParameter<PercentValue> MinimumPhenotypicSimilarityParameter {
@@ -123 +120 @@
     #region parameter properties
     public PercentValue MinimumSchemaFrequency { get { return MinimumSchemaFrequencyParameter.ActualValue; } }
-    public PercentValue ReplacementRatio { get { return ReplacementRatioParameter.ActualValue; } }
+    public PercentValue MutationRate { get { return MutationRateParameter.ActualValue; } }
     public PercentValue MinimumPhenotypicSimilarity { get { return MinimumPhenotypicSimilarityParameter.ActualValue; } }
-    public BoolValue RandomReplacement { get { return RandomReplacementParameter.ActualValue; } }
     public IntValue NumberOfChangedTrees { get { return NumberOfChangedTreesParameter.ActualValue; } }
     #endregion
@@ -135 +131 @@
 
     [Storable]
-    public string ReplacementRule { get; set; }
+    public string MutationRateUpdateRule { get; set; }
 
     [Storable]
@@ -171 +167 @@
       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(SchemaParameterName, "The current schema to be evaluated"));
       Parameters.Add(new LookupParameter<PercentValue>(MinimumSchemaFrequencyParameterName));
-      Parameters.Add(new LookupParameter<PercentValue>(ReplacementRatioParameterName));
+      Parameters.Add(new LookupParameter<PercentValue>(MutationRateParameterName));
       Parameters.Add(new LookupParameter<PercentValue>(MinimumPhenotypicSimilarityParameterName));
       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(PopulationSizeParameterName));
@@ -183 +179 @@
       Parameters.Add(new LookupParameter<ISymbolicExpressionTreeManipulator>(MutatorParameterName));
       Parameters.Add(new LookupParameter<ISymbolicExpressionTreeCrossover>(CrossoverParameterName));
-      Parameters.Add(new LookupParameter<BoolValue>(RandomReplacementParameterName));
       Parameters.Add(new LookupParameter<IntValue>(NumberOfChangedTreesParameterName));
       Parameters.Add(new LookupParameter<BoolValue>(ExecuteInParallelParameterName));
       Parameters.Add(new LookupParameter<IntValue>(MaxDegreeOfParalellismParameterName));
       Parameters.Add(new LookupParameter<BoolValue>(ExclusiveMatchingParameterName));
-      Parameters.Add(new LookupParameter<BoolValue>(UseAdaptiveReplacementRatioParameterName));
+      Parameters.Add(new LookupParameter<BoolValue>(UseAdaptiveMutationRateParameterName));
       #endregion
     }
@@ -218 +213 @@
 
       var individuals = ExecutionContext.Scope.SubScopes; // the scopes represent the individuals
-      var trees = individuals.Select(x => (ISymbolicExpressionTree)x.Variables["SymbolicExpressionTree"].Value).ToList();
+      var trees = new ISymbolicExpressionTree[individuals.Count];
+      var qualities = new double[individuals.Count];
+
+      for (int i = 0; i < individuals.Count; ++i) {
+        trees[i] = (ISymbolicExpressionTree)individuals[i].Variables["SymbolicExpressionTree"].Value;
+        qualities[i] = ((DoubleValue)individuals[i].Variables["Quality"].Value).Value;
+      }
 
       var random = RandomParameter.ActualValue;
-
-      var s = Schema;
-      var sRoot = s.Root.GetSubtree(0).GetSubtree(0);
-      int countThreshold = (int)Math.Max(2, Math.Round(MinimumSchemaFrequency.Value * individuals.Count));
+      var sRoot = Schema.Root.GetSubtree(0).GetSubtree(0);
 
       // first apply the length and root equality checks in order to filter the individuals
       var exclusiveMatching = ExclusiveMatchingParameter.ActualValue.Value;
       var filtered = new List<int>();
-      for (int i = 0; i < individuals.Count; ++i) {
+
+      for (int i = 0; i < trees.Length; ++i) {
         if (exclusiveMatching && individuals[i].Variables.ContainsKey("AlreadyMatched")) continue;
         var t = trees[i];
         var tRoot = t.Root.GetSubtree(0).GetSubtree(0);
-        if (t.Length < s.Length || !qm.EqualityComparer.Equals(tRoot, sRoot)) continue;
+        if (t.Length < Schema.Length || !qm.EqualityComparer.Equals(tRoot, sRoot)) continue;
         filtered.Add(i);
       }
@@ -239 +238 @@
       // if we don't have enough filtered individuals, then we are done
       // if the schema exceeds the minimum frequency, it gets processed further
+      int countThreshold = (int)Math.Max(2, Math.Round(MinimumSchemaFrequency.Value * individuals.Count));
       if (filtered.Count < countThreshold) {
         return base.Apply();
@@ -244 +244 @@
 
       // check if the filtered individuals match the schema
+      var matching = new List<int>();
       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 index = filtered[i];
-            var t = trees[index];
-            var tNodes = QueryMatch.InitializePostOrder(t.Root.GetSubtree(0).GetSubtree(0));
-            if (qm.Match(tNodes, sNodes)) {
-              matching[i] = true;
-            }
-          });
-
-        matchingIndividuals.AddRange(filtered.Where((x, i) => matching[i]).Select(x => individuals[x]));
+        var partitioner = Partitioner.Create(0, filtered.Count);
+        var po = new ParallelOptions { MaxDegreeOfParallelism = maxDegreeOfParallelism };
+
+        Parallel.ForEach(partitioner, po, (range, loop) => {
+          var partial = new List<int>();
+          for (int i = range.Item1; i < range.Item2; ++i) {
+            var idx = filtered[i];
+            var tRoot = trees[idx].Root.GetSubtree(0).GetSubtree(0);
+            var tNodes = QueryMatch.InitializePostOrder(tRoot);
+
+            if (qm.Match(tNodes, sNodes)) { partial.Add(idx); }
+          }
+          lock (matching) { matching.AddRange(partial); }
+        });
       } 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 index = filtered[i];
           var tRoot = trees[index].Root.GetSubtree(0).GetSubtree(0);
           var tNodes = QueryMatch.InitializePostOrder(tRoot);
-          if (qm.Match(tNodes, sNodes))
-            matchingIndividuals.Add(individuals[index]);
+          if (qm.Match(tNodes, sNodes)) {
+            matching.Add(index);
+          }
         }
       }
-
-      if (matchingIndividuals.Count < countThreshold) {
+      if (matching.Count < countThreshold) {
         return base.Apply();
       }
 
+      matching.Sort((a, b) => qualities[a].CompareTo(qualities[b])); // sort by ascending quality
+      var matchingIndividuals = matching.Select(x => individuals[x]).ToArray(); // fittest individual will be last in the array
       var similarity = CalculateSimilarity(matchingIndividuals, calculator, executeInParallel, maxDegreeOfParallelism);
       if (similarity < MinimumPhenotypicSimilarity.Value) {
@@ -286 +286 @@
       }
 
-      double replacementRatio;
-      var adaptiveReplacementRatio = UseAdaptiveReplacementRatioParameter.ActualValue.Value;
-
-      if (adaptiveReplacementRatio) {
-        var r = (double)matchingIndividuals.Count / individuals.Count;
-        replacementRatio = CalculateReplacementRatio(r);
+      double mutationRate;
+      var useAdaptiveMutationRate = UseAdaptiveMutationRateParameter.ActualValue.Value;
+
+      if (useAdaptiveMutationRate) {
+        var r = (double)matchingIndividuals.Length / individuals.Count;
+        mutationRate = CalculateMutationRate(r);
       } else {
-        replacementRatio = ReplacementRatio.Value;
-      }
-
-      int n = (int)Math.Floor(matchingIndividuals.Count * replacementRatio);
-      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(SchemaManipulator, ind);
-        var updateOp = ExecutionContext.CreateChildOperation(updateQualityOperator, ind);
-        mutationOc.Add(mutatorOp);
-        updateEstimatedValues.Add(updateOp);
+        mutationRate = MutationRate.Value;
+      }
+
+      var mutations = new OperationCollection { Parallel = false }; // cannot be parallel due to the before/after operators which insert vertices in the genealogy graph
+      var updates = new OperationCollection { Parallel = true }; // evaluation should be done in parallel when possible
+
+      // use length - 1 because we don't want to mutate the best individual in each schema group (which could also be the overall elite)
+      for (int i = 0; i < matchingIndividuals.Length - 1; ++i) {
+        if (random.NextDouble() > mutationRate) continue;
+
+        var ind = matchingIndividuals[i];
+
+        var mutate = ExecutionContext.CreateChildOperation(SchemaManipulator, ind);
+        var update = ExecutionContext.CreateChildOperation(updateQualityOperator, ind);
+
+        mutations.Add(mutate);
+        updates.Add(update);
+
         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());
-    }
-
-    private double CalculateReplacementRatio(double r) {
-      switch (ReplacementRule) {
+      NumberOfChangedTrees.Value += mutations.Count;
+
+      return new OperationCollection(mutations, updates, base.Apply());
+    }
+
+    private double CalculateMutationRate(double r) {
+      switch (MutationRateUpdateRule) {
         case "f(x) = x": {
             return r;
@@ -340 +344 @@
     }
 
-    public static double CalculateSimilarity(ScopeList individuals, ISolutionSimilarityCalculator calculator, bool parallel = false, int nThreads = -1) {
+    public static double CalculateSimilarity(IScope[] individuals, ISolutionSimilarityCalculator calculator, bool parallel = false, int nThreads = -1) {
+      if (individuals.Length < 2)
+        return double.NaN;
+
       double similarity = 0;
-      int count = individuals.Count;
-      if (count < 2) return double.NaN;
+      int count = individuals.Length;
+      int n = count * (count - 1) / 2;
+
       if (parallel) {
-        var parallelOptions = new ParallelOptions { MaxDegreeOfParallelism = nThreads };
-        var simArray = new double[count - 1];
-        Parallel.For(0, count - 1, parallelOptions, i => {
-          double innerSim = 0;
+        var ii = new int[n];
+        var jj = new int[n];
+        int k = 0;
+        for (int i = 0; i < count - 1; ++i)
           for (int j = i + 1; j < count; ++j) {
-            innerSim += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
-          }
-          simArray[i] = innerSim;
+            ii[k] = i;
+            jj[k] = j;
+            ++k;
+          }
+        var po = new ParallelOptions { MaxDegreeOfParallelism = nThreads };
+        var partitioner = Partitioner.Create(0, n);
+        var locker = new object();
+        Parallel.ForEach(partitioner, new ParallelOptions { MaxDegreeOfParallelism = 4 }, (range, loop) => {
+          var partial = 0d;
+          for (int idx = range.Item1; idx < range.Item2; ++idx) {
+            int i = ii[idx];
+            int j = jj[idx];
+            partial += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
+          }
+          lock (locker) { similarity += partial; }
         });
-        similarity = simArray.Sum();
       } else {
         for (int i = 0; i < count - 1; ++i) {
@@ -362 +381 @@
         }
       }
-      return similarity / (count * (count - 1) / 2.0);
+      return similarity / n;
     }
   }

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

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -21 +21 @@
 
 using System;
+using System.Collections;
+using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
@@ -40 +42 @@
     private const string ScaleEstimatedValuesParameterName = "ScaleEstimatedValues";
 
+    #region parameters
     public ILookupParameter<IRegressionProblemData> ProblemDataParameter {
       get { return (ILookupParameter<IRegressionProblemData>)Parameters[ProblemDataParameterName]; }
@@ -55 +58 @@
       get { return (ILookupParameter<BoolValue>)Parameters[ScaleEstimatedValuesParameterName]; }
     }
+    #endregion
 
     public UpdateQualityOperator() {
@@ -76 +80 @@
     public override IOperation Apply() {
       var tree = SymbolicExpressionTreeParameter.ActualValue;
-      FixParentLinks(tree);
       var problemData = ProblemDataParameter.ActualValue;
       var estimationLimits = EstimationLimitsParameter.ActualValue;
       var interpreter = InterpreterParameter.ActualValue;
 
-      var estimatedValues = interpreter.GetSymbolicExpressionTreeValues(tree, problemData.Dataset, problemData.TrainingIndices).ToArray();
-      var targetValues = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TrainingIndices).ToArray();
+      var estimatedValues = interpreter.GetSymbolicExpressionTreeValues(tree, problemData.Dataset, problemData.TrainingIndices);
+      var targetValues = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TrainingIndices);
 
-      if (estimatedValues.Length != targetValues.Length)
-        throw new ArgumentException("Number of elements in target and estimated values enumeration do not match.");
+      var scaleEstimatedValues = ScaleEstimatedValuesParameter.ActualValue.Value;
 
-      var linearScalingCalculator = new OnlineLinearScalingParameterCalculator();
+      IEnumerable<double> scaled;
+      if (scaleEstimatedValues) {
+        var linearScalingCalculator = new OnlineLinearScalingParameterCalculator();
 
-      for (int i = 0; i < estimatedValues.Length; ++i) {
-        var estimated = estimatedValues[i];
-        var target = targetValues[i];
-        if (!double.IsNaN(estimated) && !double.IsInfinity(estimated))
-          linearScalingCalculator.Add(estimated, target);
+        var e1 = estimatedValues.GetEnumerator();
+        var e2 = targetValues.GetEnumerator();
+
+        int count = 0;
+        while (e1.MoveNext() && e2.MoveNext()) {
+          var estimated = e1.Current;
+          var target = e2.Current;
+          if (!double.IsNaN(estimated) && !double.IsInfinity(estimated))
+            linearScalingCalculator.Add(estimated, target);
+          ++count;
+        }
+        if (e1.MoveNext() || e2.MoveNext())
+          throw new ArgumentException("Number of elements in target and estimated values enumeration do not match.");
+
+        double alpha = linearScalingCalculator.Alpha;
+        double beta = linearScalingCalculator.Beta;
+        if (linearScalingCalculator.ErrorState != OnlineCalculatorError.None) {
+          alpha = 0.0;
+          beta = 1.0;
+        }
+        scaled = estimatedValues.Select(x => x * beta + alpha).LimitToRange(estimationLimits.Lower, estimationLimits.Upper);
+      } else {
+        scaled = estimatedValues.LimitToRange(estimationLimits.Lower, estimationLimits.Upper);
       }
-      double alpha = linearScalingCalculator.Alpha;
-      double beta = linearScalingCalculator.Beta;
-      if (linearScalingCalculator.ErrorState != OnlineCalculatorError.None) {
-        alpha = 0.0;
-        beta = 1.0;
-      }
-      var scaled = estimatedValues.Select(x => x * beta + alpha).LimitToRange(estimationLimits.Lower, estimationLimits.Upper).ToArray();
+
       OnlineCalculatorError error;
       var r = OnlinePearsonsRCalculator.Calculate(targetValues, scaled, out error);
@@ -111 +127 @@
 
       ((DoubleValue)variables["Quality"].Value).Value = r2;
-      GenealogyGraph.GetByContent(tree).Quality = r2;
-
-      var scaleEstimatedValues = ScaleEstimatedValuesParameter.ActualValue;
-      if (!scaleEstimatedValues.Value)
-        scaled = estimatedValues.LimitToRange(estimationLimits.Lower, estimationLimits.Upper).ToArray();
+      //GenealogyGraph.GetByContent(tree).Quality = r2;
 
       if (variables.ContainsKey("EstimatedValues")) {
-        variables["EstimatedValues"].Value = new DoubleArray(scaled);
+        variables["EstimatedValues"].Value = new DoubleArray(scaled.ToArray());
       } else {
-        variables.Add(new Core.Variable("EstimatedValues", new DoubleArray(scaled)));
+        variables.Add(new Core.Variable("EstimatedValues", new DoubleArray(scaled.ToArray())));
       }
       return base.Apply();
     }
-
-    private static void FixParentLinks(ISymbolicExpressionTree tree) {
-      foreach (var node in tree.IterateNodesPrefix().Where(x => x.SubtreeCount > 0)) {
-        foreach (var s in node.Subtrees) {
-          if (s.Parent != node)
-            s.Parent = node;
-        }
-      }
-    }
   }
 }