Changeset 15351 for branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking

Timestamp:

09/06/17 20:51:26 (7 years ago)

Author:

bburlacu

Message:

#1772: Merge trunk changes, add a couple of convenience parameters to the SchemaCreator.

Location:

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

Files:

• . (modified) (1 prop)
• 3.4/Tracking/Analyzers/SymbolicDataAnalysisSchemaFrequencyAnalyzer.cs (modified) (1 diff)
• 3.4/Tracking/SchemaDiversification/SchemaCreator.cs (modified) (6 diffs)

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

@@ -185 +185 @@
       }
 
-      var schemas = SchemaCreator.GenerateSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
+      var schemas = SchemaCreator.GenerateCombinedSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
       var schemaStrings = schemas.Select(x => x.Root.GetSubtree(0).GetSubtree(0).FormatToString(StrictSchemaMatching)).ToList();
       int[][] matchingIndices;

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

@@ -52 +52 @@
     private const string ReplacementRatioUpdateRuleParameterName = "ReplacementRatioUpdateRule";
     private const string StrictSchemaMatchingParameterName = "StrictSchemaMatching";
+    private const string SchemaDefinitionParameterName = "SchemaDefinition";
     #endregion
 
     #region parameters
 
+    public IConstrainedValueParameter<StringValue> SchemaDefinitionParameter {
+      get { return (IConstrainedValueParameter<StringValue>)Parameters[SchemaDefinitionParameterName]; }
+    }
     public IConstrainedValueParameter<StringValue> ReplacementRatioUpdateRuleParameter {
       get { return (IConstrainedValueParameter<StringValue>)Parameters[ReplacementRatioUpdateRuleParameterName]; }
@@ -147 +151 @@
         new StringValue("f(x) = 1-sqrt(1-x)")
       });
-      Parameters.Add(new ConstrainedValueParameter<StringValue>(ReplacementRatioUpdateRuleParameterName, replacementRatioUpdateRules));
+      var replacementRatioUpdateRuleParameter = new ConstrainedValueParameter<StringValue>(ReplacementRatioUpdateRuleParameterName, replacementRatioUpdateRules);
+      replacementRatioUpdateRuleParameter.Value = replacementRatioUpdateRules.First();
+      Parameters.Add(replacementRatioUpdateRuleParameter);
+
+      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);
       #endregion
+
       NumberOfChangedTreesParameter.Hidden = true;
       NumberOfSchemasParameter.Hidden = true;
@@ -201 +217 @@
                      select v;
 
-      var schemas = GenerateSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
+      List<ISymbolicExpressionTree> schemas;
+      var def = SchemaDefinitionParameter.Value.Value;
+      switch (def) {
+        case "=":
+          schemas = GenerateAnyNodeSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
+          break;
+        case "#":
+          schemas = GenerateAnySubtreeSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
+          break;
+        case "=,#":
+          schemas = GenerateCombinedSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
+          break;
+        default:
+          return base.Apply();
+      }
+
+      if (!schemas.Any())
+        return base.Apply();
 
       #region create schemas and add subscopes representing the individuals
@@ -223 +256 @@
     }
 
-    public static IEnumerable<ISymbolicExpressionTree> GenerateSchemas(IEnumerable<IGenealogyGraphNode<ISymbolicExpressionTree>> vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
+    #region schema generation
+    public static IEnumerable<ISymbolicExpressionTree> GenerateAnyNodeSchemas(IEnumerable<IGenealogyGraphNode<ISymbolicExpressionTree>> vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
+      var anySubtreeSymbol = new AnySubtreeSymbol();
+      var groups = vertices.GroupBy(x => x.Parents.First()).Where(g => g.Count() >= minOffspringCount).OrderByDescending(g => g.Count());
+      var hash = new HashSet<string>();
+      foreach (var g in groups) {
+        var parent = g.Key;
+        if (parent.Data.Length < minimumSchemaLength)
+          continue;
+        bool replaced = false;
+        var schema = (ISymbolicExpressionTree)parent.Data.Clone();
+        var nodes = schema.IterateNodesPrefix().ToList();
+        var fragments = g.Select(x => x.InArcs.Last().Data).Where(x => x != null).Cast<IFragment<ISymbolicExpressionTreeNode>>();
+        var indices = fragments.Select(x => x.Index1).Distinct().OrderByDescending(x => schema.Root.GetBranchLevel(nodes[x]));
+        foreach (var i in indices) {
+          var node = nodes[i];
+          var anyNodeSymbol = new AnyNodeSymbol(node.Symbol.MinimumArity, node.Symbol.MaximumArity);
+          var replacement = anyNodeSymbol.CreateTreeNode();
+          SchemaUtil.ReplaceSubtree(node, replacement, true);
+          replaced = true;
+        }
+        if (replaced) {
+          var str = schema.Root.GetSubtree(0).GetSubtree(0).FormatToString(strict);
+          if (hash.Add(str))
+            yield return schema;
+        }
+      }
+    }
+
+    public static IEnumerable<ISymbolicExpressionTree> GenerateAnySubtreeSchemas(IEnumerable<IGenealogyGraphNode<ISymbolicExpressionTree>> vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
       var anySubtreeSymbol = new AnySubtreeSymbol();
       var groups = vertices.GroupBy(x => x.Parents.First()).Where(g => g.Count() >= minOffspringCount).OrderByDescending(g => g.Count());
@@ -239 +301 @@
           var node = nodes[i];
           // do not replace the node with a wildcard if it would result in a length < MinimumSchemaLength
-          //          if (schema.Length - node.GetLength() + 1 < minimumSchemaLength)
-          //            continue;
-          ISymbolicExpressionTreeNode replacement;
-          if (node.SubtreeCount > 0) {
-            var anyNodeSymbol = new AnyNodeSymbol(node.Symbol.MinimumArity, node.Symbol.MaximumArity);
-            replacement = anyNodeSymbol.CreateTreeNode();
-          } else {
-            replacement = anySubtreeSymbol.CreateTreeNode();
-          }
-          SchemaUtil.ReplaceSubtree(node, replacement, true);
-          //          var replacement = anySubtreeSymbol.CreateTreeNode();
-          //          var replacement = new AnyNodeSymbol(node.Symbol.MinimumArity, node.Symbol.MinimumArity).CreateTreeNode();
-          //          ReplaceSubtree(node, replacement, true);
-          //          SchemaUtil.ReplaceSubtree(node, replacement, false);
+          if (schema.Length - node.GetLength() + 1 < minimumSchemaLength)
+            continue;
+          var replacement = anySubtreeSymbol.CreateTreeNode();
+          SchemaUtil.ReplaceSubtree(node, replacement, false);
           replaced = true;
         }
@@ -262 +314 @@
       }
     }
+
+    public static IEnumerable<ISymbolicExpressionTree> GenerateCombinedSchemas(IEnumerable<IGenealogyGraphNode<ISymbolicExpressionTree>> vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
+      var anySubtreeSymbol = new AnySubtreeSymbol();
+      var groups = vertices.GroupBy(x => x.Parents.First()).Where(g => g.Count() >= minOffspringCount).OrderByDescending(g => g.Count());
+      var hash = new HashSet<string>();
+      foreach (var g in groups) {
+        var parent = g.Key;
+        if (parent.Data.Length < minimumSchemaLength)
+          continue;
+        bool replaced = false;
+        var schema = (ISymbolicExpressionTree)parent.Data.Clone();
+        var nodes = schema.IterateNodesPrefix().ToList();
+        var fragments = g.Select(x => x.InArcs.Last().Data).Where(x => x != null).Cast<IFragment<ISymbolicExpressionTreeNode>>();
+        var indices = fragments.Select(x => x.Index1).Distinct().OrderByDescending(x => schema.Root.GetBranchLevel(nodes[x]));
+        foreach (var i in indices) {
+          var node = nodes[i];
+          ISymbolicExpressionTreeNode replacement;
+          if (node.SubtreeCount > 0) {
+            replacement = new AnyNodeSymbol(node.Symbol.MinimumArity, node.Symbol.MaximumArity).CreateTreeNode();
+            SchemaUtil.ReplaceSubtree(node, replacement, true);
+          } else {
+            replacement = anySubtreeSymbol.CreateTreeNode();
+            SchemaUtil.ReplaceSubtree(node, replacement, false);
+          }
+          replaced = true;
+        }
+        if (replaced) {
+          var str = schema.Root.GetSubtree(0).GetSubtree(0).FormatToString(strict);
+          if (hash.Add(str))
+            yield return schema;
+        }
+      }
+    }
+    #endregion
   }
 }