Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFragmentsAnalyzer.cs @ 7799

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

#1772: Sanitized IGenealogyGraph interface, implemented new graph arc semantics (an arc signifies an interaction between the two nodes that it connects and has a data object containing specific information about the interaction).

File size: 15.0 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
55    #region Parameter properties
56    public ValueParameter<IntValue> UpdateIntervalParameter {
57      get { return (ValueParameter<IntValue>)Parameters[UpdateIntervalParameterName]; }
58    }
59    public ValueParameter<IntValue> UpdateCounterParameter {
60      get { return (ValueParameter<IntValue>)Parameters[UpdateCounterParameterName]; }
61    }
62    public LookupParameter<ResultCollection> ResultsParameter {
63      get { return (LookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
64    }
65    public LookupParameter<TraceMapType> GlobalTraceMapParameter {
66      get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
67    }
68    public LookupParameter<CloneMapType> GlobalCloneMapParameter {
69      get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
70    }
71    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
72      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
73    }
74    public LookupParameter<IntValue> GenerationsParameter {
75      get { return (LookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
76    }
77    public LookupParameter<DataTable> FragmentStatisticsParameter {
78      get { return (LookupParameter<DataTable>)Parameters[FragmentStatisticsParameterName]; }
79    }
80    #endregion
81
82    #region Parameters
83    public bool EnabledByDefault {
84      get { return true; }
85    }
86    public IntValue UpdateInterval {
87      get { return UpdateIntervalParameter.Value; }
88    }
89    public IntValue UpdateCounter {
90      get { return UpdateCounterParameter.Value; }
91    }
92    public ResultCollection Results {
93      get { return ResultsParameter.ActualValue; }
94    }
95    public CloneMapType GlobalCloneMap {
96      get { return GlobalCloneMapParameter.ActualValue; }
97    }
98    public TraceMapType GlobalTraceMap {
99      get { return GlobalTraceMapParameter.ActualValue; }
100    }
101    public CloneMapType GlobalFragmentMap {
102      get { return GlobalFragmentMapParameter.ActualValue; }
103    }
104    public IntValue Generations {
105      get { return GenerationsParameter.ActualValue; }
106    }
107    public DataTable FragmentStatistics {
108      get { return FragmentStatisticsParameter.ActualValue; }
109    }
110    #endregion
111
112    [StorableConstructor]
113    private SymbolicExpressionTreeFragmentsAnalyzer(bool deserializing)
114      : base() {
115    }
116    private SymbolicExpressionTreeFragmentsAnalyzer(SymbolicExpressionTreeFragmentsAnalyzer original, Cloner cloner)
117      : base(original, cloner) {
118    }
119    public override IDeepCloneable Clone(Cloner cloner) {
120      return new SymbolicExpressionTreeFragmentsAnalyzer(this, cloner);
121    }
122    public SymbolicExpressionTreeFragmentsAnalyzer()
123      : base() {
124      Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
125      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
126      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing the whole genealogy."));
127      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
128      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
129      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
130      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
131      Parameters.Add(new LookupParameter<DataTable>(FragmentStatisticsParameterName, "The data table to store the fragment statistics."));
132      UpdateCounterParameter.Hidden = true;
133      UpdateIntervalParameter.Hidden = true;
134    }
135    #region After deserialization code
136    [StorableHook(HookType.AfterDeserialization)]
137    private void AfterDeserialization() {
138      // check if all the parameters are present and accounted for
139      if (!Parameters.ContainsKey(UpdateIntervalParameterName)) {
140        Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
141      }
142      if (Parameters.ContainsKey(UpdateCounterParameterName)) return;
143      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
144      UpdateCounterParameter.Hidden = true;
145    }
146    #endregion
147    #region IStatefulItem members
148    public override void InitializeState() {
149      base.InitializeState();
150      UpdateCounter.Value = 0;
151    }
152
153    public override void ClearState() {
154      base.ClearState();
155      UpdateCounter.Value = 0;
156    }
157    #endregion
158
159    public override IOperation Apply() {
160      if (Generations.Value == 0) return base.Apply();
161      UpdateCounter.Value++;
162      if (UpdateCounter.Value == UpdateInterval.Value) {
163        ResultCollection results = ResultsParameter.ActualValue;
164        if (FragmentStatistics == null) {
165          FragmentStatisticsParameter.ActualValue = new DataTable("Fragment Statistics", "Statistical measurements of fragments aggregated over the whole population");
166          FragmentStatistics.VisualProperties.YAxisTitle = "Fragment length/Similarities";
167          results.Add(new Result("Fragment Statistics", FragmentStatistics));
168        }
169
170        UpdateCounter.Value = 0; // reset counter
171        var gScope = ExecutionContext.Scope;
172        while (gScope.Parent != null) gScope = gScope.Parent;
173
174        #region Fragment Statistics
175        var fragments = new List<ISymbolicExpressionTreeNode>();
176        var parents = new List<ISymbolicExpressionTree>();
177        var trees = (from s in gScope.SubScopes select s.Variables.First().Value as ISymbolicExpressionTree).ToList();
178        foreach (var tree in trees.Where(x => GlobalTraceMap.ContainsKey(x))) {
179          if (GlobalTraceMap[tree].Count == 2) { // crossover
180            var nodes = tree.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
181            var index = ((IntValue)GlobalFragmentMap[tree]).Value;
182            var fragment = nodes[index];
183            if (fragment == null) throw new ArgumentException("Fragment not found");
184            parents.AddRange(GlobalTraceMap[tree].Cast<ISymbolicExpressionTree>());
185            fragments.Add(fragment);
186          } else { // crossover followed by mutation
187            // maybe mutation fragments should be also taken into account?
188            var parent0 = (ISymbolicExpressionTree)GlobalTraceMap[tree][0];
189            if (!GlobalFragmentMap.ContainsKey(parent0)) throw new ArgumentException("Fragment not found");
190            var nodes = parent0.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
191            var index = ((IntValue)GlobalFragmentMap[parent0]).Value;
192            var fragment = nodes[index];
193            fragments.Add(fragment);
194            if (!GlobalTraceMap.ContainsKey(parent0)) throw new ArgumentException("Parent information not found");
195            parents.AddRange(GlobalTraceMap[parent0].Cast<ISymbolicExpressionTree>());
196          }
197        }
198
199        // write values to file
200        double a1 = fragments.Average(x => x.GetLength());
201        double a2 = trees.Average(x => x.Length);
202        double a3 = parents.Average(x => x.Length);
203        double s1 = CalculateSimilarity(fragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact);
204
205        #region Table data
206        // fragments
207        if (!FragmentStatistics.Rows.ContainsKey("Average fragment length")) {
208          var row = new DataRow("Average fragment length", "") { VisualProperties = { StartIndexZero = true } };
209          FragmentStatistics.Rows.Add(row);
210        }
211        FragmentStatistics.Rows["Average fragment length"].Values.Add(a1);
212        // child trees
213        if (!FragmentStatistics.Rows.ContainsKey("Average child length")) {
214          var row = new DataRow("Average child length", "") { VisualProperties = { StartIndexZero = true } };
215          FragmentStatistics.Rows.Add(row);
216        }
217        FragmentStatistics.Rows["Average child length"].Values.Add(a2);
218        // parents
219        if (!FragmentStatistics.Rows.ContainsKey("Average parent length")) {
220          var row = new DataRow("Average parent length", "") { VisualProperties = { StartIndexZero = true } };
221          FragmentStatistics.Rows.Add(row);
222        }
223        FragmentStatistics.Rows["Average parent length"].Values.Add(a3);
224        // exact similarity
225        if (!FragmentStatistics.Rows.ContainsKey("Similarity (exact)")) {
226          var row = new DataRow("Similarity (exact)", "") { VisualProperties = { StartIndexZero = true } };
227          FragmentStatistics.Rows.Add(row);
228        }
229        FragmentStatistics.Rows["Similarity (exact)"].Values.Add(s1);
230        #endregion
231
232        #endregion
233
234        // clear the global maps to save memory
235        if (this.Successor == null || !(this.Successor is SymbolicExpressionTreeGenealogyAnalyzer)) {
236          GlobalCloneMap.Clear();
237          GlobalTraceMap.Clear();
238          GlobalFragmentMap.Clear();
239        }
240      }
241      return base.Apply();
242    }
243
244    #region Similarity computations
245    #region Obsolete code
246    private void CalculateDiversityIndicators(IEnumerable<ISymbolicExpressionTreeNode> fragments, out double a, out double b, out double c) {
247      //var frags = fragments.Where(x => x.GetLength() > 1).ToList();
248      var frags = fragments.ToList();
249      var sieve = new bool[frags.Count];
250      int max = 0;
251      for (int i = 0; i != frags.Count - 1; ++i) {
252        if (sieve[i]) continue;
253        int count = 0;
254        for (int j = i + 1; j != frags.Count; ++j) {
255          if (sieve[j]) continue;
256          if (frags[i].IsSimilarTo(frags[j], (int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact)) {
257            ++count;
258            sieve[i] = true;
259            sieve[j] = true;
260          }
261        }
262        if (max < count) max = count;
263      }
264      a = (double)sieve.Count(x => x) / sieve.Length;
265      sieve = new bool[frags.Count];
266      max = 0;
267      for (int i = 0; i != frags.Count - 1; ++i) {
268        if (sieve[i]) continue;
269        int count = 0;
270        for (int j = i + 1; j != frags.Count; ++j) {
271          if (sieve[j]) continue;
272          if (frags[i].IsSimilarTo(frags[j], (int)SymbolicExpressionTreeMatching.SimilarityLevel.High)) {
273            ++count;
274            sieve[i] = true;
275            sieve[j] = true;
276          }
277        }
278        if (max < count) max = count;
279      }
280      b = (double)sieve.Count(x => x) / sieve.Length;
281      sieve = new bool[frags.Count];
282      max = 0;
283      for (int i = 0; i != frags.Count - 1; ++i) {
284        if (sieve[i]) continue;
285        int count = 0;
286        for (int j = i + 1; j != frags.Count; ++j) {
287          if (sieve[j]) continue;
288          if (frags[i].IsSimilarTo(frags[j], (int)SymbolicExpressionTreeMatching.SimilarityLevel.Relaxed)) {
289            ++count;
290            sieve[i] = true;
291            sieve[j] = true;
292          }
293        }
294        if (max < count) max = count;
295      }
296      c = (double)sieve.Count(x => x) / max;
297    }
298    #endregion
299
300    /// <summary>
301    /// Provide a measure of how similar the fragments that get passed by crossover from one generation to the next are.
302    /// </summary>
303    /// <param name="fragments">The symbolic expression tree fragments</param>
304    /// <param name="mode">The similarity mode (0 - exact, 1 - high, 2 - relaxed)</param>
305    /// <returns>The average number of similar fragments</returns>
306    private double CalculateSimilarity(List<ISymbolicExpressionTreeNode> fragments, int mode) {
307      var visited = new bool[fragments.Count];
308      int groups = 0;
309      for (int i = 0; i != fragments.Count - 1; ++i) {
310        if (visited[i]) continue;
311        for (int j = i + 1; j != fragments.Count; ++j) {
312          if (visited[j]) continue;
313          if (fragments[i].IsSimilarTo(fragments[j], mode)) visited[j] = true;
314        }
315        ++groups;
316      }
317      return (double)fragments.Count / groups;
318    }
319    #endregion
320  } //SymbolicExpressionTreeFragmentsAnalyzer
321}
Note: See TracBrowser for help on using the repository browser.