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 {
///
/// Evolvability Analyzer
///
[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 RandomParameter {
get { return (LookupParameter)Parameters[RandomParameterName]; }
}
public ValueParameter UpdateIntervalParameter {
get { return (ValueParameter)Parameters[UpdateIntervalParameterName]; }
}
public ValueParameter UpdateCounterParameter {
get { return (ValueParameter)Parameters[UpdateCounterParameterName]; }
}
public ValueParameter ConstantOptimizationIntermediateParentsParameter {
get { return (ValueParameter)Parameters[ConstantOptimizationIntermediateParentsParameterName]; }
}
public IFixedValueParameter ConstantOptimizationEvaluatorParameter {
get { return (IFixedValueParameter)Parameters[ConstantOptimizationEvaluatorParameterName]; }
}
public LookupParameter ResultsParameter {
get { return (LookupParameter)Parameters[ResultsParameterName]; }
}
public IScopeTreeLookupParameter SymbolicExpressionTreeParameter {
get { return (IScopeTreeLookupParameter)Parameters[SymbolicExpressionTreeParameterName]; }
}
public IScopeTreeLookupParameter SymbolicExpressionTreeQualityParameter {
get { return (IScopeTreeLookupParameter)Parameters[SymbolicExpressionTreeQualityParameterName]; }
}
public LookupParameter ElitesParameter {
get { return (LookupParameter)Parameters[ElitesParameterName]; }
}
public LookupParameter PopulationSizeParameter {
get { return (LookupParameter)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(SymbolicExpressionTreeParameterName, "The symbolic expression trees to analyze."));
Parameters.Add(new ScopeTreeLookupParameter(SymbolicExpressionTreeQualityParameterName, "The qualities of the symbolic expression trees"));
Parameters.Add(new ValueParameter(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
Parameters.Add(new ValueParameter(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
Parameters.Add(new ValueLookupParameter(ResultsParameterName, "The results collection where the analysis values should be stored."));
Parameters.Add(new LookupParameter(PopulationSizeParameterName, "The population size."));
Parameters.Add(new LookupParameter(ElitesParameterName, "Number of elites in the population."));
Parameters.Add(new ValueParameter(ConstantOptimizationIntermediateParentsParameterName, "Controls whether or not the constant values of the intermediate nodes should be updated.", new BoolValue(false)));
Parameters.Add(new ValueLookupParameter(RandomParameterName, "The random generator to use."));
Parameters.Add(new FixedValueParameter(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(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(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();
var mutationImprovements = new List();
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();
}
///
/// Evaluate a symbolic expression tree. We perform evaluation by adding a temporary subscope with the tree in it, and calling evaluator.Apply()
///
/// The symbolic expression tree to evaluate
/// The symbolic regression single objective evaluator to use
/// A double value representing the fitness
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; } }
}
}