source: branches/1772_HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/Analyzers/GenealogyAnalyzer.cs @ 17434

#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 License Information

using System.Collections.Generic;
using System.Linq;
using HEAL.Attic;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.EvolutionTracking;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;

[Item("GenealogyAnalyzer", "An analyzer which performs the necessary instrumentation to record the evolution of a genetic algorithm.")]
[StorableType("04001C52-025C-4555-8812-AC3FA26A2B2F")]
public abstract 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
  private const string TrimOlderGenerationsParameterName = "TrimOlderGenerations";
  #endregion parameter names

  #region parameter properties

  public IFixedValueParameter<BoolValue> TrimOlderGenerationsParameter {
    get { return (IFixedValueParameter<BoolValue>)Parameters[TrimOlderGenerationsParameterName]; }
  }

  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 parameter properties

  #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 bool TrimOlderGenerations {
    get { return TrimOlderGenerationsParameter.Value.Value; }
  }
  #endregion properties

  protected 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));
    Parameters.Add(new FixedValueParameter<BoolValue>(TrimOlderGenerationsParameterName, "Remove all the generations older than the last generation from the genealoy graph to save memory."));
    #endregion add parameters
  }

  protected GenealogyAnalyzer(GenealogyAnalyzer<T> original, Cloner cloner)
    : base(original, cloner) {
  }

  [StorableConstructor]
  protected GenealogyAnalyzer(StorableConstructorFlag _) : base(_) { }

  [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."));
    }
    if (!Parameters.ContainsKey(TrimOlderGenerationsParameterName))
      Parameters.Add(new FixedValueParameter<BoolValue>(TrimOlderGenerationsParameterName, "Remove all the generations older than the last generation from the genealoy graph to save memory."));
  }

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

  protected abstract void EvaluateIntermediateChildren();

  public override IOperation Apply() {
    IGenealogyGraph<T> genealogyGraph;
    var results = ResultsParameter.ActualValue;
    if (!results.ContainsKey(PopulationGraphParameterName)) {
      genealogyGraph = new GenealogyGraph<T>();
      results.Add(new Result(PopulationGraphParameterName, genealogyGraph));
    } else {
      genealogyGraph = (IGenealogyGraph<T>)results[PopulationGraphParameterName].Value;
    }

    var population = PopulationParameter.ActualValue;
    var qualities = QualityParameter.ActualValue;

    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;
      // identify previous elite individual
      for (int i = 0; i < population.Length; ++i) {
        if (genealogyGraph.GetByContent(population[i]).Rank.Equals(generation - 1)) {
          elite = population[i];
          index = i;
          break;
        }
      }
      // add current elite and connect with previous
      #region add elite in the graph and connect it with the previous elite
      if (elite != null) {
        var prevVertex = genealogyGraph.GetByContent(elite);
        prevVertex.IsElite = true; // mark elites in the graph retroactively
        var v = (IGenealogyGraphNode<T>)prevVertex.Clone();
        v.Rank = generation;
        v.IsElite = false;
        population[index] = v.Data;
        genealogyGraph.AddVertex(v);
        genealogyGraph.AddArc(prevVertex, v);
        // inject the graph node unique id to the scope
        ExecutionContext.Scope.SubScopes[index].Variables[BeforeManipulatorOperator.ChildParameter.ActualName].Value = v.Data;
        ExecutionContext.Scope.SubScopes[index].Variables["Id"].Value = new StringValue(v.Id);
      }
      #endregion add elite in the graph and connect it with the previous elite
    }
    // update qualities
    for (int i = 0; i < population.Length; ++i) {
      var vertex = genealogyGraph.GetByContent(population[i]);
      vertex.Quality = qualities[i].Value;
    }
    // update qualities for intermediate vertices
    EvaluateIntermediateChildren();

    // remove extra graph nodes (added by the instrumented operators in the case of offspring selection)
    var pop = new HashSet<T>(population);
    var discarded = genealogyGraph.GetByRank(generation).Where(x => !pop.Contains(x.Data)).ToList();
    for (int i = 0; i < discarded.Count; ++i) {
      var v = discarded[i];
      if (v.InDegree == 1) {
        var p = v.Parents.First();
        if (p.Rank.Equals(generation - 0.5))
          // the individual was a product of mutation. since it wasn't selected, we must remove both it and its parent
          // ("intermediate" vertex result of crossover)
          discarded.Add(v.Parents.First());
      }
    }
    genealogyGraph.RemoveVertices(discarded);

    //trim
    if (TrimOlderGenerations) {
      var vertices = genealogyGraph.Vertices.Where(x => x.Rank < generation - 1).ToList(); // select all ranks older than the previous generation
      genealogyGraph.RemoveVertices(vertices);
    }

    return base.Apply();
  }
}