Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs @ 7800

Last change on this file since 7800 was 7800, checked in by bburlacu, 11 years ago

#1772: Fixed display of genetic fragments (received via crossover) in the GenealogyGraphView. Added parent, offspring and fragment lengths histogram.

File size: 19.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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.Collections.Generic;
24using System.Drawing;
25using System.Globalization;
26using System.Linq;
27using System.Text;
28using System.Threading;
29using HeuristicLab.Common;
30using HeuristicLab.Core;
31using HeuristicLab.Data;
32using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
33using HeuristicLab.Operators;
34using HeuristicLab.Optimization;
35using HeuristicLab.Parameters;
36using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
37using HeuristicLab.Problems.DataAnalysis;
38using HeuristicLab.Problems.DataAnalysis.Symbolic;
39// type definitions for ease of use
40using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
41using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;
42
43namespace HeuristicLab.EvolutionaryTracking {
44  /// <summary>
45  /// An operator that tracks the genealogy of every individual
46  /// </summary>
47  [Item("SymbolicExpressionTreeGenealogyAnalyzer", "An operator that tracks tree lengths of Symbolic Expression Trees")]
48  [StorableClass]
49  public sealed class SymbolicExpressionTreeGenealogyAnalyzer : SingleSuccessorOperator, IAnalyzer {
50    private const string UpdateIntervalParameterName = "UpdateInterval";
51    private const string UpdateCounterParameterName = "UpdateCounter";
52    private const string ResultsParameterName = "Results";
53    private const string ElitesParameterName = "Elites";
54    private const string GenerationsParameterName = "Generations";
55    private const string MaximumGenerationsParameterName = "MaximumGenerations";
56    private const string MaximumSelectionPressureParameterName = "MaximumSelectionPressure";
57    private const string SelectionPressureParameterName = "SelectionPressure";
58    private const string GlobalTraceMapParameterName = "GlobalTraceMap";
59    private const string GlobalCloneMapParameterName = "GlobalCloneMap";
60    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
61    private const string PopulationGraphResultParameterName = "PopulationGraph";
62    private const string PopulationGraphResultParameterDescription = "Individual lineages";
63    private const string SymbolicExpressionInterpreterParameterName = "SymbolicExpressionTreeInterpreter";
64    private const string SymbolicRegressionProblemDataParameterName = "ProblemData";
65    private const string SymbolicDataAnalysisProblemEvaluatorParameterName = "Evaluator";
66
67    #region Parameter properties
68    public ValueParameter<IntValue> UpdateIntervalParameter {
69      get { return (ValueParameter<IntValue>)Parameters[UpdateIntervalParameterName]; }
70    }
71    public ValueParameter<IntValue> UpdateCounterParameter {
72      get { return (ValueParameter<IntValue>)Parameters[UpdateCounterParameterName]; }
73    }
74    public LookupParameter<ResultCollection> ResultsParameter {
75      get { return (LookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
76    }
77    public LookupParameter<IntValue> ElitesParameter {
78      get { return (LookupParameter<IntValue>)Parameters[ElitesParameterName]; }
79    }
80    public LookupParameter<IntValue> GenerationsParameter {
81      get { return (LookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
82    }
83    public LookupParameter<IntValue> MaximumGenerationsParameter {
84      get { return (LookupParameter<IntValue>)Parameters[MaximumGenerationsParameterName]; }
85    }
86    public LookupParameter<DoubleValue> SelectionPressureParameter {
87      get { return (LookupParameter<DoubleValue>)Parameters[SelectionPressureParameterName]; }
88    }
89    public LookupParameter<DoubleValue> MaximumSelectionPressureParameter {
90      get { return (LookupParameter<DoubleValue>)Parameters[MaximumSelectionPressureParameterName]; }
91    }
92    // problem data, interpreter and evaluator
93    public LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter> SymbolicExpressionInterpreterParameter {
94      get { return (LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>)Parameters[SymbolicExpressionInterpreterParameterName]; }
95    }
96    public LookupParameter<RegressionProblemData> SymbolicRegressionProblemDataParameter {
97      get { return (LookupParameter<RegressionProblemData>)Parameters[SymbolicRegressionProblemDataParameterName]; }
98    }
99    public LookupParameter<IEvaluator> SymbolicDataAnalysisProblemEvaluatorParameter {
100      get { return (LookupParameter<IEvaluator>)Parameters[SymbolicDataAnalysisProblemEvaluatorParameterName]; }
101    }
102    // genealogy global parameters
103    public LookupParameter<TraceMapType> GlobalTraceMapParameter {
104      get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
105    }
106    public LookupParameter<CloneMapType> GlobalCloneMapParameter {
107      get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
108    }
109    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
110      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
111    }
112    #endregion
113
114    #region Properties
115    public bool EnabledByDefault {
116      get { return true; }
117    }
118    public IntValue UpdateInterval {
119      get { return UpdateIntervalParameter.Value; }
120    }
121    public IntValue UpdateCounter {
122      get { return UpdateCounterParameter.Value; }
123    }
124    public ResultCollection Results {
125      get { return ResultsParameter.ActualValue; }
126    }
127    public IntValue Elites {
128      get { return ElitesParameter.ActualValue; }
129    }
130    public IntValue Generations {
131      get { return GenerationsParameter.ActualValue; }
132    }
133    public IntValue MaximumGenerations {
134      get { return MaximumGenerationsParameter.ActualValue; }
135    }
136    public DoubleValue SelectionPressure {
137      get { return SelectionPressureParameter.ActualValue; }
138    }
139    public DoubleValue MaximumSelectionPressure {
140      get { return MaximumSelectionPressureParameter.ActualValue; }
141    }
142    public CloneMapType GlobalCloneMap {
143      get { return GlobalCloneMapParameter.ActualValue; }
144    }
145    public TraceMapType GlobalTraceMap {
146      get { return GlobalTraceMapParameter.ActualValue; }
147    }
148    public CloneMapType GlobalFragmentMap {
149      get { return GlobalFragmentMapParameter.ActualValue; }
150    }
151    public SymbolicDataAnalysisExpressionTreeInterpreter SymbolicExpressionInterpreter {
152      get { return SymbolicExpressionInterpreterParameter.ActualValue; }
153    }
154    public RegressionProblemData SymbolicRegressionProblemData {
155      get { return SymbolicRegressionProblemDataParameter.ActualValue; }
156    }
157    public IEvaluator SymbolicDataAnalysisEvaluator {
158      get { return SymbolicDataAnalysisProblemEvaluatorParameter.ActualValue; }
159    }
160    #endregion
161
162    [StorableConstructor]
163    private SymbolicExpressionTreeGenealogyAnalyzer(bool deserializing)
164      : base() {
165    }
166    private SymbolicExpressionTreeGenealogyAnalyzer(SymbolicExpressionTreeGenealogyAnalyzer original, Cloner cloner)
167      : base(original, cloner) {
168    }
169    public override IDeepCloneable Clone(Cloner cloner) {
170      return new SymbolicExpressionTreeGenealogyAnalyzer(this, cloner);
171    }
172    public SymbolicExpressionTreeGenealogyAnalyzer()
173      : base() {
174      Parameters.Add(new LookupParameter<IntValue>(ElitesParameterName, "The number of elites."));
175      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
176      Parameters.Add(new LookupParameter<IntValue>(MaximumGenerationsParameterName, "The maximum number of generations"));
177      Parameters.Add(new LookupParameter<DoubleValue>(SelectionPressureParameterName, "The current selection (ony for OSGA)"));
178      Parameters.Add(new LookupParameter<DoubleValue>(MaximumSelectionPressureParameterName, "Maximum allowed value of selection pressure."));
179      Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
180      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
181      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing the whole genealogy."));
182      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
183      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
184      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
185      Parameters.Add(new LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>(SymbolicExpressionInterpreterParameterName, "Interpreter for symbolic expression trees"));
186      Parameters.Add(new LookupParameter<RegressionProblemData>(SymbolicRegressionProblemDataParameterName, "The symbolic data analysis problem."));
187      Parameters.Add(new LookupParameter<IEvaluator>(SymbolicDataAnalysisProblemEvaluatorParameterName, "The fitness evaluator"));
188
189      UpdateCounterParameter.Hidden = true;
190      UpdateIntervalParameter.Hidden = true;
191    }
192
193    [StorableHook(HookType.AfterDeserialization)]
194    private void AfterDeserialization() {
195      // check if all the parameters are present and accounted for
196      if (!Parameters.ContainsKey(UpdateIntervalParameterName)) {
197        Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
198      }
199      if (Parameters.ContainsKey(UpdateCounterParameterName)) return;
200      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
201      UpdateCounterParameter.Hidden = true;
202    }
203
204    #region IStatefulItem members
205    public override void InitializeState() {
206      base.InitializeState();
207      UpdateCounter.Value = 0;
208    }
209
210    public override void ClearState() {
211      base.ClearState();
212      UpdateCounter.Value = 0;
213    }
214    #endregion
215
216    public override IOperation Apply() {
217      UpdateCounter.Value++;
218      // the analyzer runs periodically, every 'updateInterval' times
219      if (UpdateCounter.Value == UpdateInterval.Value) {
220        UpdateCounter.Value = 0; // reset counter
221
222        var gScope = ExecutionContext.Scope;
223        while (gScope.Parent != null) gScope = gScope.Parent;
224        SymbolicExpressionTreeGenealogyGraph graph;
225        if (!Results.ContainsKey(PopulationGraphResultParameterName)) {
226          graph = new SymbolicExpressionTreeGenealogyGraph();
227          Results.Add(new Result(PopulationGraphResultParameterName, PopulationGraphResultParameterDescription, graph));
228        } else {
229          graph = (SymbolicExpressionTreeGenealogyGraph)(Results[PopulationGraphResultParameterName].Value);
230        }
231        // get tree quality values (Key => Individual, Value => Quality)
232        var qualities = (from s in gScope.SubScopes
233                         let individual = s.Variables.First().Value
234                         let quality = (DoubleValue)s.Variables["Quality"].Value
235                         orderby quality.Value descending
236                         select new Tuple<ISymbolicExpressionTree, double>((ISymbolicExpressionTree)individual, quality.Value)).ToDictionary(t => t.Item1, t => t.Item2);
237
238        // add all individuals to the evolutionary graph
239        int generation = Generations.Value;
240        string label;
241        if (generation == 0) {
242          // at generation 0 no trace map is present (since no reproduction has taken place yet),
243          // so we only add the initial individuals as nodes in the genealogy graph
244          for (int i = 0; i != qualities.Count; ++i) {
245            var tree = qualities.ElementAt(i).Key;
246            label = (i + 1).ToString(CultureInfo.InvariantCulture);
247            var node = new GenealogyGraphNode(tree) { Quality = qualities[tree], Label = label, Rank = generation, IsElite = i < Elites.Value };
248            graph.AddNode(node);
249          }
250          return base.Apply();
251        }
252
253        // add nodes to genealogy graph
254        for (int i = 0; i != qualities.Count; ++i) {
255          var child = qualities.ElementAt(i).Key;
256          label = (generation * qualities.Count + i + 1).ToString(CultureInfo.InvariantCulture);
257          if (!graph.HasNode(child)) {
258            var node = new GenealogyGraphNode(child) { Quality = qualities[child], Label = label, Rank = generation, IsElite = i < Elites.Value };
259            graph.AddNode(node);
260          }
261          if (!GlobalTraceMap.ContainsKey(child)) continue;
262          var parents = GlobalTraceMap[child].Cast<ISymbolicExpressionTree>();
263
264          foreach (var parent in parents) {
265            object data = ((List<ISymbolicExpressionTreeNode>)child.IterateNodesBreadth())[((IntValue)GlobalFragmentMap[child]).Value];
266            graph.AddArc(parent, child, null, data);
267            if (GlobalTraceMap.ContainsKey(parent)) {
268              double quality = Evaluate(parent);
269              var node = new GenealogyGraphNode(parent) { Quality = quality, Label = "", Rank = generation - 0.5 };
270              graph.AddNode(node);
271              var pp = GlobalTraceMap[parent].Cast<ISymbolicExpressionTree>();
272              foreach (var p in pp) {
273                data = ((List<ISymbolicExpressionTreeNode>)parent.IterateNodesBreadth())[((IntValue)GlobalFragmentMap[parent]).Value];
274                graph.AddArc(p, parent, null, data);
275              }
276            }
277          }
278        }
279
280        // clear trace and clone maps in preparation for the next generation
281        if (this.Successor == null || !(this.Successor is SymbolicExpressionTreeFragmentsAnalyzer)) {
282          GlobalTraceMap.Clear();
283          GlobalCloneMap.Clear();
284          GlobalFragmentMap.Clear();
285        }
286
287        #region end of the run (code for writing results to dot files)
288        //bool maxGenerationsReached = (Generations.Value == MaximumGenerations.Value);
289        //bool isOsga = (SelectionPressure != null && MaximumSelectionPressure != null);
290        //bool maxSelectionPressureReached = isOsga && (SelectionPressure.Value >= MaximumSelectionPressure.Value);
291        //if (maxGenerationsReached || maxSelectionPressureReached) {
292        //  var path = Environment.GetFolderPath(Environment.SpecialFolder.UserProfile);
293
294        //  // write whole graph to a dot file
295        //  WriteDot(path + @"\lineage.dot", graph);
296
297        //  // get genealogy of the best solution
298        //  var bestSolution = (ISymbolicExpressionTree)qualities.First().Key;
299        //  var genealogy = graph.GetNode(bestSolution).Ancestors();
300        //  //WriteDot(path + @"\bestlineage.dot", genealogy);
301
302        //  // write the direct root lineage of the best solution (is it useful?)
303
304        //  // calculate impact values of nodes in the best solution, attempt to trace those with high impact to their origins
305        //  var calculator = new SymbolicRegressionSolutionValuesCalculator();
306        //  var impactValues = calculator.CalculateImpactValues(bestSolution, SymbolicExpressionInterpreter, SymbolicRegressionProblemData, 0, 0);
307        //  foreach (var pair in impactValues.Where(pair => !(pair.Key is ConstantTreeNode || pair.Key is VariableTreeNode)).OrderByDescending(pair => pair.Value).Take(2)) {
308        //    var node = pair.Key;
309        //  }
310        //  //WriteDot(path + @"\impactancestry.dot", genealogy);
311
312        //  // trim the graph
313        //  // exclude the individuals of the last generation
314        //  var individuals = graph.Keys.Except(qualities.Select(x => x.Key)).ToList();
315        //  bool done = false;
316        //  while (!done) {
317        //    done = true;
318        //    foreach (var ind in individuals) {
319        //      // if node has no outgoing connections (absence of offspring), remove it from the graph
320        //      var node = graph.GetNode(ind);
321        //      if (node == null) continue;
322        //      if (node.OutEdges == null) {
323        //        done = false; // we still have "dead" nodes
324        //        graph.RemoveNode(ind);
325        //      }
326        //    }
327        //  }
328        //  WriteDot(path + @"\trimmedlineage.dot", graph);
329        //}
330        #endregion
331      }
332      return base.Apply();
333    }
334
335    private double Evaluate(ISymbolicExpressionTree tree) {
336      // we perform evaluation by adding a temporary subscope with the tree in it, and calling evaluator.Apply()
337      var subScope = new Scope();
338      // inject expected variables into the subscope
339      subScope.Variables.Add(new Core.Variable("SymbolicExpressionTree", tree));
340      ExecutionContext.Scope.SubScopes.Add(subScope);
341      var context = new Core.ExecutionContext(ExecutionContext, SymbolicDataAnalysisEvaluator, subScope);
342      SymbolicDataAnalysisEvaluator.Execute(context, new CancellationToken());
343      // get the quality
344      double quality = ((DoubleValue)subScope.Variables["Quality"].Value).Value;
345      // remove the subscope
346      ExecutionContext.Scope.SubScopes.Remove(subScope);
347      return quality;
348    }
349
350    #region Export to dot file
351    private static void WriteDot(string path, SymbolicExpressionTreeGenealogyGraph graph) {
352      using (var file = new System.IO.StreamWriter(path)) {
353        string nl = Environment.NewLine;
354        file.WriteLine("digraph \"lineage " + graph.AverageDegree.ToString(CultureInfo.InvariantCulture) + "\" {" + nl + "ratio=auto;" + nl + "mincross=2.0");
355        file.WriteLine("\tnode [shape=circle,label=\"\",style=filled]");
356
357        foreach (var node in graph.Values) {
358          var color = Color.FromArgb((int)((1 - node.Quality) * 255), (int)(node.Quality * 255), 0);
359          string fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", color.R, color.G, color.B);
360          string shape = "circle";
361          if (node.IsElite)
362            shape = "doublecircle";
363          file.WriteLine("\t\"" + node.Id + "\" [shape=" + shape + ",fillcolor=\"" + fillColor + "\",label=\"" + node.Label + "\"];");
364          if (node.InEdges == null)
365            continue;
366          foreach (var edge in node.InEdges) {
367            //var edgeStyle = node.InEdges.Count == 1 ? "dashed" : String.Empty;
368            var edgeStyle = String.Empty;
369            file.WriteLine("\t\"" + edge.Target.Id + "\" -> \"" + node.Id + "\" [arrowsize=.5, color=\"" + fillColor + "\", style=\"" + edgeStyle + "\"];");
370          }
371        }
372        foreach (var g in graph.Values.GroupBy(x => x.Rank)) {
373          var sb = new StringBuilder();
374          sb.Append("\t{rank=same;");
375          foreach (var node in g)
376            sb.Append("\"" + node.Id + "\" ");
377          sb.Append("}\n");
378          file.Write(sb.ToString());
379        }
380        file.WriteLine("}");
381      }
382    }
383    #endregion
384  }
385}
Note: See TracBrowser for help on using the repository browser.