source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeEvolvabilityAnalyzer.cs @ 9963

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
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;
using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;

namespace HeuristicLab.EvolutionaryTracking {
  /// <summary>
  /// Evolvability Analyzer
  /// </summary>
  [Item("SymbolicExpressionEvolvabilityAnalyzer", "An operator that measures relative improvements obtained by genetic operators and relative reproductive success.")]
  [StorableClass]
  public sealed class SymbolicExpressionEvolvabilityAnalyzer : SingleSuccessorOperator, IAnalyzer {
    #region Parameter names
    private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
    private const string SymbolicExpressionTreeQualityParameterName = "Quality";
    private const string UpdateIntervalParameterName = "UpdateInterval";
    private const string UpdateCounterParameterName = "UpdateCounter";
    private const string ResultsParameterName = "Results";
    private const string PopulationGraphParameterName = "PopulationGraph";
    private const string PopulationSizeParameterName = "PopulationSize";
    private const string ElitesParameterName = "Elites";
    private const string RelativeReproductiveSuccessResultName = "RelativeReproductiveSuccess";
    private const string GeneticOperatorsAverageImprovementResultName = "GeneticOperatorsAverageImprovement";
    private const string ConstantOptimizationIntermediateParentsParameterName = "ConstantOptimizeIntermediateParents";
    private const string ConstantOptimizationEvaluatorParameterName = "ConstantOptimizationOperator";
    private const string RandomParameterName = "Random";
    #endregion

    #region Parameter properties
    public LookupParameter<IRandom> RandomParameter {
      get { return (LookupParameter<IRandom>)Parameters[RandomParameterName]; }
    }
    public ValueParameter<IntValue> UpdateIntervalParameter {
      get { return (ValueParameter<IntValue>)Parameters[UpdateIntervalParameterName]; }
    }
    public ValueParameter<IntValue> UpdateCounterParameter {
      get { return (ValueParameter<IntValue>)Parameters[UpdateCounterParameterName]; }
    }
    public ValueParameter<BoolValue> ConstantOptimizationIntermediateParentsParameter {
      get { return (ValueParameter<BoolValue>)Parameters[ConstantOptimizationIntermediateParentsParameterName]; }
    }
    public IFixedValueParameter<SymbolicRegressionConstantOptimizationEvaluator> ConstantOptimizationEvaluatorParameter {
      get { return (IFixedValueParameter<SymbolicRegressionConstantOptimizationEvaluator>)Parameters[ConstantOptimizationEvaluatorParameterName]; }
    }
    public LookupParameter<ResultCollection> ResultsParameter {
      get { return (LookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
    }
    public IScopeTreeLookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
      get { return (IScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
    }
    public IScopeTreeLookupParameter<DoubleValue> SymbolicExpressionTreeQualityParameter {
      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters[SymbolicExpressionTreeQualityParameterName]; }
    }
    public LookupParameter<IntValue> ElitesParameter {
      get { return (LookupParameter<IntValue>)Parameters[ElitesParameterName]; }
    }
    public LookupParameter<IntValue> PopulationSizeParameter {
      get { return (LookupParameter<IntValue>)Parameters[PopulationSizeParameterName]; }
    }
    #endregion

    #region Parameters
    public IntValue UpdateInterval {
      get { return UpdateIntervalParameter.Value; }
    }
    public IntValue UpdateCounter {
      get { return UpdateCounterParameter.Value; }
    }
    public ResultCollection Results {
      get { return ResultsParameter.ActualValue; }
    }
    public IntValue PopulationSize {
      get { return PopulationSizeParameter.ActualValue; }
    }
    public IntValue Elites {
      get { return ElitesParameter.ActualValue; }
    }
    public BoolValue ConstantOptimizationIntermediateParents {
      get { return ConstantOptimizationIntermediateParentsParameter.Value; }
    }
    public SymbolicRegressionConstantOptimizationEvaluator ConstantOptimizationEvaluator {
      get { return ConstantOptimizationEvaluatorParameter.Value; }
    }
    #endregion

    [StorableConstructor]
    private SymbolicExpressionEvolvabilityAnalyzer(bool deserializing) : base(deserializing) { }
    private SymbolicExpressionEvolvabilityAnalyzer(SymbolicExpressionEvolvabilityAnalyzer original, Cloner cloner) : base(original, cloner) { }
    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicExpressionEvolvabilityAnalyzer(this, cloner); }

    public SymbolicExpressionEvolvabilityAnalyzer() {
      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"));
      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 ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
      Parameters.Add(new LookupParameter<IntValue>(PopulationSizeParameterName, "The population size."));
      Parameters.Add(new LookupParameter<IntValue>(ElitesParameterName, "Number of elites in the population."));
      Parameters.Add(new ValueParameter<BoolValue>(ConstantOptimizationIntermediateParentsParameterName, "Controls whether or not the constant values of the intermediate nodes should be updated.", new BoolValue(false)));
      Parameters.Add(new ValueLookupParameter<IRandom>(RandomParameterName, "The random generator to use."));
      Parameters.Add(new FixedValueParameter<SymbolicRegressionConstantOptimizationEvaluator>(ConstantOptimizationEvaluatorParameterName, "The operator used to perform the constant optimization"));

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

      //Changed the ActualName of the EvaluationPartitionParameter so that it matches the parameter name of symbolic regression problems.
      ConstantOptimizationEvaluator.EvaluationPartitionParameter.ActualName = "FitnessCalculationPartition";
      ConstantOptimizationEvaluator.UpdateConstantsInTree = false;
    }

    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      if (!Parameters.ContainsKey(ConstantOptimizationEvaluatorParameterName)) {
        Parameters.Add(new FixedValueParameter<SymbolicRegressionConstantOptimizationEvaluator>(ConstantOptimizationEvaluatorParameterName, "The operator used to perform the constant optimization"));
        //Changed the ActualName of the EvaluationPartitionParameter so that it matches the parameter name of symbolic regression problems.
        ConstantOptimizationEvaluator.EvaluationPartitionParameter.ActualName = "FitnessCalculationPartition";
        ConstantOptimizationEvaluator.UpdateConstantsInTree = false;
      }

      if (!Parameters.ContainsKey(ConstantOptimizationIntermediateParentsParameterName))
        Parameters.Add(new ValueParameter<BoolValue>(ConstantOptimizationIntermediateParentsParameterName, "Controls whether or not the constant values of the intermediate parents should be updated.", new BoolValue(false)));
    }

    #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++;

      if (UpdateCounter.Value == UpdateInterval.Value) {
        UpdateCounter.Value = 0;
        if (!Results.ContainsKey(PopulationGraphParameterName)) return base.Apply();
        var genealogyGraph = (SymbolicExpressionTreeGenealogyGraph)Results[PopulationGraphParameterName].Value;
        if (genealogyGraph == null) return base.Apply();

        ISymbolicExpressionTree[] trees = SymbolicExpressionTreeParameter.ActualValue.ToArray();
        var currentGen = (from tree in trees
                          select genealogyGraph.GetGraphNodes(tree).Last()).Where(n => n.InEdges != null).ToList();
        var intermediateGen = (from graphNode in currentGen
                               where graphNode.InEdges.Count == 1
                               // mutation
                               let source = (SymbolicExpressionTreeGenealogyGraphNode)graphNode.InEdges[0].Source
                               where graphNode.SymbolicExpressionTree != source.SymbolicExpressionTree // skip elites
                               select source).ToList();
        // currentGen will contain nodes corresponding to individuals in the current generation
        // + intermediate individuals (that were created via crossover, then mutated)
        currentGen.AddRange(intermediateGen);
        currentGen.Sort((a, b) => b.InEdges.Count.CompareTo(a.InEdges.Count)); // sort by InEdge count descending so that crossover offspring are first in the list

        int successfulOffspring = 0;
        var crossoverImprovements = new List<double>();
        var mutationImprovements = new List<double>();

        foreach (var graphNode in currentGen) {
          var quality = graphNode.Quality;
          double parentQuality = 0.0;
          if (graphNode.InEdges == null) throw new Exception("InEdges should not be null.");
          switch (graphNode.InEdges.Count) {
            case 2: {
                parentQuality = graphNode.InEdges.Max(e => ((SymbolicExpressionTreeGenealogyGraphNode)e.Source).Quality);
                crossoverImprovements.Add(quality - parentQuality);
                break;
              }
            case 1: {
                parentQuality = graphNode.InEdges.Max(e => ((SymbolicExpressionTreeGenealogyGraphNode)e.Source).Quality);
                if (ConstantOptimizationIntermediateParents.Value && ConstantOptimizationEvaluator != null) {

                  //Get the optimized fitness of the intermediate parent (without actually updating the constants in the tree)
                  var intermediateParent = ((SymbolicExpressionTreeGenealogyGraphNode)graphNode.InEdges[0].Source).SymbolicExpressionTree;
                  parentQuality = Evaluate(intermediateParent, ConstantOptimizationEvaluator);
                }
                mutationImprovements.Add(quality - parentQuality);
                break;
              }
          }
          if (quality > parentQuality)
            successfulOffspring++;
        }
        // reproductive success
        double reproductiveSuccess = (double)successfulOffspring / (PopulationSize.Value - Elites.Value);
        const string reproductiveSuccessDataTableName = "Reproductive success";
        if (!Results.ContainsKey(RelativeReproductiveSuccessResultName))
          Results.Add(new Result(RelativeReproductiveSuccessResultName, new DataTable(reproductiveSuccessDataTableName)));
        var relativeReproductiveSuccessTable = (DataTable)Results[RelativeReproductiveSuccessResultName].Value;
        if (!relativeReproductiveSuccessTable.Rows.ContainsKey(reproductiveSuccessDataTableName))
          relativeReproductiveSuccessTable.Rows.Add(new DataRow(reproductiveSuccessDataTableName) { VisualProperties = { StartIndexZero = true } });
        relativeReproductiveSuccessTable.Rows[reproductiveSuccessDataTableName].Values.Add(reproductiveSuccess);

        // average and relative number of leaf nodes
        if (!Results.ContainsKey("RelativeProportionOfLeafNodes"))
          Results.Add(new Result("RelativeProportionOfLeafNodes", new DataTable("Proportion of leaf nodes")));
        var relativeProportionOfLeafNodesTable = (DataTable)Results["RelativeProportionOfLeafNodes"].Value;
        if (!relativeProportionOfLeafNodesTable.Rows.ContainsKey("Percent of leaf nodes"))
          relativeProportionOfLeafNodesTable.Rows.Add(new DataRow("Percent of leaf nodes") { VisualProperties = { StartIndexZero = true } });
        if (!relativeProportionOfLeafNodesTable.Rows.ContainsKey("Average number of leafs"))
          relativeProportionOfLeafNodesTable.Rows.Add(new DataRow("Average number of leafs") { VisualProperties = { StartIndexZero = true } });

        double totalNodes = trees.Sum(x => x.Length);
        double totalLeafs = trees.Sum(t => t.IterateNodesPostfix().Count(n => n.SubtreeCount == 0));

        relativeProportionOfLeafNodesTable.Rows["Percent of leaf nodes"].Values.Add(totalLeafs / totalNodes);
        relativeProportionOfLeafNodesTable.Rows["Average number of leafs"].Values.Add(totalLeafs / trees.Length);

        // genetic operators best and average improvement values
        if (!Results.ContainsKey(GeneticOperatorsAverageImprovementResultName)) {
          Results.Add(new Result(GeneticOperatorsAverageImprovementResultName, new DataTable()));
        }
        var table = (DataTable)Results[GeneticOperatorsAverageImprovementResultName].Value;

        double cxAvgImprovement = 0.0;
        double cxMaxImprovement = 0.0;
        if (crossoverImprovements.Count > 0) {
          cxAvgImprovement = crossoverImprovements.Average();
          cxMaxImprovement = crossoverImprovements.Max();
        }
        double mutAvgImprovement = 0.0;
        double mutMaxImprovement = 0.0;
        if (mutationImprovements.Count > 0) {
          mutAvgImprovement = mutationImprovements.Average();
          mutMaxImprovement = mutationImprovements.Max();
        }

        if (!table.Rows.ContainsKey("Average crossover improvement")) {
          table.Rows.Add(new DataRow("Average crossover improvement") { VisualProperties = { StartIndexZero = true } });
        }
        table.Rows["Average crossover improvement"].Values.Add(cxAvgImprovement);

        if (!table.Rows.ContainsKey("Average mutation improvement")) {
          table.Rows.Add(new DataRow("Average mutation improvement") { VisualProperties = { StartIndexZero = true } });
        }
        table.Rows["Average mutation improvement"].Values.Add(mutAvgImprovement);

        if (!table.Rows.ContainsKey("Best crossover improvement")) {
          table.Rows.Add(new DataRow("Best crossover improvement") { VisualProperties = { StartIndexZero = true } });
        }
        table.Rows["Best crossover improvement"].Values.Add(cxMaxImprovement);

        if (!table.Rows.ContainsKey("Best mutation improvement")) {
          table.Rows.Add(new DataRow("Best mutation improvement") { VisualProperties = { StartIndexZero = true } });
        }
        table.Rows["Best mutation improvement"].Values.Add(mutMaxImprovement);

        if (!table.Rows.ContainsKey("Average improvement")) {
          table.Rows.Add(new DataRow("Average improvement") { VisualProperties = { StartIndexZero = true } });
        }
        table.Rows["Average improvement"].Values.Add((cxAvgImprovement + mutAvgImprovement) / 2);

        if (!table.Rows.ContainsKey("Best improvement")) {
          table.Rows.Add(new DataRow("Best improvement") { VisualProperties = { StartIndexZero = true } });
        }
        table.Rows["Best improvement"].Values.Add(Math.Max(cxMaxImprovement, mutMaxImprovement));
      }
      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">The symbolic expression tree to evaluate</param>
    /// <param name="evaluator">The symbolic regression single objective evaluator to use</param>
    /// <returns>A double value representing the fitness</returns>
    private double Evaluate(IItem tree, SymbolicRegressionSingleObjectiveEvaluator evaluator) {
      var subScope = new Scope();
      subScope.Variables.Add(new Variable("SymbolicExpressionTree", tree)); // inject expected variables into the subscope
      ExecutionContext.Scope.SubScopes.Add(subScope);
      var context = new Core.ExecutionContext(ExecutionContext, evaluator, subScope);
      evaluator.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;
    }

    public bool EnabledByDefault { get { return true; } }
  }
}