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

#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.Linq;
using HeuristicLab.Analysis;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.EvolutionTracking;
using HeuristicLab.Operators;
using HeuristicLab.Optimization.Operators;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Tracking {
  [Item("SchemaCreator", "An operator that builds schemas based on the heredity relationship in the genealogy graph.")]
  [StorableClass]
  public class SchemaCreator : EvolutionTrackingOperator<ISymbolicExpressionTree> {
    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";

    #region parameters
    public IFixedValueParameter<IntValue> MinimumSchemaLengthParameter {
      get { return (IFixedValueParameter<IntValue>)Parameters[MinimumSchemaLengthParameterName]; }
    }

    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]; }
    }

    private IFixedValueParameter<BoolValue> RandomReplacementParameter {
      get { return (IFixedValueParameter<BoolValue>)Parameters[RandomReplacementParameterName]; }
    }
    #endregion

    #region parameter properties
    public int MinimumSchemaLength {
      get { return MinimumSchemaLengthParameter.Value.Value; }
    }
    #endregion

    public SchemaCreator() {
      Parameters.Add(new FixedValueParameter<IntValue>(MinimumSchemaLengthParameterName, new IntValue(10)));
      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumSchemaFrequencyParameterName, new PercentValue(0.05)));
      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumPhenotypicSimilarityParameterName, new PercentValue(0.8)));
      Parameters.Add(new FixedValueParameter<PercentValue>(ReplacementRatioParameterName, new PercentValue(0.2)));
      Parameters.Add(new FixedValueParameter<BoolValue>(RandomReplacementParameterName, new BoolValue(false)));
    }

    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) { }

    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();
      // for now, only consider crossover offspring
      var vertices = GenealogyGraph.GetByRank(gen).Where(x => x.InDegree == 2).Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>();
      var groups = vertices.GroupBy(x => x.Parents.First()).OrderByDescending(g => g.Count()).ToList();
      var anySubtreeSymbol = new AnySubtreeSymbol();

      var schemaEvaluator = new SchemaEvaluator();
      var scopes = new ScopeList(this.ExecutionContext.Scope.SubScopes);
      var schemaCleanupOperator = new SchemaCleanupOperator();

      var changedTreesReducer = new DataReducer();
      changedTreesReducer.ParameterToReduce.ActualName = schemaEvaluator.ChangedTreesParameter.ActualName;
      changedTreesReducer.ReductionOperation.Value = new ReductionOperation(ReductionOperations.Sum);
      changedTreesReducer.TargetOperation.Value = new ReductionOperation(ReductionOperations.Assign); // asign the sum to the target parameter
      changedTreesReducer.TargetParameter.ActualName = "NumberOfChangedTrees";

      var valuesCollector = new DataTableValuesCollector();
      valuesCollector.CollectedValues.Add(new LookupParameter<IntValue>("NumberOfChangedTrees"));
      valuesCollector.DataTableParameter.ActualName = "Diversification";

      var resultCollector = new ResultsCollector();
      resultCollector.CollectedValues.Add(new LookupParameter<DataTable>("Diversification"));

      var reduceChangedTrees = ExecutionContext.CreateChildOperation(changedTreesReducer);
      var collectValues = ExecutionContext.CreateChildOperation(valuesCollector);
      var collectResults = ExecutionContext.CreateChildOperation(resultCollector);

      var oc = new OperationCollection();

      #region create schemas and add subscopes representing the individuals
      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 arcs = g.Select(x => x.InArcs.Last()).Where(x => x.Data != null);
        var indices = arcs.Select(x => ((IFragment<ISymbolicExpressionTreeNode>)x.Data).Index1).Distinct().ToArray();
        Array.Sort(indices);
        var nodesToReplace = indices.Where(x => x >= 2).Select(x => nodes[x]).ToList();
        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)
            continue;

          var replacement = anySubtreeSymbol.CreateTreeNode();
          ReplaceSubtree(node, replacement, false);
          replaced = true;
        }
        if (replaced) {
          var scope = new Scope("Schema");
          scope.Variables.Add(new Core.Variable("Schema", schema));
          scope.SubScopes.AddRange(ShallowCopy(scopes));

          oc.Add(ExecutionContext.CreateChildOperation(schemaEvaluator, scope));
          ExecutionContext.Scope.SubScopes.Add(scope);
        }
      }
      #endregion

      var cleanup = ExecutionContext.CreateChildOperation(schemaCleanupOperator);
      // return an operation collection containing all the scope operations + base.Apply()
      return new OperationCollection { oc, reduceChangedTrees, collectValues, collectResults, cleanup, base.Apply() };
    }

    private static ScopeList ShallowCopy(ScopeList scopes) {
      var scopeList = new ScopeList();
      // shallow-copy means that we create a new scope but reuse the variables
      foreach (var scope in scopes) {
        var s = new Scope(scope.Name);
        foreach (var v in scope.Variables)
          s.Variables.Add(v);
        scopeList.Add(s);
      }
      return scopeList;
    }

    private static void ReplaceSubtree(ISymbolicExpressionTreeNode original, ISymbolicExpressionTreeNode replacement,
      bool preserveChildren = true) {
      var parent = original.Parent;
      if (parent == null)
        throw new ArgumentException("Parent cannot be null for node " + original);
      var index = parent.IndexOfSubtree(original);
      parent.RemoveSubtree(index);
      parent.InsertSubtree(index, replacement);

      if (preserveChildren) {
        var subtrees = original.Subtrees.ToList();

        for (int i = subtrees.Count - 1; i >= 0; --i)
          original.RemoveSubtree(i);

        for (int i = 0; i < subtrees.Count; ++i) {
          replacement.AddSubtree(subtrees[i]);
        }
      }
    }
  }
}