Changeset 8557 for branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding

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.

Location:

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4

Files:

• Crossovers/TracingSymbolicExpressionTreeCrossover.cs (modified) (6 diffs)
• GenericWrapper.cs (modified) (2 diffs)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj (modified) (2 diffs)
• Interfaces/ISymbolicExpressionTreeNodeComparer.cs (added)
• Interfaces/Operators/ITracingSymbolicExpressionTreeOperator.cs (added)
• Manipulators/TracingSymbolicExpressionTreeManipulator.cs (modified) (6 diffs)
• TracingSymbolicExpressionTreeOperator.cs (added)

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/TracingSymbolicExpressionTreeCrossover.cs

@@ -28 +28 @@
 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 +34 @@
   [Item("SymbolicExpressionTreeCrossover", "A base class for operators that perform a crossover of symbolic expression trees.")]
   [StorableClass]
-  public abstract class TracingSymbolicExpressionTreeCrossover : SymbolicExpressionTreeOperator, ISymbolicExpressionTreeCrossover {
+  public abstract class TracingSymbolicExpressionTreeCrossover : TracingSymbolicExpressionTreeOperator, ISymbolicExpressionTreeCrossover {
     private const string ParentsParameterName = "Parents";
     private const string ChildParameterName = "Child";
-    private const string GlobalTraceMapParameterName = "GlobalTraceMap";
-    private const string GlobalCloneMapParameterName = "GlobalCloneMap";
-    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
+
 
     #region Parameter Properties
@@ -50 +45 @@
     public ILookupParameter<ISymbolicExpressionTree> ChildParameter {
       get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters[ChildParameterName]; }
-    }
-    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
@@ -70 +56 @@
       set { ChildParameter.ActualValue = value; }
     }
-    public CloneMapType GlobalCloneMap {
-      get { return GlobalCloneMapParameter.ActualValue; }
-    }
-    public TraceMapType GlobalTraceMap {
-      get { return GlobalTraceMapParameter.ActualValue; }
-    }
-    public CloneMapType GlobalFragmentMap {
-      get { return GlobalFragmentMapParameter.ActualValue; }
-    }
     #endregion
 
@@ -85 +62 @@
       : base(deserializing) {
     }
-
     protected TracingSymbolicExpressionTreeCrossover(TracingSymbolicExpressionTreeCrossover original, Cloner cloner)
       : base(original, cloner) {
     }
-
     protected TracingSymbolicExpressionTreeCrossover()
       : base() {
       Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(ParentsParameterName, "The parent symbolic expression trees which should be crossed."));
       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(ChildParameterName, "The child symbolic expression tree resulting from the crossover."));
-      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
-      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
-      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing tracing info."));
+
     }
-
     public sealed override IOperation Apply() {
       if (Parents.Length != 2)
         throw new ArgumentException("Number of parents must be exactly two for symbolic expression tree crossover operators.");
 
-      // add global trace cache if not already present in global scope
-      var gScope = ExecutionContext.Scope;
-      while (gScope.Parent != null)
-        gScope = gScope.Parent;
-      if (GlobalTraceMap == null)
-        gScope.Variables.Add(new Variable(GlobalTraceMapParameterName, new TraceMapType()));
-      if (GlobalFragmentMap == null)
-        gScope.Variables.Add(new Variable(GlobalFragmentMapParameterName, new CloneMapType()));
-
-      // get original parents (this info will be needed later to construct the genealogy graph)
-      var originalParents = new ItemList<IItem>(Parents.Select(x => GlobalCloneMap[x]));
+      AddTracingVariablesToGlobalScope();
 
       // save the nodes of parent0 in a list so we can track what modifications are made by crossover
@@ -124 +86 @@
       var nodes1 = Child.IterateNodesBreadth().ToList();
 
-      // compare the two nodes lists and check the difference (comparing node references so we avoid false functional identity). 
-      // if no difference is found, then it is assumed that the whole tree was swapped with itself (it can happen), so the index is 0
-      int i, min = Math.Min(nodes0.Count, nodes1.Count);
-      for (i = 0; i != min; ++i)
-        if (nodes0[i] != nodes1[i]) break;
+      // compare the two node lists and check the difference (comparing node references so we avoid false functional identity). 
+      int i = 0, min = Math.Min(nodes0.Count, nodes1.Count);
+      while (i != min && ReferenceEquals(nodes0[i], nodes1[i])) ++i;
+
       // add heredity information into the global variables
-      GlobalTraceMap[Child] = originalParents; // map child to its corresponding parents from the previous generation
-      GlobalFragmentMap[Child] = new GenericWrapper<SymbolicExpressionTreeNode>(i == min ? null : (SymbolicExpressionTreeNode)nodes1[i]); // map child to the index of its fragment
+      GlobalTraceMap[Child] = new ItemList<IItem>(Parents.Select(x => GlobalCloneMap[x])); ; // map child to its corresponding parents from the previous generation
+      GlobalFragmentMap[Child] = new GenericWrapper<ISymbolicExpressionTreeNode>(i == min ? null : nodes1[i]); // map child to the index of its fragment
       return base.Apply();
     }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/GenericWrapper.cs

@@ -6 +6 @@
   [Item("Generic wrapper", "Wrapper class for non-item HeuristicLab objects")]
   [StorableClass]
-  public class GenericWrapper<T> : NamedItem where T : class {
+  public class GenericWrapper<T> : NamedItem where T : class, IDeepCloneable {
+    [Storable]
     public T Content { get; private set; }
-
-    private GenericWrapper() {
-    }
 
     public GenericWrapper(T content) {
@@ -17 +15 @@
 
     [StorableConstructor]
-    protected GenericWrapper(bool serializing)
-      : base(serializing) {
-    }
+    private GenericWrapper(bool serializing) : base(serializing) { }
 
     private GenericWrapper(GenericWrapper<T> original, Cloner cloner)
       : base(original, cloner) {
+      this.Content = cloner.Clone(Content);
     }
 

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj

@@ -167 +167 @@
     <Compile Include="Compiler\SymbolicExpressionTreeCompiler.cs" />
     <None Include="Plugin.cs.frame" />
+    <Compile Include="Interfaces\Operators\ITracingSymbolicExpressionTreeOperator.cs" />
+    <Compile Include="TracingSymbolicExpressionTreeOperator.cs" />
     <Compile Include="Creators\TracingSymbolicExpressionTreeCreator.cs" />
     <Compile Include="Creators\FullTreeCreator.cs">
@@ -181 +183 @@
     <Compile Include="Interfaces\ISymbolicExpressionGrammarBase.cs" />
     <Compile Include="Interfaces\ISymbolicExpressionTreeGrammar.cs" />
+    <Compile Include="Interfaces\ISymbolicExpressionTreeNodeComparer.cs" />
     <Compile Include="Interfaces\Operators\ISymbolicExpressionTreeArchitectureAlteringOperator.cs" />
     <Compile Include="Interfaces\Operators\ISymbolicExpressionTreeGrammarBasedOperator.cs" />

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();
     }