source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/Analyzers/GenealogyAnalyzer.cs @ 11288

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2014 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.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.EvolutionTracking {
  [StorableClass]
  [Item("GenealogyAnalyzer", "An analyzer which performs the necessary instrumentation to record the evolution of a genetic algorithm.")]
  public class GenealogyAnalyzer<T> : SingleSuccessorOperator, IAnalyzer
  where T : class,IItem {
    #region parameter names
    private const string GenerationsParameterName = "Generations";
    private const string ResultsParameterName = "Results";
    private const string PopulationGraphParameterName = "PopulationGraph";
    public const string QualityParameterName = "Quality";
    public const string PopulationParameterName = "SymbolicExpressionTree";

    private const string CrossoverParameterName = "Crossover";
    private const string ManipulatorParameterName = "Mutator";
    private const string SolutionCreatorParameterName = "SolutionCreator";

    private const string BeforeCrossoverOperatorParameterName = "BeforeCrossoverOperator";
    private const string AfterCrossoverOperatorParameterName = "AfterCrossoverOperator";

    private const string BeforeManipulatorOperatorParameterName = "BeforeManipulatorOperator";
    private const string AfterManipulatorOperatorParameterName = "AfterManipulatorOperator";

    private const string EnableCrossoverTrackingParameterName = "EnableCrossoverTracking";
    private const string EnableManipulatorTrackingParameterName = "EnableManipulatorTracking";
    private const string EnableSolutionCreatorTrackingParameterName = "EnableSolutionCreatorTracking"; // should always be enabled. maybe superfluous
    #endregion

    #region parameter properties
    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters[QualityParameterName]; }
    }
    public IScopeTreeLookupParameter<T> PopulationParameter {
      get { return (IScopeTreeLookupParameter<T>)Parameters[PopulationParameterName]; }
    }
    public IValueParameter<ICrossoverOperator<T>> BeforeCrossoverOperatorParameter {
      get { return (IValueParameter<ICrossoverOperator<T>>)Parameters[BeforeCrossoverOperatorParameterName]; }
    }
    public IValueParameter<ICrossoverOperator<T>> AfterCrossoverOperatorParameter {
      get { return (IValueParameter<ICrossoverOperator<T>>)Parameters[AfterCrossoverOperatorParameterName]; }
    }
    public IValueParameter<IManipulatorOperator<T>> BeforeManipulatorOperatorParameter {
      get { return (IValueParameter<IManipulatorOperator<T>>)Parameters[BeforeManipulatorOperatorParameterName]; }
    }
    public IValueParameter<IManipulatorOperator<T>> AfterManipulatorOperatorParameter {
      get { return (IValueParameter<IManipulatorOperator<T>>)Parameters[AfterManipulatorOperatorParameterName]; }
    }
    public ILookupParameter<ResultCollection> ResultsParameter {
      get { return (ILookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
    }
    public ILookupParameter<IntValue> GenerationsParameter {
      get { return (ILookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
    }
    public IValueParameter<BoolValue> EnableCrossoverTrackingParameter {
      get { return (IValueParameter<BoolValue>)Parameters[EnableCrossoverTrackingParameterName]; }
    }
    public IValueParameter<BoolValue> EnableManipulatorTrackingParameter {
      get { return (IValueParameter<BoolValue>)Parameters[EnableManipulatorTrackingParameterName]; }
    }
    public IValueParameter<BoolValue> EnableSolutionCreatorTrackingParameter {
      get { return (IValueParameter<BoolValue>)Parameters[EnableSolutionCreatorTrackingParameterName]; }
    }
    public ILookupParameter<ICrossover> CrossoverParameter {
      get { return (ILookupParameter<ICrossover>)Parameters[CrossoverParameterName]; }
    }
    public ILookupParameter<IManipulator> ManipulatorParameter {
      get { return (ILookupParameter<IManipulator>)Parameters[ManipulatorParameterName]; }
    }

    public ILookupParameter<ISolutionCreator> SolutionCreatorParameter {
      get { return (ILookupParameter<ISolutionCreator>)Parameters[SolutionCreatorParameterName]; }
    }
    #endregion

    #region properties
    public ICrossoverOperator<T> BeforeCrossoverOperator {
      get { return BeforeCrossoverOperatorParameter.Value; }
    }
    public ICrossoverOperator<T> AfterCrossoverOperator {
      get { return AfterCrossoverOperatorParameter.Value; }
    }
    public IManipulatorOperator<T> BeforeManipulatorOperator {
      get { return BeforeManipulatorOperatorParameter.Value; }
    }
    public IManipulatorOperator<T> AfterManipulatorOperator {
      get { return AfterManipulatorOperatorParameter.Value; }
    }
    public BoolValue EnableCrossoverTracking {
      get { return EnableCrossoverTrackingParameter.Value; }
    }
    public BoolValue EnableManipulatorTracking {
      get { return EnableManipulatorTrackingParameter.Value; }
    }
    public BoolValue EnableSolutionCreatorTracking {
      get { return EnableSolutionCreatorTrackingParameter.Value; }
    }

    public IGenealogyGraph<T> GenealogyGraph {
      get {
        IResult result;
        var results = ResultsParameter.ActualValue;
        if (!results.ContainsKey(PopulationGraphParameterName)) {
          result = new Result(PopulationGraphParameterName, new GenealogyGraph<T>());
          results.Add(result);
        } else {
          result = results[PopulationGraphParameterName];
        }
        var graph = (IGenealogyGraph<T>)result.Value;
        return graph;
      }
    }
    #endregion

    public GenealogyAnalyzer() {
      #region add parameters
      // the instrumented operators
      Parameters.Add(new LookupParameter<ICrossover>(CrossoverParameterName, "The crossover operator."));
      Parameters.Add(new LookupParameter<IManipulator>(ManipulatorParameterName, "The manipulator operator."));
      Parameters.Add(new LookupParameter<ISolutionCreator>(SolutionCreatorParameterName, "The solution creator operator."));
      // the analyzer parameters
      Parameters.Add(new ValueParameter<BoolValue>(EnableCrossoverTrackingParameterName, new BoolValue(true)));
      Parameters.Add(new ValueParameter<BoolValue>(EnableManipulatorTrackingParameterName, new BoolValue(true)));
      Parameters.Add(new ValueParameter<BoolValue>(EnableSolutionCreatorTrackingParameterName, new BoolValue(true)));
      // parameters required by the analyzer to do its work
      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
      Parameters.Add(new LookupParameter<ResultCollection>(ResultsParameterName));
      Parameters.Add(new ScopeTreeLookupParameter<T>(PopulationParameterName, "The population of individuals."));
      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(QualityParameterName, "The individual qualities."));
      Parameters.Add(new ValueParameter<ICrossoverOperator<T>>(BeforeCrossoverOperatorParameterName));
      Parameters.Add(new ValueParameter<ICrossoverOperator<T>>(AfterCrossoverOperatorParameterName));
      Parameters.Add(new ValueParameter<IManipulatorOperator<T>>(BeforeManipulatorOperatorParameterName));
      Parameters.Add(new ValueParameter<IManipulatorOperator<T>>(AfterManipulatorOperatorParameterName));
      #endregion
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new GenealogyAnalyzer<T>(this, cloner);
    }
    protected GenealogyAnalyzer(GenealogyAnalyzer<T> original, Cloner cloner)
      : base(original, cloner) {
    }

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

    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      // the instrumented operators
      if (!Parameters.ContainsKey(CrossoverParameterName))
        Parameters.Add(new LookupParameter<ICrossover>(CrossoverParameterName, "The crossover operator."));
      if (!Parameters.ContainsKey(ManipulatorParameterName))
        Parameters.Add(new LookupParameter<IManipulator>(ManipulatorParameterName, "The manipulator operator."));
      if (!Parameters.ContainsKey(SolutionCreatorParameterName))
        Parameters.Add(new LookupParameter<ISolutionCreator>(SolutionCreatorParameterName, "The solution creator operator."));
      // the analyzer parameters
      if (!Parameters.ContainsKey(EnableCrossoverTrackingParameterName))
        Parameters.Add(new ValueParameter<BoolValue>(EnableCrossoverTrackingParameterName, new BoolValue(true)));
      if (!Parameters.ContainsKey(EnableManipulatorTrackingParameterName))
        Parameters.Add(new ValueParameter<BoolValue>(EnableManipulatorTrackingParameterName, new BoolValue(true)));
      if (!Parameters.ContainsKey(EnableSolutionCreatorTrackingParameterName))
        Parameters.Add(new ValueParameter<BoolValue>(EnableSolutionCreatorTrackingParameterName, new BoolValue(true)));
      // parameters required by the analyzer to do its work
      if (!Parameters.ContainsKey(GenerationsParameterName))
        Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
      if (!Parameters.ContainsKey(ResultsParameterName))
        Parameters.Add(new LookupParameter<ResultCollection>(ResultsParameterName));
      if (!Parameters.ContainsKey(PopulationParameterName)) {
        Parameters.Add(new ScopeTreeLookupParameter<T>(PopulationParameterName, "The population of individuals."));
      }
      if (!Parameters.ContainsKey(QualityParameterName)) {
        Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(QualityParameterName, "The individual qualities."));
      }
    }

    public bool EnabledByDefault {
      get { return false; }
    }

    private void ConfigureTrackingOperators() {
      // at the beginning we add the before/after operators to the instrumented operators
      var crossover = CrossoverParameter.ActualValue;
      if (crossover != null) {
        var instrumentedCrossover = (InstrumentedOperator)crossover;
        instrumentedCrossover.AfterExecutionOperators.Clear();
        instrumentedCrossover.BeforeExecutionOperators.Clear();

        if (EnableCrossoverTracking.Value) {
          if (BeforeCrossoverOperator != null) {
            instrumentedCrossover.BeforeExecutionOperators.Add(BeforeCrossoverOperator);
          }
          if (AfterCrossoverOperator != null) {
            instrumentedCrossover.AfterExecutionOperators.Add(AfterCrossoverOperator);
          }
        }
      }
      var manipulator = ManipulatorParameter.ActualValue;
      if (manipulator != null) {
        var instrumentedManipulator = (InstrumentedOperator)manipulator;
        instrumentedManipulator.AfterExecutionOperators.Clear();
        instrumentedManipulator.BeforeExecutionOperators.Clear();

        if (EnableManipulatorTracking.Value) {
          if (BeforeManipulatorOperator != null) {
            instrumentedManipulator.BeforeExecutionOperators.Add(BeforeManipulatorOperator);
          }
          if (AfterManipulatorOperator != null) {
            instrumentedManipulator.AfterExecutionOperators.Add(AfterManipulatorOperator);
          }
        }
      }
    }

    public override IOperation Apply() {
      var population = PopulationParameter.ActualValue;
      var qualities = QualityParameter.ActualValue.ToList();

      int generation = GenerationsParameter.ActualValue.Value;
      if (generation == 0) {
        ConfigureTrackingOperators();

        for (int i = 0; i < population.Length; ++i) {
          var individual = population[i];
          var vertex = new GenealogyGraphNode<T>(individual) { Rank = generation };
          GenealogyGraph.AddVertex(vertex);
          // save the vertex id in the individual scope (so that we can identify graph indices)
          ExecutionContext.Scope.SubScopes[i].Variables.Add(new Variable("Id", new StringValue(vertex.Id)));
        }
      } else {
        int index = 0;
        T elite = null;

        for (int i = 0; i < population.Length; ++i) {
          if (GenealogyGraph.GetByContent(population[i]).Rank.Equals(generation - 1)) {
            elite = population[i];
            index = i;
            break;
          }
        }

        #region add elite in the graph and connect it with the previous elite
        if (elite != null) {
          var prevVertex = (IGenealogyGraphNode<T>)GenealogyGraph.GetByContent(elite);
          prevVertex.IsElite = true; // mark elites in the graph retroactively
          var w = (IGenealogyGraphNode<T>)prevVertex.Clone();
          var v = new GenealogyGraphNode<T>(prevVertex.Data) {
            Rank = generation,
            Quality = prevVertex.Quality,
            IsElite = false
          };

          object data = null;
          if (prevVertex.InArcs.Any())
            data = prevVertex.InArcs.Last().Data;
          var children = prevVertex.Children.ToList();
          var parents = prevVertex.Parents.ToList();

          GenealogyGraph.RemoveVertex(prevVertex);
          GenealogyGraph.AddVertex(w);
          GenealogyGraph.AddVertex(v);
          GenealogyGraph.AddArc(w, v); // connect current elite with previous elite

          // recreate connections after prevVertex was replaced with w
          foreach (var c in children) GenealogyGraph.AddArc(w, c);
          foreach (var p in parents) GenealogyGraph.AddArc(p, w);

          v.InArcs.Last().Data = data;

          if (w.InArcs.Any())
            w.InArcs.Last().Data = data;

          // inject the graph node unique id to the scope
          ExecutionContext.Scope.SubScopes[index].Variables["Id"].Value = new StringValue(v.Id);
        }
        #endregion

        ComputeSuccessRatios();
      }
      // update qualities
      for (int i = 0; i < population.Length; ++i) {
        var vertex = GenealogyGraph.GetByContent(population[i]);
        vertex.Quality = qualities[i].Value;
      }

      // remove extra graph nodes (added by the instrumented operators in the case of offspring selection)
      RemoveUnsuccessfulOffspring();

      return base.Apply();
    }

    private void RemoveUnsuccessfulOffspring() {
      int generation = GenerationsParameter.ActualValue.Value;
      var population = PopulationParameter.ActualValue;
      var discardedOffspring = GenealogyGraph.Ranks[generation].Select(x => (T)x.Data).Except(population).ToList();
      foreach (var vertex in discardedOffspring.Select(individual => GenealogyGraph.GetByContent(individual))) {
        if (vertex.InDegree == 1) {
          var p = vertex.Parents.First();
          if (!p.Rank.Equals(generation - 0.5))
            throw new InvalidOperationException("Parent must be an intermediate vertex");
          GenealogyGraph.RemoveVertex(p);
        }
        GenealogyGraph.RemoveVertex(vertex);
      }
    }

    // this method works when called before the unsuccesful offspring are removed from the genealogy graph
    // so it must always be called before RemoveUnsuccessfulOffspring()
    private void ComputeSuccessRatios() {
      const string successfulOffspringRatioTableHistoryName = "Successful offspring ratios history";
      const string successfulOffspringAbsoluteValuesTableHistoryName = "Successful offspring values history";
      const string successfulOffspringRatioHeatMapName = "Successful offspring ratios heatmap";
      const string successfulOffspringValuesHeatMapName = "Successful offspring values heatmap";

      var population = PopulationParameter.ActualValue;
      var generation = GenerationsParameter.ActualValue.Value;
      // compute the weight of each genealogy graph node as the ratio (produced offspring) / (surviving offspring)
      foreach (var ind in population) {
        var v = GenealogyGraph.GetByContent(ind);
        if (v.Parents.Count() == 1) {
          var p = v.Parents.First();
          foreach (var pp in p.Parents)
            pp.Weight++;
        } else {
          foreach (var p in v.Parents) {
            p.Weight++;
          }
        }
      }

      var results = ResultsParameter.ActualValue;

      DataTableHistory successfulOffspringRatioHistory;
      DataTableHistory successfulOffspringAbsoluteHistory;
      if (!results.ContainsKey(successfulOffspringRatioTableHistoryName)) {
        successfulOffspringRatioHistory = new DataTableHistory();
        successfulOffspringAbsoluteHistory = new DataTableHistory();
        results.Add(new Result(successfulOffspringRatioTableHistoryName, successfulOffspringRatioHistory));
        results.Add(new Result(successfulOffspringAbsoluteValuesTableHistoryName, successfulOffspringAbsoluteHistory));
      } else {
        successfulOffspringRatioHistory = (DataTableHistory)results[successfulOffspringRatioTableHistoryName].Value;
        successfulOffspringAbsoluteHistory = (DataTableHistory)results[successfulOffspringAbsoluteValuesTableHistoryName].Value;
      }
      var successfulOffspringRatioTable = new DataTable();
      var successfulOffspringRatioRow = new DataRow("Successful Offspring Ratio") {
        VisualProperties = { ChartType = DataRowVisualProperties.DataRowChartType.Columns, StartIndexZero = true }
      };
      successfulOffspringRatioRow.Values.Replace(GenealogyGraph.Ranks[generation - 1].OrderByDescending(x => x.Quality).Select(x => x.OutDegree > 0 ? x.Weight / x.OutDegree : 0));
      successfulOffspringRatioTable.Rows.Add(successfulOffspringRatioRow);
      successfulOffspringRatioHistory.Add(successfulOffspringRatioTable);
      // create heatmap
      double[,] ratios = new double[population.Length, successfulOffspringRatioHistory.Count];
      var ratiosHistoryList = successfulOffspringRatioHistory.AsReadOnly().ToList();
      for (int i = 0; i < ratiosHistoryList.Count; ++i) {
        var values = ratiosHistoryList[i].Rows.First().Values;
        for (int j = 0; j < values.Count; ++j) {
          ratios[j, i] = values[j];
        }
      }
      var successfulOffspringRatios = new HeatMap(ratios);
      if (!results.ContainsKey(successfulOffspringRatioHeatMapName)) {
        results.Add(new Result(successfulOffspringRatioHeatMapName, successfulOffspringRatios));
      } else {
        results[successfulOffspringRatioHeatMapName].Value = successfulOffspringRatios;
      }

      var successfulOffspringValuesTable = new DataTable();
      var successfulOffspringValuesRow = new DataRow("Successful Offspring Values") {
        VisualProperties = { ChartType = DataRowVisualProperties.DataRowChartType.Columns, StartIndexZero = true }
      };
      successfulOffspringValuesRow.Values.Replace(GenealogyGraph.Ranks[generation - 1].OrderByDescending(x => x.Quality).Select(x => x.Weight));
      successfulOffspringValuesTable.Rows.Add(successfulOffspringValuesRow);
      successfulOffspringAbsoluteHistory.Add(successfulOffspringValuesTable);
      // create heatmap
      double min = 0, max = 0;
      double[,] elements = new double[population.Length, successfulOffspringAbsoluteHistory.Count];
      var absoluteHistoryList = successfulOffspringAbsoluteHistory.AsReadOnly().ToList();
      for (int i = 0; i < absoluteHistoryList.Count; ++i) {
        var values = absoluteHistoryList[i].Rows.First().Values;
        for (int j = 0; j < values.Count; ++j) {
          elements[j, i] = values[j];
          if (max < values[j])
            max = values[j];
          if (min > values[j])
            min = values[j];
        }
      }
      var heatmap = new HeatMap(elements);
      heatmap.Maximum = max;
      heatmap.Minimum = min;
      if (!results.ContainsKey(successfulOffspringValuesHeatMapName)) {
        results.Add(new Result(successfulOffspringValuesHeatMapName, heatmap));
      } else {
        results[successfulOffspringValuesHeatMapName].Value = heatmap;
      }
    }
  }
}