source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFragmentsAnalyzer.cs @ 7799

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2012 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.Analysis;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
// type definitions for ease of use
using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;

namespace HeuristicLab.EvolutionaryTracking {
  /// <summary>
  /// An operator that gathers information on tree fragments that get passed from one generation to the next via genetic operators
  /// (Tracking of genetic variance and heredity)
  /// </summary>
  /// [Item("SymbolicExpressionTreeGenealogyAnalyzer", "An operator that tracks tree lengths of Symbolic Expression Trees")]
  [StorableClass]
  public sealed class SymbolicExpressionTreeFragmentsAnalyzer : SingleSuccessorOperator, IAnalyzer {
    private const string UpdateIntervalParameterName = "UpdateInterval";
    private const string UpdateCounterParameterName = "UpdateCounter";
    private const string ResultsParameterName = "Results";
    private const string GlobalTraceMapParameterName = "GlobalTraceMap";
    private const string GlobalCloneMapParameterName = "GlobalCloneMap";
    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
    private const string GenerationsParameterName = "Generations";
    private const string FragmentStatisticsParameterName = "FragmentStatistics";

    #region Parameter properties
    public ValueParameter<IntValue> UpdateIntervalParameter {
      get { return (ValueParameter<IntValue>)Parameters[UpdateIntervalParameterName]; }
    }
    public ValueParameter<IntValue> UpdateCounterParameter {
      get { return (ValueParameter<IntValue>)Parameters[UpdateCounterParameterName]; }
    }
    public LookupParameter<ResultCollection> ResultsParameter {
      get { return (LookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
    }
    public LookupParameter<TraceMapType> GlobalTraceMapParameter {
      get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
    }
    public LookupParameter<CloneMapType> GlobalCloneMapParameter {
      get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
    }
    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
    }
    public LookupParameter<IntValue> GenerationsParameter {
      get { return (LookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
    }
    public LookupParameter<DataTable> FragmentStatisticsParameter {
      get { return (LookupParameter<DataTable>)Parameters[FragmentStatisticsParameterName]; }
    }
    #endregion

    #region Parameters
    public bool EnabledByDefault {
      get { return true; }
    }
    public IntValue UpdateInterval {
      get { return UpdateIntervalParameter.Value; }
    }
    public IntValue UpdateCounter {
      get { return UpdateCounterParameter.Value; }
    }
    public ResultCollection Results {
      get { return ResultsParameter.ActualValue; }
    }
    public CloneMapType GlobalCloneMap {
      get { return GlobalCloneMapParameter.ActualValue; }
    }
    public TraceMapType GlobalTraceMap {
      get { return GlobalTraceMapParameter.ActualValue; }
    }
    public CloneMapType GlobalFragmentMap {
      get { return GlobalFragmentMapParameter.ActualValue; }
    }
    public IntValue Generations {
      get { return GenerationsParameter.ActualValue; }
    }
    public DataTable FragmentStatistics {
      get { return FragmentStatisticsParameter.ActualValue; }
    }
    #endregion

    [StorableConstructor]
    private SymbolicExpressionTreeFragmentsAnalyzer(bool deserializing)
      : base() {
    }
    private SymbolicExpressionTreeFragmentsAnalyzer(SymbolicExpressionTreeFragmentsAnalyzer original, Cloner cloner)
      : base(original, cloner) {
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new SymbolicExpressionTreeFragmentsAnalyzer(this, cloner);
    }
    public SymbolicExpressionTreeFragmentsAnalyzer()
      : base() {
      Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing the whole genealogy."));
      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
      Parameters.Add(new LookupParameter<DataTable>(FragmentStatisticsParameterName, "The data table to store the fragment statistics."));
      UpdateCounterParameter.Hidden = true;
      UpdateIntervalParameter.Hidden = true;
    }
    #region After deserialization code
    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      // check if all the parameters are present and accounted for 
      if (!Parameters.ContainsKey(UpdateIntervalParameterName)) {
        Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
      }
      if (Parameters.ContainsKey(UpdateCounterParameterName)) return;
      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
      UpdateCounterParameter.Hidden = true;
    }
    #endregion
    #region IStatefulItem members
    public override void InitializeState() {
      base.InitializeState();
      UpdateCounter.Value = 0;
    }

    public override void ClearState() {
      base.ClearState();
      UpdateCounter.Value = 0;
    }
    #endregion

    public override IOperation Apply() {
      if (Generations.Value == 0) return base.Apply();
      UpdateCounter.Value++;
      if (UpdateCounter.Value == UpdateInterval.Value) {
        ResultCollection results = ResultsParameter.ActualValue;
        if (FragmentStatistics == null) {
          FragmentStatisticsParameter.ActualValue = new DataTable("Fragment Statistics", "Statistical measurements of fragments aggregated over the whole population");
          FragmentStatistics.VisualProperties.YAxisTitle = "Fragment length/Similarities";
          results.Add(new Result("Fragment Statistics", FragmentStatistics));
        }

        UpdateCounter.Value = 0; // reset counter
        var gScope = ExecutionContext.Scope;
        while (gScope.Parent != null) gScope = gScope.Parent;

        #region Fragment Statistics
        var fragments = new List<ISymbolicExpressionTreeNode>();
        var parents = new List<ISymbolicExpressionTree>();
        var trees = (from s in gScope.SubScopes select s.Variables.First().Value as ISymbolicExpressionTree).ToList();
        foreach (var tree in trees.Where(x => GlobalTraceMap.ContainsKey(x))) {
          if (GlobalTraceMap[tree].Count == 2) { // crossover 
            var nodes = tree.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
            var index = ((IntValue)GlobalFragmentMap[tree]).Value;
            var fragment = nodes[index];
            if (fragment == null) throw new ArgumentException("Fragment not found");
            parents.AddRange(GlobalTraceMap[tree].Cast<ISymbolicExpressionTree>());
            fragments.Add(fragment);
          } else { // crossover followed by mutation
            // maybe mutation fragments should be also taken into account?
            var parent0 = (ISymbolicExpressionTree)GlobalTraceMap[tree][0];
            if (!GlobalFragmentMap.ContainsKey(parent0)) throw new ArgumentException("Fragment not found");
            var nodes = parent0.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
            var index = ((IntValue)GlobalFragmentMap[parent0]).Value;
            var fragment = nodes[index];
            fragments.Add(fragment);
            if (!GlobalTraceMap.ContainsKey(parent0)) throw new ArgumentException("Parent information not found");
            parents.AddRange(GlobalTraceMap[parent0].Cast<ISymbolicExpressionTree>());
          }
        }

        // write values to file
        double a1 = fragments.Average(x => x.GetLength());
        double a2 = trees.Average(x => x.Length);
        double a3 = parents.Average(x => x.Length);
        double s1 = CalculateSimilarity(fragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact);

        #region Table data
        // fragments
        if (!FragmentStatistics.Rows.ContainsKey("Average fragment length")) {
          var row = new DataRow("Average fragment length", "") { VisualProperties = { StartIndexZero = true } };
          FragmentStatistics.Rows.Add(row);
        }
        FragmentStatistics.Rows["Average fragment length"].Values.Add(a1);
        // child trees
        if (!FragmentStatistics.Rows.ContainsKey("Average child length")) {
          var row = new DataRow("Average child length", "") { VisualProperties = { StartIndexZero = true } };
          FragmentStatistics.Rows.Add(row);
        }
        FragmentStatistics.Rows["Average child length"].Values.Add(a2);
        // parents
        if (!FragmentStatistics.Rows.ContainsKey("Average parent length")) {
          var row = new DataRow("Average parent length", "") { VisualProperties = { StartIndexZero = true } };
          FragmentStatistics.Rows.Add(row);
        }
        FragmentStatistics.Rows["Average parent length"].Values.Add(a3);
        // exact similarity
        if (!FragmentStatistics.Rows.ContainsKey("Similarity (exact)")) {
          var row = new DataRow("Similarity (exact)", "") { VisualProperties = { StartIndexZero = true } };
          FragmentStatistics.Rows.Add(row);
        }
        FragmentStatistics.Rows["Similarity (exact)"].Values.Add(s1);
        #endregion

        #endregion

        // clear the global maps to save memory
        if (this.Successor == null || !(this.Successor is SymbolicExpressionTreeGenealogyAnalyzer)) {
          GlobalCloneMap.Clear();
          GlobalTraceMap.Clear();
          GlobalFragmentMap.Clear();
        }
      }
      return base.Apply();
    }

    #region Similarity computations
    #region Obsolete code
    private void CalculateDiversityIndicators(IEnumerable<ISymbolicExpressionTreeNode> fragments, out double a, out double b, out double c) {
      //var frags = fragments.Where(x => x.GetLength() > 1).ToList();
      var frags = fragments.ToList();
      var sieve = new bool[frags.Count];
      int max = 0;
      for (int i = 0; i != frags.Count - 1; ++i) {
        if (sieve[i]) continue;
        int count = 0;
        for (int j = i + 1; j != frags.Count; ++j) {
          if (sieve[j]) continue;
          if (frags[i].IsSimilarTo(frags[j], (int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact)) {
            ++count;
            sieve[i] = true;
            sieve[j] = true;
          }
        }
        if (max < count) max = count;
      }
      a = (double)sieve.Count(x => x) / sieve.Length;
      sieve = new bool[frags.Count];
      max = 0;
      for (int i = 0; i != frags.Count - 1; ++i) {
        if (sieve[i]) continue;
        int count = 0;
        for (int j = i + 1; j != frags.Count; ++j) {
          if (sieve[j]) continue;
          if (frags[i].IsSimilarTo(frags[j], (int)SymbolicExpressionTreeMatching.SimilarityLevel.High)) {
            ++count;
            sieve[i] = true;
            sieve[j] = true;
          }
        }
        if (max < count) max = count;
      }
      b = (double)sieve.Count(x => x) / sieve.Length;
      sieve = new bool[frags.Count];
      max = 0;
      for (int i = 0; i != frags.Count - 1; ++i) {
        if (sieve[i]) continue;
        int count = 0;
        for (int j = i + 1; j != frags.Count; ++j) {
          if (sieve[j]) continue;
          if (frags[i].IsSimilarTo(frags[j], (int)SymbolicExpressionTreeMatching.SimilarityLevel.Relaxed)) {
            ++count;
            sieve[i] = true;
            sieve[j] = true;
          }
        }
        if (max < count) max = count;
      }
      c = (double)sieve.Count(x => x) / max;
    }
    #endregion

    /// <summary>
    /// Provide a measure of how similar the fragments that get passed by crossover from one generation to the next are. 
    /// </summary>
    /// <param name="fragments">The symbolic expression tree fragments</param>
    /// <param name="mode">The similarity mode (0 - exact, 1 - high, 2 - relaxed)</param>
    /// <returns>The average number of similar fragments</returns>
    private double CalculateSimilarity(List<ISymbolicExpressionTreeNode> fragments, int mode) {
      var visited = new bool[fragments.Count];
      int groups = 0;
      for (int i = 0; i != fragments.Count - 1; ++i) {
        if (visited[i]) continue;
        for (int j = i + 1; j != fragments.Count; ++j) {
          if (visited[j]) continue;
          if (fragments[i].IsSimilarTo(fragments[j], mode)) visited[j] = true;
        }
        ++groups;
      }
      return (double)fragments.Count / groups;
    }
    #endregion
  } //SymbolicExpressionTreeFragmentsAnalyzer
}