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

Timestamp:

05/10/12 17:17:14 (13 years ago)

Author:

bburlacu

Message:

#1772: Changelog:

• Removed GetCutIndex method, and corresponding index field in the GenealogyGraphNode.
• Implemented tracking for mutated fragments.
• Improved FindMatch method.
• Added IterateNodesBreadth functionality to symbolic expression trees and nodes.
• Added check conditions for clearing global tracking structures so that the 2 analyzers are not mutually exclusive anymore.

Location:

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

Files:

• Crossovers/TracingSymbolicExpressionTreeCrossover.cs (modified) (6 diffs)
• Interfaces/ISymbolicExpressionTree.cs (modified) (1 diff)
• Interfaces/ISymbolicExpressionTreeNode.cs (modified) (1 diff)
• Manipulators/TracingSymbolicExpressionTreeManipulator.cs (modified) (6 diffs)
• Plugin.cs (modified) (1 diff)
• SymbolicExpressionTree.cs (modified) (1 diff)
• SymbolicExpressionTreeMatching.cs (modified) (1 diff)
• SymbolicExpressionTreeNode.cs (modified) (2 diffs)

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

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
@@ -35 +36 @@
   /// 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 {
@@ -46 +46 @@
 
     #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 TraceMapType GlobalTraceMap {
+      get { return GlobalTraceMapParameter.ActualValue; }
+    }
     public CloneMapType GlobalFragmentMap {
       get { return GlobalFragmentMapParameter.ActualValue; }
     }
-
-    public TraceMapType GlobalTraceMap {
-      get { return GlobalTraceMapParameter.ActualValue; }
-    }
-
     #endregion
 
@@ -105 +93 @@
     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."));
+      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."));
     }
 
@@ -120 +103 @@
       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;
+      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
+
+      // get original parents (this info will be needed later to construct the genealogy graph)
       var originalParents = new ItemList<IItem>(Parents.Select(x => GlobalCloneMap[x]));
+
       // save the nodes of parent0 in a list so we can track what modifications are made by crossover
-      var nodes0 = Parents[0].IterateNodes().ToList();
+      var nodes0 = Parents[0].IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
+
       //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();
+      var nodes1 = Child.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
+
       // 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
@@ -141 +131 @@
         if (nodes0[i] != nodes1[i]) break;
       if (i == min) i = 0;
-      GlobalTraceMap[Child] = originalParents;
-      GlobalFragmentMap[Child] = new IntValue(i);
+
+      // add heredity information into the global variables
+      GlobalTraceMap[Child] = originalParents; // map child to its corresponding parents from the previous generation
+      GlobalFragmentMap[Child] = new IntValue(i); // map child to the index of its fragment
       return base.Apply();
     }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionTree.cs

@@ -31 +31 @@
     IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix();
     IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPostfix();
+    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth();
   }
 }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionTreeNode.cs

@@ -36 +36 @@
     IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPostfix();
     IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix();
+    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth();
     void ForEachNodePostfix(Action<ISymbolicExpressionTreeNode> a);
     void ForEachNodePrefix(Action<ISymbolicExpressionTreeNode> a);

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

@@ -21 +21 @@
 
 using System;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Data;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -39 +41 @@
     private const string GlobalTraceMapParameterName = "GlobalTraceMap";
     private const string GlobalCloneMapParameterName = "GlobalCloneMap";
+    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
 
     #region Parameter Properties
@@ -49 +52 @@
     public LookupParameter<TraceMapType> GlobalTraceMapParameter {
       get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
+    }
+    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
+      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
     }
     #endregion
@@ -62 +68 @@
       get { return GlobalTraceMapParameter.ActualValue; }
     }
+    public CloneMapType GlobalFragmentMap {
+      get { return GlobalFragmentMapParameter.ActualValue; }
+    }
     #endregion
 
@@ -72 +81 @@
       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."));
     }
 
@@ -77 +87 @@
       ISymbolicExpressionTree tree = SymbolicExpressionTreeParameter.ActualValue;
 
-      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()));
+
       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". 
+        // 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();
         GlobalTraceMap[clone] = GlobalTraceMap[tree];
         GlobalTraceMap[tree] = new ItemList<IItem> { clone };
+        GlobalFragmentMap[clone] = GlobalFragmentMap[tree];
       } 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 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;
+      GlobalFragmentMap[tree] = new IntValue(i);
 
       return base.Apply();

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.7785")]
+  [Plugin("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding","Provides operators and related classes for the symbolic expression tree encoding.", "3.4.2.7788")]
   [PluginFile("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll", PluginFileType.Assembly)]
   [PluginDependency("HeuristicLab.Analysis", "3.3")]

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

@@ -85 +85 @@
       return root.IterateNodesPostfix();
     }
+    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth() {
+      if (root == null)
+        return new SymbolicExpressionTreeNode[0];
+      return root.IterateNodesBreadth();
+    }
 
     public override IDeepCloneable Clone(Cloner cloner) {

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

@@ -70 +70 @@
 
     public static bool ContainsFragment(this ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, int mode) {
-      var nodes = tree.IterateNodesPostfix().ToArray();
-      var fragments = fragment.IterateNodesPostfix().ToArray();
+      var nodes = tree.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
+      var fragments = fragment.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
       return FindMatch(nodes, fragments, mode) != -1;
     }
 
-    #region FindMatch signatures
-    public static int FindMatch(ISymbolicExpressionTree t0, ISymbolicExpressionTree t1, int mode) {
-      return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
-    }
-    private static int FindMatch(ISymbolicExpressionTreeNode t0, ISymbolicExpressionTreeNode t1, int mode) {
-      return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
-    }
-    private static int FindMatch(ISymbolicExpressionTree t0, ISymbolicExpressionTreeNode t1, int mode) {
-      return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
-    }
-    private static int FindMatch(ISymbolicExpressionTreeNode t0, ISymbolicExpressionTree t1, int mode) {
-      return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
-    }
-    #endregion
-
     // convenience methods for less typing :)
     private static IEnumerator<ISymbolicExpressionTreeNode> Enumerator(this ISymbolicExpressionTree tree) {
-      return tree.IterateNodes().GetEnumerator();
+      return tree.IterateNodesBreadth().GetEnumerator();
     }
     private static IEnumerator<ISymbolicExpressionTreeNode> Enumerator(this ISymbolicExpressionTreeNode tree) {
-      return tree.IterateNodes().GetEnumerator();
+      return tree.IterateNodesBreadth().GetEnumerator();
     }
-    // method for breath-width iteration of nodes
-    public static IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(this ISymbolicExpressionTree tree) {
-      return IterateNodes(tree.Root);
+    public static int FindMatch(ISymbolicExpressionTree a, ISymbolicExpressionTree b, int mode) {
+      var nodesA = a.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
+      var nodesB = b.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
+      return FindMatch(nodesA, nodesB, mode);
     }
-
-    private static IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(this ISymbolicExpressionTreeNode root) {
-      var list = new List<ISymbolicExpressionTreeNode> { root };
-      int offset = 0, count = 1;
-      while (offset != count) {
-        var c = count;
-        for (int i = offset; i != count; ++i) {
-          yield return list[i]; // TODO: look into yield performance (vs returning the whole list at the end)
-          if (!list[i].Subtrees.Any()) continue;
-          list.AddRange(list[i].Subtrees);
-        }
-        offset = c;
-        count = list.Count;
-      }
-      //return list;
+    public static int FindMatch(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, int mode) {
+      var nodesA = a.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
+      var nodesB = b.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
+      return FindMatch(nodesA, nodesB, mode);
     }
-
-    /// <summary>
-    /// This method finds the point where parent and child differ. For instance in the case of crossover, 
-    /// it will return the node that was swapped into parent0 from parent1
-    /// Prerequisites: as the naming implies, heredity should exist between parent and child,
-    /// otherwise this method would not make much sense (it would always return the root of child)
-    /// </summary>
-    /// <param name="parent">The individual from the previous generation that was crossed over or mutated to produce child</param>
-    /// <param name="child">The result of a genetic operation applied on parent</param>
-    /// <returns>A symbolic expression tree node representing the difference fragment between parent and child</returns>
-    public static ISymbolicExpressionTreeNode GetFragmentDiff(ISymbolicExpressionTree parent, ISymbolicExpressionTree child) {
-      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;
-        }
-        //if (!e1.Current.IterateNodes().SequenceEqual(e2.Current.IterateNodes(), comparer)) {
-        //  return e2.Current;
-        //} // return the fragment by which child differs from parent
-      }
-      return null;
-    }
-
     // returns the index in the sequence 'seq', where pattern 'pat' is matched, or -1 for no match
     // -1 means no match, 0 means perfect match (the sequences overlap, hence the match index is 0)
-    public static int FindMatch(ISymbolicExpressionTreeNode[] seq, ISymbolicExpressionTreeNode[] pat, int mode) {
-      int patlen = pat.Length;
-      int seqlen = seq.Length;
+    public static int FindMatch(List<ISymbolicExpressionTreeNode> seq, List<ISymbolicExpressionTreeNode> pat, int mode) {
+      int patlen = pat.Count;
+      int seqlen = seq.Count;
       if (patlen == 0 || seqlen == 0) return -1;
       var comparer = new SymbolicExpressionTreeNodeComparer(mode);

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

@@ -172 +172 @@
     }
 
+    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth() {
+      var list = new List<ISymbolicExpressionTreeNode>(GetLength()) { this };
+      int offset = 0, count = 1;
+      while (offset != count) {
+        var c = count;
+        for (int i = offset; i != count; ++i)
+          if (list[i].SubtreeCount > 0)
+            list.AddRange(list[i].Subtrees);
+        offset = c;
+        count = list.Count;
+      }
+      return list;
+    }
+
     public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix() {
-      List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>();
+      List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>(GetLength());
       ForEachNodePrefix((n) => list.Add(n));
       return list;
@@ -188 +202 @@
 
     public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPostfix() {
-      List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>();
+      List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>(GetLength());
       ForEachNodePostfix((n) => list.Add(n));
       return list;