Changeset 8557 for branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4

Timestamp:

09/03/12 15:26:04 (12 years ago)

Author:

bburlacu

Message:

#1772: Introduced base class and interface for tracing operators. Introduced SymbolicExpressionTreeNodeComparer interface to be implemented by node matching operators. Fixed bug in the TracingSymbolicExpressionTreeManipulator where nodes modified by the Full- and OnePoint tree shakers were not correctly detected. The SymbolicExpressionTreeNodeSimilarityComparer is now injected in the tracing genetic operators as a parameter.

Location:

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4

Files:

• Analyzers/SymbolicExpressionTreeFragmentsAnalyzer.cs (modified) (16 diffs)
• Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs (modified) (10 diffs)
• HeuristicLab.EvolutionaryTracking-3.4.csproj (modified) (1 diff)
• Plugin.cs (modified) (1 diff)

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFragmentsAnalyzer.cs

@@ -33 +33 @@
 using HeuristicLab.Problems.DataAnalysis;
 using HeuristicLab.Problems.DataAnalysis.Symbolic;
+// type definitions for convenience
 using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
-// type definitions for convenience
 using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
-using SymbolicExpressionTreeNodeItem = HeuristicLab.EvolutionaryTracking.GenericWrapper<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeNode>;
+using SymbolicExpressionTreeNodeItem = HeuristicLab.EvolutionaryTracking.GenericWrapper<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>;
 using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;
 
@@ -47 +47 @@
   [StorableClass]
   public sealed class SymbolicExpressionTreeFragmentsAnalyzer : SingleSuccessorOperator, IAnalyzer {
+    #region Parameter names
     private const string UpdateIntervalParameterName = "UpdateInterval";
     private const string UpdateCounterParameterName = "UpdateCounter";
@@ -62 +63 @@
     private const string FragmentLengthsDistributionParametersName = "FragmentLengths";
     private const string FragmentFrequenciesParameterName = "FragmentFrequencies";
+    private const string ParentsDiversityParameterName = "ParentsDiversity";
+    #endregion
 
     // impact values calculator
-    private SymbolicRegressionSolutionValuesCalculator _calculator = new SymbolicRegressionSolutionValuesCalculator();
+    private readonly SymbolicRegressionSolutionValuesCalculator calculator = new SymbolicRegressionSolutionValuesCalculator();
 
     #region Parameter properties
@@ -97 +100 @@
     public LookupParameter<DataTable> FragmentLengthsParameter {
       get { return (LookupParameter<DataTable>)Parameters[FragmentLengthsDistributionParametersName]; }
+    }
+    public LookupParameter<DataTable> ParentsDiversityParameter {
+      get { return (LookupParameter<DataTable>)Parameters[ParentsDiversityParameterName]; }
     }
     // auxiliary structures for tracking fragments and individuals from the previous generation
@@ -165 +171 @@
       get { return FragmentFrequenciesParameter.ActualValue; }
     }
+    public DataTable ParentsDiversity {
+      get { return ParentsDiversityParameter.ActualValue; }
+    }
     public SymbolicDataAnalysisExpressionTreeInterpreter SymbolicExpressionInterpreter {
       get { return SymbolicExpressionInterpreterParameter.ActualValue; }
@@ -174 +183 @@
 
     [StorableConstructor]
-    private SymbolicExpressionTreeFragmentsAnalyzer(bool deserializing)
-      : base() {
-    }
-    private SymbolicExpressionTreeFragmentsAnalyzer(SymbolicExpressionTreeFragmentsAnalyzer original, Cloner cloner)
-      : base(original, cloner) {
-    }
+    private SymbolicExpressionTreeFragmentsAnalyzer(bool deserializing) : base(deserializing) { }
+    private SymbolicExpressionTreeFragmentsAnalyzer(SymbolicExpressionTreeFragmentsAnalyzer original, Cloner cloner) : base(original, cloner) { }
     public override IDeepCloneable Clone(Cloner cloner) {
       return new SymbolicExpressionTreeFragmentsAnalyzer(this, cloner);
@@ -185 +190 @@
     public SymbolicExpressionTreeFragmentsAnalyzer()
       : base() {
+      #region Add parameters
       // analyzer update counter and update interval
       Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
@@ -196 +202 @@
       Parameters.Add(new LookupParameter<CloneMapType>(SecondaryCloneMapParameterName, "Parameter to store the clone map from the previous generation"));
       Parameters.Add(new LookupParameter<CloneMapType>(SecondaryFragmentMapParameterName, "Parameter to store the fragment map from the previous generation"));
-      // other params
+      // fragment statistics parameters
       Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
       Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
@@ -202 +208 @@
       Parameters.Add(new LookupParameter<DataTable>(FragmentLengthsDistributionParametersName, "The data table to store the distribution of fragment lengths."));
       Parameters.Add(new LookupParameter<DataTable>(FragmentFrequenciesParameterName, "A data structure for fragment frequencies"));
+      Parameters.Add(new LookupParameter<DataTable>(ParentsDiversityParameterName, "A data structure to store the diversity of the parents per generation."));
       // impact calculation
       Parameters.Add(new LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>(SymbolicExpressionInterpreterParameterName, "Interpreter for symbolic expression trees"));
       Parameters.Add(new LookupParameter<RegressionProblemData>(SymbolicRegressionProblemDataParameterName, "The symbolic data analysis problem."));
+      #endregion
+
       UpdateCounterParameter.Hidden = true;
       UpdateIntervalParameter.Hidden = true;
-
-      //_calculator = new SymbolicRegressionSolutionValuesCalculator();
     }
     #region After deserialization code
@@ -230 +237 @@
         Parameters.Add(new LookupParameter<ItemList<ItemList<IItem>>>(FragmentFrequenciesParameterName, "A data structure for fragment frequencies"));
       }
+      if (!Parameters.ContainsKey(ParentsDiversityParameterName)) {
+        Parameters.Add(new LookupParameter<DataTable>(ParentsDiversityParameterName, "A data table to store the diversity of the parents per generation."));
+      }
     }
     #endregion
@@ -244 +254 @@
     #endregion
 
+    /* A small description of the way this analyzer works
+     * 
+     * We keep 3 maps in the global scope: the GlobalTraceMap, the GlobalFragmentMap and the GlobalCloneMap that are updated on each step: selection, crossover, mutation
+     * These maps provide information about the children, parents and transferred fragments as follows:
+     * 
+     * 1) GlobalCloneMap
+     *    This data structure provides the basis for tracking. In the selection step, every selected individual gets cloned and transferred into the recombination pool.
+     *    The GlobalCloneMap keeps track of clones by mapping them to the original individuals. This is an essential step for building the genealogy graph. Using this
+     *    structure we can find out how many times each individual was selected. 
+     *    The GlobalCloneMap consists of Key-Value pairs Clone->Original
+     *
+     * 2) GlobalTraceMap
+     *    Keeps information in the form of key-value pairs Child->{Parents}, where {Parents} is a set consisting of 
+     *      - one parent individual (in the case of mutation), by language abuse we say that the individual that mutation acted on is the parent,
+     *        and the resulting individual is the child
+     *      - two parent individuals (in the case of crossover), named Parent0 and Parent1. Parent0 is the individual that crossover acts on by replacing 
+     *        one of its subtrees with a compatible subtree, randomly selected from Parent1
+     *
+     *    CROSSOVER
+     *        Parent0     Parent1                                                                    {Parents}
+     *           \           /                                                                           ^
+     *            \       fragment (inserted from Parent1 into Parent0 to create the Child)              ^    [Mapping provided by the GlobalTraceMap]
+     *             \       /                                                                             ^
+     *              \     /                                                                              ^
+     *               Child                                                                             Child
+     *               
+     *    MUTATION
+     *        Parent0
+     *           |
+     *           |    [mutation acts on a random node/subtree in the 'parent' individual
+     *           |
+     *         Child
+     *         
+     *    Since crossover and mutation act on individuals in the recombination pool (which in fact are clones of individuals from the previous generation), the GlobalTraceMap
+     *    is populated with values given by the mappings in the GlobalCloneMap, so that the original parent for each child is known.
+     *    
+     *  3) GlobalFragmentMap
+     *     Keeps information in the form of Key-Value pairs about an individual and its respective fragment 
+     *     (ie., the subtree received via crossover or created/altered by mutation)
+     * */
     public override IOperation Apply() {
-      if (Generations.Value == 0) return base.Apply();
       UpdateCounter.Value++;
       if (UpdateCounter.Value == UpdateInterval.Value) {
-        ResultCollection results = ResultsParameter.ActualValue;
-        if (FragmentStatistics == null) {
-          FragmentStatisticsParameter.ActualValue = new DataTable("Fragment Statistics", "Statistical measurements of fragments aggregated over the whole population");
-          FragmentStatistics.VisualProperties.YAxisTitle = "Fragment length/Similarities";
-          results.Add(new Result("Fragment Statistics", FragmentStatistics));
+        UpdateCounter.Value = 0; // reset counter
+        if (Generations.Value > 0) {
+          InitializeParameters();
+
+          CalculateFragmentStatistics();
+
+          // save the current generation so it can be compared to the following one, next time the analyzer is applied
+          SecondaryTraceMap = (TraceMapType)GlobalTraceMap.Clone();
+          SecondaryTraceMap.Clear();
+          foreach (var m in GlobalTraceMap)
+            SecondaryTraceMap.Add(m.Key, m.Value);
+
+          SecondaryCloneMap.Clear();
+          foreach (var m in GlobalCloneMap)
+            SecondaryCloneMap.Add(m.Key, m.Value);
+
+          SecondaryFragmentMap.Clear();
+          foreach (var m in GlobalFragmentMap)
+            SecondaryFragmentMap.Add(m.Key, m.Value);
         }
-        if (FragmentLengths == null) {
-          FragmentLengthsParameter.ActualValue = new DataTable("Fragment Lengths", "Histograms for the distribution of fragment and individual lengths");
-          FragmentLengths.VisualProperties.YAxisTitle = "Frequency";
-          results.Add(new Result("Fragment Lengths", FragmentLengths));
-        }
-        if (FragmentFrequencies == null) {
-          FragmentFrequenciesParameter.ActualValue = new DataTable("Fragment Frequencies", "Frequencies of good and high impact fragments");
-          FragmentFrequencies.VisualProperties.YAxisTitle = "Frequency";
-          results.Add(new Result("Fragment Frequencies", FragmentFrequencies));
-        }
-        if (SecondaryTraceMap == null) {
-          SecondaryTraceMap = new TraceMapType();
-        }
-        if (SecondaryCloneMap == null) {
-          SecondaryCloneMap = new CloneMapType();
-        }
-        if (SecondaryFragmentMap == null) {
-          SecondaryFragmentMap = new CloneMapType();
-        }
-
-        UpdateCounter.Value = 0; // reset counter
-        var gScope = ExecutionContext.Scope;
-        while (gScope.Parent != null) gScope = gScope.Parent;
-
-        // for this kind of tracking/analysis, we need at least 2 successive generations of crossover
-        if (Generations.Value > 1) {
-          #region Fragment Statistics
-          InitializeRows();
-          // create a dictionary for fast lookup of parents (to see which children from the previous generation become parents, and count their fragments)
-          var parentsLookup = new Dictionary<ISymbolicExpressionTree, bool>();
-          foreach (var parent in GlobalTraceMap.Values.SelectMany(x => x.Cast<ISymbolicExpressionTree>())) {
-            if (!parentsLookup.ContainsKey(parent)) {
-              parentsLookup.Add(parent, true);
-            }
-          }
-          // the same, for fast lookup of clones (might not be needed after all)
-          var clonesLookup = new Dictionary<ISymbolicExpressionTree, bool>();
-          foreach (var original in GlobalCloneMap.Values.Cast<ISymbolicExpressionTree>()) {
-            if (!clonesLookup.ContainsKey(original)) {
-              clonesLookup.Add(original, true);
-            }
-          }
-          var goodFragments = new List<ISymbolicExpressionTreeNode>();
-          var goodParents = new List<ISymbolicExpressionTree>();
-          var goodChildren = new List<ISymbolicExpressionTree>();
-          // take all individuals that have received a fragment in the previous generation
-          foreach (var m in SecondaryFragmentMap) {
-            var individual = m.Key as ISymbolicExpressionTree;
-            // check if the individual became a parent in the current generation,
-            // by checking if it appears among the parents from the current generation trace map
-            if (parentsLookup.ContainsKey(individual)) {
-              var fragmentItem = m.Value as SymbolicExpressionTreeNodeItem;
-              var fragment = fragmentItem.Content;
-              if (fragment != null) {
-                goodFragments.Add(fragmentItem.Content);
-                goodParents.AddRange(SecondaryTraceMap[individual].Cast<ISymbolicExpressionTree>());
-                goodChildren.Add(individual);
-              }
-            }
-          }
-          var allFragments = SecondaryFragmentMap.Values.Where(x => ((SymbolicExpressionTreeNodeItem)x).Content != null).Select(x => ((SymbolicExpressionTreeNodeItem)x).Content as ISymbolicExpressionTreeNode).ToList();
-          var highImpactFragments = new List<ISymbolicExpressionTreeNode>();
-          var allParents = SecondaryTraceMap.Values.SelectMany(x => x.Cast<ISymbolicExpressionTree>()).ToList();
-          var allChildren = SecondaryFragmentMap.Keys.Select(x => x as ISymbolicExpressionTree).ToList();
-          // high impact fragments
-          //foreach (var c in goodChildren) {
-          //  var impactValues = _calculator.CalculateImpactValues(c, SymbolicExpressionInterpreter, SymbolicRegressionProblemData, 0, 0);
-          //  var fragmentItem = SecondaryFragmentMap[c] as SymbolicExpressionTreeNodeItem;
-          //  var fragment = fragmentItem.Content;
-          //  if (fragment != null && impactValues[fragment] > 0.1)
-          //    highImpactFragments.Add(fragment);
-          //}
-          FragmentFrequencies.Rows["Frequency of useful fragments"].Values.Add(goodFragments.Count);
-          FragmentFrequencies.Rows["Frequency of high impact fragments"].Values.Add(highImpactFragments.Count);
-          FragmentStatistics.Rows["Fragment lengths (good)"].Values.Add(goodFragments.Average(x => x.GetLength()));
-          FragmentStatistics.Rows["Fragment lengths (all)"].Values.Add(allFragments.Average(x => x.GetLength()));
-          //double avg = highImpactFragments.Count > 0 ? highImpactFragments.Average(x => x.GetLength()) : 0;
-          //FragmentStatistics.Rows["Fragment lengths (high impact)"].Values.Add(avg);
-          FragmentStatistics.Rows["Parent lengths (good)"].Values.Add(goodParents.Average(x => x.Length));
-          FragmentStatistics.Rows["Parent lengths (all)"].Values.Add(allParents.Average(x => x.Length));
-          FragmentStatistics.Rows["Child lengths (good)"].Values.Add(goodChildren.Average(x => x.Length));
-          FragmentStatistics.Rows["Child lengths (all)"].Values.Add(allChildren.Average(x => x.Length));
-          FragmentStatistics.Rows["Avg visitation length (all children)"].Values.Add(allChildren.Average(x => VisitationLength(x)));
-          FragmentStatistics.Rows["Avg visitation length (good children)"].Values.Add(goodChildren.Average(x => VisitationLength(x)));
-          //FragmentStatistics.Rows["Exact similarity (good fragments)"].Values.Add(CalculateSimilarity(allFragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact));
-          //foreach (var f in allFragments) f.SortSubtrees();
-          //FragmentStatistics.Rows["Exact similarity (all fragments)"].Values.Add(CalculateSimilarity(allFragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact));
-
-          FragmentLengths.Rows["All fragments length distribution"].Values.Replace(allFragments.Select(x => (double)x.GetLength()));
-          FragmentLengths.Rows["Useful fragments length distribution"].Values.Replace(goodFragments.Select(x => (double)x.GetLength()));
-          FragmentLengths.Rows["All children length distribution"].Values.Replace(allChildren.Select(x => (double)x.Length));
-          FragmentLengths.Rows["Useful children length distribution"].Values.Replace(goodChildren.Select(x => (double)x.Length));
-          #endregion
-        }
-        // save the current generation so it can be compared to the following one, next time the analyzer is applied
-        SecondaryTraceMap.Clear();
-        foreach (var m in GlobalTraceMap)
-          SecondaryTraceMap.Add(m.Key, m.Value);
-
-        SecondaryCloneMap.Clear();
-        foreach (var m in GlobalCloneMap)
-          SecondaryCloneMap.Add(m.Key, m.Value);
-
-        SecondaryFragmentMap.Clear();
-        foreach (var m in GlobalFragmentMap)
-          SecondaryFragmentMap.Add(m.Key, m.Value);
-
-        // clear the global maps to save memory
+      }
+      if (Generations.Value > 0)
         if (this.Successor == null || !(this.Successor is SymbolicExpressionTreeGenealogyAnalyzer)) {
+          // clear the global maps to save memory
           GlobalCloneMap.Clear();
           GlobalTraceMap.Clear();
           GlobalFragmentMap.Clear();
         }
-      }
       return base.Apply();
+    }
+
+    private void InitializeParameters() {
+      #region Init parameters
+      var results = ResultsParameter.ActualValue;
+
+      if (FragmentStatistics == null) {
+        FragmentStatisticsParameter.ActualValue = new DataTable("Fragment Statistics", "Statistical measurements of fragments aggregated over the whole population");
+        FragmentStatistics.VisualProperties.YAxisTitle = "Fragment length/Similarities";
+        results.Add(new Result("Fragment Statistics", FragmentStatistics));
+      }
+      if (FragmentLengths == null) {
+        FragmentLengthsParameter.ActualValue = new DataTable("Fragment Lengths", "Histograms for the distribution of fragment and individual lengths");
+        FragmentLengths.VisualProperties.YAxisTitle = "Frequency";
+        results.Add(new Result("Fragment Lengths", FragmentLengths));
+      }
+      if (FragmentFrequencies == null) {
+        FragmentFrequenciesParameter.ActualValue = new DataTable("Fragment Frequencies", "Frequencies of good and high impact fragments");
+        FragmentFrequencies.VisualProperties.YAxisTitle = "Frequency";
+        results.Add(new Result("Fragment Frequencies", FragmentFrequencies));
+      }
+      if (ParentsDiversity == null) {
+        ParentsDiversityParameter.ActualValue = new DataTable("Parents Diversity", "Number of unique parents per generation");
+        ParentsDiversity.VisualProperties.YAxisTitle = "Unique parents";
+        results.Add(new Result("Parents Diversity", ParentsDiversity));
+      }
+      if (SecondaryTraceMap == null) {
+        SecondaryTraceMap = new TraceMapType();
+      }
+      if (SecondaryCloneMap == null) {
+        SecondaryCloneMap = new CloneMapType();
+      }
+      if (SecondaryFragmentMap == null) {
+        SecondaryFragmentMap = new CloneMapType();
+      }
+      #endregion
     }
 
@@ -435 +428 @@
       if (!FragmentFrequencies.Rows.ContainsKey("Frequency of high impact fragments")) {
         FragmentFrequencies.Rows.Add(new DataRow("Frequency of high impact fragments") {
+          VisualProperties = { StartIndexZero = true }
+        });
+      }
+      if (!ParentsDiversity.Rows.ContainsKey("Unique parents")) {
+        ParentsDiversity.Rows.Add(new DataRow("Unique parents") {
           VisualProperties = { StartIndexZero = true }
         });
@@ -473 +471 @@
     }
 
+    private void CalculateFragmentStatistics() {
+      // for this kind of tracking/analysis, we need at least 2 successive generations of crossover
+      if (Generations.Value > 1) {
+        InitializeRows();
+
+        #region Fragment Statistics
+        // create a hashset for fast lookup of parents (to see which children from the previous generation become parents, and count their fragments)
+        var parentsLookup = new HashSet<ISymbolicExpressionTree>(GlobalTraceMap.Values.SelectMany(x => x.Cast<ISymbolicExpressionTree>()));
+        var allParents = SecondaryTraceMap.Values.SelectMany(x => x.Cast<ISymbolicExpressionTree>()).ToList();
+        var allChildren = SecondaryFragmentMap.Keys.Cast<ISymbolicExpressionTree>().ToList(); /* SecondaryTraceMap.Keys should be the same with SecondaryFragmentMap.Keys */
+        var allFragments = SecondaryFragmentMap.Values.Cast<SymbolicExpressionTreeNodeItem>().Select(x => x.Content).Where(x => x != null).ToList();
+        // "good" fragments are fragments contained in a surviving offspring (that became a parent)
+        // "good" parents are those that produced a surviving offspring
+        // "good" children are the surviving offspring
+        var goodFragments = new List<ISymbolicExpressionTreeNode>();
+        var goodParents = new List<ISymbolicExpressionTree>();
+        var goodChildren = new List<ISymbolicExpressionTree>();
+
+        // take all individuals that have received a fragment in the previous generation
+        foreach (var m in SecondaryFragmentMap) {
+          var individual = m.Key as ISymbolicExpressionTree;
+          // check if the individual became a parent in the current generation,
+          // by checking if it appears among the parents from the current generation trace map
+          if (parentsLookup.Contains(individual)) {
+            var symbExprTreeNodeItem = m.Value as SymbolicExpressionTreeNodeItem;
+            var fragment = symbExprTreeNodeItem.Content;
+            if (fragment != null) {
+              goodFragments.Add(fragment);
+              goodParents.AddRange(SecondaryTraceMap[individual].Cast<ISymbolicExpressionTree>());
+              goodChildren.Add(individual);
+            }
+          }
+        }
+
+        if (false) {
+          var highImpactFragments = new List<ISymbolicExpressionTreeNode>();
+          foreach (var child in goodChildren) {
+            var impactValues = calculator.CalculateImpactValues(child, SymbolicExpressionInterpreter, SymbolicRegressionProblemData, 0, 0);
+            var fragmentItem = SecondaryFragmentMap[child] as SymbolicExpressionTreeNodeItem;
+            var fragment = fragmentItem.Content;
+            if (fragment != null && impactValues[fragment] > 0.1) {
+              if (highImpactFragments.Contains(fragment, new SymbolicExpressionTreeNodeSimilarityComparer(SimilarityLevel.Exact)))
+                continue;
+              // prune fragment (remove irrelevant/low impact nodes)
+              // this works because a child will never have an impact value greater than its parent
+              foreach (var fnode in fragment.IterateNodesBreadth().Where(x => x.SubtreeCount > 0)) {
+                for (int i = 0; i < fnode.SubtreeCount; ++i) {
+                  var subtree = fnode.GetSubtree(i);
+                  if (impactValues[subtree] < 0.1)
+                    fnode.RemoveSubtree(i);
+                }
+              }
+              highImpactFragments.Add(fragment);
+            }
+          }
+        }
+
+        FragmentFrequencies.Rows["Frequency of useful fragments"].Values.Add(goodFragments.Count);
+        //        FragmentFrequencies.Rows["Frequency of high impact fragments"].Values.Add(highImpactFragments.Count);
+        FragmentStatistics.Rows["Fragment lengths (good)"].Values.Add(goodFragments.Average(x => x.GetLength()));
+        FragmentStatistics.Rows["Fragment lengths (all)"].Values.Add(allFragments.Average(x => x.GetLength()));
+        //        double avg = highImpactFragments.Count > 0 ? highImpactFragments.Average(x => x.GetLength()) : 0;
+        //        FragmentStatistics.Rows["Fragment lengths (high impact)"].Values.Add(avg);
+        FragmentStatistics.Rows["Parent lengths (good)"].Values.Add(goodParents.Average(x => x.Length));
+        FragmentStatistics.Rows["Parent lengths (all)"].Values.Add(allParents.Average(x => x.Length));
+        FragmentStatistics.Rows["Child lengths (good)"].Values.Add(goodChildren.Average(x => x.Length));
+        FragmentStatistics.Rows["Child lengths (all)"].Values.Add(allChildren.Average(x => x.Length));
+        //        FragmentStatistics.Rows["Avg visitation length (all children)"].Values.Add(allChildren.Average(x => VisitationLength(x)));
+        //        FragmentStatistics.Rows["Avg visitation length (good children)"].Values.Add(goodChildren.Average(x => VisitationLength(x)));
+        FragmentLengths.Rows["All fragments length distribution"].Values.Replace(allFragments.Select(x => (double)x.GetLength()));
+        FragmentLengths.Rows["Useful fragments length distribution"].Values.Replace(goodFragments.Select(x => (double)x.GetLength()));
+        FragmentLengths.Rows["All children length distribution"].Values.Replace(allChildren.Select(x => (double)x.Length));
+        FragmentLengths.Rows["Useful children length distribution"].Values.Replace(goodChildren.Select(x => (double)x.Length));
+        ParentsDiversity.Rows["Unique parents"].Values.Add(SecondaryCloneMap.Values.GroupBy(x => x).Count());
+        #endregion
+      }
+    }
+
     private static int VisitationLength(ISymbolicExpressionTree tree) {
       return VisitationLength(tree.Root);
@@ -478 +554 @@
 
     private static int VisitationLength(ISymbolicExpressionTreeNode node) {
-      int sum = 0;
-      foreach (var n in node.IterateNodesBreadth())
-        sum += n.GetLength();
-      return sum;
+      return node.IterateNodesBreadth().Sum(n => n.GetLength());
     }
 
@@ -491 +564 @@
     /// <param name="mode">The similarity mode (0 - exact, 1 - high, 2 - relaxed)</param>
     /// <returns>The average number of similar fragments</returns>
-    private static double CalculateSimilarity(IList<ISymbolicExpressionTreeNode> fragments, int mode) {
+    private static double CalculateSimilarity(IList<ISymbolicExpressionTreeNode> fragments, SimilarityLevel similarity) {
       var visited = new bool[fragments.Count];
       int groups = 0;
@@ -498 +571 @@
         for (int j = i + 1; j != fragments.Count; ++j) {
           if (visited[j]) continue;
-          if (fragments[i].IsSimilarTo(fragments[j], mode)) visited[j] = true;
+          if (fragments[i].IsSimilarTo(fragments[j], similarity))
+            visited[j] = true;
         }
         ++groups;

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs

@@ -20 +20 @@
 #endregion
 
-using System;
-using System.Drawing;
 using System.Globalization;
 using System.Linq;
-using System.Text;
 using System.Threading;
 using HeuristicLab.Common;
@@ -44 +41 @@
   /// An operator that tracks the genealogy of every individual
   /// </summary>
-  [Item("SymbolicExpressionTreeGenealogyAnalyzer", "An operator that tracks tree lengths of Symbolic Expression Trees")]
+  [Item("SymbolicExpressionTreeGenealogyAnalyzer", "An operator that tracks the genealogy of tree individuals")]
   [StorableClass]
   public sealed class SymbolicExpressionTreeGenealogyAnalyzer : SingleSuccessorOperator, IAnalyzer {
+    #region Parameter names
     private const string UpdateIntervalParameterName = "UpdateInterval";
     private const string UpdateCounterParameterName = "UpdateCounter";
@@ -63 +61 @@
     private const string SymbolicRegressionProblemDataParameterName = "ProblemData";
     private const string SymbolicDataAnalysisProblemEvaluatorParameterName = "Evaluator";
+    #endregion
 
     #region Parameter properties
@@ -159 +158 @@
 
     [StorableConstructor]
-    private SymbolicExpressionTreeGenealogyAnalyzer(bool deserializing)
-      : base() {
-    }
-    private SymbolicExpressionTreeGenealogyAnalyzer(SymbolicExpressionTreeGenealogyAnalyzer original, Cloner cloner)
-      : base(original, cloner) {
-    }
+    private SymbolicExpressionTreeGenealogyAnalyzer(bool deserializing) : base(deserializing) { }
+    private SymbolicExpressionTreeGenealogyAnalyzer(SymbolicExpressionTreeGenealogyAnalyzer original, Cloner cloner) : base(original, cloner) { }
     public override IDeepCloneable Clone(Cloner cloner) {
       return new SymbolicExpressionTreeGenealogyAnalyzer(this, cloner);
@@ -218 +213 @@
         UpdateCounter.Value = 0; // reset counter
 
-        var gScope = ExecutionContext.Scope;
-        while (gScope.Parent != null) gScope = gScope.Parent;
         SymbolicExpressionTreeGenealogyGraph graph;
         if (!Results.ContainsKey(PopulationGraphResultParameterName)) {
@@ -227 +220 @@
           graph = (SymbolicExpressionTreeGenealogyGraph)(Results[PopulationGraphResultParameterName].Value);
         }
-        // get tree quality values (Key => Individual, Value => Quality)
+
+        var gScope = ExecutionContext.Scope;
+        while (gScope.Parent != null) gScope = gScope.Parent;
         var scopes = (from s in gScope.SubScopes
                       let individual = s.Variables.First().Value
@@ -240 +235 @@
           var indiv = scopes[i].Tree;
           var label = (generation * scopes.Count + i + 1).ToString(CultureInfo.InvariantCulture);
-          if (!graph.HasNode(indiv)) {
-            var node = new GenealogyGraphNode(indiv) { Label = label };
-            graph.AddNode(node);
-            // node metadata
-            graph[node].Ranks.Add(generation);
-            graph[node].Quality = scopes[i].Quality;
-            graph[node].IsElite = i < Elites.Value;
-          } else {
-            var node = graph.GetNode(indiv);
-            graph[node].Ranks.Add(generation);
-          }
+          var childGraphNode = new SymbolicExpressionGenealogyGraphNode {
+            SymbolicExpressionTree = indiv,
+            Quality = scopes[i].Quality,
+            IsElite = i < Elites.Value,
+            Label = label
+          };
+          graph.AddNode(childGraphNode);
+          childGraphNode.Ranks.Add(generation);
           if (generation == 0) continue;
           if (!GlobalTraceMap.ContainsKey(indiv)) continue;
@@ -256 +248 @@
           var parents = GlobalTraceMap[indiv].Cast<ISymbolicExpressionTree>();
           foreach (var parent in parents) {
-            object data = ((GenericWrapper<SymbolicExpressionTreeNode>)GlobalFragmentMap[indiv]).Content;
+            var fragmentFromParent = ((GenericWrapper<ISymbolicExpressionTreeNode>)GlobalFragmentMap[indiv]).Content;
+            SymbolicExpressionGenealogyGraphNode parentGraphNode;
             if (GlobalTraceMap.ContainsKey(parent)) {
-              var node = new GenealogyGraphNode(parent) { Label = "X" };
-              graph.AddNode(node);
-              graph[node].Quality = Evaluate(parent);
-              graph[node].Ranks.Add(generation - 0.5);
-              var pp = GlobalTraceMap[parent].Cast<SymbolicExpressionTree>();
-              foreach (var p in pp) {
-                data = ((GenericWrapper<SymbolicExpressionTreeNode>)GlobalFragmentMap[parent]).Content;
-                graph.AddArc(p, parent, null, data);
+              parentGraphNode = new SymbolicExpressionGenealogyGraphNode {
+                SymbolicExpressionTree = parent,
+                Quality = Evaluate(parent)
+              };
+              graph.AddNode(parentGraphNode);
+              parentGraphNode.Ranks.Add(generation - 0.5);
+              var parentParents = GlobalTraceMap[parent].Cast<SymbolicExpressionTree>();
+              foreach (var parentParent in parentParents) {
+                var fragmentFromParentParent = ((GenericWrapper<ISymbolicExpressionTreeNode>)GlobalFragmentMap[parent]).Content;
+                // we store the fragment in the arc
+                var parentParentGraphNode = graph.GetGraphNodes(parentParent).Last();
+                graph.AddArc(parentParentGraphNode, parentGraphNode, null, fragmentFromParentParent);
               }
+            } else { // individual is an elite
+              parentGraphNode = graph.GetGraphNodes(parent).Last();
             }
-            graph.AddArc(parent, indiv, null, data);
+            graph.AddArc(parentGraphNode, childGraphNode, null, fragmentFromParent);
           }
         }
         // clear trace and clone maps in preparation for the next generation
-        if (generation == 0) return base.Apply();
+
+      }
+      if (Generations.Value > 0)
         if (this.Successor == null || !(this.Successor is SymbolicExpressionTreeFragmentsAnalyzer)) {
           GlobalTraceMap.Clear();
@@ -278 +279 @@
           GlobalFragmentMap.Clear();
         }
-      }
       return base.Apply();
     }
@@ -296 +296 @@
       return quality;
     }
-
-    #region Export to dot file
-    private static void WriteDot(string path, SymbolicExpressionTreeGenealogyGraph graph) {
-      using (var file = new System.IO.StreamWriter(path)) {
-        string nl = Environment.NewLine;
-        file.WriteLine("digraph \"lineage " + graph.AverageDegree.ToString(CultureInfo.InvariantCulture) + "\" {" + nl + "ratio=auto;" + nl + "mincross=2.0");
-        file.WriteLine("\tnode [shape=circle,label=\"\",style=filled]");
-
-        foreach (var node in graph.Values) {
-          var color = Color.FromArgb((int)((1 - graph[node].Quality) * 255), (int)(graph[node].Quality * 255), 0);
-          string fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", color.R, color.G, color.B);
-          string shape = "circle";
-          if (graph[node].IsElite)
-            shape = "doublecircle";
-          file.WriteLine("\t\"" + node.Id + "\" [shape=" + shape + ",fillcolor=\"" + fillColor + "\",label=\"" + node.Label + "\"];");
-          if (node.InEdges == null)
-            continue;
-          foreach (var edge in node.InEdges) {
-            //var edgeStyle = node.InEdges.Count == 1 ? "dashed" : String.Empty;
-            var edgeStyle = String.Empty;
-            file.WriteLine("\t\"" + edge.Target.Id + "\" -> \"" + node.Id + "\" [arrowsize=.5, color=\"" + fillColor + "\", style=\"" + edgeStyle + "\"];");
-          }
-        }
-        foreach (var g in graph.Values.GroupBy(x => graph[x].Ranks[0])) {
-          var sb = new StringBuilder();
-          sb.Append("\t{rank=same;");
-          foreach (var node in g)
-            sb.Append("\"" + node.Id + "\" ");
-          sb.Append("}\n");
-          file.Write(sb.ToString());
-        }
-        file.WriteLine("}");
-      }
-    }
-    #endregion
   }
 }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/HeuristicLab.EvolutionaryTracking-3.4.csproj

@@ -89 +89 @@
     <Compile Include="Analyzers\SymbolicExpressionTreeFragmentsAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicExpressionTreeGenealogyAnalyzer.cs" />
+    <Compile Include="Analyzers\SymbolicExpressionTreeLineagesAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicExpressionTreeRelativeLengthAnalyzer.cs" />
     <Compile Include="GenealogyGraph.cs" />
+    <Compile Include="GenealogyGraphArc.cs" />
+    <Compile Include="GenealogyGraphNode.cs" />
     <Compile Include="Interfaces\IGenealogyGraph.cs" />
+    <Compile Include="Interfaces\IGenealogyGraphNode.cs" />
+    <Compile Include="Interfaces\ISymbolicExpressionTreeGenealogyGraph.cs" />
     <Compile Include="Plugin.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Plugin.cs

@@ -30 +30 @@
   [PluginDependency("HeuristicLab.Common.Resources", "3.3")]
   [PluginDependency("HeuristicLab.Core", "3.3")]
-  [PluginDependency("HeuristicLab.Data", "3.3")]
   [PluginDependency("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding", "3.4")]
   [PluginDependency("HeuristicLab.Operators", "3.3")]