source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Operators/SymbolicExpressionTreeGenealogyGraphBuilder.cs @ 9082

#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 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>
  /// Builds a genealogy graph of the algorithms population.
  /// </summary>
  [Item("SymbolicExpressionTreeGenealogyGraphBuilder", "An operator that tracks the genealogy of tree individuals")]
  [StorableClass]
  public sealed class SymbolicExpressionTreeGenealogyGraphBuilder : SingleSuccessorOperator {
    #region Parameter names
    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 PopulationGraphParameterName = "PopulationGraph";
    private const string PopulationGraphParameterDescription = "Individual lineages";
    private const string SymbolicExpressionInterpreterParameterName = "SymbolicExpressionTreeInterpreter";
    private const string SymbolicRegressionProblemDataParameterName = "ProblemData";
    private const string SymbolicDataAnalysisProblemEvaluatorParameterName = "Evaluator";
    private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
    private const string SymbolicExpressionTreeQualityParameterName = "Quality";
    #endregion
    #region Parameter properties
    public IScopeTreeLookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
      get { return (IScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
    }
    public IScopeTreeLookupParameter<DoubleValue> SymbolicExpressionTreeQualityParameter {
      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters[SymbolicExpressionTreeQualityParameterName]; }
    }
    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 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 SymbolicExpressionTreeGenealogyGraphBuilder(bool deserializing) : base(deserializing) { }
    private SymbolicExpressionTreeGenealogyGraphBuilder(SymbolicExpressionTreeGenealogyGraphBuilder original, Cloner cloner) : base(original, cloner) { }
    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicExpressionTreeGenealogyGraphBuilder(this, cloner); }
    public SymbolicExpressionTreeGenealogyGraphBuilder()
      : base() {
      #region Add parameters
      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 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"));
      Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression trees to analyze"));
      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(SymbolicExpressionTreeQualityParameterName, "The qualities of the symbolic expression trees"));
      #endregion
    }

    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() { }

    #region IStatefulItem members
    public override void InitializeState() {
      base.InitializeState();
    }

    public override void ClearState() {
      base.ClearState();
    }
    #endregion

    public override IOperation Apply() {
      if (GlobalTraceMap == null) return base.Apply(); // no trace map, no genealogy graph

      if (!Parameters.ContainsKey("Results")) return base.Apply();

      SymbolicExpressionTreeGenealogyGraph graph;
      if (Results.ContainsKey(PopulationGraphParameterName)) {
        graph = (SymbolicExpressionTreeGenealogyGraph)(Results[PopulationGraphParameterName].Value);
      } else {
        graph = new SymbolicExpressionTreeGenealogyGraph();
        Results.Add(new Result(PopulationGraphParameterName, PopulationGraphParameterDescription, graph));
      }

      var trees = SymbolicExpressionTreeParameter.ActualValue.ToArray();
      var qualities = SymbolicExpressionTreeQualityParameter.ActualValue.ToArray();

      if (trees.Length != qualities.Length) throw new Exception("Error: trees and qualities array sizes do not match!");

      // add all individuals to the evolutionary graph
      int generation = Generations.Value;

      var pairs = trees.Zip(qualities, (t, q) => new { Tree = t, Quality = q.Value }).OrderByDescending(x => x.Quality).ToList();

      var graphNodes = new List<SymbolicExpressionGenealogyGraphNode>(
        (from i in Enumerable.Range(0, trees.Length)
         let tree = pairs[i].Tree
         let quality = pairs[i].Quality
         select new SymbolicExpressionGenealogyGraphNode { SymbolicExpressionTree = tree, Quality = quality, Rank = generation, IsElite = i < Elites.Value }
        ).Concat
        (from t in trees
         where GlobalTraceMap.ContainsKey(t)
         let parents = GlobalTraceMap[t]
         where parents.Count == 1 // 1 parent means mutation
         let p = (ISymbolicExpressionTree)parents[0]
         select new SymbolicExpressionGenealogyGraphNode { SymbolicExpressionTree = p, Quality = Evaluate(p), Rank = generation - 0.5 }
        )).ToList();

      foreach (var node in graphNodes) {
        graph.AddNode(node);
      }

      foreach (var node in graphNodes) {
        var tree = node.SymbolicExpressionTree;
        if (!GlobalTraceMap.ContainsKey(tree)) continue;
        var parents = GlobalTraceMap[tree].Cast<ISymbolicExpressionTree>();
        foreach (var p in parents) {
          var nodes = graph.GetGraphNodes(p);
          if (nodes == null) continue;
          var sourceNode = nodes.LastOrDefault(n => n.Rank < node.Rank);
          if (sourceNode == null) continue;
          var arc = new Arc { Source = sourceNode, Target = node, Data = GlobalFragmentMap[tree] };
          sourceNode.AddForwardArc(arc);
          node.AddReverseArc(arc);
        }
      }
      return base.Apply();
    }

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