Changeset 7788

Timestamp:

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

Author:

bburlacu

Message:

#1772: Fixed bug in fragment tracing.

Location:

branches/HeuristicLab.EvolutionaryTracking

Files:

• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/TracingSymbolicExpressionTreeCrossover.cs (modified) (4 diffs)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj.user (modified) (1 diff)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Plugin.cs (modified) (1 diff)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeMatching.cs (modified) (3 diffs)
• HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFragmentsAnalyzer.cs (modified) (11 diffs)
• HeuristicLab.Selection/3.3/Plugin.cs (modified) (1 diff)
• HeuristicLab.Tracking.suo (modified) (previous)

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

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFragmentsAnalyzer.cs

@@ -20 +20 @@
 #endregion
 
-using System;
 using System.Collections.Generic;
 using System.Linq;
-using System.Text;
 using HeuristicLab.Analysis;
 using HeuristicLab.Common;
@@ -33 +31 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.Problems.DataAnalysis;
-using HeuristicLab.Problems.DataAnalysis.Symbolic;
 // type definitions for ease of use
 using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
@@ -52 +48 @@
     private const string GlobalTraceMapParameterName = "GlobalTraceMap";
     private const string GlobalCloneMapParameterName = "GlobalCloneMap";
+    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
     private const string GenerationsParameterName = "Generations";
     private const string FragmentStatisticsParameterName = "FragmentStatistics";
@@ -71 +68 @@
       get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
     }
+    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
+      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
+    }
     public LookupParameter<IntValue> GenerationsParameter {
       get { return (LookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
@@ -76 +76 @@
     public LookupParameter<DataTable> FragmentStatisticsParameter {
       get { return (LookupParameter<DataTable>)Parameters[FragmentStatisticsParameterName]; }
-
     }
     #endregion
@@ -98 +97 @@
     public TraceMapType GlobalTraceMap {
       get { return GlobalTraceMapParameter.ActualValue; }
+    }
+    public CloneMapType GlobalFragmentMap {
+      get { return GlobalFragmentMapParameter.ActualValue; }
     }
     public IntValue Generations {
@@ -123 +125 @@
       Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing the whole genealogy."));
       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 ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
       Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
@@ -159 +162 @@
         ResultCollection results = ResultsParameter.ActualValue;
         if (FragmentStatistics == null) {
-          FragmentStatisticsParameter.ActualValue = new DataTable("Fragment Statistics", "Statistical measurements of fragments aggregated over the whole population");
+          FragmentStatisticsParameter.ActualValue = new DataTable("Fragment Statistics",
+                                                                  "Statistical measurements of fragments aggregated over the whole population");
           FragmentStatistics.VisualProperties.YAxisTitle = "Fragment length/Similarities";
           results.Add(new Result("Fragment Statistics", FragmentStatistics));
         }
-
-        int numberOfValues = FragmentStatistics.Rows.Select(r => r.Values.Count).DefaultIfEmpty().First();
 
         UpdateCounter.Value = 0; // reset counter
@@ -171 +173 @@
 
         #region Fragment Statistics
-        // write these to file for now, later we will use a DataTable and display the results inside HeuristicLab
-        var path = Environment.GetFolderPath(Environment.SpecialFolder.Personal);
-        //using (var file = System.IO.File.AppendText(path + @"\tracking.csv")) {
         var fragments = new List<ISymbolicExpressionTreeNode>();
         var parents = new List<ISymbolicExpressionTree>();
-        double best = gScope.SubScopes.Select(x => x.Variables["Quality"].Value as DoubleValue).Max(x => x.Value);
         var trees = (from s in gScope.SubScopes select s.Variables.First().Value as ISymbolicExpressionTree).ToList();
         foreach (var tree in trees.Where(x => GlobalTraceMap.ContainsKey(x))) {
-          var parent0 = (ISymbolicExpressionTree)GlobalTraceMap[tree][0];
-          var fragment = SymbolicExpressionTreeMatching.GetFragmentDiff(parent0, tree);
-          if (fragment != null) {
-            parents.Add(parent0);
-            fragments.Add(fragment);
-            if (GlobalTraceMap.ContainsKey(parent0)) {
-              var p = (ISymbolicExpressionTree)GlobalTraceMap[parent0][0];
-              fragment = SymbolicExpressionTreeMatching.GetFragmentDiff(p, parent0);
-              if (fragment != null) {
-                parents.Add(p);
-                fragments.Add(fragment);
+          if (GlobalTraceMap[tree].Count == 2) {
+            var fragment = tree.IterateNodes().ElementAt(((IntValue)GlobalFragmentMap[tree]).Value);
+            if (fragment != null) {
+              parents.AddRange(GlobalTraceMap[tree].Cast<ISymbolicExpressionTree>());
+              fragments.Add(fragment);
+            } else { // "intermediate crossovers" (immediately followed by mutation)
+              var parent0 = (ISymbolicExpressionTree)GlobalTraceMap[tree][0];
+              if (GlobalTraceMap.ContainsKey(parent0)) {
+                var p = (ISymbolicExpressionTree)GlobalTraceMap[parent0][0];
+                fragment = parent0.IterateNodes().ElementAt(((IntValue)GlobalFragmentMap[parent0]).Value);
+                if (fragment != null) {
+                  parents.AddRange(GlobalTraceMap[parent0].Cast<ISymbolicExpressionTree>());
+                  fragments.Add(fragment);
+                }
               }
             }
@@ -200 +201 @@
         double a3 = parents.Average(x => x.Length);
         double s1 = CalculateSimilarity(fragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact);
-        double s2 = CalculateSimilarity(fragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.High);
-        double s3 = CalculateSimilarity(fragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.Relaxed);
+        //double s2 = CalculateSimilarity(fragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.High);
+        //double s3 = CalculateSimilarity(fragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.Relaxed);
 
         #region Table data
@@ -232 +233 @@
         }
         FragmentStatistics.Rows["Similarity (exact)"].Values.Add(s1);
-        // exact similarity
-        if (!FragmentStatistics.Rows.ContainsKey("Similarity (high)")) {
-          DataRow row = new DataRow("Similarity (high)", "");
-          row.VisualProperties.StartIndexZero = true;
-          FragmentStatistics.Rows.Add(row);
-        }
-        FragmentStatistics.Rows["Similarity (high)"].Values.Add(s2);
-        // exact similarity
-        if (!FragmentStatistics.Rows.ContainsKey("Similarity (relaxed)")) {
-          DataRow row = new DataRow("Similarity (relaxed)", "");
-          row.VisualProperties.StartIndexZero = true;
-          FragmentStatistics.Rows.Add(row);
-        }
-        FragmentStatistics.Rows["Similarity (relaxed)"].Values.Add(s3);
-
-        //file.WriteLine(best * 10.0 + " " + a1 + " " + a2 + " " + a3 + " " + s1 + " " + s2 + " " + s3);
+        // high similarity
+        //if (!FragmentStatistics.Rows.ContainsKey("Similarity (high)")) {
+        //  DataRow row = new DataRow("Similarity (high)", "");
+        //  row.VisualProperties.StartIndexZero = true;
+        //  FragmentStatistics.Rows.Add(row);
         //}
+        //FragmentStatistics.Rows["Similarity (high)"].Values.Add(s2);
+        //// relaxed similarity
+        //if (!FragmentStatistics.Rows.ContainsKey("Similarity (relaxed)")) {
+        //  DataRow row = new DataRow("Similarity (relaxed)", "");
+        //  row.VisualProperties.StartIndexZero = true;
+        //  FragmentStatistics.Rows.Add(row);
+        //}
+        //FragmentStatistics.Rows["Similarity (relaxed)"].Values.Add(s3);
         #endregion
+
         #endregion
+
         // clear the global maps to save memory
         GlobalCloneMap.Clear();
         GlobalTraceMap.Clear();
+        GlobalFragmentMap.Clear();
       }
       return base.Apply();

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Selection/3.3/Plugin.cs

@@ -26 +26 @@
   /// Plugin class for HeuristicLab.Selection plugin.
   /// </summary>
-  [Plugin("HeuristicLab.Selection", "3.3.6.7779")]
+  [Plugin("HeuristicLab.Selection", "3.3.6.7785")]
   [PluginFile("HeuristicLab.Selection-3.3.dll", PluginFileType.Assembly)]
   [PluginDependency("HeuristicLab.Collections", "3.3")]