source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/Analyzers/GenealogyAnalyzer.cs @ 11262

Last change on this file since 11262 was 11262, checked in by bburlacu, 8 years ago

#1772: Added missing Storable constructor to GenealogyGraphNode<T> class. Prefer cloning vertices in the GenealogyAnalyzer. Add In/Out Degree in node tooltip in the GenealogyGraphChart.

File size: 18.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Linq;
24using HeuristicLab.Analysis;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Operators;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33namespace HeuristicLab.EvolutionTracking {
34  [StorableClass]
35  [Item("GenealogyAnalyzer", "An analyzer which performs the necessary instrumentation to record the evolution of a genetic algorithm.")]
36  public class GenealogyAnalyzer<T> : SingleSuccessorOperator, IAnalyzer
37  where T : class,IItem {
38    #region parameter names
39    private const string GenerationsParameterName = "Generations";
40    private const string ResultsParameterName = "Results";
41    private const string PopulationGraphParameterName = "PopulationGraph";
42    public const string QualityParameterName = "Quality";
43    public const string PopulationParameterName = "SymbolicExpressionTree";
44
45    private const string CrossoverParameterName = "Crossover";
46    private const string ManipulatorParameterName = "Mutator";
47    private const string SolutionCreatorParameterName = "SolutionCreator";
48
49    private const string BeforeCrossoverOperatorParameterName = "BeforeCrossoverOperator";
50    private const string AfterCrossoverOperatorParameterName = "AfterCrossoverOperator";
51
52    private const string BeforeManipulatorOperatorParameterName = "BeforeManipulatorOperator";
53    private const string AfterManipulatorOperatorParameterName = "AfterManipulatorOperator";
54
55    private const string EnableCrossoverTrackingParameterName = "EnableCrossoverTracking";
56    private const string EnableManipulatorTrackingParameterName = "EnableManipulatorTracking";
57    private const string EnableSolutionCreatorTrackingParameterName = "EnableSolutionCreatorTracking"; // should always be enabled. maybe superfluous
58    #endregion
59
60    #region parameter properties
61    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
62      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters[QualityParameterName]; }
63    }
64    public IScopeTreeLookupParameter<T> PopulationParameter {
65      get { return (IScopeTreeLookupParameter<T>)Parameters[PopulationParameterName]; }
66    }
67    public IValueParameter<ICrossoverOperator<T>> BeforeCrossoverOperatorParameter {
68      get { return (IValueParameter<ICrossoverOperator<T>>)Parameters[BeforeCrossoverOperatorParameterName]; }
69    }
70    public IValueParameter<ICrossoverOperator<T>> AfterCrossoverOperatorParameter {
71      get { return (IValueParameter<ICrossoverOperator<T>>)Parameters[AfterCrossoverOperatorParameterName]; }
72    }
73    public IValueParameter<IManipulatorOperator<T>> BeforeManipulatorOperatorParameter {
74      get { return (IValueParameter<IManipulatorOperator<T>>)Parameters[BeforeManipulatorOperatorParameterName]; }
75    }
76    public IValueParameter<IManipulatorOperator<T>> AfterManipulatorOperatorParameter {
77      get { return (IValueParameter<IManipulatorOperator<T>>)Parameters[AfterManipulatorOperatorParameterName]; }
78    }
79    public ILookupParameter<ResultCollection> ResultsParameter {
80      get { return (ILookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
81    }
82    public ILookupParameter<IntValue> GenerationsParameter {
83      get { return (ILookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
84    }
85    public IValueParameter<BoolValue> EnableCrossoverTrackingParameter {
86      get { return (IValueParameter<BoolValue>)Parameters[EnableCrossoverTrackingParameterName]; }
87    }
88    public IValueParameter<BoolValue> EnableManipulatorTrackingParameter {
89      get { return (IValueParameter<BoolValue>)Parameters[EnableManipulatorTrackingParameterName]; }
90    }
91    public IValueParameter<BoolValue> EnableSolutionCreatorTrackingParameter {
92      get { return (IValueParameter<BoolValue>)Parameters[EnableSolutionCreatorTrackingParameterName]; }
93    }
94    public ILookupParameter<ICrossover> CrossoverParameter {
95      get { return (ILookupParameter<ICrossover>)Parameters[CrossoverParameterName]; }
96    }
97    public ILookupParameter<IManipulator> ManipulatorParameter {
98      get { return (ILookupParameter<IManipulator>)Parameters[ManipulatorParameterName]; }
99    }
100
101    public ILookupParameter<ISolutionCreator> SolutionCreatorParameter {
102      get { return (ILookupParameter<ISolutionCreator>)Parameters[SolutionCreatorParameterName]; }
103    }
104    #endregion
105
106    #region properties
107    public ICrossoverOperator<T> BeforeCrossoverOperator {
108      get { return BeforeCrossoverOperatorParameter.Value; }
109    }
110    public ICrossoverOperator<T> AfterCrossoverOperator {
111      get { return AfterCrossoverOperatorParameter.Value; }
112    }
113    public IManipulatorOperator<T> BeforeManipulatorOperator {
114      get { return BeforeManipulatorOperatorParameter.Value; }
115    }
116    public IManipulatorOperator<T> AfterManipulatorOperator {
117      get { return AfterManipulatorOperatorParameter.Value; }
118    }
119    public BoolValue EnableCrossoverTracking {
120      get { return EnableCrossoverTrackingParameter.Value; }
121    }
122    public BoolValue EnableManipulatorTracking {
123      get { return EnableManipulatorTrackingParameter.Value; }
124    }
125    public BoolValue EnableSolutionCreatorTracking {
126      get { return EnableSolutionCreatorTrackingParameter.Value; }
127    }
128
129    public IGenealogyGraph<T> GenealogyGraph {
130      get {
131        IResult result;
132        var results = ResultsParameter.ActualValue;
133        if (!results.ContainsKey(PopulationGraphParameterName)) {
134          result = new Result(PopulationGraphParameterName, new GenealogyGraph<T>());
135          results.Add(result);
136        } else {
137          result = results[PopulationGraphParameterName];
138        }
139        var graph = (IGenealogyGraph<T>)result.Value;
140        return graph;
141      }
142    }
143    #endregion
144
145    public GenealogyAnalyzer() {
146      #region add parameters
147      // the instrumented operators
148      Parameters.Add(new LookupParameter<ICrossover>(CrossoverParameterName, "The crossover operator."));
149      Parameters.Add(new LookupParameter<IManipulator>(ManipulatorParameterName, "The manipulator operator."));
150      Parameters.Add(new LookupParameter<ISolutionCreator>(SolutionCreatorParameterName, "The solution creator operator."));
151      // the analyzer parameters
152      Parameters.Add(new ValueParameter<BoolValue>(EnableCrossoverTrackingParameterName, new BoolValue(true)));
153      Parameters.Add(new ValueParameter<BoolValue>(EnableManipulatorTrackingParameterName, new BoolValue(true)));
154      Parameters.Add(new ValueParameter<BoolValue>(EnableSolutionCreatorTrackingParameterName, new BoolValue(true)));
155      // parameters required by the analyzer to do its work
156      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
157      Parameters.Add(new LookupParameter<ResultCollection>(ResultsParameterName));
158      Parameters.Add(new ScopeTreeLookupParameter<T>(PopulationParameterName, "The population of individuals."));
159      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(QualityParameterName, "The individual qualities."));
160      Parameters.Add(new ValueParameter<ICrossoverOperator<T>>(BeforeCrossoverOperatorParameterName));
161      Parameters.Add(new ValueParameter<ICrossoverOperator<T>>(AfterCrossoverOperatorParameterName));
162      Parameters.Add(new ValueParameter<IManipulatorOperator<T>>(BeforeManipulatorOperatorParameterName));
163      Parameters.Add(new ValueParameter<IManipulatorOperator<T>>(AfterManipulatorOperatorParameterName));
164      #endregion
165    }
166    public override IDeepCloneable Clone(Cloner cloner) {
167      return new GenealogyAnalyzer<T>(this, cloner);
168    }
169    protected GenealogyAnalyzer(GenealogyAnalyzer<T> original, Cloner cloner)
170      : base(original, cloner) {
171    }
172
173    [StorableConstructor]
174    protected GenealogyAnalyzer(bool deserializing) : base(deserializing) { }
175
176    [StorableHook(HookType.AfterDeserialization)]
177    private void AfterDeserialization() {
178      // the instrumented operators
179      if (!Parameters.ContainsKey(CrossoverParameterName))
180        Parameters.Add(new LookupParameter<ICrossover>(CrossoverParameterName, "The crossover operator."));
181      if (!Parameters.ContainsKey(ManipulatorParameterName))
182        Parameters.Add(new LookupParameter<IManipulator>(ManipulatorParameterName, "The manipulator operator."));
183      if (!Parameters.ContainsKey(SolutionCreatorParameterName))
184        Parameters.Add(new LookupParameter<ISolutionCreator>(SolutionCreatorParameterName, "The solution creator operator."));
185      // the analyzer parameters
186      if (!Parameters.ContainsKey(EnableCrossoverTrackingParameterName))
187        Parameters.Add(new ValueParameter<BoolValue>(EnableCrossoverTrackingParameterName, new BoolValue(true)));
188      if (!Parameters.ContainsKey(EnableManipulatorTrackingParameterName))
189        Parameters.Add(new ValueParameter<BoolValue>(EnableManipulatorTrackingParameterName, new BoolValue(true)));
190      if (!Parameters.ContainsKey(EnableSolutionCreatorTrackingParameterName))
191        Parameters.Add(new ValueParameter<BoolValue>(EnableSolutionCreatorTrackingParameterName, new BoolValue(true)));
192      // parameters required by the analyzer to do its work
193      if (!Parameters.ContainsKey(GenerationsParameterName))
194        Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
195      if (!Parameters.ContainsKey(ResultsParameterName))
196        Parameters.Add(new LookupParameter<ResultCollection>(ResultsParameterName));
197      if (!Parameters.ContainsKey(PopulationParameterName)) {
198        Parameters.Add(new ScopeTreeLookupParameter<T>(PopulationParameterName, "The population of individuals."));
199      }
200      if (!Parameters.ContainsKey(QualityParameterName)) {
201        Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(QualityParameterName, "The individual qualities."));
202      }
203    }
204
205    public bool EnabledByDefault {
206      get { return false; }
207    }
208
209    private void ConfigureTrackingOperators() {
210      // at the beginning we add the before/after operators to the instrumented operators
211      var crossover = CrossoverParameter.ActualValue;
212      if (crossover != null) {
213        var instrumentedCrossover = (InstrumentedOperator)crossover;
214        instrumentedCrossover.AfterExecutionOperators.Clear();
215        instrumentedCrossover.BeforeExecutionOperators.Clear();
216
217        if (EnableCrossoverTracking.Value) {
218          if (BeforeCrossoverOperator != null) {
219            instrumentedCrossover.BeforeExecutionOperators.Add(BeforeCrossoverOperator);
220          }
221          if (AfterCrossoverOperator != null) {
222            instrumentedCrossover.AfterExecutionOperators.Add(AfterCrossoverOperator);
223          }
224        }
225      }
226      var manipulator = ManipulatorParameter.ActualValue;
227      if (manipulator != null) {
228        var instrumentedManipulator = (InstrumentedOperator)manipulator;
229        instrumentedManipulator.AfterExecutionOperators.Clear();
230        instrumentedManipulator.BeforeExecutionOperators.Clear();
231
232        if (EnableManipulatorTracking.Value) {
233          if (BeforeManipulatorOperator != null) {
234            instrumentedManipulator.BeforeExecutionOperators.Add(BeforeManipulatorOperator);
235          }
236          if (AfterManipulatorOperator != null) {
237            instrumentedManipulator.AfterExecutionOperators.Add(AfterManipulatorOperator);
238          }
239        }
240      }
241    }
242
243    public override IOperation Apply() {
244      var population = PopulationParameter.ActualValue;
245      var qualities = QualityParameter.ActualValue.ToList();
246
247      int generation = GenerationsParameter.ActualValue.Value;
248      if (generation == 0) {
249        ConfigureTrackingOperators();
250
251        for (int i = 0; i < population.Length; ++i) {
252          var individual = population[i];
253          var vertex = new GenealogyGraphNode<T>(individual) { Rank = generation };
254          GenealogyGraph.AddVertex(vertex);
255          // save the vertex id in the individual scope (so that we can identify graph indices)
256          ExecutionContext.Scope.SubScopes[i].Variables.Add(new Variable("Id", new StringValue(vertex.Id)));
257        }
258      } else {
259        int index = 0;
260        T elite = null;
261
262        for (int i = 0; i < population.Length; ++i) {
263          if (GenealogyGraph.GetByContent(population[i]).Rank.Equals(generation - 1)) {
264            elite = population[i];
265            index = i;
266            break;
267          }
268        }
269
270        #region add elite in the graph and connect it with the previous elite
271        if (elite != null) {
272          var prevVertex = (IGenealogyGraphNode<T>)GenealogyGraph.GetByContent(elite);
273          prevVertex.IsElite = true; // mark elites in the graph retroactively
274          var w = (IGenealogyGraphNode<T>)prevVertex.Clone();
275          var v = new GenealogyGraphNode<T>(prevVertex.Data) {
276            Rank = generation,
277            Quality = prevVertex.Quality,
278            IsElite = false
279          };
280
281          object data = null;
282          if (prevVertex.InArcs.Any())
283            data = prevVertex.InArcs.Last().Data;
284          var children = prevVertex.Children.ToList();
285          var parents = prevVertex.Parents.ToList();
286
287          GenealogyGraph.RemoveVertex(prevVertex);
288          GenealogyGraph.AddVertex(w);
289          GenealogyGraph.AddVertex(v);
290          GenealogyGraph.AddArc(w, v); // connect current elite with previous elite
291
292          // recreate connections after prevVertex was replaced with w
293          foreach (var c in children) GenealogyGraph.AddArc(w, c);
294          foreach (var p in parents) GenealogyGraph.AddArc(p, w);
295
296          v.InArcs.Last().Data = data;
297
298          if (w.InArcs.Any())
299            w.InArcs.Last().Data = data;
300
301          // inject the graph node unique id to the scope
302          ExecutionContext.Scope.SubScopes[index].Variables["Id"].Value = new StringValue(v.Id);
303        }
304        #endregion
305
306        ComputeSuccessRatios();
307      }
308      // update qualities
309      for (int i = 0; i < population.Length; ++i) {
310        var vertex = GenealogyGraph.GetByContent(population[i]);
311        vertex.Quality = qualities[i].Value;
312      }
313
314      // remove extra graph nodes (added by the instrumented operators in the case of offspring selection)
315      RemoveUnsuccessfulOffspring();
316
317      return base.Apply();
318    }
319
320    private void RemoveUnsuccessfulOffspring() {
321      int generation = GenerationsParameter.ActualValue.Value;
322      var population = PopulationParameter.ActualValue;
323      var discardedOffspring = GenealogyGraph.Ranks[generation].Select(x => (T)x.Data).Except(population).ToList();
324      foreach (var vertex in discardedOffspring.Select(individual => GenealogyGraph.GetByContent(individual))) {
325        if (vertex.InDegree == 1) {
326          var p = vertex.Parents.First();
327          if (!p.Rank.Equals(generation - 0.5))
328            throw new InvalidOperationException("Parent must be an intermediate vertex");
329          GenealogyGraph.RemoveVertex(p);
330        }
331        GenealogyGraph.RemoveVertex(vertex);
332      }
333    }
334
335    private void ComputeSuccessRatios() {
336      const string successfulOffspringRatioTableHistoryName = "Successful offspring ratio";
337      const string successfulOffspringRatioHeatMapName = "Successful offspring ratio heatmap";
338
339      var population = PopulationParameter.ActualValue;
340      var generation = GenerationsParameter.ActualValue.Value;
341      // compute the weight of each genealogy graph node as the ratio (produced offspring) / (surviving offspring)
342      foreach (var ind in population) {
343        var v = GenealogyGraph.GetByContent(ind);
344        foreach (var p in v.Parents)
345          p.Weight++;
346      }
347      foreach (var v in GenealogyGraph.Ranks[generation - 1]) {
348        if (v.OutDegree > 0)
349          v.Weight /= v.OutDegree;
350      }
351
352      var results = ResultsParameter.ActualValue;
353
354      DataTableHistory history;
355      if (!results.ContainsKey(successfulOffspringRatioTableHistoryName)) {
356        history = new DataTableHistory();
357        results.Add(new Result(successfulOffspringRatioTableHistoryName, history));
358      } else {
359        history = (DataTableHistory)results[successfulOffspringRatioTableHistoryName].Value;
360      }
361      var table = new DataTable();
362      var row = new DataRow("Successful Offspring") {
363        VisualProperties = { ChartType = DataRowVisualProperties.DataRowChartType.Columns, StartIndexZero = true }
364      };
365      row.Values.Replace(GenealogyGraph.Ranks[generation - 1].OrderByDescending(x => x.Quality).Select(x => x.Weight));
366      table.Rows.Add(row);
367      history.Add(table);
368      double[,] elements = new double[population.Length, history.Count];
369      var col = history.AsReadOnly().ToList();
370      for (int i = 0; i < col.Count; ++i) {
371        var values = col[i].Rows.First().Values;
372        for (int j = 0; j < values.Count; ++j) {
373          elements[j, i] = values[j];
374        }
375      }
376
377      var heatmap = new HeatMap(elements);
378      if (!results.ContainsKey(successfulOffspringRatioHeatMapName)) {
379        results.Add(new Result(successfulOffspringRatioHeatMapName, heatmap));
380      } else {
381        results[successfulOffspringRatioHeatMapName].Value = heatmap;
382      }
383    }
384  }
385}
Note: See TracBrowser for help on using the repository browser.