Changeset 7779 for branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs

Timestamp:

05/03/12 12:26:11 (12 years ago)

Author:

bburlacu

Message:

#1772: Implemented new View, improved functionality (tracking of fragments and operators)

File:

• branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs (modified) (10 diffs)

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

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
+using System.Drawing;
 using System.Globalization;
 using System.Linq;
@@ -36 +37 @@
 using HeuristicLab.Problems.DataAnalysis;
 using HeuristicLab.Problems.DataAnalysis.Symbolic;
-using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
 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>>;
@@ -47 +47 @@
   [StorableClass]
   public sealed class SymbolicExpressionTreeGenealogyAnalyzer : SingleSuccessorOperator, IAnalyzer {
+    public enum GeneticOperator { Crossover, Mutation }
+
     private const string UpdateIntervalParameterName = "UpdateInterval";
     private const string UpdateCounterParameterName = "UpdateCounter";
@@ -213 +215 @@
         var gScope = ExecutionContext.Scope;
         while (gScope.Parent != null) gScope = gScope.Parent;
-        GenealogyGraph graph;
+        SymbolicExpressionTreeGenealogyGraph graph;
         if (!Results.ContainsKey(PopulationGraphResultParameterName)) {
-          graph = new GenealogyGraph();
+          graph = new SymbolicExpressionTreeGenealogyGraph();
           Results.Add(new Result(PopulationGraphResultParameterName, PopulationGraphResultParameterDescription, graph));
         } else {
-          graph = (GenealogyGraph)Results[PopulationGraphResultParameterName].Value;
+          graph = (SymbolicExpressionTreeGenealogyGraph)Results[PopulationGraphResultParameterName].Value;
         }
         // get tree quality values
@@ -225 +227 @@
                          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);
+                         select new Tuple<ISymbolicExpressionTree, double>((ISymbolicExpressionTree)individual, quality.Value)).ToDictionary(t => t.Item1, t => t.Item2);
 
         // add all individuals to the evolutionary graph
@@ -232 +234 @@
 
         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
+          // 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;
@@ -242 +243 @@
         }
 
+        // add nodes to genealogy graph
         for (int i = 0; i != qualities.Count; ++i) {
           var child = qualities.ElementAt(i).Key;
           label = (generation * qualities.Count + i + 1).ToString(CultureInfo.InvariantCulture);
-          if (i < Elites.Value) {
-            if (graph.HasNode(child))
-              graph.GetNode(child).Label += "\\n" + label;
-            else
-              graph.AddNode(child, qualities[child], label, generation, true);
-          } else
-            graph.AddNode(child, qualities[child], label, generation);
+          if (!graph.HasNode(child)) graph.AddNode(child, qualities[child], label, generation, i < Elites.Value);
           if (!GlobalTraceMap.ContainsKey(child)) continue;
           var parents = GlobalTraceMap[child];
+
           foreach (var parent in parents) {
+            int opType;
             if (GlobalTraceMap.ContainsKey(parent)) {
               double quality = Evaluate((ISymbolicExpressionTree)parent);
-              graph.AddNode(parent, quality, "", generation - 0.5);
-              foreach (var p in GlobalTraceMap[parent])
-                graph.AddArc(p, parent);
+              graph.AddNode((ISymbolicExpressionTree)parent, quality, "", generation - 0.5);
+              var pp = GlobalTraceMap[parent];
+              foreach (var p in pp) {
+                opType = pp.Count == 2 ? (int)GeneticOperator.Crossover : (int)GeneticOperator.Mutation;
+                graph.AddArc((ISymbolicExpressionTree)p, (ISymbolicExpressionTree)parent, opType);
+              }
             }
-            graph.AddArc(parent, child);
+            opType = parents.Count == 2 ? (int)GeneticOperator.Crossover : (int)GeneticOperator.Mutation;
+            graph.AddArc((ISymbolicExpressionTree)parent, child, opType);
           }
         }
 
+        // clear trace and clone maps in preparation for the next generation
         GlobalTraceMap.Clear();
         GlobalCloneMap.Clear();
 
-        #region end of the run
-        bool maxGenerationsReached = (Generations.Value == MaximumGenerations.Value);
-        bool isOsga = (SelectionPressure != null && MaximumSelectionPressure != null);
-        bool maxSelectionPressureReached = isOsga && (SelectionPressure.Value >= MaximumSelectionPressure.Value);
-        if (maxGenerationsReached || maxSelectionPressureReached) {
-          var path = Environment.GetFolderPath(Environment.SpecialFolder.UserProfile);
-
-          // write whole graph to a dot file
-          WriteDot(path + @"\lineage.dot", graph);
-
-          // get genealogy of the best solution
-          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 calculator = new SymbolicRegressionSolutionValuesCalculator();
-          var impactValues = calculator.CalculateImpactValues(bestSolution, SymbolicExpressionInterpreter, SymbolicRegressionProblemData, 0, 0);
-          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(qualities.Select(x => x.Key)).ToList();
-          bool done = false;
-          while (!done) {
-            done = true;
-            foreach (var ind in individuals) {
-              // if node has no outgoing connections (absence of offspring), remove it from the graph
-              var node = graph.GetNode(ind);
-              if (node == null) continue;
-              if (node.OutEdges == null) {
-                done = false; // we still have "dead" nodes
-                graph.RemoveNode(ind);
-              }
-            }
-          }
-          WriteDot(path + @"\trimmedlineage.dot", graph);
-        }
+        #region end of the run (code for writing results to dot files)
+        //bool maxGenerationsReached = (Generations.Value == MaximumGenerations.Value);
+        //bool isOsga = (SelectionPressure != null && MaximumSelectionPressure != null);
+        //bool maxSelectionPressureReached = isOsga && (SelectionPressure.Value >= MaximumSelectionPressure.Value);
+        //if (maxGenerationsReached || maxSelectionPressureReached) {
+        //  var path = Environment.GetFolderPath(Environment.SpecialFolder.UserProfile);
+
+        //  // write whole graph to a dot file
+        //  WriteDot(path + @"\lineage.dot", graph);
+
+        //  // get genealogy of the best solution
+        //  var bestSolution = (ISymbolicExpressionTree)qualities.First().Key;
+        //  var genealogy = graph.GetNode(bestSolution).Ancestors();
+        //  //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 calculator = new SymbolicRegressionSolutionValuesCalculator();
+        //  var impactValues = calculator.CalculateImpactValues(bestSolution, SymbolicExpressionInterpreter, SymbolicRegressionProblemData, 0, 0);
+        //  foreach (var pair in impactValues.Where(pair => !(pair.Key is ConstantTreeNode || pair.Key is VariableTreeNode)).OrderByDescending(pair => pair.Value).Take(2)) {
+        //    var node = pair.Key;
+        //  }
+        //  //WriteDot(path + @"\impactancestry.dot", genealogy);
+
+        //  // trim the graph
+        //  // exclude the individuals of the last generation
+        //  var individuals = graph.Keys.Except(qualities.Select(x => x.Key)).ToList();
+        //  bool done = false;
+        //  while (!done) {
+        //    done = true;
+        //    foreach (var ind in individuals) {
+        //      // if node has no outgoing connections (absence of offspring), remove it from the graph
+        //      var node = graph.GetNode(ind);
+        //      if (node == null) continue;
+        //      if (node.OutEdges == null) {
+        //        done = false; // we still have "dead" nodes
+        //        graph.RemoveNode(ind);
+        //      }
+        //    }
+        //  }
+        //  WriteDot(path + @"\trimmedlineage.dot", graph);
+        //}
         #endregion
       }
@@ -336 +335 @@
 
     #region Export to dot file
-    private static void WriteDot(string path, GenealogyGraph graph) {
+    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("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) {
-          string fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", node.Color.R, node.Color.G, node.Color.B);
+          var color = Color.FromArgb((int)((1 - node.Quality) * 255), (int)(node.Quality * 255), 0);
+          string fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", color.R, color.G, color.B);
           string shape = "circle";
           if (node.IsElite)
@@ -353 +351 @@
             continue;
           foreach (var edge in node.InEdges) {
-            var edgeStyle = node.InEdges.Count == 1 ? "dashed" : String.Empty;
+            //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 + "\"];");
           }
@@ -370 +369 @@
     #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
+    // method of iterating tree nodes in a breadth-wise manner
     private IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(ISymbolicExpressionTree tree) {
       return IterateNodes(tree.Root);