Free cookie consent management tool by TermsFeed Policy Generator

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

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

#1772: Changelog:

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