Changeset 11387

Timestamp:

09/23/14 17:08:59 (10 years ago)

Author:

bburlacu

Message:

#1772: Simplified fragment tracing code in the before/after manipulation operators.

Location:

branches/HeuristicLab.EvolutionTracking

Files:

• HeuristicLab.EvolutionTracking/3.4/Operators/BeforeManipulatorOperator.cs (modified) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionAfterManipulatorOperator.cs (modified) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionBeforeManipulatorOperator.cs (modified) (1 diff)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/Operators/BeforeManipulatorOperator.cs

@@ -53 +53 @@
     public override IOperation Apply() {
       // since mutation always takes place after crossover, the vertex for the current child is already in the tree
-      var childVertex = (IGenealogyGraphNode<T>)GenealogyGraph.GetByContent(ChildParameter.ActualValue);
+      var childVertex = GenealogyGraph.GetByContent(ChildParameter.ActualValue);
       var clonedVertex = (IGenealogyGraphNode<T>)childVertex.Clone();
       clonedVertex.Rank = childVertex.Rank - 0.5;
@@ -64 +64 @@
         GenealogyGraph.AddArc(new GenealogyGraphArc(p, clonedVertex));
       }
-      clonedVertex.InArcs.Last().Data = arcs.Last().Data; // preserve fragment data
+      // by convention, the arc connecting child with parent (non-root parent in case of crossover)
+      // holds fragment data when applicable. the following line of code preserves this data 
+      // the graph arcs are now connecting parent (rank n) --> clone (rank n+0.5) --> child (rank n+1)
+      clonedVertex.InArcs.Last().Data = arcs.Last().Data;
       GenealogyGraph.AddArc(new GenealogyGraphArc(clonedVertex, childVertex));
 

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionAfterManipulatorOperator.cs

@@ -20 +20 @@
 #endregion
 
-using System;
-using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Core;
@@ -30 +28 @@
   public class SymbolicDataAnalysisExpressionAfterManipulatorOperator : AfterManipulatorOperator<ISymbolicExpressionTree> {
     public override IOperation Apply() {
-      var childVertex = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph.GetByContent(ChildParameter.ActualValue);
-      var nodesBefore = (List<ISymbolicExpressionTreeNode>)childVertex.InArcs.First().Data;
-      var nodesAfter = ChildParameter.ActualValue.IterateNodesPrefix().ToList();
-      IFragment<ISymbolicExpressionTreeNode> fragment = null;
-
-      // try to find if a subtree was replaced by comparing references
-      for (int i = 0; i < Math.Min(nodesBefore.Count, nodesAfter.Count); ++i) {
-        if (nodesAfter[i] != nodesBefore[i]) {
-          fragment = new Fragment<ISymbolicExpressionTreeNode> {
-            Root = nodesAfter[i],
-            Index1 = i,
-            Index2 = i
-          };
-        }
-      }
-      // if the fragment could not be identified by reference comparison, we try to identify it by comparing node labels
-      // the fragment root will be the lowest common ancestor of all the differing nodes
-      if (fragment == null) {
-        var list = new List<ISymbolicExpressionTreeNode>();
-        var root = ChildParameter.ActualValue.Root;
-
-        for (int i = 0; i < Math.Min(nodesBefore.Count, nodesAfter.Count); ++i) {
-          var a = nodesAfter[i];
-          var b = nodesBefore[i];
-
-          if (!Equals(a.ToString(), b.ToString())) // label comparison is sufficient
-            list.Add(a);
-        }
-
-        var lca = LowestCommonAncestor(root, list);
-        int index = nodesAfter.IndexOf(lca);
-        fragment = new Fragment<ISymbolicExpressionTreeNode> {
-          Root = lca,
-          Index1 = index,
-          Index2 = index
-        };
-      }
-
-      if (fragment == null)
-        throw new ArgumentNullException("Could not identify fragment.");
-
-      childVertex.InArcs.First().Data = fragment;
+      var child = ChildParameter.ActualValue;
+      var childVertex = GenealogyGraph.GetByContent(child);
+      var parent = childVertex.Parents.First().Data;
+      var subtree = child.Difference(parent);
+      int index = child.IterateNodesPrefix().TakeWhile(node => node != subtree).Count();
+      var fragment = new Fragment<ISymbolicExpressionTreeNode> { Root = subtree, Index1 = index, Index2 = index };
+      childVertex.InArcs.Last().Data = fragment;
       return base.Apply();
-    }
-
-    private static ISymbolicExpressionTreeNode LowestCommonAncestor(ISymbolicExpressionTreeNode root, List<ISymbolicExpressionTreeNode> nodes) {
-      if (nodes.Count == 0)
-        throw new ArgumentException("The nodes list should contain at least one element.");
-
-      if (nodes.Count == 1)
-        return nodes[0];
-
-      int lowestLevel = nodes.Min(x => root.GetBranchLevel(x));
-
-      // bring the nodes in the nodes to the same level (relative to the root)
-      for (int i = 0; i < nodes.Count; ++i) {
-        var node = nodes[i];
-        var level = root.GetBranchLevel(node);
-        for (int j = lowestLevel; j < level; ++j)
-          node = node.Parent;
-        nodes[i] = node;
-      }
-
-      // while not all the elements in the nodes are equal, go one level up
-      while (nodes.Any(x => x != nodes[0])) {
-        for (int i = 0; i < nodes.Count; ++i)
-          nodes[i] = nodes[i].Parent;
-      }
-
-      return nodes[0];
     }
   }

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionBeforeManipulatorOperator.cs

@@ -28 +28 @@
   public class SymbolicDataAnalysisExpressionBeforeManipulatorOperator : BeforeManipulatorOperator<ISymbolicExpressionTree> {
     public override IOperation Apply() {
-      var result = base.Apply(); // add the vertex in the genealogy graph
-
-      var vChild = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph.GetByContent(ChildParameter.ActualValue);
+      // the call below does the following things:
+      // 1) creates a clone of the individual to be manipulated, and adds it in the genealogy graph with rank = currentRank - 0.5.
+      //    the cloning will also clone the vertex data object, therefore reference comparison of node lists will not work
+      // 2) replaces the parent of the current individual with the clone, and alters graph connections accordingly
+      //    therefore, vChild will be the vertex of the child, and vClone the vertex of the cloned parent
+      var result = base.Apply();
+      var vChild = GenealogyGraph.GetByContent(ChildParameter.ActualValue);
       var vClone = vChild.Parents.Last();
-      vChild.InArcs.First().Data = vClone.Data.IterateNodesPrefix().ToList();
 
       var fragment = (IFragment<ISymbolicExpressionTreeNode>)vClone.InArcs.Last().Data;
       if (fragment != null) {
         // this step must be performed because the fragment root actually references the original child (not the clone). 
-        // then, a mutation operation (acting on the original child), could disrupt it
+        // when mutation occurs the fragment root would point to the mutated subtree in the child instead of the original one in the clone
         fragment.Root = vClone.Data.IterateNodesPrefix().ElementAt(fragment.Index1);
       }