#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 .
*/
#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 : 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 QualityParameter {
get { return (IScopeTreeLookupParameter)Parameters[QualityParameterName]; }
}
public IScopeTreeLookupParameter PopulationParameter {
get { return (IScopeTreeLookupParameter)Parameters[PopulationParameterName]; }
}
public IValueParameter> BeforeCrossoverOperatorParameter {
get { return (IValueParameter>)Parameters[BeforeCrossoverOperatorParameterName]; }
}
public IValueParameter> AfterCrossoverOperatorParameter {
get { return (IValueParameter>)Parameters[AfterCrossoverOperatorParameterName]; }
}
public IValueParameter> BeforeManipulatorOperatorParameter {
get { return (IValueParameter>)Parameters[BeforeManipulatorOperatorParameterName]; }
}
public IValueParameter> AfterManipulatorOperatorParameter {
get { return (IValueParameter>)Parameters[AfterManipulatorOperatorParameterName]; }
}
public ILookupParameter ResultsParameter {
get { return (ILookupParameter)Parameters[ResultsParameterName]; }
}
public ILookupParameter GenerationsParameter {
get { return (ILookupParameter)Parameters[GenerationsParameterName]; }
}
public IValueParameter EnableCrossoverTrackingParameter {
get { return (IValueParameter)Parameters[EnableCrossoverTrackingParameterName]; }
}
public IValueParameter EnableManipulatorTrackingParameter {
get { return (IValueParameter)Parameters[EnableManipulatorTrackingParameterName]; }
}
public IValueParameter EnableSolutionCreatorTrackingParameter {
get { return (IValueParameter)Parameters[EnableSolutionCreatorTrackingParameterName]; }
}
public ILookupParameter CrossoverParameter {
get { return (ILookupParameter)Parameters[CrossoverParameterName]; }
}
public ILookupParameter ManipulatorParameter {
get { return (ILookupParameter)Parameters[ManipulatorParameterName]; }
}
public ILookupParameter SolutionCreatorParameter {
get { return (ILookupParameter)Parameters[SolutionCreatorParameterName]; }
}
#endregion
#region properties
public ICrossoverOperator BeforeCrossoverOperator {
get { return BeforeCrossoverOperatorParameter.Value; }
}
public ICrossoverOperator AfterCrossoverOperator {
get { return AfterCrossoverOperatorParameter.Value; }
}
public IManipulatorOperator BeforeManipulatorOperator {
get { return BeforeManipulatorOperatorParameter.Value; }
}
public IManipulatorOperator 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 GenealogyGraph {
get {
IResult result;
var results = ResultsParameter.ActualValue;
if (!results.ContainsKey(PopulationGraphParameterName)) {
result = new Result(PopulationGraphParameterName, new GenealogyGraph());
results.Add(result);
} else {
result = results[PopulationGraphParameterName];
}
var graph = (IGenealogyGraph)result.Value;
return graph;
}
}
#endregion
public GenealogyAnalyzer() {
#region add parameters
// the instrumented operators
Parameters.Add(new LookupParameter(CrossoverParameterName, "The crossover operator."));
Parameters.Add(new LookupParameter(ManipulatorParameterName, "The manipulator operator."));
Parameters.Add(new LookupParameter(SolutionCreatorParameterName, "The solution creator operator."));
// the analyzer parameters
Parameters.Add(new ValueParameter(EnableCrossoverTrackingParameterName, new BoolValue(true)));
Parameters.Add(new ValueParameter(EnableManipulatorTrackingParameterName, new BoolValue(true)));
Parameters.Add(new ValueParameter(EnableSolutionCreatorTrackingParameterName, new BoolValue(true)));
// parameters required by the analyzer to do its work
Parameters.Add(new LookupParameter(GenerationsParameterName, "The number of generations so far."));
Parameters.Add(new LookupParameter(ResultsParameterName));
Parameters.Add(new ScopeTreeLookupParameter(PopulationParameterName, "The population of individuals."));
Parameters.Add(new ScopeTreeLookupParameter(QualityParameterName, "The individual qualities."));
Parameters.Add(new ValueParameter>(BeforeCrossoverOperatorParameterName));
Parameters.Add(new ValueParameter>(AfterCrossoverOperatorParameterName));
Parameters.Add(new ValueParameter>(BeforeManipulatorOperatorParameterName));
Parameters.Add(new ValueParameter>(AfterManipulatorOperatorParameterName));
#endregion
}
public override IDeepCloneable Clone(Cloner cloner) {
return new GenealogyAnalyzer(this, cloner);
}
protected GenealogyAnalyzer(GenealogyAnalyzer 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(CrossoverParameterName, "The crossover operator."));
if (!Parameters.ContainsKey(ManipulatorParameterName))
Parameters.Add(new LookupParameter(ManipulatorParameterName, "The manipulator operator."));
if (!Parameters.ContainsKey(SolutionCreatorParameterName))
Parameters.Add(new LookupParameter(SolutionCreatorParameterName, "The solution creator operator."));
// the analyzer parameters
if (!Parameters.ContainsKey(EnableCrossoverTrackingParameterName))
Parameters.Add(new ValueParameter(EnableCrossoverTrackingParameterName, new BoolValue(true)));
if (!Parameters.ContainsKey(EnableManipulatorTrackingParameterName))
Parameters.Add(new ValueParameter(EnableManipulatorTrackingParameterName, new BoolValue(true)));
if (!Parameters.ContainsKey(EnableSolutionCreatorTrackingParameterName))
Parameters.Add(new ValueParameter(EnableSolutionCreatorTrackingParameterName, new BoolValue(true)));
// parameters required by the analyzer to do its work
if (!Parameters.ContainsKey(GenerationsParameterName))
Parameters.Add(new LookupParameter(GenerationsParameterName, "The number of generations so far."));
if (!Parameters.ContainsKey(ResultsParameterName))
Parameters.Add(new LookupParameter(ResultsParameterName));
if (!Parameters.ContainsKey(PopulationParameterName)) {
Parameters.Add(new ScopeTreeLookupParameter(PopulationParameterName, "The population of individuals."));
}
if (!Parameters.ContainsKey(QualityParameterName)) {
Parameters.Add(new ScopeTreeLookupParameter(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(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)GenealogyGraph.GetByContent(elite);
prevVertex.IsElite = true; // mark elites in the graph retroactively
var w = (IGenealogyGraphNode)prevVertex.Clone();
var v = new GenealogyGraphNode(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);
}
}
private void ComputeSuccessRatios() {
const string successfulOffspringRatioTableHistoryName = "Successful offspring ratio";
const string successfulOffspringRatioHeatMapName = "Successful offspring ratio 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);
foreach (var p in v.Parents)
p.Weight++;
}
foreach (var v in GenealogyGraph.Ranks[generation - 1]) {
if (v.OutDegree > 0)
v.Weight /= v.OutDegree;
}
var results = ResultsParameter.ActualValue;
DataTableHistory history;
if (!results.ContainsKey(successfulOffspringRatioTableHistoryName)) {
history = new DataTableHistory();
results.Add(new Result(successfulOffspringRatioTableHistoryName, history));
} else {
history = (DataTableHistory)results[successfulOffspringRatioTableHistoryName].Value;
}
var table = new DataTable();
var row = new DataRow("Successful Offspring") {
VisualProperties = { ChartType = DataRowVisualProperties.DataRowChartType.Columns, StartIndexZero = true }
};
row.Values.Replace(GenealogyGraph.Ranks[generation - 1].OrderByDescending(x => x.Quality).Select(x => x.Weight));
table.Rows.Add(row);
history.Add(table);
double[,] elements = new double[population.Length, history.Count];
var col = history.AsReadOnly().ToList();
for (int i = 0; i < col.Count; ++i) {
var values = col[i].Rows.First().Values;
for (int j = 0; j < values.Count; ++j) {
elements[j, i] = values[j];
}
}
var heatmap = new HeatMap(elements);
if (!results.ContainsKey(successfulOffspringRatioHeatMapName)) {
results.Add(new Result(successfulOffspringRatioHeatMapName, heatmap));
} else {
results[successfulOffspringRatioHeatMapName].Value = heatmap;
}
}
}
}