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

Timestamp:

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

Author:

bburlacu

Message:

#1772: Fixed bug in fragment tracing.

Location:

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

Files:

• Crossovers/TracingSymbolicExpressionTreeCrossover.cs (modified) (4 diffs)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj.user (modified) (1 diff)
• Plugin.cs (modified) (1 diff)
• SymbolicExpressionTreeMatching.cs (modified) (3 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();
     }

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

@@ -7 +7 @@
   <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Release|AnyCPU'">
     <StartAction>Program</StartAction>
-    <StartProgram>C:\Users\Bogdan\Desktop\Trunk\sources\bin\HeuristicLab 3.3.exe</StartProgram>
+    <StartProgram>C:\Users\bburlacu\Desktop\HL-Core\trunk\sources\bin\HeuristicLab 3.3.exe</StartProgram>
   </PropertyGroup>
   <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Release|x86'">

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

@@ -26 +26 @@
 
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
-  [Plugin("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding","Provides operators and related classes for the symbolic expression tree encoding.", "3.4.2.7779")]
+  [Plugin("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding","Provides operators and related classes for the symbolic expression tree encoding.", "3.4.2.7785")]
   [PluginFile("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll", PluginFileType.Assembly)]
   [PluginDependency("HeuristicLab.Analysis", "3.3")]

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

@@ -92 +92 @@
     // convenience methods for less typing :)
     private static IEnumerator<ISymbolicExpressionTreeNode> Enumerator(this ISymbolicExpressionTree tree) {
-      return tree.IterateNodesPostfix().GetEnumerator();
+      return tree.IterateNodes().GetEnumerator();
     }
     private static IEnumerator<ISymbolicExpressionTreeNode> Enumerator(this ISymbolicExpressionTreeNode tree) {
-      return tree.IterateNodesPostfix().GetEnumerator();
+      return tree.IterateNodes().GetEnumerator();
     }
     // method for breath-width iteration of nodes
-    private static IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(this ISymbolicExpressionTree tree) {
+    public static IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(this ISymbolicExpressionTree tree) {
       return IterateNodes(tree.Root);
     }
@@ -128 +128 @@
     /// <returns>A symbolic expression tree node representing the difference fragment between parent and child</returns>
     public static ISymbolicExpressionTreeNode GetFragmentDiff(ISymbolicExpressionTree parent, ISymbolicExpressionTree child) {
-      var e1 = parent.Enumerator();
-      var e2 = child.Enumerator();
+      var nodes1 = parent.IterateNodes().ToList();
+      var nodes2 = child.IterateNodes().ToList();
+      var e1 = nodes1.AsEnumerable().GetEnumerator();
+      var e2 = nodes2.AsEnumerable().GetEnumerator();
       while (e1.MoveNext() && e2.MoveNext()) {
         var comparer = new SymbolicExpressionTreeNodeComparer((int)SimilarityLevel.Exact);
-        if (!comparer.Equals(e1.Current, e2.Current)) { return e2.Current; } // return the fragment by which child differs from parent
+        if (!comparer.Equals(e1.Current, e2.Current)) {
+          return e2.Current;
+        }
+        //if (!e1.Current.IterateNodes().SequenceEqual(e2.Current.IterateNodes(), comparer)) {
+        //  return e2.Current;
+        //} // return the fragment by which child differs from parent
       }
       return null;
@@ -145 +152 @@
       var comparer = new SymbolicExpressionTreeNodeComparer(mode);
       if (patlen == seqlen) return seq.SequenceEqual(pat, comparer) ? 0 : -1;
-      //int i = patlen;            
-      //while (i <= seqlen) {
-      //  var ch = seq[i - 1];
-      //  if (comparer.Equals(ch, pat.Last()))
-      //    if (seq.Skip(i - patlen).Take(patlen).SequenceEqual(pat, comparer))
-      //      return i - patlen;
-      //  ++i;
-      //}
       for (int i = patlen; i <= seqlen; ++i) {
         if (comparer.Equals(seq[i - 1], pat.Last())) // first check if last element is a match