Changeset 15482

Timestamp:

11/21/17 16:00:15 (7 years ago)

Author:

bburlacu

Message:

#1772: Add the option to specify a separate mutation operation for schema diversification (independent of the one used in the algorithm main loop). Refactor duplicated code for schema generation in SchemaCreator.cs.

Location:

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

Files:

• SchemaCreator.cs (modified) (10 diffs)
• SchemaEvaluator.cs (modified) (4 diffs)

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

@@ -30 +30 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.PluginInfrastructure;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
+  using Vertices = IEnumerable<IGenealogyGraphNode<ISymbolicExpressionTree>>;
+
   [Item("SchemaCreator", "An operator that builds schemas based on the heredity relationship in the genealogy graph.")]
   [StorableClass]
@@ -53 +56 @@
     private const string StrictSchemaMatchingParameterName = "StrictSchemaMatching";
     private const string SchemaDefinitionParameterName = "SchemaDefinition";
+    private const string SchemaManipulatorParameterName = "SchemaManipulator";
     #endregion
 
     #region parameters
-
+    public IConstrainedValueParameter<ISymbolicExpressionTreeManipulator> SchemaManipulatorParameter {
+      get { return (IConstrainedValueParameter<ISymbolicExpressionTreeManipulator>)Parameters[SchemaManipulatorParameterName]; }
+    }
     public IConstrainedValueParameter<StringValue> SchemaDefinitionParameter {
       get { return (IConstrainedValueParameter<StringValue>)Parameters[SchemaDefinitionParameterName]; }
@@ -143 +149 @@
       Parameters.Add(new FixedValueParameter<BoolValue>(UseAdaptiveReplacementRatioParameterName, new BoolValue(true)));
 
+      // add update rules
       var replacementRatioUpdateRules = new ItemSet<StringValue>(new[] {
         new StringValue("f(x) = x"),
@@ -155 +162 @@
       Parameters.Add(replacementRatioUpdateRuleParameter);
 
-      var schemaDefinitions = new ItemSet<StringValue>(new[] {
-         new StringValue("="),
-         new StringValue("#"),
-         new StringValue("=,#")
-      });
+      // add schema definitions
+      var schemaDefinitions = new ItemSet<StringValue>(new[] { "=", "#", "=,#" }.Select(x => new StringValue(x)));
       var schemaDefinitionParameter = new ConstrainedValueParameter<StringValue>(SchemaDefinitionParameterName, schemaDefinitions);
       schemaDefinitionParameter.Value = schemaDefinitions.First();
       Parameters.Add(schemaDefinitionParameter);
+
+      // use a separate set of manipulators in order to allow the user to specify different mutations for schemas
+      // and not be limited to the manipulator parameter for the whole algorithm
+      var manipulators = ApplicationManager.Manager.GetTypes(typeof(ISymbolicExpressionTreeManipulator))
+                                           .Where(x => !typeof(IMultiOperator<ISymbolicExpressionTreeManipulator>).IsAssignableFrom(x)
+                                                       && !typeof(ISymbolicExpressionTreeArchitectureAlteringOperator).IsAssignableFrom(x))
+                                           .Select(x => (ISymbolicExpressionTreeManipulator)Activator.CreateInstance(x)).ToList();
+      manipulators.Add(new MultiSymbolicExpressionTreeManipulator());
+
+      // add individual manipulators
+      var manipulatorParameter = new ConstrainedValueParameter<ISymbolicExpressionTreeManipulator>(SchemaManipulatorParameterName, new ItemSet<ISymbolicExpressionTreeManipulator>(manipulators));
+      // add a multi manipulator as well
+      manipulatorParameter.Value = manipulators.First();
+      Parameters.Add(manipulatorParameter);
       #endregion
 
@@ -206 +224 @@
 
       var replacementRule = ReplacementRatioUpdateRuleParameter.Value.Value;
+      var schemaManipulator = SchemaManipulatorParameter.Value;
 
       var evaluateSchemas = new OperationCollection();
@@ -218 +237 @@
 
       List<ISymbolicExpressionTree> schemas;
-      var def = SchemaDefinitionParameter.Value.Value;
-      switch (def) {
+      switch (SchemaDefinitionParameter.Value.Value) {
         case "=":
           schemas = GenerateAnyNodeSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
@@ -238 +256 @@
       #region create schemas and add subscopes representing the individuals
       foreach (var schema in schemas) {
-        evaluateSchemas.Add(ExecutionContext.CreateChildOperation(new SchemaEvaluator { Schema = schema, ReplacementRule = replacementRule }, ExecutionContext.Scope));
+        evaluateSchemas.Add(ExecutionContext.CreateChildOperation(new SchemaEvaluator { Schema = schema, ReplacementRule = replacementRule, SchemaManipulator = schemaManipulator }, ExecutionContext.Scope));
       }
       #endregion
@@ -257 +275 @@
 
     #region schema generation
-    public static IEnumerable<ISymbolicExpressionTree> GenerateAnyNodeSchemas(IEnumerable<IGenealogyGraphNode<ISymbolicExpressionTree>> vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
+    public static IEnumerable<ISymbolicExpressionTree> GenerateAnyNodeSchemas(Vertices vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
+      return GenerateSchemas(vertices, ReplaceAnyNode, minimumSchemaLength, minOffspringCount, strict);
+    }
+
+    public static IEnumerable<ISymbolicExpressionTree> GenerateAnySubtreeSchemas(Vertices vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
+      return GenerateSchemas(vertices, ReplaceAnySubtree, minimumSchemaLength, minOffspringCount, strict);
+    }
+
+    public static IEnumerable<ISymbolicExpressionTree> GenerateCombinedSchemas(Vertices vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
+      return GenerateSchemas(vertices, ReplaceCombined, minimumSchemaLength, minOffspringCount, strict);
+    }
+
+    public static IEnumerable<ISymbolicExpressionTree> GenerateSchemas(Vertices vertices, Func<ISymbolicExpressionTree, ISymbolicExpressionTreeNode, int, bool> replaceFunc, int minimumSchemaLength, int minOffspringCount, 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 groups = vertices.GroupBy(x => x.Parents.First()).Where(g => g.Skip(minOffspringCount - 1).Any()).OrderByDescending(g => g.Count());
       var hash = new HashSet<string>();
       foreach (var g in groups) {
@@ -271 +301 @@
         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;
+          replaced |= replaceFunc(schema, nodes[i], minimumSchemaLength);
         }
         if (replaced) {
@@ -285 +311 @@
     }
 
-    public static IEnumerable<ISymbolicExpressionTree> GenerateAnySubtreeSchemas(IEnumerable<IGenealogyGraphNode<ISymbolicExpressionTree>> vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
+    // node replacement rules
+    private static bool ReplaceAnyNode(ISymbolicExpressionTree schema, ISymbolicExpressionTreeNode node, int minSchemaLength) {
+      var anyNodeSymbol = new AnyNodeSymbol(node.Symbol.MinimumArity, node.Symbol.MaximumArity);
+      var replacement = anyNodeSymbol.CreateTreeNode();
+      SchemaUtil.ReplaceSubtree(node, replacement, true);
+
+      return true;
+    }
+
+    private static bool ReplaceAnySubtree(ISymbolicExpressionTree schema, ISymbolicExpressionTreeNode node, int minSchemaLength) {
+      if (schema.Length - node.GetLength() + 1 < minSchemaLength)
+        return false;
+
       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];
-          // do not replace the node with a wildcard if it would result in a length < MinimumSchemaLength
-          if (schema.Length - node.GetLength() + 1 < minimumSchemaLength)
-            continue;
-          var 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;
-        }
-      }
-    }
-
-    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;
-        }
-      }
+      var replacement = anySubtreeSymbol.CreateTreeNode();
+
+      SchemaUtil.ReplaceSubtree(node, replacement, false);
+      return true;
+    }
+
+    private static bool ReplaceCombined(ISymbolicExpressionTree schema, ISymbolicExpressionTreeNode node, int minSchemaLength) {
+      ISymbol wildcard;
+      if (node.SubtreeCount > 0)
+        wildcard = new AnyNodeSymbol(node.Symbol.MinimumArity, node.Symbol.MaximumArity);
+      else
+        wildcard = new AnySubtreeSymbol();
+
+      SchemaUtil.ReplaceSubtree(node, wildcard.CreateTreeNode(), node.SubtreeCount > 0);
+      return true;
     }
     #endregion

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

@@ -92 +92 @@
       get { return (ILookupParameter<BoolValue>)Parameters[RandomReplacementParameterName]; }
     }
-    public ILookupParameter<ISymbolicExpressionTreeManipulator> MutatorParameter {
-      get { return (ILookupParameter<ISymbolicExpressionTreeManipulator>)Parameters[MutatorParameterName]; }
-    }
     public ILookupParameter<ISymbolicExpressionTreeCrossover> CrossoverParameter {
       get { return (ILookupParameter<ISymbolicExpressionTreeCrossover>)Parameters[CrossoverParameterName]; }
@@ -148 +145 @@
     [Storable]
     private readonly UpdateQualityOperator updateQualityOperator;
+
+    [Storable]
+    public ISymbolicExpressionTreeManipulator SchemaManipulator { get; set; }
 
     [StorableHook(HookType.AfterDeserialization)]
@@ -221 +221 @@
 
       var random = RandomParameter.ActualValue;
-      var mutator = MutatorParameter.ActualValue;
 
       var s = Schema;
@@ -303 +302 @@
       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 mutatorOp = ExecutionContext.CreateChildOperation(SchemaManipulator, ind);
         var updateOp = ExecutionContext.CreateChildOperation(updateQualityOperator, ind);
         mutationOc.Add(mutatorOp);