Changeset 11493 for branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking

Timestamp:

10/24/14 16:02:59 (10 years ago)

Author:

bburlacu

Message:

#1772: Improved the way the TraceCalculator handles mutations, worked on the SymbolicDataAnalysisPoly10Analyzer (analyzer that tries to identify building blocks for the Poly-10 problem by doing a semantic comparison).

File:

• branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs (modified) (4 diffs)

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

@@ -1 @@
-using System;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using HeuristicLab.Common;
@@ -73 +95 @@
         }
 
-        int fragmentLength = fragment.Root.GetLength();
-        int subtreeLength = g.Data.NodeAt(si).GetLength();
+        int fi = fragment.Index1;               // fragment index
+        int fl = fragment.Root.GetLength();     // fragment length
+        int sl = g.Data.NodeAt(si).GetLength(); // subtree length
 
         #region trace crossover
         if (parents.Count == 2) {
-          if (fragment.Index1 == si) {
+          if (fi == si) {
             g = parents[1];
             si = fragment.Index2;
             continue;
           }
-          if (fragment.Index1 < si) {
-            if (fragment.Index1 + fragmentLength > si) {
+          if (fi < si) {
+            if (fi + fl > si) {
               // fragment contains subtree
               g = parents[1];
-              si += fragment.Index2 - fragment.Index1;
+              si += fragment.Index2 - fi;
             } else {
               // fragment distinct from subtree
               g = parents[0];
-              si += g.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
+              si += g.Data.NodeAt(fi).GetLength() - fl;
             }
             continue;
           }
-          if (fragment.Index1 > si) {
-            if (fragment.Index1 < si + subtreeLength) {
+          if (fi > si) {
+            if (fi < si + sl) {
               // subtree contains fragment => branching point in the fragment graph
-              var n = traceGraph.GetByContent(g.Data);
-              if (n == null) {
-                n = g.Copy();
-                traceGraph.AddVertex(n);
-                traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
-              }
-
+              var n = GetTraceNode(g, si, fi);
               Trace(parents[0], si, n);
               Trace(parents[1], fragment.Index2, n);
@@ -117 +134 @@
         #endregion
         #region trace mutation
+        // mutation is handled in a simple way: we branch every time there is an overlap between the subtree and the fragment
+        // (since mutation effects can be quite unpredictable: replace branch, change node, shake tree, etc)
         if (parents.Count == 1) {
-          if (si == fragment.Index1) {
-            // fragment and subtree coincide
-            // since mutation can potentially alter trees quite drastically, we branch here,
-            // in order not to miss any changes
-            var n = traceGraph.GetByContent(g.Data);
-            if (n == null) {
-              n = g.Copy();
-              traceGraph.AddVertex(n);
-              traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
-            }
-            Trace(parents[0], si, n);
+          Debug.Assert(fragment.Index1 == fragment.Index2);
+          // check if the subtree and the fragment overlap => branch out
+          if ((si == fi) || (si < fi && fi < si + sl) || (fi < si && si < fi + fl)) {
+            var n = GetTraceNode(g, si, fi);
+            int i = si < fi ? si : fi;
+            Trace(parents[0], i, n);
             break;
-          }
-          if (fragment.Index1 < si) {
-            if (si < fragment.Index1 + fragmentLength) {
-              // fragment contains subtree
-              g = parents[0];
-              si = fragment.Index2;
-            } else {
-              // fragment and subtree are distinct
-              // since the fragment occurs before the subtree in the prefix node ordering
-              // the subtree index must be adjusted according to the fragment length
-              g = parents[0];
-              si += g.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
-            }
+          } else {
+            // if they don't overlap, go up
+            g = parents[0];
+            if (fi < si)
+              si += g.Data.NodeAt(fi).GetLength() - fl;
             continue;
-          }
-          if (si < fragment.Index1) {
-            // subtree occurs before fragment in the prefix node ordering
-            if (fragment.Index1 < si + subtreeLength) {
-              // subtree contains fragment, we are interested to see what the subtree looked like before
-              // but we also want to keep track of what it looks like now, therefore we branch here
-              var n = traceGraph.GetByContent(g.Data);
-              if (n == null) {
-                n = g.Copy();
-                traceGraph.AddVertex(n);
-                traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
-              }
-              Trace(parents[0], si, n);
-              break;
-            } else {
-              // fragment and subtree are distinct, subtree index stays the same
-              // since the subtree comes before the fragment in the prefix node ordering
-              g = parents[0];
-              continue;
-            }
           }
         }
@@ -171 +157 @@
       // when we are out of the while the last vertex must be connected with the current one
       ConnectLast(g, si, last);
+    }
+
+    /// <summary>
+    /// Get the trace node from the trace graph which corresponds to node g from the genealogy graph.
+    /// If the trace graph does not contain such a node, one is created by performing a shallow copy of g, then inserted into the trace graph.
+    /// </summary>
+    /// <param name="g">The genealogy graph node</param>
+    /// <param name="si">The subtree index</param>
+    /// <param name="fi">The fragment index</param>
+    /// <returns></returns>
+    private IGenealogyGraphNode<ISymbolicExpressionTree> GetTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, int fi) {
+      var n = traceGraph.GetByContent(g.Data);
+      if (n == null) {
+        n = g.Copy();
+        traceGraph.AddVertex(n);
+        Debug.Assert(!traceMap.ContainsKey(n));
+        traceMap[n] = new Tuple<int, int>(si, fi);
+      }
+      return n;
     }