Changeset 7788 for branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/TracingSymbolicExpressionTreeCrossover.cs

Timestamp:

05/09/12 17:29:33 (12 years ago)

Author:

bburlacu

Message:

#1772: Fixed bug in fragment tracing.

File:

• branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/TracingSymbolicExpressionTreeCrossover.cs (modified) (4 diffs)

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

@@ -24 +24 @@
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Data;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -34 +35 @@
   /// A base class for operators that perform a crossover of symbolic expression trees.
   /// </summary>
-  [Item("SymbolicExpressionTreeCrossover", "A base class for operators that perform a crossover of symbolic expression trees.")]
+  [Item("SymbolicExpressionTreeCrossover",
+    "A base class for operators that perform a crossover of symbolic expression trees.")]
   [StorableClass]
   public abstract class TracingSymbolicExpressionTreeCrossover : SymbolicExpressionTreeOperator, ISymbolicExpressionTreeCrossover {
@@ -41 +43 @@
     private const string GlobalTraceMapParameterName = "GlobalTraceMap";
     private const string GlobalCloneMapParameterName = "GlobalCloneMap";
+    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
+
     #region Parameter Properties
+
     public ILookupParameter<ItemArray<ISymbolicExpressionTree>> ParentsParameter {
       get { return (ScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[ParentsParameterName]; }
     }
+
     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
+
     #region Properties
+
     public ItemArray<ISymbolicExpressionTree> Parents {
       get { return ParentsParameter.ActualValue; }
     }
+
     public ISymbolicExpressionTree Child {
       get { return ChildParameter.ActualValue; }
       set { ChildParameter.ActualValue = value; }
     }
+
     public CloneMapType GlobalCloneMap {
       get { return GlobalCloneMapParameter.ActualValue; }
     }
+
+    public CloneMapType GlobalFragmentMap {
+      get { return GlobalFragmentMapParameter.ActualValue; }
+    }
+
     public TraceMapType GlobalTraceMap {
       get { return GlobalTraceMapParameter.ActualValue; }
     }
+
     #endregion
+
     [StorableConstructor]
-    protected TracingSymbolicExpressionTreeCrossover(bool deserializing) : base(deserializing) { }
-    protected TracingSymbolicExpressionTreeCrossover(TracingSymbolicExpressionTreeCrossover original, Cloner cloner) : base(original, cloner) { }
+    protected TracingSymbolicExpressionTreeCrossover(bool deserializing)
+      : 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<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing tracing info."));
+      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."));
     }
 
@@ -85 +121 @@
         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
-      if (GlobalTraceMap == null) {
-        var gScope = ExecutionContext.Scope;
-        while (gScope.Parent != null) gScope = gScope.Parent;
+      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
       var originalParents = new ItemList<IItem>(Parents.Select(x => GlobalCloneMap[x]));
-      ISymbolicExpressionTree result = Crossover(Random, Parents[0], Parents[1]);
-      Child = result;
-      GlobalTraceMap.Add(Child, originalParents);
-
+      // save the nodes of parent0 in a list so we can track what modifications are made by crossover
+      var nodes0 = Parents[0].IterateNodes().ToList();
+      //perform crossover
+      Child = Crossover(Random, Parents[0], Parents[1]);
+      // create another list of parent0's nodes, so we can compare it with the first list to see what changed
+      var nodes1 = Child.IterateNodes().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.Max(nodes0.Count, nodes1.Count);
+      for (i = 0; i != min; ++i)
+        if (nodes0[i] != nodes1[i]) break;
+      if (i == min) i = 0;
+      GlobalTraceMap[Child] = originalParents;
+      GlobalFragmentMap[Child] = new IntValue(i);
       return base.Apply();
     }