Changeset 10755 for branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4

Timestamp:

04/16/14 17:15:33 (11 years ago)

Author:

bburlacu

Message:

#1772: Simplified genealogy graph and fragment graph creation:

• the genealogy graph now has a 1-1 mapping between content and vertices (as opposed to 1-n as it was previously, to account for elites); this required changes to the directed graph implementation
• the fragment graph only contains bifurcation points (where the subtree contains the fragment so tracing must be done both ways (in the root parent AND in the other parent). in the other cases, tracing is restarted from the parent genealogy graph node.

Location:

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

Files:

• SymbolicDataAnalysisExpressionAfterCrossoverOperator.cs (modified) (2 diffs)
• SymbolicDataAnalysisExpressionAfterManipulatorOperator.cs (modified) (2 diffs)
• SymbolicDataAnalysisExpressionBeforeCrossoverOperator.cs (modified) (1 diff)
• SymbolicDataAnalysisExpressionBeforeManipulatorOperator.cs (modified) (1 diff)
• SymbolicDataAnalysisExpressionTracing.cs (modified) (2 diffs)

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

@@ -10 +10 @@
     public override IOperation Apply() {
       var child = ChildParameter.ActualValue;
-      var childVertex = (IGenealogyGraphNode)GenealogyGraph[child].Last();
+      var childVertex = (IGenealogyGraphNode)GenealogyGraph[child];
       var arcs = childVertex.InArcs.ToList();
       var nodes0 = (List<ISymbolicExpressionTreeNode>)arcs[0].Data;
@@ -20 +20 @@
         fragment = new Fragment<ISymbolicExpressionTreeNode> {
           Root = childNodes[i],
-          Index = i,
+          Index1 = i,
         };
-        fragment.OldIndex = nodes1.IndexOf(fragment.Root);
+        fragment.Index2 = nodes1.IndexOf(fragment.Root);
         break;
       }

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

@@ -7 +7 @@
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
-  public class SymbolicDataAnalysisExpressionAfterManipulatorOperator : BeforeManipulatorOperator<ISymbolicExpressionTree> {
+  public class SymbolicDataAnalysisExpressionAfterManipulatorOperator : AfterManipulatorOperator<ISymbolicExpressionTree> {
     private readonly SymbolicExpressionTreeNodeSimilarityComparer comparer;
 
@@ -19 +19 @@
 
     public override IOperation Apply() {
-      var vChild = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph[ChildParameter.ActualValue].First();
+      var vChild = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph[ChildParameter.ActualValue];
       var nodesBefore = (List<ISymbolicExpressionTreeNode>)vChild.InArcs.First().Data;
-      var nodesAfter = ChildParameter.ActualValue.IterateNodesBreadth().ToList();
+      var nodesAfter = ChildParameter.ActualValue.IterateNodesPrefix().ToList();
       IFragment<ISymbolicExpressionTreeNode> fragment = null;
 
       for (int i = 0; i < Math.Min(nodesAfter.Count, nodesBefore.Count); ++i) {
-        if (comparer.Equals(nodesAfter[i], nodesBefore[i])) continue;
+        var a = nodesAfter[i];
+        var b = nodesBefore[i];
+        if (ReferenceEquals(a, b) && comparer.Equals(a, b)) continue;
         fragment = new Fragment<ISymbolicExpressionTreeNode> {
-          Root = nodesAfter[i],
-          Index = i
+          Root = a,
+          Index1 = i
         };
       }

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

@@ -31 +31 @@
       var result = base.Apply(); // the base operator will add the child to the graph before the actual crossover operation takes place
       var parents = ParentsParameter.ActualValue.ToList();
-      var childVertex = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph[parents[0]].Last(); // use the parent since it is actually the child before crossover (and the ChildParameter doesn't have a value yet)
+      var childVertex = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph[parents[0]]; // use the parent since it is actually the child before crossover (and the ChildParameter doesn't have a value yet)
       var arcs = childVertex.InArcs.ToList();
 

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

@@ -7 +7 @@
   public class SymbolicDataAnalysisExpressionBeforeManipulatorOperator : BeforeManipulatorOperator<ISymbolicExpressionTree> {
     public override IOperation Apply() {
-      var result = base.Apply();
+      var result = base.Apply(); // add the vertex in the genealogy graph
 
-      var vChild = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph[ChildParameter.ActualValue].Last();
-      vChild.InArcs.First().Data = vChild.Content.IterateNodesBreadth().ToList();
+      var vChild = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph[ChildParameter.ActualValue];
+      vChild.InArcs.First().Data = vChild.Content.IterateNodesPrefix().ToList();
 
       return result;

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

@@ -1 +1 @@
 
+using System;
 using System.Collections.Generic;
 using System.IO;
@@ -24 +25 @@
       var index = subtreeIndex; // current index
       var parent = parentNode; // current parent
+
       while (true) {
+        if (!node.Parents.Any()) {
+          var fragmentNode = new FragmentNode {
+            Content = new Fragment<ISymbolicExpressionTreeNode> { Root = node.Content.NodeAt(index) },
+            Rank = node.Rank
+          };
+          if (parent != null) {
+            var arc = new GenealogyGraphArc { Source = parent, Target = fragmentNode };
+            parent.AddForwardArc(arc);
+            //            fragmentNode.Content.Index1 = parent.Content.Index1;
+          }
+          yield return fragmentNode; // no tracing if there are no parents
+          break;
+        }
+
+        if (node.IsElite) {
+          node = node.Parents.First();
+          continue;
+        } // skip elite, go up the graph to original individual
+
         var tree = node.Content;
         var subtree = tree.NodeAt(index);
         var subtreeLength = subtree.GetLength();
-        var fragmentNode = new FragmentNode {
-          Content = new Fragment<ISymbolicExpressionTreeNode> { Root = subtree },
-          Rank = node.Rank
-        };
-        if (parent != null) {
-          var arc = new GenealogyGraphArc { Source = parent, Target = fragmentNode };
-          parent.AddForwardArc(arc);
-        }
-        parent = fragmentNode;
-        yield return fragmentNode;
-        if (!node.Parents.Any()) break;
-        if (node.IsElite) {
-          node = node.Parents.First();
-          continue;
-        }
+
         var fragment = (IFragment<ISymbolicExpressionTreeNode>)node.InArcs.Last().Data;
         if (fragment == null) break;
         var fragmentLength = fragment.Root.GetLength();
-        if (fragment.Index == index) {
+
+        if (fragment.Index1 == index) {
           node = node.Parents.Last(); // take second parent which contains the fragment
-          index = fragment.OldIndex;
-        } else if (fragment.Index < index) {
-          if (fragment.Index + fragmentLength > index) { // fragment contains subtree
-            node = node.Parents.Last(); // take second parent
-            index += fragment.OldIndex - fragment.Index;
-          } else { // fragment distinct from subtree
+          index = fragment.Index2;
+        } else if (fragment.Index1 < index) {
+          if (fragment.Index1 + fragmentLength > index) {
+            node = node.Parents.Last(); // fragment contains subtree, take second parent
+            index += fragment.Index2 - fragment.Index1; // the subtree has the same index relative to the fragment
+          } else {
+            // fragment distinct from subtree
             node = node.Parents.First(); // take first parent which contains the subtree
-            index += node.Content.NodeAt(fragment.Index).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes
+            index += node.Content.NodeAt(fragment.Index1).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes
           }
-        } else if (fragment.Index > index) {
-          if (fragment.Index < index + subtreeLength) { // subtree contains fragment => bifurcation point in the fragment graph
-            fragmentNode.Content.Index = fragment.Index - index;
+        } else if (fragment.Index1 > index) {
+          if (fragment.Index1 < index + subtreeLength) {
+            // subtree contains fragment => bifurcation point in the fragment graph
+            var fragmentNode = new FragmentNode {
+              Content = new Fragment<ISymbolicExpressionTreeNode> { Root = subtree },
+              Rank = node.Rank
+            };
+            if (parent != null) {
+              var arc = new GenealogyGraphArc { Source = parent, Target = fragmentNode };
+              parent.AddForwardArc(arc);
+            }
+            fragmentNode.Content.Index1 = fragment.Index1 - index;
+            yield return fragmentNode;
+
             var left = Trace(node.Parents.First(), index, fragmentNode); // trace subtree
-            var right = Trace(node.Parents.Last(), fragment.OldIndex, fragmentNode); // trace fragment
-            foreach (var v in left.Concat(right)) { yield return v; }
+
+            if (node.Parents.Last().Content.NodeAt(fragment.Index2).GetLength() != fragmentLength) {
+              throw new Exception("Fragment lengths should match!");
+            }
+            var right = Trace(node.Parents.Last(), fragment.Index2, fragmentNode); // trace fragment
+            foreach (var v in left.Concat(right)) {
+              yield return v;
+            }
             break;
+          } else {
+            node = node.Parents.First(); // fragment distinct from subtree: update node, index remains unchanged
           }
-          node = node.Parents.First(); // fragment distinct from subtree: update node, index remains unchanged
         }
       }