Changeset 8557 for branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/TracingSymbolicExpressionTreeManipulator.cs

Timestamp:

09/03/12 15:26:04 (12 years ago)

Author:

bburlacu

Message:

#1772: Introduced base class and interface for tracing operators. Introduced SymbolicExpressionTreeNodeComparer interface to be implemented by node matching operators. Fixed bug in the TracingSymbolicExpressionTreeManipulator where nodes modified by the Full- and OnePoint tree shakers were not correctly detected. The SymbolicExpressionTreeNodeSimilarityComparer is now injected in the tracing genetic operators as a parameter.

File:

• branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/TracingSymbolicExpressionTreeManipulator.cs (modified) (6 diffs)

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/TracingSymbolicExpressionTreeManipulator.cs

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
@@ -28 +29 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
-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>>;
-
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
   /// <summary>
@@ -37 +35 @@
   [Item("TracingSymbolicExpressionTreeManipulator", "A base class for operators that manipulate symbolic expression trees.")]
   [StorableClass]
-  public abstract class TracingSymbolicExpressionTreeManipulator : SymbolicExpressionTreeOperator, ISymbolicExpressionTreeManipulator {
+  public abstract class TracingSymbolicExpressionTreeManipulator : TracingSymbolicExpressionTreeOperator, ISymbolicExpressionTreeManipulator {
     private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
-    private const string GlobalTraceMapParameterName = "GlobalTraceMap";
-    private const string GlobalCloneMapParameterName = "GlobalCloneMap";
-    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
 
     #region Parameter Properties
     public ILookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
       get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
-    }
-    public LookupParameter<CloneMapType> GlobalCloneMapParameter {
-      get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
-    }
-    public LookupParameter<TraceMapType> GlobalTraceMapParameter {
-      get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
-    }
-    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
-      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
     }
     #endregion
@@ -61 +47 @@
     public ISymbolicExpressionTree SymbolicExpressionTree {
       get { return SymbolicExpressionTreeParameter.ActualValue; }
-    }
-    public CloneMapType GlobalCloneMap {
-      get { return GlobalCloneMapParameter.ActualValue; }
-    }
-    public TraceMapType GlobalTraceMap {
-      get { return GlobalTraceMapParameter.ActualValue; }
-    }
-    public CloneMapType GlobalFragmentMap {
-      get { return GlobalFragmentMapParameter.ActualValue; }
     }
     #endregion
@@ -79 +56 @@
       : base() {
       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression tree on which the operator should be applied."));
-      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
-      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing tracing info."));
-      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
     }
 
@@ -87 +61 @@
       ISymbolicExpressionTree tree = SymbolicExpressionTreeParameter.ActualValue;
 
-      var gScope = ExecutionContext.Scope;
-      while (gScope.Parent != null)
-        gScope = gScope.Parent;
+      AddTracingVariablesToGlobalScope();
 
-      if (GlobalTraceMap == null)
-        gScope.Variables.Add(new Variable(GlobalTraceMapParameterName, new TraceMapType()));
-      if (GlobalFragmentMap == null)
-        gScope.Variables.Add(new Variable(GlobalFragmentMapParameterName, new CloneMapType()));
-
-      int i = 0;
+      /* The following block needs to be explained in more detail;
+       * If the tree was already affected by crossover (before mutation), then:
+       * - it will already be contained in the GlobalTraceMap
+       * - In order to preserve information, a clone of the tree is created
+       * - The clone represents the intermediate stage of the tree, before mutation is applied
+       * - The clone therefore represents the child after crossover so GlobalTraceMap[clone] will get tree's parents
+       *   and GlobalFragmentMap[clone] will get the subtree from clone that represents the cloned fragment
+       * - After tree is mutated, we set GlobalTraceMap[tree] = clone and GlobalFragmentMap[tree] = modified node from tree
+       */
+      ISymbolicExpressionTreeNode fragment;
       if (GlobalTraceMap.ContainsKey(tree)) {
-        // tree was affected by crossover before mutation
-        // if the tree to be manipulated is already a product of crossover (in the current reproduction phase), 
-        // then there exists no relationship with the original "parent". 
-        // In order to preserve information, a tree clone is created before mutation and added to the trace map.
-        var clone = (IItem)tree.Clone();
+        var clone = (IItem)tree.Clone(); // create clone of tree
         GlobalTraceMap[clone] = GlobalTraceMap[tree]; // clone gets parents of tree
         GlobalTraceMap[tree] = new ItemList<IItem> { clone }; // tree gets clone as parent
-        var nodes = tree.IterateNodesBreadth().ToList();
-        for (i = 0; i != nodes.Count; ++i) {
-          if ((GlobalFragmentMap[tree] as GenericWrapper<SymbolicExpressionTreeNode>).Content == nodes[i]) break;
+        fragment = ((GenericWrapper<ISymbolicExpressionTreeNode>)GlobalFragmentMap[tree]).Content;
+        int index = tree.IterateNodesBreadth().ToList().IndexOf(fragment); // returns -1 if fragment is not present in tree
+        GlobalFragmentMap[clone] = new GenericWrapper<ISymbolicExpressionTreeNode>(index == -1 ? null : ((ISymbolicExpressionTree)clone).IterateNodesBreadth().ElementAt(index));
+      } else {
+        GlobalTraceMap[tree] = new ItemList<IItem> { GlobalCloneMap[tree] };
+      }
+
+      var original = GlobalCloneMap[tree];
+      var nodes0 = ((ISymbolicExpressionTree)original).IterateNodesBreadth().ToList();
+
+      // perform mutation
+      Manipulate(RandomParameter.ActualValue, tree);
+
+      var nodes1 = tree.IterateNodesBreadth().ToList();
+
+      int min = Math.Min(nodes0.Count, nodes1.Count);
+      // some tree manipulators only change local parameters while the actual node stays the same
+      // consequently, we need a stronger comparison than ReferenceEquals
+      var comp = SymbolicExpressionTreeNodeComparer;
+      if (comp == null)
+        throw new Exception(Name + ": Could not get SymbolicExpressionTreeNodeComparerParameter!");
+      var mismatches = new List<int>();
+      for (int i = 0; i != min; ++i) {
+        if (!comp.Equals(nodes0[i], nodes1[i])) {
+          mismatches.Add(i);
         }
-        var fragment = (SymbolicExpressionTreeNode)(((SymbolicExpressionTree)clone).IterateNodesBreadth().ElementAt(i));
-        GlobalFragmentMap[clone] = new GenericWrapper<SymbolicExpressionTreeNode>(fragment);
-      } else {
-        var original = GlobalCloneMap[tree];
-        GlobalTraceMap[tree] = new ItemList<IItem> { original };
       }
-      var nodes0 = tree.IterateNodesBreadth().ToList();
-      Manipulate(RandomParameter.ActualValue, tree);
-      var nodes1 = tree.IterateNodesBreadth().ToList();
-      int min = Math.Min(nodes0.Count, nodes1.Count);
-      for (i = 0; i != min; ++i)
-        if (nodes0[i] != nodes1[i]) break;
-      GlobalFragmentMap[tree] = new GenericWrapper<SymbolicExpressionTreeNode>(i == min ? null : (SymbolicExpressionTreeNode)nodes1[i]);
+      if (mismatches.Count == 0) // should never happen
+        fragment = null;
+      else
+        fragment = mismatches.Count > 1 ? nodes1[mismatches[0]].Parent : nodes1[mismatches[0]];
+      GlobalFragmentMap[tree] = new GenericWrapper<ISymbolicExpressionTreeNode>(fragment);
       return base.Apply();
     }