Changeset 11253 for branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic

Timestamp:

07/31/14 17:11:39 (10 years ago)

Author:

bburlacu

Message:

#1772: Ported the rest of the changes to the DirectedGraph and Vertex to the GenealogyGraph and GenealogyGraphNode. Adapted tracking operators, analyzers and views.

Location:

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

Files:

• Analyzers/SymbolicDataAnalysisPopulationDiversityAnalyzer.cs (deleted)
• HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (2 diffs)
• Tracking/SymbolicDataAnalysisExpressionAfterCrossoverOperator.cs (modified) (1 diff)
• Tracking/SymbolicDataAnalysisExpressionAfterManipulatorOperator.cs (modified) (1 diff)
• Tracking/SymbolicDataAnalysisExpressionBeforeManipulatorOperator.cs (modified) (2 diffs)
• Tracking/SymbolicDataAnalysisExpressionTracing.cs (modified) (5 diffs)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -173 +173 @@
   </ItemGroup>
   <ItemGroup>
-    <Compile Include="Analyzers\SymbolicDataAnalysisInternalDiversityAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectivePruningAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisGenealogyAnalyzer.cs" />
@@ -207 +206 @@
     <Compile Include="SlidingWindow\SlidingWindowVisualizer.cs" />
     <Compile Include="SymbolicDataAnalysisExpressionPruningOperator.cs" />
-    <Compile Include="SymbolicDataAnalysisExpressionTreeSimilarityCalculator.cs" />
     <Compile Include="SymbolicDataAnalysisSolutionPruningOptimizer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisVariableFrequencyAnalyzer.cs" />

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

@@ -34 +34 @@
       var nodes0 = (List<ISymbolicExpressionTreeNode>)arcs[0].Data;
       var nodes1 = (List<ISymbolicExpressionTreeNode>)arcs[1].Data;
-      var childNodes = childVertex.Content.IterateNodesPrefix().ToList();
+      var childNodes = childVertex.Data.IterateNodesPrefix().ToList();
       IFragment<ISymbolicExpressionTreeNode> fragment = null;
       for (int i = 0; i < Math.Min(nodes0.Count, childNodes.Count); ++i) {

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

@@ -29 +29 @@
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   public class SymbolicDataAnalysisExpressionAfterManipulatorOperator : AfterManipulatorOperator<ISymbolicExpressionTree> {
-    private readonly SymbolicExpressionTreeNodeSimilarityComparer comparer;
-
-    public SymbolicDataAnalysisExpressionAfterManipulatorOperator() {
-      comparer = new SymbolicExpressionTreeNodeSimilarityComparer {
-        MatchVariableNames = true,
-        MatchVariableWeights = true,
-        MatchConstantValues = true
-      };
-    }
-
     public override IOperation Apply() {
-      var vChild = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph.GetByContent(ChildParameter.ActualValue);
-      var nodesBefore = (List<ISymbolicExpressionTreeNode>)vChild.InArcs.First().Data;
+      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;
 
-      for (int i = 0; i < Math.Min(nodesAfter.Count, nodesBefore.Count); ++i) {
-        var a = nodesAfter[i];
-        var b = nodesBefore[i];
+      // 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;
 
-        bool found = false;
-        if (comparer.Equals(a, b)) {
-          int m = 0;
-          for (int j = 0; j < a.SubtreeCount; ++j) {
-            if (!AreSimilar(a.GetSubtree(j), b.GetSubtree(j), comparer)) { ++m; }
-            if (m > 1) {
-              found = true;
-              break;
-            }
-          }
-          if (m == 0) {
-            // everything is similar so we skip the whole subtree
-            i += a.GetLength();
-          }
-          if (!found) continue;
+        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 = a,
-          Index1 = i,
-          Index2 = i
+          Root = lca,
+          Index1 = index,
+          Index2 = index
         };
-        break;
       }
 
-      vChild.InArcs.First().Data = fragment;
+      if (fragment == null)
+        throw new ArgumentNullException("Could not identify fragment.");
+
+      childVertex.InArcs.First().Data = fragment;
       return base.Apply();
     }
 
-    private bool AreSimilar(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {
-      int length = a.GetLength();
-      return comparer.Equals(a, b) && length.Equals(b.GetLength()) && SymbolicExpressionTreeMatching.Match(a, b, comp) == length;
+    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

@@ -32 +32 @@
       var vChild = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph.GetByContent(ChildParameter.ActualValue);
       var vClone = vChild.Parents.Last();
-      vChild.InArcs.First().Data = vClone.Content.IterateNodesPrefix().ToList();
+      vChild.InArcs.First().Data = vClone.Data.IterateNodesPrefix().ToList();
 
       var fragment = (IFragment<ISymbolicExpressionTreeNode>)vClone.InArcs.Last().Data;
@@ -38 +38 @@
         // 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
-        fragment.Root = vClone.Content.IterateNodesPrefix().ElementAt(fragment.Index1);
+        fragment.Root = vClone.Data.IterateNodesPrefix().ElementAt(fragment.Index1);
       }
 

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

@@ -24 +24 @@
 using System.IO;
 using System.Linq;
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.EvolutionTracking;
@@ -74 +75 @@
         }
         var fragmentLength = fragment.Root.GetLength();
-        var tree = node.Content;
+        var tree = node.Data;
         var subtree = tree.NodeAt(index);
         var subtreeLength = subtree.GetLength();
@@ -97 +98 @@
               // subtree contained in fragment, index stays the same
             } else {
-              index += node.Content.NodeAt(fragment.Index1).GetLength() - fragmentLength;
+              index += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
             }
           } else if (subtreeIndex < fragment.Index1) {
@@ -131 +132 @@
               // fragment distinct from subtree
               node = parents[0]; // take first parent which contains the subtree
-              index += node.Content.NodeAt(fragment.Index1).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes
+              index += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes
             }
             continue;
@@ -150 +151 @@
               yield return fragmentNode;
 
-              if (parents[1].Content.NodeAt(fragment.Index2).GetLength() != fragmentLength) {
+              if (parents[1].Data.NodeAt(fragment.Index2).GetLength() != fragmentLength) {
                 throw new Exception("Fragment lengths should match!");
               }