#region License Information
/* HeuristicLab
* Copyright (C) 2002-2012 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 System.Threading;
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;
using HeuristicLab.Problems.DataAnalysis.Symbolic;
// type definitions for ease of use
using CloneMapType = HeuristicLab.Core.ItemDictionary;
using TraceMapType = HeuristicLab.Core.ItemDictionary>;
namespace HeuristicLab.EvolutionaryTracking {
///
/// Builds a genealogy graph of the algorithms population.
///
[Item("SymbolicExpressionTreeGenealogyGraphBuilder", "An operator that tracks the genealogy of tree individuals")]
[StorableClass]
public sealed class SymbolicExpressionTreeGenealogyGraphBuilder : SingleSuccessorOperator {
#region Parameter names
private const string ResultsParameterName = "Results";
private const string ElitesParameterName = "Elites";
private const string GenerationsParameterName = "Generations";
private const string MaximumGenerationsParameterName = "MaximumGenerations";
private const string MaximumSelectionPressureParameterName = "MaximumSelectionPressure";
private const string SelectionPressureParameterName = "SelectionPressure";
private const string GlobalTraceMapParameterName = "GlobalTraceMap";
private const string GlobalCloneMapParameterName = "GlobalCloneMap";
private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
private const string PopulationGraphParameterName = "PopulationGraph";
private const string PopulationGraphParameterDescription = "Individual lineages";
private const string SymbolicExpressionInterpreterParameterName = "SymbolicExpressionTreeInterpreter";
private const string SymbolicRegressionProblemDataParameterName = "ProblemData";
private const string SymbolicDataAnalysisProblemEvaluatorParameterName = "Evaluator";
private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
private const string SymbolicExpressionTreeQualityParameterName = "Quality";
#endregion
#region Parameters
public IScopeTreeLookupParameter SymbolicExpressionTreeParameter {
get { return (IScopeTreeLookupParameter)Parameters[SymbolicExpressionTreeParameterName]; }
}
public IScopeTreeLookupParameter SymbolicExpressionTreeQualityParameter {
get { return (IScopeTreeLookupParameter)Parameters[SymbolicExpressionTreeQualityParameterName]; }
}
public LookupParameter ResultsParameter {
get { return (LookupParameter)Parameters[ResultsParameterName]; }
}
public LookupParameter ElitesParameter {
get { return (LookupParameter)Parameters[ElitesParameterName]; }
}
public LookupParameter GenerationsParameter {
get { return (LookupParameter)Parameters[GenerationsParameterName]; }
}
public LookupParameter MaximumGenerationsParameter {
get { return (LookupParameter)Parameters[MaximumGenerationsParameterName]; }
}
public LookupParameter SelectionPressureParameter {
get { return (LookupParameter)Parameters[SelectionPressureParameterName]; }
}
public LookupParameter MaximumSelectionPressureParameter {
get { return (LookupParameter)Parameters[MaximumSelectionPressureParameterName]; }
}
// problem data, interpreter and evaluator
public LookupParameter SymbolicExpressionInterpreterParameter {
get { return (LookupParameter)Parameters[SymbolicExpressionInterpreterParameterName]; }
}
public LookupParameter SymbolicRegressionProblemDataParameter {
get { return (LookupParameter)Parameters[SymbolicRegressionProblemDataParameterName]; }
}
public LookupParameter SymbolicDataAnalysisProblemEvaluatorParameter {
get { return (LookupParameter)Parameters[SymbolicDataAnalysisProblemEvaluatorParameterName]; }
}
// genealogy global parameters
public LookupParameter GlobalTraceMapParameter {
get { return (LookupParameter)Parameters[GlobalTraceMapParameterName]; }
}
public LookupParameter GlobalCloneMapParameter {
get { return (LookupParameter)Parameters[GlobalCloneMapParameterName]; }
}
public LookupParameter GlobalFragmentMapParameter {
get { return (LookupParameter)Parameters[GlobalFragmentMapParameterName]; }
}
#endregion
#region Parameter properties
public bool EnabledByDefault {
get { return true; }
}
public ResultCollection Results {
get { return ResultsParameter.ActualValue; }
}
public IntValue Elites {
get { return ElitesParameter.ActualValue; }
}
public IntValue Generations {
get { return GenerationsParameter.ActualValue; }
}
public IntValue MaximumGenerations {
get { return MaximumGenerationsParameter.ActualValue; }
}
public DoubleValue SelectionPressure {
get { return SelectionPressureParameter.ActualValue; }
}
public DoubleValue MaximumSelectionPressure {
get { return MaximumSelectionPressureParameter.ActualValue; }
}
public CloneMapType GlobalCloneMap {
get { return GlobalCloneMapParameter.ActualValue; }
}
public TraceMapType GlobalTraceMap {
get { return GlobalTraceMapParameter.ActualValue; }
}
public CloneMapType GlobalFragmentMap {
get { return GlobalFragmentMapParameter.ActualValue; }
}
public SymbolicDataAnalysisExpressionTreeInterpreter SymbolicExpressionInterpreter {
get { return SymbolicExpressionInterpreterParameter.ActualValue; }
}
public RegressionProblemData SymbolicRegressionProblemData {
get { return SymbolicRegressionProblemDataParameter.ActualValue; }
}
public IEvaluator SymbolicDataAnalysisEvaluator {
get { return SymbolicDataAnalysisProblemEvaluatorParameter.ActualValue; }
}
#endregion
[StorableConstructor]
private SymbolicExpressionTreeGenealogyGraphBuilder(bool deserializing) : base(deserializing) { }
private SymbolicExpressionTreeGenealogyGraphBuilder(SymbolicExpressionTreeGenealogyGraphBuilder original, Cloner cloner) : base(original, cloner) { }
public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicExpressionTreeGenealogyGraphBuilder(this, cloner); }
public SymbolicExpressionTreeGenealogyGraphBuilder()
: base() {
#region Add parameters
Parameters.Add(new LookupParameter(ElitesParameterName, "The number of elites."));
Parameters.Add(new LookupParameter(GenerationsParameterName, "The number of generations so far."));
Parameters.Add(new LookupParameter(MaximumGenerationsParameterName, "The maximum number of generations"));
Parameters.Add(new LookupParameter(SelectionPressureParameterName, "The current selection (ony for OSGA)"));
Parameters.Add(new LookupParameter(MaximumSelectionPressureParameterName, "Maximum allowed value of selection pressure."));
Parameters.Add(new LookupParameter(GlobalTraceMapParameterName, "A global cache containing the whole genealogy."));
Parameters.Add(new LookupParameter(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
Parameters.Add(new LookupParameter(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
Parameters.Add(new ValueLookupParameter(ResultsParameterName, "The results collection where the analysis values should be stored."));
Parameters.Add(new LookupParameter(SymbolicExpressionInterpreterParameterName, "Interpreter for symbolic expression trees"));
Parameters.Add(new LookupParameter(SymbolicRegressionProblemDataParameterName, "The symbolic data analysis problem."));
Parameters.Add(new LookupParameter(SymbolicDataAnalysisProblemEvaluatorParameterName, "The fitness evaluator"));
Parameters.Add(new ScopeTreeLookupParameter(SymbolicExpressionTreeParameterName, "The symbolic expression trees to analyze"));
Parameters.Add(new ScopeTreeLookupParameter(SymbolicExpressionTreeQualityParameterName, "The qualities of the symbolic expression trees"));
#endregion
}
[StorableHook(HookType.AfterDeserialization)]
private void AfterDeserialization() { }
#region IStatefulItem members
public override void InitializeState() {
base.InitializeState();
}
public override void ClearState() {
base.ClearState();
}
#endregion
public override IOperation Apply() {
if (!Parameters.ContainsKey("Results")) return base.Apply();
SymbolicExpressionTreeGenealogyGraph graph;
if (Results.ContainsKey(PopulationGraphParameterName)) {
graph = (SymbolicExpressionTreeGenealogyGraph)(Results[PopulationGraphParameterName].Value);
} else {
graph = new SymbolicExpressionTreeGenealogyGraph();
Results.Add(new Result(PopulationGraphParameterName, PopulationGraphParameterDescription, graph));
}
var trees = SymbolicExpressionTreeParameter.ActualValue.ToArray();
var qualities = SymbolicExpressionTreeQualityParameter.ActualValue.ToArray();
if (trees.Length != qualities.Length)
throw new Exception("Error: trees and qualities array sizes do not match!");
// add all individuals to the evolutionary graph
int generation = Generations.Value;
var pairs = trees.Zip(qualities, (t, q) => new { Tree = t, Quality = q.Value }).OrderByDescending(x => x.Quality).ToList();
if (generation == 0) {
// add the trees in the graph and return
foreach (var pair in pairs) {
var tree = pair.Tree;
var quality = pair.Quality;
graph.AddNode(new SymbolicExpressionGenealogyGraphNode {
SymbolicExpressionTree = tree,
Quality = quality,
Rank = generation
});
}
return base.Apply();
}
var graphNodes = (from i in Enumerable.Range(0, trees.Length)
let tree = pairs[i].Tree
let quality = pairs[i].Quality
select new SymbolicExpressionGenealogyGraphNode {
SymbolicExpressionTree = tree,
Quality = quality,
Rank = generation,
IsElite = i < Elites.Value
}).Concat
// the following query addds the intermediate nodes that were created when
// crossover was followed by mutation (they are not present in the scope)
(from t in trees
where GlobalTraceMap.ContainsKey(t)
let parents = GlobalTraceMap[t]
where parents.Count == 1
// 1 parent means mutation
let p = (ISymbolicExpressionTree)parents[0]
select new SymbolicExpressionGenealogyGraphNode {
SymbolicExpressionTree = p,
Quality = Evaluate(p),
Rank = generation - 0.5
// an intermediate parent that would normally be 'invisible' to the evolutionary process
}
).ToList();
foreach (var node in graphNodes) {
graph.AddNode(node);
}
graphNodes.Sort((a, b) => b.Rank.CompareTo(a.Rank));
foreach (var node in graphNodes) {
var tree = node.SymbolicExpressionTree;
if (!GlobalTraceMap.ContainsKey(tree)) {
var nodes = graph.GetGraphNodes(tree);
if (nodes.Count > 1) {
// link elites from previous generation
var last = nodes[nodes.Count - 2];
var arc = new Arc { Source = last, Target = node, Data = new Fragment { Root = null } };
last.AddForwardArc(arc);
node.AddReverseArc(arc);
}
continue;
}
var parents = GlobalTraceMap[tree].Cast().ToList();
var fragment = GlobalFragmentMap[tree];
foreach (var p in parents) {
var nodes = graph.GetGraphNodes(p);
if (nodes == null) {
throw new Exception("Node cannot have no parents");
}
var sourceNode = nodes.LastOrDefault(n => n.Rank < node.Rank);
if (sourceNode == null) {
throw new Exception("Source node cannot be null");
}
var arc = new Arc { Source = sourceNode, Target = node, Data = fragment };
sourceNode.AddForwardArc(arc);
node.AddReverseArc(arc);
}
// the root parent is the one that receives the subtree/fragment from the other parent
// so it does not actually pass a subtree to the child, therefore the fragment is null
// so in case of crossover, we add a null fragment below
if (parents.Count > 1) node.InEdges[0].Data = new Fragment { Root = null };
}
// notify listeners that the genealogy graph was updated
graph.Updated();
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
/// A double value representing the individual quality
private double Evaluate(IItem tree) {
var subScope = new Scope();
subScope.Variables.Add(new Core.Variable("SymbolicExpressionTree", tree)); // inject expected variables into the subscope
ExecutionContext.Scope.SubScopes.Add(subScope);
var context = new Core.ExecutionContext(ExecutionContext, SymbolicDataAnalysisEvaluator, subScope);
SymbolicDataAnalysisEvaluator.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;
}
}
}