source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs @ 8249

#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.Drawing;
using System.Globalization;
using System.Linq;
using System.Text;
using System.Threading;
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;
using HeuristicLab.Problems.DataAnalysis;
using HeuristicLab.Problems.DataAnalysis.Symbolic;
// 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 tracks the genealogy of every individual
  /// </summary>
  [Item("SymbolicExpressionTreeGenealogyAnalyzer", "An operator that tracks tree lengths of Symbolic Expression Trees")]
  [StorableClass]
  public sealed class SymbolicExpressionTreeGenealogyAnalyzer : SingleSuccessorOperator, IAnalyzer {
    private const string UpdateIntervalParameterName = "UpdateInterval";
    private const string UpdateCounterParameterName = "UpdateCounter";
    private const string ResultsParameterName = "Results";
    private const string ElitesParameterName = "Elites";
    private const string GenerationsParameterName = "Generations";
    private const string MaximumGenerationsParameterName = "MaximumGenerations";
    private const string MaximumSelectionPressureParameterName = "MaximumSelectionPressure";
    private const string SelectionPressureParameterName = "SelectionPressure";
    private const string GlobalTraceMapParameterName = "GlobalTraceMap";
    private const string GlobalCloneMapParameterName = "GlobalCloneMap";
    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
    private const string PopulationGraphResultParameterName = "PopulationGraph";
    private const string PopulationGraphResultParameterDescription = "Individual lineages";
    private const string SymbolicExpressionInterpreterParameterName = "SymbolicExpressionTreeInterpreter";
    private const string SymbolicRegressionProblemDataParameterName = "ProblemData";
    private const string SymbolicDataAnalysisProblemEvaluatorParameterName = "Evaluator";

    #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<IntValue> ElitesParameter {
      get { return (LookupParameter<IntValue>)Parameters[ElitesParameterName]; }
    }
    public LookupParameter<IntValue> GenerationsParameter {
      get { return (LookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
    }
    public LookupParameter<IntValue> MaximumGenerationsParameter {
      get { return (LookupParameter<IntValue>)Parameters[MaximumGenerationsParameterName]; }
    }
    public LookupParameter<DoubleValue> SelectionPressureParameter {
      get { return (LookupParameter<DoubleValue>)Parameters[SelectionPressureParameterName]; }
    }
    public LookupParameter<DoubleValue> MaximumSelectionPressureParameter {
      get { return (LookupParameter<DoubleValue>)Parameters[MaximumSelectionPressureParameterName]; }
    }
    // problem data, interpreter and evaluator
    public LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter> SymbolicExpressionInterpreterParameter {
      get { return (LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>)Parameters[SymbolicExpressionInterpreterParameterName]; }
    }
    public LookupParameter<RegressionProblemData> SymbolicRegressionProblemDataParameter {
      get { return (LookupParameter<RegressionProblemData>)Parameters[SymbolicRegressionProblemDataParameterName]; }
    }
    public LookupParameter<IEvaluator> SymbolicDataAnalysisProblemEvaluatorParameter {
      get { return (LookupParameter<IEvaluator>)Parameters[SymbolicDataAnalysisProblemEvaluatorParameterName]; }
    }
    // genealogy global parameters
    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]; }
    }
    #endregion
    #region Properties
    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 IntValue Elites {
      get { return ElitesParameter.ActualValue; }
    }
    public IntValue Generations {
      get { return GenerationsParameter.ActualValue; }
    }
    public IntValue MaximumGenerations {
      get { return MaximumGenerationsParameter.ActualValue; }
    }
    public DoubleValue SelectionPressure {
      get { return SelectionPressureParameter.ActualValue; }
    }
    public DoubleValue MaximumSelectionPressure {
      get { return MaximumSelectionPressureParameter.ActualValue; }
    }
    public CloneMapType GlobalCloneMap {
      get { return GlobalCloneMapParameter.ActualValue; }
    }
    public TraceMapType GlobalTraceMap {
      get { return GlobalTraceMapParameter.ActualValue; }
    }
    public CloneMapType GlobalFragmentMap {
      get { return GlobalFragmentMapParameter.ActualValue; }
    }
    public SymbolicDataAnalysisExpressionTreeInterpreter SymbolicExpressionInterpreter {
      get { return SymbolicExpressionInterpreterParameter.ActualValue; }
    }
    public RegressionProblemData SymbolicRegressionProblemData {
      get { return SymbolicRegressionProblemDataParameter.ActualValue; }
    }
    public IEvaluator SymbolicDataAnalysisEvaluator {
      get { return SymbolicDataAnalysisProblemEvaluatorParameter.ActualValue; }
    }
    #endregion

    [StorableConstructor]
    private SymbolicExpressionTreeGenealogyAnalyzer(bool deserializing)
      : base() {
    }
    private SymbolicExpressionTreeGenealogyAnalyzer(SymbolicExpressionTreeGenealogyAnalyzer original, Cloner cloner)
      : base(original, cloner) {
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new SymbolicExpressionTreeGenealogyAnalyzer(this, cloner);
    }
    public SymbolicExpressionTreeGenealogyAnalyzer()
      : base() {
      Parameters.Add(new LookupParameter<IntValue>(ElitesParameterName, "The number of elites."));
      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
      Parameters.Add(new LookupParameter<IntValue>(MaximumGenerationsParameterName, "The maximum number of generations"));
      Parameters.Add(new LookupParameter<DoubleValue>(SelectionPressureParameterName, "The current selection (ony for OSGA)"));
      Parameters.Add(new LookupParameter<DoubleValue>(MaximumSelectionPressureParameterName, "Maximum allowed value of selection pressure."));
      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<SymbolicDataAnalysisExpressionTreeInterpreter>(SymbolicExpressionInterpreterParameterName, "Interpreter for symbolic expression trees"));
      Parameters.Add(new LookupParameter<RegressionProblemData>(SymbolicRegressionProblemDataParameterName, "The symbolic data analysis problem."));
      Parameters.Add(new LookupParameter<IEvaluator>(SymbolicDataAnalysisProblemEvaluatorParameterName, "The fitness evaluator"));

      UpdateCounterParameter.Hidden = true;
      UpdateIntervalParameter.Hidden = true;
    }

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

    #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() {
      UpdateCounter.Value++;
      // the analyzer runs periodically, every 'updateInterval' times
      if (UpdateCounter.Value == UpdateInterval.Value) {
        UpdateCounter.Value = 0; // reset counter

        var gScope = ExecutionContext.Scope;
        while (gScope.Parent != null) gScope = gScope.Parent;
        SymbolicExpressionTreeGenealogyGraph graph;
        if (!Results.ContainsKey(PopulationGraphResultParameterName)) {
          graph = new SymbolicExpressionTreeGenealogyGraph();
          Results.Add(new Result(PopulationGraphResultParameterName, PopulationGraphResultParameterDescription, graph));
        } else {
          graph = (SymbolicExpressionTreeGenealogyGraph)(Results[PopulationGraphResultParameterName].Value);
        }
        // get tree quality values (Key => Individual, Value => Quality)
        var scopes = (from s in gScope.SubScopes
                      let individual = s.Variables.First().Value
                      let quality = (DoubleValue)s.Variables["Quality"].Value
                      orderby quality.Value descending
                      select new { Tree = (ISymbolicExpressionTree)individual, Quality = quality.Value }).ToList();

        // add all individuals to the evolutionary graph
        int generation = Generations.Value;
        // add nodes to genealogy graph
        for (int i = 0; i != scopes.Count; ++i) {
          var indiv = scopes[i].Tree;
          var label = (generation * scopes.Count + i + 1).ToString(CultureInfo.InvariantCulture);
          if (!graph.HasNode(indiv)) {
            var node = new GenealogyGraphNode(indiv) { Label = label };
            graph.AddNode(node);
            // node metadata
            graph[node].Ranks.Add(generation);
            graph[node].Quality = scopes[i].Quality;
            graph[node].IsElite = i < Elites.Value;
          } else {
            var node = graph.GetNode(indiv);
            graph[node].Ranks.Add(generation);
          }
          if (generation == 0) continue;
          if (!GlobalTraceMap.ContainsKey(indiv)) continue;

          var parents = GlobalTraceMap[indiv].Cast<ISymbolicExpressionTree>();
          foreach (var parent in parents) {
            object data = ((GenericWrapper<SymbolicExpressionTreeNode>)GlobalFragmentMap[indiv]).Content;
            if (GlobalTraceMap.ContainsKey(parent)) {
              var node = new GenealogyGraphNode(parent) { Label = "X" };
              graph.AddNode(node);
              graph[node].Quality = Evaluate(parent);
              graph[node].Ranks.Add(generation - 0.5);
              var pp = GlobalTraceMap[parent].Cast<SymbolicExpressionTree>();
              foreach (var p in pp) {
                data = ((GenericWrapper<SymbolicExpressionTreeNode>)GlobalFragmentMap[parent]).Content;
                graph.AddArc(p, parent, null, data);
              }
            }
            graph.AddArc(parent, indiv, null, data);
          }
        }
        // clear trace and clone maps in preparation for the next generation
        if (generation == 0) return base.Apply();
        if (this.Successor == null || !(this.Successor is SymbolicExpressionTreeFragmentsAnalyzer)) {
          GlobalTraceMap.Clear();
          GlobalCloneMap.Clear();
          GlobalFragmentMap.Clear();
        }
      }
      return base.Apply();
    }

    private double Evaluate(ISymbolicExpressionTree tree) {
      // we perform evaluation by adding a temporary subscope with the tree in it, and calling evaluator.Apply()
      var subScope = new Scope();
      // inject expected variables into the subscope
      subScope.Variables.Add(new Core.Variable("SymbolicExpressionTree", tree));
      ExecutionContext.Scope.SubScopes.Add(subScope);
      var context = new Core.ExecutionContext(ExecutionContext, SymbolicDataAnalysisEvaluator, subScope);
      SymbolicDataAnalysisEvaluator.Execute(context, new CancellationToken());
      // get the quality
      double quality = ((DoubleValue)subScope.Variables["Quality"].Value).Value;
      // remove the subscope
      ExecutionContext.Scope.SubScopes.Remove(subScope);
      return quality;
    }

    #region Export to dot file
    private static void WriteDot(string path, SymbolicExpressionTreeGenealogyGraph graph) {
      using (var file = new System.IO.StreamWriter(path)) {
        string nl = Environment.NewLine;
        file.WriteLine("digraph \"lineage " + graph.AverageDegree.ToString(CultureInfo.InvariantCulture) + "\" {" + nl + "ratio=auto;" + nl + "mincross=2.0");
        file.WriteLine("\tnode [shape=circle,label=\"\",style=filled]");

        foreach (var node in graph.Values) {
          var color = Color.FromArgb((int)((1 - graph[node].Quality) * 255), (int)(graph[node].Quality * 255), 0);
          string fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", color.R, color.G, color.B);
          string shape = "circle";
          if (graph[node].IsElite)
            shape = "doublecircle";
          file.WriteLine("\t\"" + node.Id + "\" [shape=" + shape + ",fillcolor=\"" + fillColor + "\",label=\"" + node.Label + "\"];");
          if (node.InEdges == null)
            continue;
          foreach (var edge in node.InEdges) {
            //var edgeStyle = node.InEdges.Count == 1 ? "dashed" : String.Empty;
            var edgeStyle = String.Empty;
            file.WriteLine("\t\"" + edge.Target.Id + "\" -> \"" + node.Id + "\" [arrowsize=.5, color=\"" + fillColor + "\", style=\"" + edgeStyle + "\"];");
          }
        }
        foreach (var g in graph.Values.GroupBy(x => graph[x].Ranks[0])) {
          var sb = new StringBuilder();
          sb.Append("\t{rank=same;");
          foreach (var node in g)
            sb.Append("\"" + node.Id + "\" ");
          sb.Append("}\n");
          file.Write(sb.ToString());
        }
        file.WriteLine("}");
      }
    }
    #endregion
  }
}