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

Timestamp:

12/17/15 20:13:57 (8 years ago)

Author:

bburlacu

Message:

#1772: Schema diversification strategy: implement adaptive replacement ratio and added number of evaluated solutions per generation to the diversification statistics operator

File:

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

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

@@ -35 +35 @@
   [StorableClass]
   public class SchemaCreator : EvolutionTrackingOperator<ISymbolicExpressionTree> {
+    #region parameter names
     private const string MinimumSchemaLengthParameterName = "MinimumSchemaLength";
     private const string MinimumSchemaFrequencyParameterName = "MinimumSchemaFrequency";
@@ -48 +49 @@
     private const string NumberOfSchemasParameterName = "NumberOfSchemas";
     private const string AverageSchemaLengthParameterName = "AverageSchemaLength";
+    private const string UseAdaptiveReplacementRatioParameterName = "UseAdaptiveReplacementRatio";
+    private const string ReplacementRatioUpdateRuleParameterName = "ReplacementRatioUpdateRule";
+    #endregion
 
     #region parameters
+
+    public IConstrainedValueParameter<StringValue> ReplacementRatioUpdateRuleParameter {
+      get { return (IConstrainedValueParameter<StringValue>)Parameters[ReplacementRatioUpdateRuleParameterName]; }
+    }
+    public IFixedValueParameter<BoolValue> UseAdaptiveReplacementRatioParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters[UseAdaptiveReplacementRatioParameterName]; }
+    }
     public IFixedValueParameter<BoolValue> ExclusiveMatchingParameter {
       get { return (IFixedValueParameter<BoolValue>)Parameters[ExclusiveMatchingParameterName]; }
@@ -99 +110 @@
 
     public SchemaCreator() {
+      #region add parameters
       Parameters.Add(new FixedValueParameter<IntValue>(MinimumSchemaLengthParameterName, new IntValue(10)));
       Parameters.Add(new FixedValueParameter<PercentValue>(MinimumSchemaFrequencyParameterName, new PercentValue(0.01)));
@@ -112 +124 @@
       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)));
+
+      var replacementRatioUpdateRules = new ItemSet<StringValue>(new[] { new StringValue("f(x) = x"), new StringValue("f(x) = tanh(x)"), new StringValue("f(x) = tanh(2x)"), new StringValue("f(x) = tanh(3x)") });
+      Parameters.Add(new ConstrainedValueParameter<StringValue>(ReplacementRatioUpdateRuleParameterName, replacementRatioUpdateRules));
+      #endregion
       NumberOfChangedTreesParameter.Hidden = true;
       NumberOfSchemasParameter.Hidden = true;
@@ -138 +154 @@
       var n = (int)Math.Round(ExecutionContext.Scope.SubScopes.Count * PercentageOfPopulation);
       var scopes = new ScopeList(ExecutionContext.Scope.SubScopes.Take(n));
+
+      var updateEstimatedValues = new OperationCollection { Parallel = true };
+      if (updateEstimatedValuesOperator == null)
+        updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
+
+      foreach (var s in scopes) {
+        if (!s.Variables.ContainsKey("EstimatedValues"))
+          s.Variables.Add(new Core.Variable("EstimatedValues"));
+        updateEstimatedValues.Add(ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, s));
+      }
+
+      Func<double, double> rule;
+      var replacementRule = ReplacementRatioUpdateRuleParameter.Value.Value;
+
+      switch (replacementRule) {
+        case "f(x) = x": {
+            rule = x => x;
+            break;
+          }
+        case "f(x) = tanh(x)": {
+            rule = x => Math.Tanh(x);
+            break;
+          }
+        case "f(x) = tanh(2x)": {
+            rule = x => Math.Tanh(2 * x);
+            break;
+          }
+        case "f(x) = tanh(3x)": {
+            rule = x => Math.Tanh(3 * x);
+            break;
+          }
+        default:
+          throw new ArgumentException("Unknown replacement rule");
+      }
+
+      var evaluateSchemas = new OperationCollection();
 
       // for now, only consider crossover offspring
@@ -146 +198 @@
                      select v;
 
+      var schemas = new List<ISymbolicExpressionTree>(GenerateSchemas(vertices, MinimumSchemaLength));
+
+      #region create schemas and add subscopes representing the individuals
+      foreach (var schema in schemas) {
+        evaluateSchemas.Add(ExecutionContext.CreateChildOperation(new SchemaEvaluator { Schema = schema, ReplacementRule = rule }, ExecutionContext.Scope));
+      }
+      #endregion
+
+      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 { updateEstimatedValues, evaluateSchemas, calculateStatistics, base.Apply() };
+    }
+
+    public static IEnumerable<ISymbolicExpressionTree> GenerateSchemas(IEnumerable<IGenealogyGraphNode<ISymbolicExpressionTree>> vertices, int minimumSchemaLength) {
+      var anySubtreeSymbol = new AnySubtreeSymbol();
+      //      var anyNodeSymbol = new AnyNodeSymbol();
       var groups = vertices.GroupBy(x => x.Parents.First()).OrderByDescending(g => g.Count()).ToList();
-      var anySubtreeSymbol = new AnySubtreeSymbol();
-
-      var updateEstimatedValues = new OperationCollection { Parallel = true };
-      if (updateEstimatedValuesOperator == null)
-        updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
-
-      foreach (var s in scopes) {
-        if (!s.Variables.ContainsKey("EstimatedValues"))
-          s.Variables.Add(new Core.Variable("EstimatedValues"));
-        updateEstimatedValues.Add(ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, s));
-      }
-
-      var evaluateSchemas = new OperationCollection();
-      var schemas = new List<ISymbolicExpressionTree>();
-      var wildCardCounts = new List<double>();
-      #region create schemas and add subscopes representing the individuals
+      var hash = new HashSet<string>();
+      var formatter = new SymbolicExpressionTreeStringFormatter { Indent = false, AppendNewLines = false };
       foreach (var g in groups) {
         var parent = g.Key;
-        if (parent.Data.Length < MinimumSchemaLength)
+        if (parent.Data.Length < minimumSchemaLength)
           continue;
         bool replaced = false;
@@ -171 +234 @@
         var nodes = schema.IterateNodesPrefix().ToList();
         var arcs = g.Select(x => x.InArcs.Last()).Where(x => x.Data != null);
-        var indices = arcs.Select(x => ((IFragment<ISymbolicExpressionTreeNode>)x.Data).Index1).Distinct().ToArray();
+        var indices = (from arc in arcs
+                       let fragment = (IFragment<ISymbolicExpressionTreeNode>)arc.Data
+                       select fragment.Index1).Distinct().ToArray();
         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];
 
           // do not replace the node with a wildcard if it would result in a length < MinimumSchemaLength
-          if ((schema.Length - node.GetLength() + 1) < MinimumSchemaLength)
+          if (schema.Length - node.GetLength() + 1 < minimumSchemaLength)
             continue;
 
-          var replacement = anySubtreeSymbol.CreateTreeNode();
-          ReplaceSubtree(node, replacement, false);
+          //          var replacement = anySubtreeSymbol.CreateTreeNode();
+          //          ReplaceSubtree(node, replacement, false);
+          var replacement = new AnyNodeSymbol(node.Symbol.MinimumArity, node.Symbol.MinimumArity).CreateTreeNode();
+          ReplaceSubtree(node, replacement, true);
           replaced = true;
-          ++w;
         }
         if (replaced) {
-          // store the schemas and the number of wildcards they contain in two lists
-          schemas.Add(schema);
-          wildCardCounts.Add(w);
+          var str = formatter.Format(schema.Root.GetSubtree(0).GetSubtree(0));
+          if (hash.Contains(str)) continue;
+          yield return schema;
+          hash.Add(str);
         }
       }
-
-      for (int i = 0; i < schemas.Count; ++i) {
-        var schema = schemas[i];
-        evaluateSchemas.Add(ExecutionContext.CreateChildOperation(new SchemaEvaluator { Schema = schema }, ExecutionContext.Scope));
-      }
-      #endregion
-
-      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 { updateEstimatedValues, evaluateSchemas, calculateStatistics, base.Apply() };
-    }
-
-    private static void ReplaceSubtree(ISymbolicExpressionTreeNode original, ISymbolicExpressionTreeNode replacement,
-      bool preserveChildren = true) {
+    }
+
+    private static void ReplaceSubtree(ISymbolicExpressionTreeNode original, ISymbolicExpressionTreeNode replacement, bool preserveChildren = true) {
       var parent = original.Parent;
       if (parent == null)