#region License Information /* HeuristicLab * Copyright (C) 2002-2015 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 License Information using System.Collections.Generic; using System.Linq; 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 abstract 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 private const string TrimOlderGenerationsParameterName = "TrimOlderGenerations"; #endregion parameter names #region parameter properties public IFixedValueParameter TrimOlderGenerationsParameter { get { return (IFixedValueParameter)Parameters[TrimOlderGenerationsParameterName]; } } 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 parameter properties #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 bool TrimOlderGenerations { get { return TrimOlderGenerationsParameter.Value.Value; } } #endregion properties protected 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)); Parameters.Add(new FixedValueParameter(TrimOlderGenerationsParameterName, "Remove all the generations older than the last generation from the genealoy graph to save memory.")); #endregion add parameters } 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.")); } if (!Parameters.ContainsKey(TrimOlderGenerationsParameterName)) Parameters.Add(new FixedValueParameter(TrimOlderGenerationsParameterName, "Remove all the generations older than the last generation from the genealoy graph to save memory.")); } 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); } } } } protected abstract void EvaluateIntermediateChildren(); public override IOperation Apply() { IGenealogyGraph genealogyGraph; var results = ResultsParameter.ActualValue; if (!results.ContainsKey(PopulationGraphParameterName)) { genealogyGraph = new GenealogyGraph(); results.Add(new Result(PopulationGraphParameterName, genealogyGraph)); } else { genealogyGraph = (IGenealogyGraph)results[PopulationGraphParameterName].Value; } var population = PopulationParameter.ActualValue; var qualities = QualityParameter.ActualValue; 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; // identify previous elite individual for (int i = 0; i < population.Length; ++i) { if (genealogyGraph.GetByContent(population[i]).Rank.Equals(generation - 1)) { elite = population[i]; index = i; break; } } // add current elite and connect with previous #region add elite in the graph and connect it with the previous elite if (elite != null) { var prevVertex = genealogyGraph.GetByContent(elite); prevVertex.IsElite = true; // mark elites in the graph retroactively var v = (IGenealogyGraphNode)prevVertex.Clone(); v.Rank = generation; v.IsElite = false; population[index] = v.Data; genealogyGraph.AddVertex(v); genealogyGraph.AddArc(prevVertex, v); // inject the graph node unique id to the scope ExecutionContext.Scope.SubScopes[index].Variables[BeforeManipulatorOperator.ChildParameter.ActualName].Value = v.Data; ExecutionContext.Scope.SubScopes[index].Variables["Id"].Value = new StringValue(v.Id); } #endregion add elite in the graph and connect it with the previous elite } // update qualities for (int i = 0; i < population.Length; ++i) { var vertex = genealogyGraph.GetByContent(population[i]); vertex.Quality = qualities[i].Value; } // update qualities for intermediate vertices EvaluateIntermediateChildren(); // remove extra graph nodes (added by the instrumented operators in the case of offspring selection) var pop = new HashSet(population); var discarded = genealogyGraph.GetByRank(generation).Where(x => !pop.Contains(x.Data)).ToList(); for (int i = 0; i < discarded.Count; ++i) { var v = discarded[i]; if (v.InDegree == 1) { var p = v.Parents.First(); if (p.Rank.Equals(generation - 0.5)) // the individual was a product of mutation. since it wasn't selected, we must remove both it and its parent // ("intermediate" vertex result of crossover) discarded.Add(v.Parents.First()); } } genealogyGraph.RemoveVertices(discarded); //trim if (TrimOlderGenerations) { var vertices = genealogyGraph.Vertices.Where(x => x.Rank < generation - 1).ToList(); // select all ranks older than the previous generation genealogyGraph.RemoveVertices(vertices); } return base.Apply(); } } }