source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/Analyzers/SymbolicDataAnalysisSchemaFrequencyAnalyzer.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.Collections.Generic;
using System.Linq;
using System.Text;
using HeuristicLab.Analysis;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.EvolutionTracking;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Random;

namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Tracking.Analyzers {
  [Item("SymbolicDataAnalysisSchemaFrequencyAnalyzer", "Analyze common schemas occuring in the population")]
  [StorableClass]
  public class SymbolicDataAnalysisSchemaFrequencyAnalyzer : EvolutionTrackingAnalyzer<ISymbolicExpressionTree> {
    private const string GenotypeSimilarityThresholdParameterName = "GenotypeSimilarityThreshold";
    private const string PhenotypeSimilarityThresholdParameterName = "PhenotypeSimilarityThreshold";
    private const string SchemaLengthThresholdParameterName = "SchemaLengthThreshold";
    private const string SchemaFrequencyThresholdParameterName = "SchemaFrequencyThreshold";
    private const string ReplacementRatioParameterName = "ReplacementRatio";
    private const string EvaluatorParameterName = "Evaluator";
    private const string ProblemDataParameterName = "ProblemData";
    private const string InterpreterParameterName = "SymbolicExpressionTreeInterpreter";
    private const string EstimationLimitsParameterName = "EstimationLimits";
    private const string ApplyLinearScalingParameterName = "ApplyLinearScaling";
    private const string RandomParameterName = "Random";
    private const string SolutionCreatorParameterName = "SolutionCreator";
    private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
    private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
    private const string GrammarParameterName = "SymbolicExpressionTreeGrammar";
    private const string MutatorParameterName = "Mutator";
    private const string RandomReplacementParameterName = "RandomReplacement";

    private ISymbolicExpressionTreeNodeEqualityComparer comparer;
    private QueryMatch qm;
    private SymbolicExpressionTreePhenotypicSimilarityCalculator phenotypicSimilarityCalculator;
    private SymbolicExpressionTreeBottomUpSimilarityCalculator bottomUpSimilarityCalculator;

    private static readonly Dictionary<string, string> ShortNames = new Dictionary<string, string> {
      { "Addition", "+" },
      { "Subtraction", "-" },
      { "Multiplication", "*" },
      { "Division", "/" },
      { "Exponential", "exp" },
      { "Logarithm", "log" }
    };

    #region parameters
    public IFixedValueParameter<BoolValue> RandomReplacementParameter {
      get { return (IFixedValueParameter<BoolValue>)Parameters[RandomReplacementParameterName]; }
    }
    public ILookupParameter<ISymbolicExpressionTreeManipulator> MutatorParameter {
      get { return (ILookupParameter<ISymbolicExpressionTreeManipulator>)Parameters[MutatorParameterName]; }
    }
    public IFixedValueParameter<PercentValue> GenotypeSimilarityThresholdParameter {
      get { return (IFixedValueParameter<PercentValue>)Parameters[GenotypeSimilarityThresholdParameterName]; }
    }
    public IFixedValueParameter<PercentValue> PhenotypeSimilarityThresholdParameter {
      get { return (IFixedValueParameter<PercentValue>)Parameters[PhenotypeSimilarityThresholdParameterName]; }
    }
    public IFixedValueParameter<IntValue> SchemaLengthThresholdParameter {
      get { return (IFixedValueParameter<IntValue>)Parameters[SchemaLengthThresholdParameterName]; }
    }
    public IFixedValueParameter<PercentValue> SchemaFrequencyThresholdParameter {
      get { return (IFixedValueParameter<PercentValue>)Parameters[SchemaFrequencyThresholdParameterName]; }
    }
    public IFixedValueParameter<PercentValue> ReplacementRatioParameter {
      get { return (IFixedValueParameter<PercentValue>)Parameters[ReplacementRatioParameterName]; }
    }
    public ILookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>> EvaluatorParameter {
      get { return (ILookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>>)Parameters[EvaluatorParameterName]; }
    }
    public ILookupParameter<IRegressionProblemData> ProblemDataParameter {
      get { return (ILookupParameter<IRegressionProblemData>)Parameters[ProblemDataParameterName]; }
    }
    public ILookupParameter<ISymbolicDataAnalysisExpressionTreeInterpreter> InterpreterParameter {
      get { return (ILookupParameter<ISymbolicDataAnalysisExpressionTreeInterpreter>)Parameters[InterpreterParameterName]; }
    }
    public ILookupParameter<DoubleLimit> EstimationLimitsParameter {
      get { return (ILookupParameter<DoubleLimit>)Parameters[EstimationLimitsParameterName]; }
    }
    public ILookupParameter<BoolValue> ApplyLinearScalingParameter {
      get { return (ILookupParameter<BoolValue>)Parameters[ApplyLinearScalingParameterName]; }
    }
    public ILookupParameter<IRandom> RandomParameter {
      get { return (ILookupParameter<IRandom>)Parameters[RandomParameterName]; }
    }
    public ILookupParameter<SymbolicExpressionTreeCreator> SolutionCreatorParameter {
      get { return (ILookupParameter<SymbolicExpressionTreeCreator>)Parameters[SolutionCreatorParameterName]; }
    }

    public ILookupParameter<IntValue> MaximumSymbolicExpressionTreeLengthParameter {
      get { return (ILookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeLengthParameterName]; }
    }

    public ILookupParameter<IntValue> MaximumSymbolicExpressionTreeDepthParameter {
      get { return (ILookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeDepthParameterName]; }
    }

    public ILookupParameter<ISymbolicDataAnalysisGrammar> GrammarParameter {
      get { return (ILookupParameter<ISymbolicDataAnalysisGrammar>)Parameters[GrammarParameterName]; }
    }

    public double GenotypeSimilarityThreshold {
      get { return GenotypeSimilarityThresholdParameter.Value.Value; }
    }
    public double PhenotypeSimilarityThreshold {
      get { return PhenotypeSimilarityThresholdParameter.Value.Value; }
    }
    public double SchemaLengthThreshold {
      get { return SchemaLengthThresholdParameter.Value.Value; }
    }
    public double SchemaFrequencyThreshold {
      get { return SchemaFrequencyThresholdParameter.Value.Value; }
    }
    public double ReplacementRatio {
      get { return ReplacementRatioParameter.Value.Value; }
    }

    public bool RandomReplacement {
      get { return RandomReplacementParameter.Value.Value; }
    }
    #endregion

    public SymbolicDataAnalysisSchemaFrequencyAnalyzer() {
      Parameters.Add(new FixedValueParameter<PercentValue>(GenotypeSimilarityThresholdParameterName));
      Parameters.Add(new FixedValueParameter<PercentValue>(PhenotypeSimilarityThresholdParameterName));
      Parameters.Add(new FixedValueParameter<IntValue>(SchemaLengthThresholdParameterName));
      Parameters.Add(new FixedValueParameter<PercentValue>(SchemaFrequencyThresholdParameterName));
      Parameters.Add(new FixedValueParameter<PercentValue>(ReplacementRatioParameterName));
      Parameters.Add(new LookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>>(EvaluatorParameterName));
      Parameters.Add(new LookupParameter<IRegressionProblemData>(ProblemDataParameterName));
      Parameters.Add(new LookupParameter<ISymbolicDataAnalysisExpressionTreeInterpreter>(InterpreterParameterName));
      Parameters.Add(new LookupParameter<DoubleLimit>(EstimationLimitsParameterName));
      Parameters.Add(new LookupParameter<BoolValue>(ApplyLinearScalingParameterName));
      Parameters.Add(new LookupParameter<IRandom>(RandomParameterName));
      Parameters.Add(new LookupParameter<SymbolicExpressionTreeCreator>(SolutionCreatorParameterName));
      Parameters.Add(new LookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName));
      Parameters.Add(new LookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName));
      Parameters.Add(new LookupParameter<ISymbolicDataAnalysisGrammar>(GrammarParameterName));
      Parameters.Add(new LookupParameter<ISymbolicExpressionTreeManipulator>(MutatorParameterName));
      Parameters.Add(new FixedValueParameter<BoolValue>(RandomReplacementParameterName, new BoolValue(true)));

      comparer = new SymbolicExpressionTreeNodeEqualityComparer {
        MatchConstantValues = false,
        MatchVariableWeights = false,
        MatchVariableNames = true
      };
      qm = new QueryMatch(comparer) { MatchParents = true };
      phenotypicSimilarityCalculator = new SymbolicExpressionTreePhenotypicSimilarityCalculator();
      bottomUpSimilarityCalculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator();
    }


    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      comparer = new SymbolicExpressionTreeNodeEqualityComparer {
        MatchConstantValues = false,
        MatchVariableWeights = false,
        MatchVariableNames = true
      };
      qm = new QueryMatch(comparer) { MatchParents = true };
      phenotypicSimilarityCalculator = new SymbolicExpressionTreePhenotypicSimilarityCalculator();
      bottomUpSimilarityCalculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator();
    }

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

    protected SymbolicDataAnalysisSchemaFrequencyAnalyzer(SymbolicDataAnalysisSchemaFrequencyAnalyzer original, Cloner cloner) : base(original, cloner) {
      this.comparer = original.comparer;
      this.qm = original.qm;
      this.phenotypicSimilarityCalculator = original.phenotypicSimilarityCalculator;
      this.bottomUpSimilarityCalculator = original.bottomUpSimilarityCalculator;
    }

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

    public override IOperation Apply() {
      IntValue updateCounter = UpdateCounterParameter.ActualValue;
      if (updateCounter == null) {
        updateCounter = new IntValue(0);
        UpdateCounterParameter.ActualValue = updateCounter;
      }
      updateCounter.Value++;
      if (updateCounter.Value != UpdateInterval.Value) return base.Apply();
      updateCounter.Value = 0;

      var graph = PopulationGraph;
      if (graph == null || Generation.Value == 0)
        return base.Apply();

      var vertices = PopulationGraph.GetByRank(Generation.Value).Where(x => x.InDegree == 2).Select(x => (IGenealogyGraphNode<ISymbolicExpressionTree>)x).ToList();
      var groups = vertices.GroupBy(x => x.Parents.First()).ToList();

      var schemas = new List<ISymbolicExpressionTree>();
      var anySubtreeSymbol = new AnySubtreeSymbol();
      //var map = new Dictionary<ISymbolicExpressionTree, IGenealogyGraphNode<ISymbolicExpressionTree>>();
      int mutatedTrees = 0;
      var scopes = this.ExecutionContext.Scope.SubScopes;

      var problemData = ProblemDataParameter.ActualValue;
      var interpreter = InterpreterParameter.ActualValue;
      var evaluator = EvaluatorParameter.ActualValue;
      var random = RandomParameter.ActualValue;
      var maxTreeLength = MaximumSymbolicExpressionTreeLengthParameter.ActualValue.Value;
      var maxTreeDepth = MaximumSymbolicExpressionTreeDepthParameter.ActualValue.Value;
      var estimationLimits = EstimationLimitsParameter.ActualValue;



      foreach (var g in groups) {
        bool replaced = false;
        var parentVertex = g.Key;
        var schema = (ISymbolicExpressionTree)parentVertex.Data.Clone();
        var arcs = g.Select(x => x.InArcs.Last()).Where(x => x.Data != null);
        var fragments = arcs.Select(x => (IFragment<ISymbolicExpressionTreeNode>)x.Data).ToArray();
        var indices = fragments.Select(x => x.Index1).Distinct().ToArray();
        // sort cutpoint indices and fragments
        Array.Sort(indices); // indices ordered in increasing preorder index
        var nodes = schema.IterateNodesPrefix().ToList();
        var nodesToReplace = indices.Where(x => x > 2).Select(x => nodes[x]).ToList();
        // walking in postorder so that schemas are more granular
        for (int i = nodesToReplace.Count - 1; i >= 0; --i) {
          //if (schemas.Any(x => qm.Match(nodesToReplace[i], x.Root))) continue;
          // replace node with wildcard (#)
          var replacement = anySubtreeSymbol.CreateTreeNode();
          ReplaceSubtree(nodesToReplace[i], replacement, false);
          replaced = true;
        }
        if (replaced && schemas.Any(x => qm.Match(schema.Root, x.Root)))
          continue;
        // if conditions are satisfied, attempt to diversify the individuals matching the schema
        if (replaced && schema.Length >= SchemaLengthThreshold) {
          //          var matchingIndividuals = individuals.Where(x => x.Changed.Value == false && qm.Match(x.Tree, schema)).ToList();
          var matchingScopes = (from s in scopes
                                let t = (ISymbolicExpressionTree)s.Variables["SymbolicExpressionTree"].Value
                                where qm.Match(t, schema)
                                select s).ToList();

          if (matchingScopes.Count >= SchemaFrequencyThreshold * scopes.Count) {
            phenotypicSimilarityCalculator.Interpreter = interpreter;
            phenotypicSimilarityCalculator.ProblemData = problemData;
            var phenotypicSimilarity = CalculatePhenotypicSimilarity(matchingScopes, phenotypicSimilarityCalculator);
            if (phenotypicSimilarity > PhenotypeSimilarityThreshold) {
              var n = (int)Math.Round(ReplacementRatio * matchingScopes.Count);
              var individualsToReplace = RandomReplacement
                ? matchingScopes.SampleRandomWithoutRepetition(random, n)
                : matchingScopes.OrderBy(x => (DoubleValue)x.Variables["Quality"].Value).Take(n);
              foreach (var ind in individualsToReplace) {
                var tree = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value;
                ReplaceBranchManipulation.ReplaceRandomBranch(random, tree, maxTreeLength, maxTreeDepth);
                var quality = evaluator.Evaluate(this.ExecutionContext, tree, problemData, problemData.TrainingIndices);
                var v = PopulationGraph.GetByContent(tree);
                v.Quality = quality;
                ((DoubleValue)ind.Variables["Quality"].Value).Value = quality;
                ind.Variables["EstimatedValues"].Value = new DoubleArray(interpreter.GetSymbolicExpressionTreeValues(tree, problemData.Dataset, problemData.TrainingIndices)
                  .LimitToRange(estimationLimits.Lower, estimationLimits.Upper).ToArray());
                mutatedTrees++;
              }
            }
          }
        }
      }

      DataTable table;
      if (!Results.ContainsKey("MutatedTrees")) {
        table = new DataTable("MutatedTrees");
        table.Rows.Add(new DataRow("MutatedTrees") { VisualProperties = { StartIndexZero = true } });
        Results.Add(new Result("MutatedTrees", table));
      } else {
        table = (DataTable)Results["MutatedTrees"].Value;
      }
      table.Rows["MutatedTrees"].Values.Add(mutatedTrees);

      return base.Apply();
    }

    private static double CalculatePhenotypicSimilarity(List<IScope> individuals, SymbolicExpressionTreePhenotypicSimilarityCalculator calculator) {
      double similarity = 0;
      int count = individuals.Count;
      for (int i = 0; i < count - 1; ++i) {
        for (int j = i + 1; j < count; ++j) {
          similarity += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
        }
      }
      return similarity / (count * (count - 1) / 2.0);
    }

    private 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.ToString());
      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]);
        }
      }
      //CheckNodeIntegrity(parent);
    }

    private bool CheckNodeIntegrity(ISymbolicExpressionTreeNode node) {
      var nodes = node.IterateNodesPrefix().ToList();
      for (int i = nodes.Count - 1; i >= 0; --i) {
        var n = nodes[i];

        if (n.GetLength() != n.IterateNodesPrefix().Count())
          throw new Exception("Node length cache is compromised for node " + n + "(" + i + ")");

        if (n.Symbol is ProgramRootSymbol)
          continue;
        if (n.Parent == null) {
          throw new Exception("Parent cannot be null for node " + n + "(" + i + ")");
        }
      }
      return true;
    }

    private string SubtreeToString(ISymbolicExpressionTreeNode node) {
      StringBuilder strBuilder = new StringBuilder();
      // internal nodes or leaf nodes?
      if (node is AnySubtree)
        return "# ";

      if (node.SubtreeCount > 0) {
        strBuilder.Append("(");
        // symbol on same line as '('
        string label = string.Empty;
        if (node is AnyNode)
          label = "=";
        else {
          var name = node.Symbol.Name;
          label = ShortNames.ContainsKey(name) ? ShortNames[name] : name;
        }
        strBuilder.Append(label + " ");
        // each subtree expression on a new line
        // and closing ')' also on new line
        foreach (var subtree in node.Subtrees) {
          strBuilder.Append(SubtreeToString(subtree));
        }
        strBuilder.Append(") ");
      } else {
        // symbol in the same line with as '(' and ')'
        var v = node as VariableTreeNode;
        var c = node as ConstantTreeNode;
        var w = node as AnyNode; // wildcard
        string label = string.Empty;
        if (w != null)
          label = "=";
        else if (v != null)
          label = string.Format("{0:0.00}_{1}", v.Weight, v.VariableName);
        else if (c != null)
          label = string.Format("{0:0.00}", c.Value);
        strBuilder.Append(label);
        if (node.Parent != null && node != node.Parent.Subtrees.Last())
          strBuilder.Append(" ");
        //strBuilder.Append(")");
      }
      return strBuilder.ToString();
    }
  }
}