Changeset 8557 for branches

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

Files:

• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/TracingSymbolicExpressionTreeCrossover.cs (modified) (6 diffs)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/GenericWrapper.cs (modified) (2 diffs)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj (modified) (2 diffs)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionTreeNodeComparer.cs (added)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/Operators/ITracingSymbolicExpressionTreeOperator.cs (added)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/TracingSymbolicExpressionTreeManipulator.cs (modified) (6 diffs)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/TracingSymbolicExpressionTreeOperator.cs (added)
• HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFragmentsAnalyzer.cs (modified) (16 diffs)
• HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs (modified) (10 diffs)
• HeuristicLab.EvolutionaryTracking/3.4/HeuristicLab.EvolutionaryTracking-3.4.csproj (modified) (1 diff)
• HeuristicLab.EvolutionaryTracking/3.4/Plugin.cs (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeMatching.cs (modified) (6 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisProblem.cs (modified) (1 diff)
• HeuristicLab.Selection/3.3/Plugin.cs (modified) (1 diff)
• HeuristicLab.Tracking.sln (modified) (2 diffs)

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/TracingSymbolicExpressionTreeCrossover.cs

@@ -28 +28 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
-using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
-using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;
-
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
   /// <summary>
@@ -37 +34 @@
   [Item("SymbolicExpressionTreeCrossover", "A base class for operators that perform a crossover of symbolic expression trees.")]
   [StorableClass]
-  public abstract class TracingSymbolicExpressionTreeCrossover : SymbolicExpressionTreeOperator, ISymbolicExpressionTreeCrossover {
+  public abstract class TracingSymbolicExpressionTreeCrossover : TracingSymbolicExpressionTreeOperator, ISymbolicExpressionTreeCrossover {
     private const string ParentsParameterName = "Parents";
     private const string ChildParameterName = "Child";
-    private const string GlobalTraceMapParameterName = "GlobalTraceMap";
-    private const string GlobalCloneMapParameterName = "GlobalCloneMap";
-    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
+
 
     #region Parameter Properties
@@ -50 +45 @@
     public ILookupParameter<ISymbolicExpressionTree> ChildParameter {
       get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters[ChildParameterName]; }
-    }
-    public LookupParameter<CloneMapType> GlobalCloneMapParameter {
-      get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
-    }
-    public LookupParameter<TraceMapType> GlobalTraceMapParameter {
-      get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
-    }
-    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
-      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
     }
     #endregion
@@ -70 +56 @@
       set { ChildParameter.ActualValue = value; }
     }
-    public CloneMapType GlobalCloneMap {
-      get { return GlobalCloneMapParameter.ActualValue; }
-    }
-    public TraceMapType GlobalTraceMap {
-      get { return GlobalTraceMapParameter.ActualValue; }
-    }
-    public CloneMapType GlobalFragmentMap {
-      get { return GlobalFragmentMapParameter.ActualValue; }
-    }
     #endregion
 
@@ -85 +62 @@
       : base(deserializing) {
     }
-
     protected TracingSymbolicExpressionTreeCrossover(TracingSymbolicExpressionTreeCrossover original, Cloner cloner)
       : base(original, cloner) {
     }
-
     protected TracingSymbolicExpressionTreeCrossover()
       : base() {
       Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(ParentsParameterName, "The parent symbolic expression trees which should be crossed."));
       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(ChildParameterName, "The child symbolic expression tree resulting from the crossover."));
-      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
-      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
-      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing tracing info."));
+
     }
-
     public sealed override IOperation Apply() {
       if (Parents.Length != 2)
         throw new ArgumentException("Number of parents must be exactly two for symbolic expression tree crossover operators.");
 
-      // add global trace cache if not already present in global scope
-      var gScope = ExecutionContext.Scope;
-      while (gScope.Parent != null)
-        gScope = gScope.Parent;
-      if (GlobalTraceMap == null)
-        gScope.Variables.Add(new Variable(GlobalTraceMapParameterName, new TraceMapType()));
-      if (GlobalFragmentMap == null)
-        gScope.Variables.Add(new Variable(GlobalFragmentMapParameterName, new CloneMapType()));
-
-      // get original parents (this info will be needed later to construct the genealogy graph)
-      var originalParents = new ItemList<IItem>(Parents.Select(x => GlobalCloneMap[x]));
+      AddTracingVariablesToGlobalScope();
 
       // save the nodes of parent0 in a list so we can track what modifications are made by crossover
@@ -124 +86 @@
       var nodes1 = Child.IterateNodesBreadth().ToList();
 
-      // compare the two nodes lists and check the difference (comparing node references so we avoid false functional identity). 
-      // if no difference is found, then it is assumed that the whole tree was swapped with itself (it can happen), so the index is 0
-      int i, min = Math.Min(nodes0.Count, nodes1.Count);
-      for (i = 0; i != min; ++i)
-        if (nodes0[i] != nodes1[i]) break;
+      // compare the two node lists and check the difference (comparing node references so we avoid false functional identity). 
+      int i = 0, min = Math.Min(nodes0.Count, nodes1.Count);
+      while (i != min && ReferenceEquals(nodes0[i], nodes1[i])) ++i;
+
       // add heredity information into the global variables
-      GlobalTraceMap[Child] = originalParents; // map child to its corresponding parents from the previous generation
-      GlobalFragmentMap[Child] = new GenericWrapper<SymbolicExpressionTreeNode>(i == min ? null : (SymbolicExpressionTreeNode)nodes1[i]); // map child to the index of its fragment
+      GlobalTraceMap[Child] = new ItemList<IItem>(Parents.Select(x => GlobalCloneMap[x])); ; // map child to its corresponding parents from the previous generation
+      GlobalFragmentMap[Child] = new GenericWrapper<ISymbolicExpressionTreeNode>(i == min ? null : nodes1[i]); // map child to the index of its fragment
       return base.Apply();
     }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/GenericWrapper.cs

@@ -6 +6 @@
   [Item("Generic wrapper", "Wrapper class for non-item HeuristicLab objects")]
   [StorableClass]
-  public class GenericWrapper<T> : NamedItem where T : class {
+  public class GenericWrapper<T> : NamedItem where T : class, IDeepCloneable {
+    [Storable]
     public T Content { get; private set; }
-
-    private GenericWrapper() {
-    }
 
     public GenericWrapper(T content) {
@@ -17 +15 @@
 
     [StorableConstructor]
-    protected GenericWrapper(bool serializing)
-      : base(serializing) {
-    }
+    private GenericWrapper(bool serializing) : base(serializing) { }
 
     private GenericWrapper(GenericWrapper<T> original, Cloner cloner)
       : base(original, cloner) {
+      this.Content = cloner.Clone(Content);
     }
 

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

@@ -167 +167 @@
     <Compile Include="Compiler\SymbolicExpressionTreeCompiler.cs" />
     <None Include="Plugin.cs.frame" />
+    <Compile Include="Interfaces\Operators\ITracingSymbolicExpressionTreeOperator.cs" />
+    <Compile Include="TracingSymbolicExpressionTreeOperator.cs" />
     <Compile Include="Creators\TracingSymbolicExpressionTreeCreator.cs" />
     <Compile Include="Creators\FullTreeCreator.cs">
@@ -181 +183 @@
     <Compile Include="Interfaces\ISymbolicExpressionGrammarBase.cs" />
     <Compile Include="Interfaces\ISymbolicExpressionTreeGrammar.cs" />
+    <Compile Include="Interfaces\ISymbolicExpressionTreeNodeComparer.cs" />
     <Compile Include="Interfaces\Operators\ISymbolicExpressionTreeArchitectureAlteringOperator.cs" />
     <Compile Include="Interfaces\Operators\ISymbolicExpressionTreeGrammarBasedOperator.cs" />

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/TracingSymbolicExpressionTreeManipulator.cs

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
@@ -28 +29 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
-using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
-using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;
-
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
   /// <summary>
@@ -37 +35 @@
   [Item("TracingSymbolicExpressionTreeManipulator", "A base class for operators that manipulate symbolic expression trees.")]
   [StorableClass]
-  public abstract class TracingSymbolicExpressionTreeManipulator : SymbolicExpressionTreeOperator, ISymbolicExpressionTreeManipulator {
+  public abstract class TracingSymbolicExpressionTreeManipulator : TracingSymbolicExpressionTreeOperator, ISymbolicExpressionTreeManipulator {
     private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
-    private const string GlobalTraceMapParameterName = "GlobalTraceMap";
-    private const string GlobalCloneMapParameterName = "GlobalCloneMap";
-    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
 
     #region Parameter Properties
     public ILookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
       get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
-    }
-    public LookupParameter<CloneMapType> GlobalCloneMapParameter {
-      get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
-    }
-    public LookupParameter<TraceMapType> GlobalTraceMapParameter {
-      get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
-    }
-    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
-      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
     }
     #endregion
@@ -61 +47 @@
     public ISymbolicExpressionTree SymbolicExpressionTree {
       get { return SymbolicExpressionTreeParameter.ActualValue; }
-    }
-    public CloneMapType GlobalCloneMap {
-      get { return GlobalCloneMapParameter.ActualValue; }
-    }
-    public TraceMapType GlobalTraceMap {
-      get { return GlobalTraceMapParameter.ActualValue; }
-    }
-    public CloneMapType GlobalFragmentMap {
-      get { return GlobalFragmentMapParameter.ActualValue; }
     }
     #endregion
@@ -79 +56 @@
       : base() {
       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression tree on which the operator should be applied."));
-      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
-      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing tracing info."));
-      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
     }
 
@@ -87 +61 @@
       ISymbolicExpressionTree tree = SymbolicExpressionTreeParameter.ActualValue;
 
-      var gScope = ExecutionContext.Scope;
-      while (gScope.Parent != null)
-        gScope = gScope.Parent;
+      AddTracingVariablesToGlobalScope();
 
-      if (GlobalTraceMap == null)
-        gScope.Variables.Add(new Variable(GlobalTraceMapParameterName, new TraceMapType()));
-      if (GlobalFragmentMap == null)
-        gScope.Variables.Add(new Variable(GlobalFragmentMapParameterName, new CloneMapType()));
-
-      int i = 0;
+      /* The following block needs to be explained in more detail;
+       * If the tree was already affected by crossover (before mutation), then:
+       * - it will already be contained in the GlobalTraceMap
+       * - In order to preserve information, a clone of the tree is created
+       * - The clone represents the intermediate stage of the tree, before mutation is applied
+       * - The clone therefore represents the child after crossover so GlobalTraceMap[clone] will get tree's parents
+       *   and GlobalFragmentMap[clone] will get the subtree from clone that represents the cloned fragment
+       * - After tree is mutated, we set GlobalTraceMap[tree] = clone and GlobalFragmentMap[tree] = modified node from tree
+       */
+      ISymbolicExpressionTreeNode fragment;
       if (GlobalTraceMap.ContainsKey(tree)) {
-        // tree was affected by crossover before mutation
-        // if the tree to be manipulated is already a product of crossover (in the current reproduction phase), 
-        // then there exists no relationship with the original "parent". 
-        // In order to preserve information, a tree clone is created before mutation and added to the trace map.
-        var clone = (IItem)tree.Clone();
+        var clone = (IItem)tree.Clone(); // create clone of tree
         GlobalTraceMap[clone] = GlobalTraceMap[tree]; // clone gets parents of tree
         GlobalTraceMap[tree] = new ItemList<IItem> { clone }; // tree gets clone as parent
-        var nodes = tree.IterateNodesBreadth().ToList();
-        for (i = 0; i != nodes.Count; ++i) {
-          if ((GlobalFragmentMap[tree] as GenericWrapper<SymbolicExpressionTreeNode>).Content == nodes[i]) break;
+        fragment = ((GenericWrapper<ISymbolicExpressionTreeNode>)GlobalFragmentMap[tree]).Content;
+        int index = tree.IterateNodesBreadth().ToList().IndexOf(fragment); // returns -1 if fragment is not present in tree
+        GlobalFragmentMap[clone] = new GenericWrapper<ISymbolicExpressionTreeNode>(index == -1 ? null : ((ISymbolicExpressionTree)clone).IterateNodesBreadth().ElementAt(index));
+      } else {
+        GlobalTraceMap[tree] = new ItemList<IItem> { GlobalCloneMap[tree] };
+      }
+
+      var original = GlobalCloneMap[tree];
+      var nodes0 = ((ISymbolicExpressionTree)original).IterateNodesBreadth().ToList();
+
+      // perform mutation
+      Manipulate(RandomParameter.ActualValue, tree);
+
+      var nodes1 = tree.IterateNodesBreadth().ToList();
+
+      int min = Math.Min(nodes0.Count, nodes1.Count);
+      // some tree manipulators only change local parameters while the actual node stays the same
+      // consequently, we need a stronger comparison than ReferenceEquals
+      var comp = SymbolicExpressionTreeNodeComparer;
+      if (comp == null)
+        throw new Exception(Name + ": Could not get SymbolicExpressionTreeNodeComparerParameter!");
+      var mismatches = new List<int>();
+      for (int i = 0; i != min; ++i) {
+        if (!comp.Equals(nodes0[i], nodes1[i])) {
+          mismatches.Add(i);
         }
-        var fragment = (SymbolicExpressionTreeNode)(((SymbolicExpressionTree)clone).IterateNodesBreadth().ElementAt(i));
-        GlobalFragmentMap[clone] = new GenericWrapper<SymbolicExpressionTreeNode>(fragment);
-      } else {
-        var original = GlobalCloneMap[tree];
-        GlobalTraceMap[tree] = new ItemList<IItem> { original };
       }
-      var nodes0 = tree.IterateNodesBreadth().ToList();
-      Manipulate(RandomParameter.ActualValue, tree);
-      var nodes1 = tree.IterateNodesBreadth().ToList();
-      int min = Math.Min(nodes0.Count, nodes1.Count);
-      for (i = 0; i != min; ++i)
-        if (nodes0[i] != nodes1[i]) break;
-      GlobalFragmentMap[tree] = new GenericWrapper<SymbolicExpressionTreeNode>(i == min ? null : (SymbolicExpressionTreeNode)nodes1[i]);
+      if (mismatches.Count == 0) // should never happen
+        fragment = null;
+      else
+        fragment = mismatches.Count > 1 ? nodes1[mismatches[0]].Parent : nodes1[mismatches[0]];
+      GlobalFragmentMap[tree] = new GenericWrapper<ISymbolicExpressionTreeNode>(fragment);
       return base.Apply();
     }

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")]

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -169 +169 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="Analyzers\SymbolicDataAnalysisComplexityAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectiveValidationParetoBestSolutionAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectiveTrainingParetoBestSolutionAnalyzer.cs" />

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeMatching.cs

@@ -1 @@
-using System.Collections.Generic;
+using System;
+using System.Collections.Generic;
+using System.IO;
 using System.Linq;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
-  public class SymbolicExpressionTreeNodeSimilarityComparer : IEqualityComparer<ISymbolicExpressionTreeNode> {
-
-    public SymbolicExpressionTreeNodeSimilarityComparer(int similarityLevel) {
-      _similarityLevel = similarityLevel;
+  public enum SimilarityLevel {
+    Exact,   // everything is matched bit by bit (functions and terminals)
+    High,    // symbols are matched. leaf node types are matched
+    Relaxed  // only symbols are matched, leafs count as wildcards
+  }
+  [Item("SymbolicExpressionTreeNodeSimilarityComparer", "A comparison operator that checks node equality based on different similarity measures.")]
+  [StorableClass]
+  public class SymbolicExpressionTreeNodeSimilarityComparer : Item, ISymbolicExpressionTreeNodeComparer {
+    [StorableConstructor]
+    private SymbolicExpressionTreeNodeSimilarityComparer(bool deserializing) : base(deserializing) { }
+    private SymbolicExpressionTreeNodeSimilarityComparer(SymbolicExpressionTreeNodeSimilarityComparer original, Cloner cloner) : base(original, cloner) { }
+    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicExpressionTreeNodeSimilarityComparer(this, cloner); }
+
+    private SimilarityLevel similarityLevel;
+    public SimilarityLevel SimilarityLevel {
+      get { return similarityLevel; }
+      set { similarityLevel = value; }
+    }
+
+    public SymbolicExpressionTreeNodeSimilarityComparer() {
+      this.similarityLevel = SimilarityLevel.Exact;
+    }
+
+    public SymbolicExpressionTreeNodeSimilarityComparer(SimilarityLevel similarityLevel) {
+      this.similarityLevel = similarityLevel;
     }
 
@@ -15 +41 @@
 
     public bool Equals(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
-      if (a.SubtreeCount != b.SubtreeCount) { return false; }
-      if (a.SubtreeCount > 0) { return a.Symbol.ToString().Equals(b.Symbol.ToString()); }
-      // compare leaf nodes according to desired similarity level
-      switch (_similarityLevel) {
-        case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact):
-          if (a is ConstantTreeNode && b is ConstantTreeNode) {
-            return ((ConstantTreeNode)a).Value.Equals(((ConstantTreeNode)b).Value);
-          }
-          if (a is VariableTreeNode && b is VariableTreeNode) {
-            return (a as VariableTreeNode).Weight.Equals((b as VariableTreeNode).Weight);
-          }
+      var ca = a as ConstantTreeNode;
+      var cb = b as ConstantTreeNode;
+      var va = a as VariableTreeNode;
+      var vb = b as VariableTreeNode;
+
+      var aIsConstant = ca != null;
+      var aIsVariable = va != null;
+      var bIsConstant = cb != null;
+      var bIsVariable = vb != null;
+      var aIsFunction = (!(aIsConstant | aIsVariable));
+      var bIsFunction = (!(bIsConstant | bIsVariable));
+
+      if (aIsFunction)
+        return bIsFunction && a.Symbol.Name.Equals(b.Symbol.Name);
+      if (bIsFunction) // one is function and the other is not, return false
+        return false;
+
+      switch (similarityLevel) {
+        case (SimilarityLevel.Exact):
+          if (aIsConstant & bIsConstant)
+            return ca.Value.Equals(cb.Value);
+          if (aIsVariable & bIsVariable)
+            return va.Weight.Equals(vb.Weight);
           return false;
-
-        case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.High):
-          return (a is ConstantTreeNode && b is ConstantTreeNode) || (a is VariableTreeNode && b is VariableTreeNode);
-
-        case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.Relaxed):
+        case (SimilarityLevel.High):
+          return ((aIsConstant & bIsConstant) || (aIsVariable & bIsVariable));
+        case (SimilarityLevel.Relaxed):
           return true;
-
         default:
           return false;
@@ -39 +74 @@
     }
 
-    private readonly int _similarityLevel;
+    public static bool ExactlySimilar(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
+      return Similar(a, b, SimilarityLevel.Exact);
+    }
+
+    public static bool Similar(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SimilarityLevel level) {
+      var comp = new SymbolicExpressionTreeNodeSimilarityComparer(level);
+      return comp.Equals(a, b);
+    }
   }
 
   public class SymbolicExpressionTreeNodeOrderingComparer : IComparer<ISymbolicExpressionTreeNode> {
     public int Compare(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
-      if (a is ConstantTreeNode) {
-        if (b is ConstantTreeNode)
-          return a.Symbol.ToString().Equals(b.Symbol.ToString()) ?
-            (a as ConstantTreeNode).Value.CompareTo((b as ConstantTreeNode).Value) : System.String.Compare(a.Symbol.ToString(), b.Symbol.ToString());
-        return -1; // if b is not constant then we consider a < b because by convention Constant < Variable < Function
-      }
-      if (a is VariableTreeNode) {
-        if (b is ConstantTreeNode)
-          return 1;
-        if (b is VariableTreeNode)
-          return a.Symbol.ToString().Equals(b.Symbol.ToString()) ?
-            (a as VariableTreeNode).Weight.CompareTo((b as VariableTreeNode).Weight) : System.String.Compare(a.Symbol.ToString(), b.Symbol.ToString());
-        return -1;
-      }
-      if (b is ConstantTreeNode || b is VariableTreeNode)
-        return 1; // a is a Function node and is greater than Constants or Variables
-
-      return a.Symbol.ToString().Equals(b.Symbol.ToString()) ? a.SubtreeCount.CompareTo(b.SubtreeCount) : System.String.Compare(a.Symbol.ToString(), b.Symbol.ToString());
+      var ca = a as ConstantTreeNode;
+      var cb = b as ConstantTreeNode;
+      var va = a as VariableTreeNode;
+      var vb = b as VariableTreeNode;
+
+      var aIsConstant = ca != null;
+      var aIsVariable = va != null;
+      var bIsConstant = cb != null;
+      var bIsVariable = vb != null;
+      var aIsFunction = (!(aIsConstant | aIsVariable));
+      var bIsFunction = (!(bIsConstant | bIsVariable));
+
+      if (aIsFunction)
+        return bIsFunction ? a.Symbol.Name.CompareTo(b.Symbol.Name) : -1;
+      if (bIsFunction) // a is Constant or Variables
+        return 1;
+      if (aIsVariable)
+        return bIsVariable ? va.Weight.CompareTo(vb.Weight) : -1;
+      return
+        bIsVariable ? 1 : ca.Value.CompareTo(cb.Value);
     }
   }
@@ -68 +112 @@
   public class SymbolicExpressionTreeEqualityComparer : IEqualityComparer<ISymbolicExpressionTree> {
     public bool Equals(ISymbolicExpressionTree a, ISymbolicExpressionTree b) {
-      return SymbolicExpressionTreeMatching.FindMatch(a, b, _mode) == 0;
+      return SymbolicExpressionTreeMatching.FindMatch(a, b, similarityLevel) == 0;
     }
 
     public int GetHashCode(ISymbolicExpressionTree tree) {
-      return tree.Length;
-    }
-
-    private int _mode;
-    public void SetComparisonMode(int mode) {
-      _mode = mode;
+      return (tree.Length << 8) % 12345;
+    }
+
+    private SimilarityLevel similarityLevel;
+    public void SetComparisonMode(SimilarityLevel simLevel) {
+      similarityLevel = simLevel;
     }
   }
 
   public static class SymbolicExpressionTreeMatching {
-    public enum SimilarityLevel {
-      Exact,   // everything is matched bit by bit (functions and terminals)
-      High,    // symbols are matched. leaf node types are matched
-      Relaxed  // only symbols are matched, leafs count as wildcards
-    }
-
-    public static bool IsSimilarTo(this ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, int mode) {
+    public static bool IsSimilarTo(this ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, SimilarityLevel mode) {
       return FindMatch(t1, t2, mode) == 0;
     }
-    public static bool IsSimilarTo(this ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, int mode) {
+
+    public static bool IsSimilarTo(this ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, SimilarityLevel mode) {
       return FindMatch(t1, t2, mode) == 0;
     }
 
-    public static bool ContainsFragment(this ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, int mode) {
-      var nodes = tree.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
-      var fragments = fragment.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
-      return FindMatch(nodes, fragments, mode) != -1;
+    public static bool ContainsFragment(this ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, SimilarityLevel mode) {
+      var matches = FindMatches(tree, fragment, mode);
+      return matches.Count > 0;
     }
 
@@ -106 +144 @@
 
     public static void SortSubtrees(this ISymbolicExpressionTreeNode node) {
-      if (node.SubtreeCount > 0) {
-        var subtrees = node.Subtrees as List<ISymbolicExpressionTreeNode>;
-        if (subtrees == null) return;
-        subtrees.Sort(new SymbolicExpressionTreeNodeOrderingComparer());
-        foreach (var subtree in subtrees)
-          subtree.SortSubtrees();
-      }
-    }
-
-    public static int FindMatch(ISymbolicExpressionTree a, ISymbolicExpressionTree b, int mode) {
+      if (node.SubtreeCount == 0) return;
+      var subtrees = node.Subtrees as List<ISymbolicExpressionTreeNode>;
+      if (subtrees == null) return;
+      var comparer = new SymbolicExpressionTreeNodeOrderingComparer();
+      subtrees.Sort(comparer);
+      foreach (var subtree in subtrees)
+        subtree.SortSubtrees();
+    }
+
+    // return child that is the same as node
+    public static ISymbolicExpressionTreeNode FindChild(this ISymbolicExpressionTreeNode parent, ISymbolicExpressionTreeNode node) {
+      var subtrees = parent.Subtrees as List<ISymbolicExpressionTreeNode>;
+      var comparer = new SymbolicExpressionTreeNodeSimilarityComparer(SimilarityLevel.Exact);
+      return subtrees.Find(x => comparer.Equals(x, node));
+    }
+
+    public static int FindMatch(ISymbolicExpressionTree a, ISymbolicExpressionTree b, SimilarityLevel similarityLevel) {
       var nodesA = a.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
       var nodesB = b.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
-      return FindMatch(nodesA, nodesB, mode);
-    }
-    public static int FindMatch(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, int mode) {
+      return FindMatch(nodesA, nodesB, similarityLevel);
+    }
+
+    public static int FindMatch(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SimilarityLevel similarityLevel) {
       var nodesA = a.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
       var nodesB = b.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
-      return FindMatch(nodesA, nodesB, mode);
-    }
+      return FindMatch(nodesA, nodesB, similarityLevel);
+    }
+
     // returns the index in the sequence 'seq', where pattern 'pat' is matched, or -1 for no match
     // -1 means no match, 0 means perfect match (the sequences overlap, hence the match index is 0)
-    public static int FindMatch(List<ISymbolicExpressionTreeNode> seq, List<ISymbolicExpressionTreeNode> pat, int mode) {
+    public static int FindMatch(List<ISymbolicExpressionTreeNode> seq, List<ISymbolicExpressionTreeNode> pat, SimilarityLevel similarityLevel) {
       int patlen = pat.Count;
       int seqlen = seq.Count;
       if (patlen == 0 || seqlen == 0) return -1;
-      var comparer = new SymbolicExpressionTreeNodeSimilarityComparer(mode);
+      var comparer = new SymbolicExpressionTreeNodeSimilarityComparer(similarityLevel);
       if (patlen == seqlen) return seq.SequenceEqual(pat, comparer) ? 0 : -1;
       for (int i = patlen; i <= seqlen; ++i) {
@@ -140 +187 @@
       return -1;
     }
+
+    public static List<ISymbolicExpressionTreeNode> FindMatches(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, SimilarityLevel similarityLevel) {
+      var comp = new SymbolicExpressionTreeNodeSimilarityComparer(similarityLevel);
+      return FindMatches(tree.Root, fragment, comp);
+    }
+
+    public static List<ISymbolicExpressionTreeNode>
+    FindMatches(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode fragment, SymbolicExpressionTreeNodeSimilarityComparer comp) {
+      var matches = new List<ISymbolicExpressionTreeNode>();
+      root.ForEachNodePostfix(node => {
+        if (Match(node, fragment, comp) == fragment.GetLength()) matches.Add(node);
+      });
+      return matches;
+    }
+
+    ///<summary>
+    /// Finds the longest common subsequence in quadratic time and linear space
+    /// Variant of:
+    /// D . S. Hirschberg. A linear space algorithm for or computing maximal common subsequences. 1975.
+    /// http://dl.acm.org/citation.cfm?id=360861
+    /// </summary>
+    /// <returns>Number of pairs that were matched</returns>
+    public static int
+    Match(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {
+      if (!comp.Equals(a, b))
+        return 0;
+
+      int m = a.SubtreeCount;
+      int n = b.SubtreeCount;
+      if (m == 0 || n == 0) return 1;
+
+      var matrix = new int[m + 1, n + 1];
+      for (int i = 1; i <= m; ++i)
+        for (int j = 1; j <= n; ++j) {
+          var ai = a.GetSubtree(i - 1);
+          var bj = b.GetSubtree(j - 1);
+          int match = Match(ai, bj, comp);
+          matrix[i, j] = Math.Max(Math.Max(matrix[i, j - 1], matrix[i - 1, j]), matrix[i - 1, j - 1] + match);
+        }
+      return matrix[m, n] + 1;
+    }
+
+    public static int
+    LCS(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {
+      var nodesA = a.IterateNodesPrefix().ToList();
+      var nodesB = b.IterateNodesPrefix().ToList();
+      int m = nodesA.Count;
+      int n = nodesB.Count;
+      var matrix = new int[m + 1, n + 1];
+      for (int i = 1; i <= m; ++i) {
+        for (int j = 1; j <= n; ++j) {
+          int w = comp.Equals(a, b) ? 1 : 0;
+          matrix[i, j] = Math.Max(Math.Max(matrix[i, j - 1], matrix[i - 1, j]), matrix[i - 1, j - 1] + w);
+        }
+      }
+      return matrix[m, n];
+    }
+
+    public static void RenderTree(TextWriter writer, ISymbolicExpressionTree tree) {
+      RenderNode(writer, tree.Root, string.Empty);
+    }
+
+    public static void RenderNode(TextWriter writer, ISymbolicExpressionTreeNode node, string prefix) {
+      string label;
+      if (node is VariableTreeNode) {
+        var variable = node as VariableTreeNode;
+        label = string.Concat(string.Format("{0:0.000}", variable.Weight), '·', variable.VariableName);
+      } else if (node is ConstantTreeNode) {
+        var constant = node as ConstantTreeNode;
+        label = string.Format("{0:0.000}", constant.Value);
+      } else {
+        label = node.Symbol.ToString();
+      }
+
+      writer.Write(label);
+      if (node.SubtreeCount > 0) {
+        char connector, extender = ' ';
+        var padding = prefix + new string(' ', label.Length);
+        for (int i = 0; i != node.SubtreeCount; ++i) {
+          if (i == 0) {
+            if (node.SubtreeCount > 1) {
+              connector = RenderChars.JunctionDown;
+              extender = RenderChars.VerticalLine;
+            } else {
+              connector = RenderChars.HorizontalLine;
+              extender = ' ';
+            }
+          } else {
+            writer.Write(padding);
+            if (i == node.SubtreeCount - 1) {
+              connector = RenderChars.CornerRight;
+              extender = ' ';
+            } else {
+              connector = RenderChars.JunctionRight;
+              extender = RenderChars.VerticalLine;
+            }
+          }
+          writer.Write(string.Concat(connector, RenderChars.HorizontalLine));
+          var newPrefix = string.Concat(padding, extender, ' ');
+          RenderNode(writer, node.GetSubtree(i), newPrefix);
+        }
+      } else
+        writer.WriteLine();
+    }
+  }
+
+  // helper class providing characters for displaying a tree in the console
+  public static class RenderChars {
+    public const char JunctionDown = '┬';
+    public const char HorizontalLine = '─';
+    public const char VerticalLine = '│';
+    public const char JunctionRight = '├';
+    public const char CornerRight = '└';
   }
 }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisProblem.cs

@@ -319 +319 @@
         op.EvaluatorParameter.ActualName = EvaluatorParameter.Name;
       }
+      var comparers = ApplicationManager.Manager.GetInstances<ISymbolicExpressionTreeNodeComparer>().ToList();
+      if (comparers.Count > 0)
+        foreach (var op in operators.OfType<ITracingSymbolicExpressionTreeOperator>()) {
+          op.SymbolicExpressionTreeNodeComparerParameter.ActualValue = comparers.First();
+        }
     }
 

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Selection/3.3/Plugin.cs

@@ -26 +26 @@
   /// Plugin class for HeuristicLab.Selection plugin.
   /// </summary>
-  [Plugin("HeuristicLab.Selection", "3.3.6.8236")]
+  [Plugin("HeuristicLab.Selection", "3.3.6.8248")]
   [PluginFile("HeuristicLab.Selection-3.3.dll", PluginFileType.Assembly)]
   [PluginDependency("HeuristicLab.Collections", "3.3")]

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Tracking.sln

@@ -7 +7 @@
   ProjectSection(SolutionItems) = preProject
     Build.cmd = Build.cmd
+    HeuristicLab.Tracking.vsmdi = HeuristicLab.Tracking.vsmdi
+    Local.testsettings = Local.testsettings
     PreBuildEvent.cmd = PreBuildEvent.cmd
+    TraceAndTestImpact.testsettings = TraceAndTestImpact.testsettings
   EndProjectSection
 EndProject
@@ -19 +22 @@
 EndProject
 Global
+  GlobalSection(TestCaseManagementSettings) = postSolution
+    CategoryFile = HeuristicLab.Tracking.vsmdi
+  EndGlobalSection
   GlobalSection(SolutionConfigurationPlatforms) = preSolution
     Debug|Any CPU = Debug|Any CPU