Changeset 15482


Ignore:
Timestamp:
11/21/17 16:00:15 (3 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:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaCreator.cs

    r15351 r15482  
    3030using HeuristicLab.Parameters;
    3131using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     32using HeuristicLab.PluginInfrastructure;
    3233
    3334namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
     35  using Vertices = IEnumerable<IGenealogyGraphNode<ISymbolicExpressionTree>>;
     36
    3437  [Item("SchemaCreator", "An operator that builds schemas based on the heredity relationship in the genealogy graph.")]
    3538  [StorableClass]
     
    5356    private const string StrictSchemaMatchingParameterName = "StrictSchemaMatching";
    5457    private const string SchemaDefinitionParameterName = "SchemaDefinition";
     58    private const string SchemaManipulatorParameterName = "SchemaManipulator";
    5559    #endregion
    5660
    5761    #region parameters
    58 
     62    public IConstrainedValueParameter<ISymbolicExpressionTreeManipulator> SchemaManipulatorParameter {
     63      get { return (IConstrainedValueParameter<ISymbolicExpressionTreeManipulator>)Parameters[SchemaManipulatorParameterName]; }
     64    }
    5965    public IConstrainedValueParameter<StringValue> SchemaDefinitionParameter {
    6066      get { return (IConstrainedValueParameter<StringValue>)Parameters[SchemaDefinitionParameterName]; }
     
    143149      Parameters.Add(new FixedValueParameter<BoolValue>(UseAdaptiveReplacementRatioParameterName, new BoolValue(true)));
    144150
     151      // add update rules
    145152      var replacementRatioUpdateRules = new ItemSet<StringValue>(new[] {
    146153        new StringValue("f(x) = x"),
     
    155162      Parameters.Add(replacementRatioUpdateRuleParameter);
    156163
    157       var schemaDefinitions = new ItemSet<StringValue>(new[] {
    158          new StringValue("="),
    159          new StringValue("#"),
    160          new StringValue("=,#")
    161       });
     164      // add schema definitions
     165      var schemaDefinitions = new ItemSet<StringValue>(new[] { "=", "#", "=,#" }.Select(x => new StringValue(x)));
    162166      var schemaDefinitionParameter = new ConstrainedValueParameter<StringValue>(SchemaDefinitionParameterName, schemaDefinitions);
    163167      schemaDefinitionParameter.Value = schemaDefinitions.First();
    164168      Parameters.Add(schemaDefinitionParameter);
     169
     170      // use a separate set of manipulators in order to allow the user to specify different mutations for schemas
     171      // and not be limited to the manipulator parameter for the whole algorithm
     172      var manipulators = ApplicationManager.Manager.GetTypes(typeof(ISymbolicExpressionTreeManipulator))
     173                                           .Where(x => !typeof(IMultiOperator<ISymbolicExpressionTreeManipulator>).IsAssignableFrom(x)
     174                                                       && !typeof(ISymbolicExpressionTreeArchitectureAlteringOperator).IsAssignableFrom(x))
     175                                           .Select(x => (ISymbolicExpressionTreeManipulator)Activator.CreateInstance(x)).ToList();
     176      manipulators.Add(new MultiSymbolicExpressionTreeManipulator());
     177
     178      // add individual manipulators
     179      var manipulatorParameter = new ConstrainedValueParameter<ISymbolicExpressionTreeManipulator>(SchemaManipulatorParameterName, new ItemSet<ISymbolicExpressionTreeManipulator>(manipulators));
     180      // add a multi manipulator as well
     181      manipulatorParameter.Value = manipulators.First();
     182      Parameters.Add(manipulatorParameter);
    165183      #endregion
    166184
     
    206224
    207225      var replacementRule = ReplacementRatioUpdateRuleParameter.Value.Value;
     226      var schemaManipulator = SchemaManipulatorParameter.Value;
    208227
    209228      var evaluateSchemas = new OperationCollection();
     
    218237
    219238      List<ISymbolicExpressionTree> schemas;
    220       var def = SchemaDefinitionParameter.Value.Value;
    221       switch (def) {
     239      switch (SchemaDefinitionParameter.Value.Value) {
    222240        case "=":
    223241          schemas = GenerateAnyNodeSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
     
    238256      #region create schemas and add subscopes representing the individuals
    239257      foreach (var schema in schemas) {
    240         evaluateSchemas.Add(ExecutionContext.CreateChildOperation(new SchemaEvaluator { Schema = schema, ReplacementRule = replacementRule }, ExecutionContext.Scope));
     258        evaluateSchemas.Add(ExecutionContext.CreateChildOperation(new SchemaEvaluator { Schema = schema, ReplacementRule = replacementRule, SchemaManipulator = schemaManipulator }, ExecutionContext.Scope));
    241259      }
    242260      #endregion
     
    257275
    258276    #region schema generation
    259     public static IEnumerable<ISymbolicExpressionTree> GenerateAnyNodeSchemas(IEnumerable<IGenealogyGraphNode<ISymbolicExpressionTree>> vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
     277    public static IEnumerable<ISymbolicExpressionTree> GenerateAnyNodeSchemas(Vertices vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
     278      return GenerateSchemas(vertices, ReplaceAnyNode, minimumSchemaLength, minOffspringCount, strict);
     279    }
     280
     281    public static IEnumerable<ISymbolicExpressionTree> GenerateAnySubtreeSchemas(Vertices vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
     282      return GenerateSchemas(vertices, ReplaceAnySubtree, minimumSchemaLength, minOffspringCount, strict);
     283    }
     284
     285    public static IEnumerable<ISymbolicExpressionTree> GenerateCombinedSchemas(Vertices vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
     286      return GenerateSchemas(vertices, ReplaceCombined, minimumSchemaLength, minOffspringCount, strict);
     287    }
     288
     289    public static IEnumerable<ISymbolicExpressionTree> GenerateSchemas(Vertices vertices, Func<ISymbolicExpressionTree, ISymbolicExpressionTreeNode, int, bool> replaceFunc, int minimumSchemaLength, int minOffspringCount, bool strict = true) {
    260290      var anySubtreeSymbol = new AnySubtreeSymbol();
    261       var groups = vertices.GroupBy(x => x.Parents.First()).Where(g => g.Count() >= minOffspringCount).OrderByDescending(g => g.Count());
     291      var groups = vertices.GroupBy(x => x.Parents.First()).Where(g => g.Skip(minOffspringCount - 1).Any()).OrderByDescending(g => g.Count());
    262292      var hash = new HashSet<string>();
    263293      foreach (var g in groups) {
     
    271301        var indices = fragments.Select(x => x.Index1).Distinct().OrderByDescending(x => schema.Root.GetBranchLevel(nodes[x]));
    272302        foreach (var i in indices) {
    273           var node = nodes[i];
    274           var anyNodeSymbol = new AnyNodeSymbol(node.Symbol.MinimumArity, node.Symbol.MaximumArity);
    275           var replacement = anyNodeSymbol.CreateTreeNode();
    276           SchemaUtil.ReplaceSubtree(node, replacement, true);
    277           replaced = true;
     303          replaced |= replaceFunc(schema, nodes[i], minimumSchemaLength);
    278304        }
    279305        if (replaced) {
     
    285311    }
    286312
    287     public static IEnumerable<ISymbolicExpressionTree> GenerateAnySubtreeSchemas(IEnumerable<IGenealogyGraphNode<ISymbolicExpressionTree>> vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
     313    // node replacement rules
     314    private static bool ReplaceAnyNode(ISymbolicExpressionTree schema, ISymbolicExpressionTreeNode node, int minSchemaLength) {
     315      var anyNodeSymbol = new AnyNodeSymbol(node.Symbol.MinimumArity, node.Symbol.MaximumArity);
     316      var replacement = anyNodeSymbol.CreateTreeNode();
     317      SchemaUtil.ReplaceSubtree(node, replacement, true);
     318
     319      return true;
     320    }
     321
     322    private static bool ReplaceAnySubtree(ISymbolicExpressionTree schema, ISymbolicExpressionTreeNode node, int minSchemaLength) {
     323      if (schema.Length - node.GetLength() + 1 < minSchemaLength)
     324        return false;
     325
    288326      var anySubtreeSymbol = new AnySubtreeSymbol();
    289       var groups = vertices.GroupBy(x => x.Parents.First()).Where(g => g.Count() >= minOffspringCount).OrderByDescending(g => g.Count());
    290       var hash = new HashSet<string>();
    291       foreach (var g in groups) {
    292         var parent = g.Key;
    293         if (parent.Data.Length < minimumSchemaLength)
    294           continue;
    295         bool replaced = false;
    296         var schema = (ISymbolicExpressionTree)parent.Data.Clone();
    297         var nodes = schema.IterateNodesPrefix().ToList();
    298         var fragments = g.Select(x => x.InArcs.Last().Data).Where(x => x != null).Cast<IFragment<ISymbolicExpressionTreeNode>>();
    299         var indices = fragments.Select(x => x.Index1).Distinct().OrderByDescending(x => schema.Root.GetBranchLevel(nodes[x]));
    300         foreach (var i in indices) {
    301           var node = nodes[i];
    302           // do not replace the node with a wildcard if it would result in a length < MinimumSchemaLength
    303           if (schema.Length - node.GetLength() + 1 < minimumSchemaLength)
    304             continue;
    305           var replacement = anySubtreeSymbol.CreateTreeNode();
    306           SchemaUtil.ReplaceSubtree(node, replacement, false);
    307           replaced = true;
    308         }
    309         if (replaced) {
    310           var str = schema.Root.GetSubtree(0).GetSubtree(0).FormatToString(strict);
    311           if (hash.Add(str))
    312             yield return schema;
    313         }
    314       }
    315     }
    316 
    317     public static IEnumerable<ISymbolicExpressionTree> GenerateCombinedSchemas(IEnumerable<IGenealogyGraphNode<ISymbolicExpressionTree>> vertices, int minimumSchemaLength, int minOffspringCount = 1, bool strict = true) {
    318       var anySubtreeSymbol = new AnySubtreeSymbol();
    319       var groups = vertices.GroupBy(x => x.Parents.First()).Where(g => g.Count() >= minOffspringCount).OrderByDescending(g => g.Count());
    320       var hash = new HashSet<string>();
    321       foreach (var g in groups) {
    322         var parent = g.Key;
    323         if (parent.Data.Length < minimumSchemaLength)
    324           continue;
    325         bool replaced = false;
    326         var schema = (ISymbolicExpressionTree)parent.Data.Clone();
    327         var nodes = schema.IterateNodesPrefix().ToList();
    328         var fragments = g.Select(x => x.InArcs.Last().Data).Where(x => x != null).Cast<IFragment<ISymbolicExpressionTreeNode>>();
    329         var indices = fragments.Select(x => x.Index1).Distinct().OrderByDescending(x => schema.Root.GetBranchLevel(nodes[x]));
    330         foreach (var i in indices) {
    331           var node = nodes[i];
    332           ISymbolicExpressionTreeNode replacement;
    333           if (node.SubtreeCount > 0) {
    334             replacement = new AnyNodeSymbol(node.Symbol.MinimumArity, node.Symbol.MaximumArity).CreateTreeNode();
    335             SchemaUtil.ReplaceSubtree(node, replacement, true);
    336           } else {
    337             replacement = anySubtreeSymbol.CreateTreeNode();
    338             SchemaUtil.ReplaceSubtree(node, replacement, false);
    339           }
    340           replaced = true;
    341         }
    342         if (replaced) {
    343           var str = schema.Root.GetSubtree(0).GetSubtree(0).FormatToString(strict);
    344           if (hash.Add(str))
    345             yield return schema;
    346         }
    347       }
     327      var replacement = anySubtreeSymbol.CreateTreeNode();
     328
     329      SchemaUtil.ReplaceSubtree(node, replacement, false);
     330      return true;
     331    }
     332
     333    private static bool ReplaceCombined(ISymbolicExpressionTree schema, ISymbolicExpressionTreeNode node, int minSchemaLength) {
     334      ISymbol wildcard;
     335      if (node.SubtreeCount > 0)
     336        wildcard = new AnyNodeSymbol(node.Symbol.MinimumArity, node.Symbol.MaximumArity);
     337      else
     338        wildcard = new AnySubtreeSymbol();
     339
     340      SchemaUtil.ReplaceSubtree(node, wildcard.CreateTreeNode(), node.SubtreeCount > 0);
     341      return true;
    348342    }
    349343    #endregion
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaEvaluator.cs

    r14427 r15482  
    9292      get { return (ILookupParameter<BoolValue>)Parameters[RandomReplacementParameterName]; }
    9393    }
    94     public ILookupParameter<ISymbolicExpressionTreeManipulator> MutatorParameter {
    95       get { return (ILookupParameter<ISymbolicExpressionTreeManipulator>)Parameters[MutatorParameterName]; }
    96     }
    9794    public ILookupParameter<ISymbolicExpressionTreeCrossover> CrossoverParameter {
    9895      get { return (ILookupParameter<ISymbolicExpressionTreeCrossover>)Parameters[CrossoverParameterName]; }
     
    148145    [Storable]
    149146    private readonly UpdateQualityOperator updateQualityOperator;
     147
     148    [Storable]
     149    public ISymbolicExpressionTreeManipulator SchemaManipulator { get; set; }
    150150
    151151    [StorableHook(HookType.AfterDeserialization)]
     
    221221
    222222      var random = RandomParameter.ActualValue;
    223       var mutator = MutatorParameter.ActualValue;
    224223
    225224      var s = Schema;
     
    303302      var updateEstimatedValues = new OperationCollection { Parallel = true }; // evaluation should be done in parallel when possible
    304303      foreach (var ind in individualsToReplace) {
    305         var mutatorOp = ExecutionContext.CreateChildOperation(mutator, ind);
     304        var mutatorOp = ExecutionContext.CreateChildOperation(SchemaManipulator, ind);
    306305        var updateOp = ExecutionContext.CreateChildOperation(updateQualityOperator, ind);
    307306        mutationOc.Add(mutatorOp);
Note: See TracChangeset for help on using the changeset viewer.