source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaCreator.cs @ 15482

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.EvolutionTracking;
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]
  public class SchemaCreator : EvolutionTrackingOperator<ISymbolicExpressionTree> {
    #region parameter names
    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";
    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 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

    #region parameters
    public IConstrainedValueParameter<ISymbolicExpressionTreeManipulator> SchemaManipulatorParameter {
      get { return (IConstrainedValueParameter<ISymbolicExpressionTreeManipulator>)Parameters[SchemaManipulatorParameterName]; }
    }
    public IConstrainedValueParameter<StringValue> SchemaDefinitionParameter {
      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 IFixedValueParameter<BoolValue> StrictSchemaMatchingParameter {
      get { return (IFixedValueParameter<BoolValue>)Parameters[StrictSchemaMatchingParameterName]; }
    }
    public IFixedValueParameter<BoolValue> ExclusiveMatchingParameter {
      get { return (IFixedValueParameter<BoolValue>)Parameters[ExclusiveMatchingParameterName]; }
    }
    public IFixedValueParameter<BoolValue> ScaleEstimatedValuesParameter {
      get { return (IFixedValueParameter<BoolValue>)Parameters[ScaleEstimatedValuesParameterName]; }
    }
    public IFixedValueParameter<PercentValue> PercentageOfPopulationParameter {
      get { return (IFixedValueParameter<PercentValue>)Parameters[PercentageOfPopulationParameterName]; }
    }
    public IFixedValueParameter<IntValue> MinimumSchemaLengthParameter {
      get { return (IFixedValueParameter<IntValue>)Parameters[MinimumSchemaLengthParameterName]; }
    }
    public IFixedValueParameter<BoolValue> ExecuteInParallelParameter {
      get { return (IFixedValueParameter<BoolValue>)Parameters[ExecuteInParallelParameterName]; }
    }
    public IFixedValueParameter<IntValue> MaxDegreeOfParallelismParameter {
      get { return (IFixedValueParameter<IntValue>)Parameters[MaxDegreeOfParalellismParameterName]; }
    }
    public IFixedValueParameter<PercentValue> MinimumSchemaFrequencyParameter {
      get { return (IFixedValueParameter<PercentValue>)Parameters[MinimumSchemaFrequencyParameterName]; }
    }
    public IFixedValueParameter<PercentValue> MinimumPhenotypicSimilarityParameter {
      get { return (IFixedValueParameter<PercentValue>)Parameters[MinimumPhenotypicSimilarityParameterName]; }
    }
    public IFixedValueParameter<PercentValue> ReplacementRatioParameter {
      get { return (IFixedValueParameter<PercentValue>)Parameters[ReplacementRatioParameterName]; }
    }
    public IValueParameter<IntValue> NumberOfSchemasParameter {
      get { return (IValueParameter<IntValue>)Parameters[NumberOfSchemasParameterName]; }
    }
    public IValueParameter<DoubleValue> AverageSchemaLengthParameter {
      get { return (IValueParameter<DoubleValue>)Parameters[AverageSchemaLengthParameterName]; }
    }
    public IValueParameter<IntValue> NumberOfChangedTreesParameter {
      get { return (IValueParameter<IntValue>)Parameters[NumberOfChangedTreesParameterName]; }
    }
    #endregion

    #region parameter properties
    public int MinimumSchemaLength { get { return MinimumSchemaLengthParameter.Value.Value; } }
    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 bool StrictSchemaMatching { get { return StrictSchemaMatchingParameter.Value.Value; } }
    #endregion

    private UpdateQualityOperator updateQualityOperator;
    private DiversificationStatisticsOperator diversificationStatisticsOperator;

    public override void ClearState() {
      NumberOfChangedTreesParameter.Value.Value = 0;
      NumberOfChangedTreesParameter.Value.Value = 0;
      AverageSchemaLengthParameter.Value.Value = 0;
      base.ClearState();
    }

    public SchemaCreator() {
      #region add parameters
      Parameters.Add(new FixedValueParameter<IntValue>(MinimumSchemaLengthParameterName, new IntValue(10)));
      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<BoolValue>(ExecuteInParallelParameterName, new BoolValue(false)));
      Parameters.Add(new FixedValueParameter<IntValue>(MaxDegreeOfParalellismParameterName, new IntValue(-1)));
      Parameters.Add(new FixedValueParameter<BoolValue>(ScaleEstimatedValuesParameterName, new BoolValue(true)));
      Parameters.Add(new FixedValueParameter<BoolValue>(ExclusiveMatchingParameterName, new BoolValue(false)));
      Parameters.Add(new FixedValueParameter<BoolValue>(StrictSchemaMatchingParameterName, new BoolValue(false)));
      Parameters.Add(new ValueParameter<IntValue>(NumberOfChangedTreesParameterName, new IntValue(0)));
      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)));

      // add update rules
      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)"),
        new StringValue("f(x) = tanh(4x)"),
        new StringValue("f(x) = 1-sqrt(1-x)")
      });
      var replacementRatioUpdateRuleParameter = new ConstrainedValueParameter<StringValue>(ReplacementRatioUpdateRuleParameterName, replacementRatioUpdateRules);
      replacementRatioUpdateRuleParameter.Value = replacementRatioUpdateRules.First();
      Parameters.Add(replacementRatioUpdateRuleParameter);

      // 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

      NumberOfChangedTreesParameter.Hidden = true;
      NumberOfSchemasParameter.Hidden = true;
      AverageSchemaLengthParameter.Hidden = true;

      ExecuteInParallelParameter.Hidden = true;
      MaxDegreeOfParallelismParameter.Hidden = true;
    }

    protected SchemaCreator(SchemaCreator original, Cloner cloner) : base(original, cloner) { }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new SchemaCreator(this, cloner);
    }

    [StorableConstructor]
    protected SchemaCreator(bool deserializing) : base(deserializing) { }


    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      if (!Parameters.ContainsKey(StrictSchemaMatchingParameterName))
        Parameters.Add(new FixedValueParameter<BoolValue>(StrictSchemaMatchingParameterName, new BoolValue(false)));
    }

    public override IOperation Apply() {
      // apply only when at least one generation has passed
      var gen = Generations.Value;
      if (gen < 1 || GenealogyGraph == null)
        return base.Apply();

      var n = (int)Math.Round(ExecutionContext.Scope.SubScopes.Count * PercentageOfPopulation);

      var updateEstimatedValues = new OperationCollection { Parallel = true };
      if (updateQualityOperator == null)
        updateQualityOperator = new UpdateQualityOperator();

      foreach (var s in ExecutionContext.Scope.SubScopes.Where(s => !s.Variables.ContainsKey("EstimatedValues"))) {
        updateEstimatedValues.Add(ExecutionContext.CreateChildOperation(updateQualityOperator, s));
      }

      var replacementRule = ReplacementRatioUpdateRuleParameter.Value.Value;
      var schemaManipulator = SchemaManipulatorParameter.Value;

      var evaluateSchemas = new OperationCollection();

      // 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
                     let v = GenealogyGraph.GetByContent(t)
                     where v.InDegree == 2
                     select v;

      List<ISymbolicExpressionTree> schemas;
      switch (SchemaDefinitionParameter.Value.Value) {
        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
      foreach (var schema in schemas) {
        evaluateSchemas.Add(ExecutionContext.CreateChildOperation(new SchemaEvaluator { Schema = schema, ReplacementRule = replacementRule, SchemaManipulator = schemaManipulator }, 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() };
    }

    #region schema generation
    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.Skip(minOffspringCount - 1).Any()).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) {
          replaced |= replaceFunc(schema, nodes[i], minimumSchemaLength);
        }
        if (replaced) {
          var str = schema.Root.GetSubtree(0).GetSubtree(0).FormatToString(strict);
          if (hash.Add(str))
            yield return schema;
        }
      }
    }

    // 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 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
  }
}