Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFragmentsAnalyzer.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: 18.2 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.Linq;
25using HeuristicLab.Analysis;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
30using HeuristicLab.Operators;
31using HeuristicLab.Optimization;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34// type definitions for ease of use
35using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
36using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;
37
38namespace HeuristicLab.EvolutionaryTracking {
39  /// <summary>
40  /// An operator that gathers information on tree fragments that get passed from one generation to the next via genetic operators
41  /// (Tracking of genetic variance and heredity)
42  /// </summary>
43  /// [Item("SymbolicExpressionTreeGenealogyAnalyzer", "An operator that tracks tree lengths of Symbolic Expression Trees")]
44  [StorableClass]
45  public sealed class SymbolicExpressionTreeFragmentsAnalyzer : SingleSuccessorOperator, IAnalyzer {
46    private const string UpdateIntervalParameterName = "UpdateInterval";
47    private const string UpdateCounterParameterName = "UpdateCounter";
48    private const string ResultsParameterName = "Results";
49    private const string GlobalTraceMapParameterName = "GlobalTraceMap";
50    private const string GlobalCloneMapParameterName = "GlobalCloneMap";
51    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
52    private const string GenerationsParameterName = "Generations";
53    private const string FragmentStatisticsParameterName = "FragmentStatistics";
54    private const string FragmentLengthsDistributionParametersName = "FragmentLengths";
55
56    #region Parameter properties
57    public ValueParameter<IntValue> UpdateIntervalParameter {
58      get { return (ValueParameter<IntValue>)Parameters[UpdateIntervalParameterName]; }
59    }
60    public ValueParameter<IntValue> UpdateCounterParameter {
61      get { return (ValueParameter<IntValue>)Parameters[UpdateCounterParameterName]; }
62    }
63    public LookupParameter<ResultCollection> ResultsParameter {
64      get { return (LookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
65    }
66    public LookupParameter<TraceMapType> GlobalTraceMapParameter {
67      get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
68    }
69    public LookupParameter<CloneMapType> GlobalCloneMapParameter {
70      get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
71    }
72    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
73      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
74    }
75    public LookupParameter<IntValue> GenerationsParameter {
76      get { return (LookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
77    }
78    public LookupParameter<DataTable> FragmentStatisticsParameter {
79      get { return (LookupParameter<DataTable>)Parameters[FragmentStatisticsParameterName]; }
80    }
81    public LookupParameter<DataTable> FragmentLengthsParameter {
82      get { return (LookupParameter<DataTable>)Parameters[FragmentLengthsDistributionParametersName]; }
83    }
84    #endregion
85
86    #region Parameters
87    public bool EnabledByDefault {
88      get { return true; }
89    }
90    public IntValue UpdateInterval {
91      get { return UpdateIntervalParameter.Value; }
92    }
93    public IntValue UpdateCounter {
94      get { return UpdateCounterParameter.Value; }
95    }
96    public ResultCollection Results {
97      get { return ResultsParameter.ActualValue; }
98    }
99    public CloneMapType GlobalCloneMap {
100      get { return GlobalCloneMapParameter.ActualValue; }
101    }
102    public TraceMapType GlobalTraceMap {
103      get { return GlobalTraceMapParameter.ActualValue; }
104    }
105    public CloneMapType GlobalFragmentMap {
106      get { return GlobalFragmentMapParameter.ActualValue; }
107    }
108    public IntValue Generations {
109      get { return GenerationsParameter.ActualValue; }
110    }
111    public DataTable FragmentStatistics {
112      get { return FragmentStatisticsParameter.ActualValue; }
113    }
114    public DataTable FragmentLengths {
115      get { return FragmentLengthsParameter.ActualValue; }
116    }
117    #endregion
118
119    [StorableConstructor]
120    private SymbolicExpressionTreeFragmentsAnalyzer(bool deserializing)
121      : base() {
122    }
123    private SymbolicExpressionTreeFragmentsAnalyzer(SymbolicExpressionTreeFragmentsAnalyzer original, Cloner cloner)
124      : base(original, cloner) {
125    }
126    public override IDeepCloneable Clone(Cloner cloner) {
127      return new SymbolicExpressionTreeFragmentsAnalyzer(this, cloner);
128    }
129    public SymbolicExpressionTreeFragmentsAnalyzer()
130      : base() {
131      Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
132      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
133      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing the whole genealogy."));
134      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
135      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
136      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
137      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
138      Parameters.Add(new LookupParameter<DataTable>(FragmentStatisticsParameterName, "The data table to store the fragment statistics."));
139      Parameters.Add(new LookupParameter<DataTable>(FragmentLengthsDistributionParametersName, "The data table to store the distribution of fragment lengths."));
140      UpdateCounterParameter.Hidden = true;
141      UpdateIntervalParameter.Hidden = true;
142    }
143    #region After deserialization code
144    [StorableHook(HookType.AfterDeserialization)]
145    private void AfterDeserialization() {
146      // check if all the parameters are present and accounted for
147      if (!Parameters.ContainsKey(UpdateIntervalParameterName)) {
148        Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
149      }
150      if (!Parameters.ContainsKey(UpdateCounterParameterName)) {
151        Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
152        UpdateCounterParameter.Hidden = true;
153      }
154      if (!Parameters.ContainsKey(FragmentLengthsDistributionParametersName)) {
155        Parameters.Add(new LookupParameter<DataTable>(FragmentLengthsDistributionParametersName, "The data table to store the distribution of fragment lengths."));
156      }
157    }
158    #endregion
159    #region IStatefulItem members
160    public override void InitializeState() {
161      base.InitializeState();
162      UpdateCounter.Value = 0;
163    }
164
165    public override void ClearState() {
166      base.ClearState();
167      UpdateCounter.Value = 0;
168    }
169    #endregion
170
171    public override IOperation Apply() {
172      if (Generations.Value == 0) return base.Apply();
173      UpdateCounter.Value++;
174      if (UpdateCounter.Value == UpdateInterval.Value) {
175        ResultCollection results = ResultsParameter.ActualValue;
176        if (FragmentStatistics == null) {
177          FragmentStatisticsParameter.ActualValue = new DataTable("Fragment Statistics", "Statistical measurements of fragments aggregated over the whole population");
178          FragmentStatistics.VisualProperties.YAxisTitle = "Fragment length/Similarities";
179          results.Add(new Result("Fragment Statistics", FragmentStatistics));
180        }
181        if (FragmentLengths == null) {
182          FragmentLengthsParameter.ActualValue = new DataTable("Fragment and Tree Lengths", "Distribution of the lengths of the trees sampled by crossover");
183          FragmentLengths.VisualProperties.XAxisTitle = "Tree/fragment length";
184          results.Add(new Result("Fragment Lengths", FragmentLengths));
185        }
186
187        UpdateCounter.Value = 0; // reset counter
188        var gScope = ExecutionContext.Scope;
189        while (gScope.Parent != null) gScope = gScope.Parent;
190
191        #region Fragment Statistics
192        #region Table data
193        if (!FragmentLengths.Rows.ContainsKey("Parent lengths distribution")) {
194          var parentLenghtsRow = new DataRow("Parent lengths distribution");
195          parentLenghtsRow.VisualProperties.ChartType = DataRowVisualProperties.DataRowChartType.Histogram;
196          parentLenghtsRow.VisualProperties.StartIndexZero = true;
197          parentLenghtsRow.VisualProperties.ScaleFactor = 1.0;
198          FragmentLengths.Rows.Add(parentLenghtsRow);
199        }
200        if (!FragmentLengths.Rows.ContainsKey("Child lengths distribution")) {
201          var treeLengthsRow = new DataRow("Child lengths distribution");
202          treeLengthsRow.VisualProperties.ChartType = DataRowVisualProperties.DataRowChartType.Histogram;
203          treeLengthsRow.VisualProperties.StartIndexZero = true;
204          treeLengthsRow.VisualProperties.ScaleFactor = 1.0;
205          FragmentLengths.Rows.Add(treeLengthsRow);
206        }
207        if (!FragmentLengths.Rows.ContainsKey("Fragment lengths distribution")) {
208          var fragmentLengthsRow = new DataRow("Fragment lengths distribution");
209          fragmentLengthsRow.VisualProperties.ChartType = DataRowVisualProperties.DataRowChartType.Histogram;
210          fragmentLengthsRow.VisualProperties.StartIndexZero = true;
211          fragmentLengthsRow.VisualProperties.ScaleFactor = 1.0;
212          FragmentLengths.Rows.Add(fragmentLengthsRow);
213        }
214        // fragments
215        if (!FragmentStatistics.Rows.ContainsKey("Average fragment length")) {
216          var row = new DataRow("Average fragment length") { VisualProperties = { StartIndexZero = true } };
217          FragmentStatistics.Rows.Add(row);
218        }
219        // child trees
220        if (!FragmentStatistics.Rows.ContainsKey("Average child length")) {
221          var row = new DataRow("Average child length") { VisualProperties = { StartIndexZero = true } };
222          FragmentStatistics.Rows.Add(row);
223        }
224
225        // parents
226        if (!FragmentStatistics.Rows.ContainsKey("Average parent length")) {
227          var row = new DataRow("Average parent length") { VisualProperties = { StartIndexZero = true } };
228          FragmentStatistics.Rows.Add(row);
229        }
230        // exact similarity
231        if (!FragmentStatistics.Rows.ContainsKey("Similarity (exact)")) {
232          var row = new DataRow("Similarity (exact)") { VisualProperties = { StartIndexZero = true } };
233          FragmentStatistics.Rows.Add(row);
234        }
235        #endregion
236
237        var fragments = new List<ISymbolicExpressionTreeNode>();
238        var parents = new List<ISymbolicExpressionTree>();
239        var trees = (from s in gScope.SubScopes select s.Variables.First().Value as ISymbolicExpressionTree).ToList();
240
241        foreach (var tree in trees.Where(x => GlobalTraceMap.ContainsKey(x))) {
242          if (GlobalTraceMap[tree].Count == 2) { // crossover
243            var parent0 = (ISymbolicExpressionTree)GlobalTraceMap[tree][0];
244            var nodes = tree.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
245            var index = ((IntValue)GlobalFragmentMap[tree]).Value;
246            var fragment = nodes[index];
247            if (fragment == null) throw new ArgumentException("Fragment not found");
248            parents.Add(parent0);
249            fragments.Add(fragment);
250          } else { // crossover followed by mutation
251            // maybe mutation fragments should be also taken into account?
252            var parent0 = (ISymbolicExpressionTree)GlobalTraceMap[tree][0];
253            if (!GlobalFragmentMap.ContainsKey(parent0)) throw new ArgumentException("Fragment not found");
254            var nodes = parent0.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
255            var index = ((IntValue)GlobalFragmentMap[parent0]).Value;
256            var fragment = nodes[index];
257            fragments.Add(fragment);
258            if (!GlobalTraceMap.ContainsKey(parent0)) throw new ArgumentException("Parent information not found");
259            parents.Add(parent0);
260          }
261        }
262        //var zeros = new List<int>(Enumerable.Repeat<int>(0, 201));
263        //var lengths = (from t in fragments
264        //               let len = t.GetLength()
265        //               orderby len
266        //               group len by len into g
267        //               select new Tuple<int,int>(g.First(), g.Count()));
268        //foreach (var len in lengths)
269        //  zeros[len.Item1] = len.Item2;
270        FragmentLengths.Rows["Parent lengths distribution"].Values.Replace(parents.Select(x => (double)x.Length));
271        FragmentLengths.Rows["Child lengths distribution"].Values.Replace(trees.Select(x => (double)x.Length));
272        FragmentLengths.Rows["Fragment lengths distribution"].Values.Replace(fragments.Select(x => (double)x.GetLength()));
273
274        // write values to file
275        double a1 = fragments.Average(x => x.GetLength());
276        double a2 = trees.Average(x => x.Length);
277        double a3 = parents.Average(x => x.Length);
278        double s1 = CalculateSimilarity(fragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact);
279
280
281        FragmentStatistics.Rows["Average fragment length"].Values.Add(a1);
282        FragmentStatistics.Rows["Average child length"].Values.Add(a2);
283        FragmentStatistics.Rows["Average parent length"].Values.Add(a3);
284        FragmentStatistics.Rows["Similarity (exact)"].Values.Add(s1);
285
286        #endregion
287
288        // clear the global maps to save memory
289        if (this.Successor == null || !(this.Successor is SymbolicExpressionTreeGenealogyAnalyzer)) {
290          GlobalCloneMap.Clear();
291          GlobalTraceMap.Clear();
292          GlobalFragmentMap.Clear();
293        }
294      }
295      return base.Apply();
296    }
297
298    #region Similarity computations
299    #region Obsolete code
300    private void CalculateDiversityIndicators(IEnumerable<ISymbolicExpressionTreeNode> fragments, out double a, out double b, out double c) {
301      //var frags = fragments.Where(x => x.GetLength() > 1).ToList();
302      var frags = fragments.ToList();
303      var sieve = new bool[frags.Count];
304      int max = 0;
305      for (int i = 0; i != frags.Count - 1; ++i) {
306        if (sieve[i]) continue;
307        int count = 0;
308        for (int j = i + 1; j != frags.Count; ++j) {
309          if (sieve[j]) continue;
310          if (frags[i].IsSimilarTo(frags[j], (int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact)) {
311            ++count;
312            sieve[i] = true;
313            sieve[j] = true;
314          }
315        }
316        if (max < count) max = count;
317      }
318      a = (double)sieve.Count(x => x) / sieve.Length;
319      sieve = new bool[frags.Count];
320      max = 0;
321      for (int i = 0; i != frags.Count - 1; ++i) {
322        if (sieve[i]) continue;
323        int count = 0;
324        for (int j = i + 1; j != frags.Count; ++j) {
325          if (sieve[j]) continue;
326          if (frags[i].IsSimilarTo(frags[j], (int)SymbolicExpressionTreeMatching.SimilarityLevel.High)) {
327            ++count;
328            sieve[i] = true;
329            sieve[j] = true;
330          }
331        }
332        if (max < count) max = count;
333      }
334      b = (double)sieve.Count(x => x) / sieve.Length;
335      sieve = new bool[frags.Count];
336      max = 0;
337      for (int i = 0; i != frags.Count - 1; ++i) {
338        if (sieve[i]) continue;
339        int count = 0;
340        for (int j = i + 1; j != frags.Count; ++j) {
341          if (sieve[j]) continue;
342          if (frags[i].IsSimilarTo(frags[j], (int)SymbolicExpressionTreeMatching.SimilarityLevel.Relaxed)) {
343            ++count;
344            sieve[i] = true;
345            sieve[j] = true;
346          }
347        }
348        if (max < count) max = count;
349      }
350      c = (double)sieve.Count(x => x) / max;
351    }
352    #endregion
353
354    /// <summary>
355    /// Provide a measure of how similar the fragments that get passed by crossover from one generation to the next are.
356    /// </summary>
357    /// <param name="fragments">The symbolic expression tree fragments</param>
358    /// <param name="mode">The similarity mode (0 - exact, 1 - high, 2 - relaxed)</param>
359    /// <returns>The average number of similar fragments</returns>
360    private double CalculateSimilarity(List<ISymbolicExpressionTreeNode> fragments, int mode) {
361      var visited = new bool[fragments.Count];
362      int groups = 0;
363      for (int i = 0; i != fragments.Count - 1; ++i) {
364        if (visited[i]) continue;
365        for (int j = i + 1; j != fragments.Count; ++j) {
366          if (visited[j]) continue;
367          if (fragments[i].IsSimilarTo(fragments[j], mode)) visited[j] = true;
368        }
369        ++groups;
370      }
371      return (double)fragments.Count / groups;
372    }
373    #endregion
374  } //SymbolicExpressionTreeFragmentsAnalyzer
375}
Note: See TracBrowser for help on using the repository browser.