Changeset 7515

Timestamp:

02/24/12 10:59:26 (13 years ago)

Author:

bburlacu

Message:

#1772: Added tracking for mutation operators.

Location:

branches/HeuristicLab.EvolutionaryTracking

Files:

• . (modified) (1 prop)
• HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs (modified) (12 diffs)
• HeuristicLab.EvolutionaryTracking/3.4/GenealogyGraph.cs (modified) (10 diffs)
• HeuristicLab.EvolutionaryTracking/3.4/HeuristicLab.EvolutionaryTracking-3.4.csproj (modified) (2 diffs)
• HeuristicLab.EvolutionaryTracking/3.4/HeuristicLab.EvolutionaryTracking-3.4.csproj.user (modified) (1 diff)
• HeuristicLab.EvolutionaryTracking/3.4/RegressionSolutionImpactValuesCalculator.cs (added)
• HeuristicLab.Tracking.sln.DotSettings.user (added)
• HeuristicLab.Tracking.sln.docstates.suo (modified) (previous)
• HeuristicLab.Tracking.suo (modified) (previous)

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

@@ -24 +24 @@
 using System.Globalization;
 using System.Linq;
+using System.Text;
+using System.Threading;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -32 +34 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-
-using TreeCacheType = HeuristicLab.Core.ItemList<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTree>;
-using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTree,
-                                                      HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTree>;
-using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTree,
-                                                      HeuristicLab.Core.IItemArray<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTree>>;
+using HeuristicLab.Problems.DataAnalysis;
+using HeuristicLab.Problems.DataAnalysis.Symbolic;
+
+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.EvolutionaryTracking {
@@ -46 +47 @@
   [StorableClass]
   public sealed class SymbolicExpressionTreeGenealogyAnalyzer : SingleSuccessorOperator, IAnalyzer {
-    private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
     private const string UpdateIntervalParameterName = "UpdateInterval";
     private const string UpdateCounterParameterName = "UpdateCounter";
@@ -55 +55 @@
     private const string MaximumSelectionPressureParameterName = "MaximumSelectionPressure";
     private const string SelectionPressureParameterName = "SelectionPressure";
-    private const string GlobalTreeCacheParameterName = "GlobalTreeCache";
     private const string GlobalTraceMapParameterName = "GlobalTraceMap";
     private const string GlobalCloneMapParameterName = "GlobalCloneMap";
     private const string PopulationGraphResultParameterName = "PopulationGraph";
     private const string PopulationGraphResultParameterDescription = "Individual lineages";
+    private const string SymbolicExpressionInterpreterParameterName = "SymbolicExpressionTreeInterpreter";
+    private const string SymbolicRegressionProblemDataParameterName = "ProblemData";
+    private const string SymbolicDataAnalysisProblemEvaluatorParameterName = "Evaluator";
 
     #region Parameter properties
@@ -86 +88 @@
       get { return (LookupParameter<DoubleValue>)Parameters[MaximumSelectionPressureParameterName]; }
     }
+    // problem data, interpreter and evaluator
+    public LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter> SymbolicExpressionInterpreterParameter {
+      get { return (LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>)Parameters[SymbolicExpressionInterpreterParameterName]; }
+    }
+    public LookupParameter<RegressionProblemData> SymbolicRegressionProblemDataParameter {
+      get { return (LookupParameter<RegressionProblemData>)Parameters[SymbolicRegressionProblemDataParameterName]; }
+    }
+    public LookupParameter<IEvaluator> SymbolicDataAnalysisProblemEvaluatorParameter {
+      get { return (LookupParameter<IEvaluator>)Parameters[SymbolicDataAnalysisProblemEvaluatorParameterName]; }
+    }
     // genealogy global parameters
-    public LookupParameter<TreeCacheType> GlobalTreeCacheParameter {
-      get { return (LookupParameter<TreeCacheType>)Parameters[GlobalTreeCacheParameterName]; }
-    }
     public LookupParameter<TraceMapType> GlobalTraceMapParameter {
       get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
@@ -126 +135 @@
       get { return MaximumSelectionPressureParameter.ActualValue; }
     }
-    public ItemList<ISymbolicExpressionTree> GlobalTreeCache {
-      get { return GlobalTreeCacheParameter.ActualValue; }
-    }
-    public ItemDictionary<ISymbolicExpressionTree, ISymbolicExpressionTree> GlobalCloneMap {
+    public CloneMapType GlobalCloneMap {
       get { return GlobalCloneMapParameter.ActualValue; }
     }
-    public ItemDictionary<ISymbolicExpressionTree, IItemArray<ISymbolicExpressionTree>> GlobalTraceMap {
+    public TraceMapType GlobalTraceMap {
       get { return GlobalTraceMapParameter.ActualValue; }
+    }
+    public SymbolicDataAnalysisExpressionTreeInterpreter SymbolicExpressionInterpreter {
+      get { return SymbolicExpressionInterpreterParameter.ActualValue; }
+    }
+    public RegressionProblemData SymbolicRegressionProblemData {
+      get { return SymbolicRegressionProblemDataParameter.ActualValue; }
+    }
+    public IEvaluator SymbolicDataAnalysisEvaluator {
+      get { return SymbolicDataAnalysisProblemEvaluatorParameter.ActualValue; }
     }
     #endregion
@@ -149 +164 @@
     public SymbolicExpressionTreeGenealogyAnalyzer()
       : base() {
-      Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression tree whose length should be calculated."));
       Parameters.Add(new LookupParameter<IntValue>(ElitesParameterName, "The number of elites."));
       Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
@@ -157 +171 @@
       Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
       Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
-      Parameters.Add(new LookupParameter<TreeCacheType>(GlobalTreeCacheParameterName, "A global list holding all trees from all generations."));
       Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing the whole genealogy."));
       Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
       Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
+      Parameters.Add(new LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>(SymbolicExpressionInterpreterParameterName, "Interpreter for symbolic expression trees"));
+      Parameters.Add(new LookupParameter<RegressionProblemData>(SymbolicRegressionProblemDataParameterName, "The symbolic data analysis problem."));
+      Parameters.Add(new LookupParameter<IEvaluator>(SymbolicDataAnalysisProblemEvaluatorParameterName, "The fitness evaluator"));
 
       UpdateCounterParameter.Hidden = true;
@@ -170 +186 @@
       // check if all the parameters are present and accounted for 
       if (!Parameters.ContainsKey(UpdateIntervalParameterName)) {
-        Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName,
-                                                    "The interval in which the tree length analysis should be applied.",
-                                                    new IntValue(1)));
-      }
-      //necessary code to correct UpdateCounterParameter - type was changed from LookupParameter to ValueParameter
-      if (Parameters.ContainsKey(UpdateCounterParameterName) &&
-          (Parameters[UpdateCounterParameterName] is LookupParameter<IntValue>))
-        Parameters.Remove(UpdateCounterParameterName);
-      if (!Parameters.ContainsKey(UpdateCounterParameterName)) {
-        Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName,
-                                                    "The value which counts how many times the operator was called since the last update",
-                                                    new IntValue(0)));
-        UpdateCounterParameter.Hidden = true;
-      }
+        Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
+      }
+      if (Parameters.ContainsKey(UpdateCounterParameterName)) return;
+      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
+      UpdateCounterParameter.Hidden = true;
     }
 
@@ -206 +213 @@
         var gScope = ExecutionContext.Scope;
         while (gScope.Parent != null) gScope = gScope.Parent;
-
-        GenealogyGraph _graph;
+        GenealogyGraph graph;
         if (!Results.ContainsKey(PopulationGraphResultParameterName)) {
-          _graph = new GenealogyGraph();
-          Results.Add(new Result(PopulationGraphResultParameterName, PopulationGraphResultParameterDescription, _graph));
+          graph = new GenealogyGraph();
+          Results.Add(new Result(PopulationGraphResultParameterName, PopulationGraphResultParameterDescription, graph));
         } else {
-          _graph = (GenealogyGraph)Results[PopulationGraphResultParameterName].Value;
-        }
-
-        var treeQualities = (from s in gScope.SubScopes
-                             let tree = (SymbolicExpressionTree)s.Variables["SymbolicExpressionTree"].Value
-                             let quality = (DoubleValue)s.Variables["Quality"].Value
-                             orderby quality.Value descending
-                             select new Tuple<ISymbolicExpressionTree, DoubleValue>(tree, quality)).ToList();
+          graph = (GenealogyGraph)Results[PopulationGraphResultParameterName].Value;
+        }
+        // get tree quality values
+        var qualities = (from s in gScope.SubScopes
+                         let individual = s.Variables.First().Value
+                         let quality = (DoubleValue)s.Variables["Quality"].Value
+                         orderby quality.Value descending
+                         select new Tuple<IItem, double>(individual, quality.Value)).ToDictionary(t => t.Item1, t => t.Item2);
+
         // add all individuals to the evolutionary graph
-        for (int i = 0; i != treeQualities.Count; ++i) {
-          var tree = treeQualities[i].Item1;
-          var quality = treeQualities[i].Item2;
-          if (!_graph.HasNode(tree)) {
-            _graph.AddNode(tree, quality.Value, (Generations.Value * treeQualities.Count + i + 1).ToString(CultureInfo.InvariantCulture));
-          } else {
-            _graph.GetNode(tree).Label += "\\n" + (Generations.Value * treeQualities.Count + i + 1).ToString(CultureInfo.InvariantCulture);
+        int generation = Generations.Value;
+        int count = GlobalTraceMap.Count;
+        string label;
+
+        if (generation == 0) {
+          // at generation 0 no trace map is present (since no reproduction has taken place yet), 
+          // so we only add the initial trees as nodes in the genealogy graph
+          for (int i = 0; i != qualities.Count; ++i) {
+            var tree = qualities.ElementAt(i).Key;
+            label = (i + 1).ToString(CultureInfo.InvariantCulture);
+            graph.AddNode(tree, qualities[tree], label, generation);
           }
-
-          if (GlobalTraceMap == null || !GlobalTraceMap.ContainsKey(tree))
-            continue;
-          // get number of parents and adjust label (2 parents => crossover, 1 parent => mutation)
-          var parents = GlobalTraceMap[tree];
-          string label = (parents.Count == 2) ? "c" : "m";
+          return base.Apply();
+        }
+
+        // mark and add elites
+        // elites do not appear in the trace map (because they are never the product of a genetic operation)
+        var elites = qualities.OrderByDescending(x => x.Value).Take(Elites.Value).Select(x => x.Key).ToList();
+        for (int i = 0; i != Elites.Value; ++i) {
+          label = (generation * count + i + 1).ToString(CultureInfo.InvariantCulture);
+          var elite = elites[i];
+          if (!graph.HasNode(elite))
+            graph.AddNode(elite, qualities[elite], label, Generations.Value, true);
+          else
+            graph.GetNode(elite).Label += "\\n" + label;
+
+          graph.GetNode(elite).Color = new Color { R = 0, G = 100, B = 150 };
+        }
+
+        for (int i = 0; i != count; ++i) {
+          var trace = GlobalTraceMap.ElementAt(i);
+          var child = (ISymbolicExpressionTree)trace.Key;
+
+          if (!graph.HasNode(child)) {
+            // due to the structure of the trace map, qualities[child] will never throw an exception, so we use it directly
+            label = (generation * count + i + 1 + Elites.Value).ToString(CultureInfo.InvariantCulture);
+            graph.AddNode(child, qualities[child], label, generation);
+          }
+          var parents = trace.Value;
           foreach (var parent in parents) {
-            _graph.AddArc(parent, tree, label);
+            if (!graph.HasNode(parent)) {
+              // if the node is a clone introduced pre-mutation, then its quality value has to be evaluated
+              if (!qualities.ContainsKey(parent))
+                qualities[parent] = Evaluate((ISymbolicExpressionTree)parent);
+              label = ((generation - 1) * count + i + 1).ToString(CultureInfo.InvariantCulture);
+              graph.AddNode(parent, qualities[parent], label, generation - 1);
+            }
+            graph.AddArc(parent, child);
           }
         }
-        if (GlobalTraceMap != null)
-          GlobalTraceMap.Clear();
-
-        // mark elites
-        for (int i = 0; i != Elites.Value; ++i)
-          _graph.GetNode(treeQualities[i].Item1).IsElite = true;
+        GlobalTraceMap.Clear(); // no need to check for null here (see line 212)
 
         // if we've reached the end of the run
-        if (Generations.Value == MaximumGenerations.Value ||
-           (SelectionPressureParameter != null && SelectionPressure.Value >= MaximumSelectionPressure.Value)) {
-
+        bool maxGenerationsReached = (Generations.Value == MaximumGenerations.Value);
+        bool isOsga = (SelectionPressure != null && MaximumSelectionPressure != null);
+        bool maxSelectionPressureReached = isOsga && (SelectionPressure.Value >= MaximumSelectionPressure.Value);
+
+        #region end of the run
+        if (maxGenerationsReached || maxSelectionPressureReached) {
           var path = Environment.GetFolderPath(Environment.SpecialFolder.UserProfile);
 
           // write whole graph to a dot file
-          WriteDot(path + @"\lineage.dot", _graph);
+          WriteDot(path + @"\lineage.dot", graph);
 
           // get genealogy of the best solution
-          var bestSolution = treeQualities.First().Item1;
-          var genealogy = _graph.GetNode(bestSolution).Genealogy();
+          var bestSolution = (ISymbolicExpressionTree)qualities.First().Key;
+          var genealogy = graph.GetNode(bestSolution).Genealogy();
           WriteDot(path + @"\bestlineage.dot", genealogy);
+
+          // write the direct root lineage of the best solution (is it useful?)
+
+          // calculate impact values of nodes in the best solution, attempt to trace those with high impact to their origins
+          //var impactValuesCalculator = new RegressionSolutionImpactValuesCalculator();
+          //var impactValues = impactValuesCalculator.CalculateImpactValues(bestSolution, SymbolicExpressionInterpreter, SymbolicRegressionProblemData);
+          ////var impactValues = CalculateImpactValues(bestSolution);
+          //foreach (var pair in impactValues.Where(pair => !(pair.Key is ConstantTreeNode || pair.Key is VariableTreeNode) && pair.Value > 0.9)) {
+          //  var node = pair.Key;
+
+          //  foreach (var ancestor in genealogy.Keys) {
+          //    graph.GetNode(ancestor).Color = ContainsSubtree(ancestor as ISymbolicExpressionTree, node) ? new Color { R = 0, G = 0, B = 150 } : new Color { R = 255, G = 255, B = 255 };
+          //  }
+          //}
+          //WriteDot(path + @"\impactancestry.dot", genealogy);
 
           // trim the graph
           // exclude the individuals of the last generation
-          var individuals = _graph.Keys.Except(treeQualities.Select(x => x.Item1)).ToList();
+          var individuals = graph.Keys.Except(qualities.Select(x => x.Key)).ToList();
           bool done = false;
           while (!done) {
@@ -268 +320 @@
             foreach (var ind in individuals) {
               // if node has no outgoing connections (absence of offspring), remove it from the graph
-              var node = _graph.GetNode(ind);
+              var node = graph.GetNode(ind);
               if (node == null) continue;
               if (node.OutEdges == null) {
                 done = false; // we still have "dead" nodes
-                _graph.RemoveNode(ind);
+                graph.RemoveNode(ind);
               }
             }
           }
-          WriteDot(path + @"\trimmedlineage.dot", _graph);
-        }
+          WriteDot(path + @"\trimmedlineage.dot", graph);
+        }
+        #endregion
       }
       return base.Apply();
     }
 
+    private double Evaluate(ISymbolicExpressionTree tree) {
+      // we perform evaluation by adding a temporary subscope with the tree in it, and calling evaluator.Apply()
+      var subScope = new Scope();
+      // inject expected variables into the subscope
+      subScope.Variables.Add(new Core.Variable("SymbolicExpressionTree", tree));
+      ExecutionContext.Scope.SubScopes.Add(subScope);
+      var context = new Core.ExecutionContext(ExecutionContext, SymbolicDataAnalysisEvaluator, subScope);
+      SymbolicDataAnalysisEvaluator.Execute(context, new CancellationToken());
+      // get the quality
+      double quality = ((DoubleValue)subScope.Variables["Quality"].Value).Value;
+      // remove the subscope
+      ExecutionContext.Scope.SubScopes.Remove(subScope);
+      return quality;
+    }
+
+    #region Export to dot file
     private static void WriteDot(string path, GenealogyGraph graph) {
       using (var file = new System.IO.StreamWriter(path)) {
         string nl = Environment.NewLine;
-        file.WriteLine("digraph \"lineage " + graph.AverageDegree.ToString() + "\" {" + nl +
+        file.WriteLine("digraph \"lineage " + graph.AverageDegree.ToString(CultureInfo.InvariantCulture) + "\" {" + nl +
                        "ratio=auto;" + nl +
                        "mincross=2.0");
@@ -291 +360 @@
 
         foreach (var node in graph.Values) {
-          var quality = node.Quality;
-          string fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", (int)(255 - 255 * quality), (int)(255 * quality), (int)(100 * quality));
+          string fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", node.Color.R, node.Color.G, node.Color.B);
           if (node.IsElite)
-            fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", (int)(255 - 255 * quality), (int)(255 * quality), (int)(255 * quality));
+            fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", node.Color.R, node.Color.G, 150);
           file.WriteLine("\t\"" + node.Id + "\" [fillcolor=\"" + fillColor + "\",label=\"" + node.Label + "\"];");
           if (node.InEdges == null)
             continue;
-          foreach (var edge in node.InEdges)
-            file.WriteLine("\t\"" + edge.Target.Id + "\" -> \"" + node.Id + "\" [arrowsize=.5, color=\"" + fillColor + "\"];");
+          foreach (var edge in node.InEdges) {
+            var edgeStyle = node.InEdges.Count == 1 ? "dashed" : String.Empty;
+            file.WriteLine("\t\"" + edge.Target.Id + "\" -> \"" + node.Id + "\" [arrowsize=.5, color=\"" + fillColor + "\", style=\"" + edgeStyle + "\"];");
+          }
+        }
+        foreach (var g in graph.Values.GroupBy(x => x.Generation)) {
+          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
+
+    #region Impact values (code for calculating to be moved in separate class)
+    private Dictionary<ISymbolicExpressionTreeNode, double> CalculateImpactValues(ISymbolicExpressionTree tree) {
+      var interpreter = SymbolicExpressionInterpreter;
+      var problemData = (IRegressionProblemData)SymbolicDataAnalysisEvaluator.Parameters["ProblemData"].ActualValue;
+      var dataset = problemData.Dataset;
+      var rows = problemData.TrainingIndizes;
+      string targetVariable = problemData.TargetVariable;
+      var impactValues = new Dictionary<ISymbolicExpressionTreeNode, double>();
+      var nodes = tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPostfix().ToList();
+      var originalOutput = interpreter.GetSymbolicExpressionTreeValues(tree, dataset, rows);
+      var targetValues = dataset.GetDoubleValues(targetVariable, rows);
+      OnlineCalculatorError errorState;
+      double originalR2 = OnlinePearsonsRSquaredCalculator.Calculate(targetValues, originalOutput, out errorState);
+      if (errorState != OnlineCalculatorError.None) originalR2 = 0.0;
+
+      var constantNode = ((ConstantTreeNode)new Constant().CreateTreeNode());
+      var root = new ProgramRootSymbol().CreateTreeNode(); // root node
+      var start = new StartSymbol().CreateTreeNode(); // start node
+      root.AddSubtree(start);
+      var tempTree = new SymbolicExpressionTree(root);
+
+      foreach (ISymbolicExpressionTreeNode node in nodes) {
+        var parent = node.Parent;
+        constantNode.Value = CalculateReplacementValue(tempTree, node, tree);
+        ISymbolicExpressionTreeNode replacementNode = constantNode;
+        SwitchNode(parent, node, replacementNode);
+        var newOutput = interpreter.GetSymbolicExpressionTreeValues(tree, dataset, rows);
+        double newR2 = OnlinePearsonsRSquaredCalculator.Calculate(targetValues, newOutput, out errorState);
+        if (errorState != OnlineCalculatorError.None) newR2 = 0.0;
+
+        // impact = 0 if no change
+        // impact < 0 if new solution is better
+        // impact > 0 if new solution is worse
+        impactValues[node] = originalR2 - newR2;
+        SwitchNode(parent, replacementNode, node);
+      }
+      return impactValues;
+    }
+
+    private double CalculateReplacementValue(ISymbolicExpressionTree tempTree, ISymbolicExpressionTreeNode node, ISymbolicExpressionTree sourceTree) {
+      // remove old ADFs
+      while (tempTree.Root.SubtreeCount > 1) tempTree.Root.RemoveSubtree(1);
+      // clone ADFs of source tree
+      for (int i = 1; i < sourceTree.Root.SubtreeCount; i++) {
+        tempTree.Root.AddSubtree((ISymbolicExpressionTreeNode)sourceTree.Root.GetSubtree(i).Clone());
+      }
+      var start = tempTree.Root.GetSubtree(0);
+      while (start.SubtreeCount > 0) start.RemoveSubtree(0);
+      start.AddSubtree((ISymbolicExpressionTreeNode)node.Clone());
+      var interpreter = SymbolicExpressionInterpreter;
+      var rows = SymbolicRegressionProblemData.TrainingIndizes;
+      return interpreter.GetSymbolicExpressionTreeValues(tempTree, SymbolicRegressionProblemData.Dataset, rows).Median();
+    }
+
+    private static void SwitchNode(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode oldBranch, ISymbolicExpressionTreeNode newBranch) {
+      for (int i = 0; i < root.SubtreeCount; i++) {
+        if (root.GetSubtree(i) == oldBranch) {
+          root.RemoveSubtree(i);
+          root.InsertSubtree(i, newBranch);
+          return;
+        }
+      }
+    }
+    #endregion
+
+    #region Allele tracking
+    private bool ContainsSubtree(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode node) {
+      return tree.IterateNodesPostfix().Where(n => n.Symbol == node.Symbol && n.GetLength() == node.GetLength())
+                                       .Where(n => n.Subtrees.Any() && node.Subtrees.Any())
+                                       .Any(n => n.Subtrees.First().Symbol == node.Subtrees.First().Symbol);
+    }
+    #endregion
+
+    #region Extra / not really needed
+    private IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(ISymbolicExpressionTree tree) {
+      return IterateNodes(tree.Root);
+    }
+
+    private static IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(ISymbolicExpressionTreeNode root) {
+      var list = new List<ISymbolicExpressionTreeNode> { root };
+      int offset = 0, count = 1;
+      while (offset != count) {
+        var c = count;
+        for (int i = offset; i != count; ++i) {
+          yield return list[i];
+          if (!list[i].Subtrees.Any()) continue;
+          list.AddRange(list[i].Subtrees);
+        }
+        offset = c;
+        count = list.Count;
+      }
+    }
+    #endregion
   }
 }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenealogyGraph.cs

@@ -5 +5 @@
 using HeuristicLab.Common;
 using HeuristicLab.Core;
-using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
 namespace HeuristicLab.EvolutionaryTracking {
   public class GenealogyGraph : NamedItem {
-    private readonly Dictionary<ISymbolicExpressionTree, Node> _dictionary;
+    private readonly Dictionary<object, Node> _dictionary;
+
     public GenealogyGraph() {
-      _dictionary = new Dictionary<ISymbolicExpressionTree, Node>();
+      _dictionary = new Dictionary<object, Node>();
     }
 
     public GenealogyGraph(GenealogyGraph g) {
-      _dictionary = new Dictionary<ISymbolicExpressionTree, Node>(g._dictionary);
+      _dictionary = new Dictionary<object, Node>(g._dictionary);
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new GenealogyGraph(this, cloner);
+    }
+
+    public override string ItemName {
+      get { return "GenealogyGraph"; }
+    }
+
+    public override string ItemDescription {
+      get { return "A graph describing the genealogies of all the individuals"; }
+    }
+
+    public new Version ItemVersion {
+      get { return new Version(3, 3, 6); }
+    }
+
+    public new Image ItemImage {
+      get { return Common.Resources.VSImageLibrary.Graph; }
     }
 
     [StorableConstructor]
-    private GenealogyGraph(bool serializing) : base(serializing) { }
+    private GenealogyGraph(bool serializing)
+      : base(serializing) {
+    }
 
     private GenealogyGraph(GenealogyGraph original, Cloner cloner)
       : base(original, cloner) {
-      _dictionary = new Dictionary<ISymbolicExpressionTree, Node>(original._dictionary);
-    }
-
-    public bool HasNode(ISymbolicExpressionTree t) {
+      _dictionary = new Dictionary<object, Node>(original._dictionary);
+    }
+
+    public bool HasNode(object t) {
       return _dictionary.ContainsKey(t);
     }
 
-    public Node GetNode(ISymbolicExpressionTree t) {
+    public Node GetNode(object t) {
       return this.HasNode(t) ? _dictionary[t] : null;
     }
 
-    public IEnumerable<ISymbolicExpressionTree> Keys {
+    public IEnumerable<object> Keys {
       get { return _dictionary.Keys; }
     }
@@ -47 +69 @@
     }
 
-    public bool Any(Func<KeyValuePair<ISymbolicExpressionTree, Node>, bool> predicate) {
+    public bool Any(Func<KeyValuePair<object, Node>, bool> predicate) {
       return _dictionary.Any(predicate);
     }
@@ -59 +81 @@
     /// </summary>
     /// <param name="t">The symbolic expression tree</param>
-    public void AddNode(ISymbolicExpressionTree t, double q = 0.0, string l = "", bool elite = false) {
+    /// <param name="q">The quality value </param>
+    /// <param name="l">The node label</param>
+    /// <param name="elite">Specifies if this node is an elite</param>
+    public void AddNode(object t, double q = 0.0, string l = "", int g = 0, bool elite = false) {
       if (HasNode(t)) return;
-      _dictionary[t] = new Node { Data = t, Quality = q, Label = l, IsElite = elite };
+      var color = new Color { R = (byte)(255 - 255 * q), G = (byte)(255 * q), B = 50 };
+      _dictionary[t] = new Node { Data = t, Quality = q, Label = l, IsElite = elite, Generation = g, Color = color };
     }
 
@@ -69 +95 @@
     /// <param name="n"></param>
     public void AddNode(Node n) {
-      var t = (ISymbolicExpressionTree)n.Data;
+      var t = n.Data;
       if (HasNode(t))
         return;
@@ -79 +105 @@
     /// </summary>
     /// <param name="t">The graph node</param>
-    public void RemoveNode(ISymbolicExpressionTree t) {
+    public void RemoveNode(object t) {
       if (!_dictionary.ContainsKey(t))
         return;
@@ -94 +120 @@
         foreach (var e in n.OutEdges.Where(e => e.Target.InEdges != null)) {
           e.Target.InEdges.RemoveAll(arc => arc.Target == n);
-          if (!e.Target.OutEdges.Any())
+          if (!e.Target.InEdges.Any())
             e.Target.InEdges = null; // set to null to be a little more memory efficient
         }
@@ -112 +138 @@
     /// <param name="b"></param>
     /// <param name="label"></param>
-    public void AddArc(ISymbolicExpressionTree a, ISymbolicExpressionTree b, string label) {
+    public void AddArc(object a, object b, string label = "") {
       Node src, dest;
       if (!HasNode(a)) {
@@ -131 +157 @@
     }
 
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new GenealogyGraph(this, cloner);
-    }
-
-    public override string ItemName {
-      get { return "GenealogyGraph"; }
-    }
-
-    public override string ItemDescription {
-      get { return "A graph describing the genealogies of all the individuals"; }
-    }
-
-    public new Version ItemVersion {
-      get { return new Version(3, 3, 6); }
-    }
-
-    public new Image ItemImage {
-      get { return Common.Resources.VSImageLibrary.Graph; }
+    public void AddArcs(object[] a, object b, string label) {
+      Node src, dest;
+      if (!HasNode(b)) {
+        dest = new Node { Data = b };
+        _dictionary[b] = dest;
+      } else {
+        dest = _dictionary[b];
+      }
+      foreach (var o in a) {
+        if (!HasNode(o)) {
+          src = new Node { Data = o };
+          _dictionary[o] = src;
+        } else {
+          src = _dictionary[o];
+        }
+        src.AddForwardArc(dest, label);
+        dest.AddReverseArc(src, label);
+      }
     }
   }
@@ -160 +186 @@
     public object Data { get; set; }
     public double Quality { get; set; }
+    public int Generation { get; set; }
+    public Color Color { get; set; }
 
     public int Degree {
@@ -229 +257 @@
     // other attributes
   }
-
   // an edge can be represented as a tuple<Node, Node> TODO: figure it out (might be useful for easier querying)
+
+  public struct Color {
+    public byte R { get; set; }
+    public byte G { get; set; }
+    public byte B { get; set; }
+  }
 }

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

@@ -67 +67 @@
     </Reference>
     <Reference Include="HeuristicLab.PluginInfrastructure-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
+    <Reference Include="HeuristicLab.Problems.DataAnalysis-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
+    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
+    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Regression-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
+    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Regression.Views-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
+    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Views-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
     <Reference Include="Microsoft.GLEE">
       <HintPath>..\..\..\..\..\..\..\..\Program Files\Microsoft Research\GLEE\bin\Microsoft.GLEE.dll</HintPath>
@@ -97 +102 @@
     <Compile Include="Plugin.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="RegressionSolutionImpactValuesCalculator.cs">
+      <SubType>UserControl</SubType>
+    </Compile>
   </ItemGroup>
   <ItemGroup>

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

@@ -2 +2 @@
 <Project ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
   <PropertyGroup>
-    <ProjectView>ShowAllFiles</ProjectView>
+    <ProjectView>ProjectFiles</ProjectView>
   </PropertyGroup>
 </Project>