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

Timestamp:

02/24/12 17:30:16 (12 years ago)

Author:

bburlacu

Message:

#1772: Merged changes from trunk, rigged the TournamentSelector to track clones, improved tracking code.

Location:

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4

Files:

• Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs (modified) (7 diffs)
• GenealogyGraph.cs (modified) (2 diffs)
• HeuristicLab.EvolutionaryTracking-3.4.csproj (modified) (1 diff)
• RegressionSolutionImpactValuesCalculator.cs (deleted)

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

@@ -36 +36 @@
 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>>;
@@ -229 +229 @@
         // add all individuals to the evolutionary graph
         int generation = Generations.Value;
-        int count = GlobalTraceMap.Count;
         string label;
 
@@ -238 +237 @@
             var tree = qualities.ElementAt(i).Key;
             label = (i + 1).ToString(CultureInfo.InvariantCulture);
-            graph.AddNode(tree, qualities[tree], label, generation);
+            graph.AddNode(tree, qualities[tree], label, generation, i < Elites.Value);
           }
           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);
+        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);
-          }
-          var parents = trace.Value;
+          if (!GlobalTraceMap.ContainsKey(child)) continue;
+          var parents = GlobalTraceMap[child];
           foreach (var parent in parents) {
-            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);
+            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.AddArc(parent, child);
           }
         }
-        GlobalTraceMap.Clear(); // no need to check for null here (see line 212)
-
-        // if we've reached the end of the run
+
+        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);
-
-        #region end of the run
         if (maxGenerationsReached || maxSelectionPressureReached) {
           var path = Environment.GetFolderPath(Environment.SpecialFolder.UserProfile);
@@ -300 +286 @@
 
           // 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);
+          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
@@ -361 +346 @@
         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);
+          string shape = "circle";
           if (node.IsElite)
-            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 + "\"];");
+            shape = "doublecircle";
+          file.WriteLine("\t\"" + node.Id + "\" [shape=" + shape + ",fillcolor=\"" + fillColor + "\",label=\"" + node.Label + "\"];");
           if (node.InEdges == null)
             continue;
@@ -371 +357 @@
           }
         }
-        foreach (var g in graph.Values.GroupBy(x => x.Generation)) {
+        foreach (var g in graph.Values.GroupBy(x => x.Rank)) {
           var sb = new StringBuilder();
           sb.Append("\t{rank=same;");
@@ -380 +366 @@
         }
         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;
-        }
       }
     }

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

@@ -84 +84 @@
     /// <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) {
+    public void AddNode(object t, double q = 0.0, string l = "", double g = 0, bool elite = false) {
       if (HasNode(t)) return;
       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 };
+      _dictionary[t] = new Node { Data = t, Quality = q, Label = l, IsElite = elite, Rank = g, Color = color };
     }
 
@@ -186 +186 @@
     public object Data { get; set; }
     public double Quality { get; set; }
-    public int Generation { get; set; }
+    public double Rank { get; set; }
     public Color Color { get; set; }
 

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

@@ -102 +102 @@
     <Compile Include="Plugin.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
-    <Compile Include="RegressionSolutionImpactValuesCalculator.cs">
-      <SubType>UserControl</SubType>
-    </Compile>
   </ItemGroup>
   <ItemGroup>