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