Changeset 11224 for branches/HeuristicLab.BottomUpTreeDistance

Timestamp:

07/24/14 16:57:38 (10 years ago)

Author:

bburlacu

Message:

#2215: Added checks for debugging purposes in the BottomUpSimilarityCalculator and refactored the SymbolicDataAnalysisInternalDiversityAnalyzer.

Location:

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4

Files:

• Analyzers/SymbolicDataAnalysisInternalDiversityAnalyzer.cs (modified) (7 diffs)
• SimilarityCalculators/BottomUpSimilarityCalculator.cs (modified) (5 diffs)

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Analyzers/SymbolicDataAnalysisInternalDiversityAnalyzer.cs

@@ -20 +20 @@
 #endregion
 
+using System;
+using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Analysis;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Data;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Operators;
@@ -35 +38 @@
   public class SymbolicDataAnalysisInternalDiversityAnalyzer : SingleSuccessorOperator, ISymbolicDataAnalysisAnalyzer {
     private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
+    private const string QualityParameterName = "Quality";
+    private const string PercentageOfBestSolutionsParameterName = "PercentageOfBestSolutions";
+
     private const string ResultCollectionParameterName = "Results";
     private readonly BottomUpSimilarityCalculator busCalculator;
@@ -42 +48 @@
 
       Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName));
+      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(QualityParameterName));
       Parameters.Add(new LookupParameter<ResultCollection>(ResultCollectionParameterName));
+      Parameters.Add(new FixedValueParameter<PercentValue>(PercentageOfBestSolutionsParameterName));
     }
 
@@ -53 +61 @@
     }
 
+    #region parameter properties
     public IScopeTreeLookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
       get { return (IScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
     }
+
+    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
+      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters[QualityParameterName]; }
+    }
+
     public ILookupParameter<ResultCollection> ResultCollectionParameter {
       get { return (ILookupParameter<ResultCollection>)Parameters[ResultCollectionParameterName]; }
+    }
+
+    public IFixedValueParameter<PercentValue> PercentageOfBestSolutionsParameter {
+      get { return (IFixedValueParameter<PercentValue>)Parameters[PercentageOfBestSolutionsParameterName]; }
+    }
+    #endregion
+
+    public double PercentageOfBestSolutions {
+      get { return PercentageOfBestSolutionsParameter.Value.Value; }
+      set { PercentageOfBestSolutionsParameter.Value.Value = value; }
     }
 
@@ -69 +93 @@
       if (!results.ContainsKey("Avg. Internal Diversity")) {
         table = new DataTable("Internal Diversity") { VisualProperties = { YAxisTitle = "Internal Diversity" } };
-        table.Rows.Add(new DataRow("Avg. Internal Diversity"));
+        var row = new DataRow("Avg. Internal Diversity") { VisualProperties = { StartIndexZero = true } };
+        table.Rows.Add(row);
         results.Add(new Result("Avg. Internal Diversity", table));
       } else {
@@ -75 +100 @@
       }
 
-      double diversity = 0;
-      var trees = SymbolicExpressionTreeParameter.ActualValue;
-      foreach (var tree in trees) {
-        diversity += CalculateInternalDiversity(tree);
-      }
+      var trees = SymbolicExpressionTreeParameter.ActualValue.ToArray();
+      var qualities = QualityParameter.ActualValue.ToArray();
 
-      table.Rows["Avg. Internal Diversity"].Values.Add(diversity / trees.Length);
+      Array.Sort(qualities, trees, new ReverseComparer());
+      int n = (int)Math.Floor(trees.Length * PercentageOfBestSolutions);
+
+      double avgInternalDiversity = trees.Take(n).Average(tree => CalculateInternalDiversity(tree));
+
+      table.Rows["Avg. Internal Diversity"].Values.Add(avgInternalDiversity);
       return base.Apply();
     }
@@ -109 +136 @@
     }
   }
+
+  internal class ReverseComparer : IComparer<DoubleValue> {
+    public int Compare(DoubleValue x, DoubleValue y) {
+      return y.CompareTo(x);
+    }
+  }
 }

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
+using System.Drawing;
+using System.Globalization;
 using System.Linq;
+using System.Text;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
 using HeuristicLab.Optimization.Operators;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -52 +56 @@
         throw new ArgumentException("Cannot calculate similarity when one of the arguments is null.");
 
-      return CalculateSolutionSimilarity(t1, t2);
+      var similarity = CalculateSolutionSimilarity(t1, t2);
+      if (similarity > 1.0)
+        throw new Exception("Similarity value cannot be greater than 1");
+
+      return similarity;
     }
 
@@ -69 +77 @@
       var reverseMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
 
-      foreach (var v in n1.IterateNodesBreadth()) {
+      foreach (var v in IterateBreadthOrdered(n1)) {
         if (forwardMap.ContainsKey(v)) continue;
         var kv = compactedGraph[v];
         ISymbolicExpressionTreeNode w = null;
-        foreach (var t in n2.IterateNodesBreadth()) {
+        foreach (var t in IterateBreadthOrdered(n2)) {
           if (reverseMap.ContainsKey(t) || compactedGraph[t] != kv) continue;
           w = t;
@@ -88 +96 @@
           var s = eV.Current;
           var t = eW.Current;
+          if (reverseMap.ContainsKey(t))
+            throw new Exception("Mapping already present");
           forwardMap[s] = t;
           reverseMap[t] = s;
@@ -201 +211 @@
       return arc;
     }
+
+    // debugging
+    private static string FormatMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) {
+      var symbolNameMap = new Dictionary<string, string>
+    {
+      {"ProgramRootSymbol", "Prog"},
+      {"StartSymbol","RPB"},
+      {"Multiplication", "$\\times$"},
+      {"Division", "$\\div$"},
+      {"Addition", "$+$"},
+      {"Subtraction", "$-$"},
+      {"Exponential", "$\\exp$"},
+      {"Logarithm", "$\\log$"}
+    };
+
+      var sb = new StringBuilder();
+      var nodeIds = new Dictionary<ISymbolicExpressionTreeNode, string>();
+      int offset = 0;
+      var layoutEngine = new ReingoldTilfordLayoutEngine<ISymbolicExpressionTreeNode>(x => x.Subtrees);
+      var nodeCoordinates = layoutEngine.CalculateLayout(t1.Root).ToDictionary(n => n.Content, n => new PointF(n.X, n.Y));
+
+      double ws = 0.5;
+      double hs = 0.5;
+
+      var nl = Environment.NewLine;
+      sb.Append("\\documentclass[class=minimal,border=0pt]{standalone}" + nl +
+                 "\\usepackage{tikz}" + nl +
+                 "\\begin{document}" + nl +
+                 "\\begin{tikzpicture}" + nl +
+                 "\\def\\ws{1}" + nl +
+                 "\\def\\hs{0.7}" + nl +
+                 "\\def\\offs{" + offset + "}" + nl);
+
+      foreach (var node in t1.IterateNodesBreadth()) {
+        var id = Guid.NewGuid().ToString();
+        nodeIds[node] = id;
+        var coord = nodeCoordinates[node];
+        var nodeName = symbolNameMap.ContainsKey(node.Symbol.Name) ? symbolNameMap[node.Symbol.Name] : node.ToString();
+        sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\node ({0}) at (\\ws*{1} + \\offs,\\hs*{2}) {{{3}}};", nodeIds[node], ws * coord.X, -hs * coord.Y, EscapeLatexString(nodeName)));
+      }
+
+      foreach (ISymbolicExpressionTreeNode t in t1.IterateNodesBreadth()) {
+        var n = t;
+        foreach (var s in t.Subtrees) {
+          sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", nodeIds[n], nodeIds[s]));
+        }
+      }
+
+      nodeCoordinates = layoutEngine.CalculateLayout(t2.Root).ToDictionary(n => n.Content, n => new PointF(n.X, n.Y));
+
+      offset = 20;
+      sb.Append("\\def\\offs{" + offset + "}" + nl);
+      foreach (var node in t2.IterateNodesBreadth()) {
+        var id = Guid.NewGuid().ToString();
+        nodeIds[node] = id;
+        var coord = nodeCoordinates[node];
+        var nodeName = symbolNameMap.ContainsKey(node.Symbol.Name) ? symbolNameMap[node.Symbol.Name] : node.ToString();
+        sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\node ({0}) at (\\ws*{1} + \\offs,\\hs*{2}) {{{3}}};", nodeIds[node], ws * coord.X, -hs * coord.Y, EscapeLatexString(nodeName)));
+      }
+
+      foreach (ISymbolicExpressionTreeNode t in t2.IterateNodesBreadth()) {
+        var n = t;
+        foreach (var s in t.Subtrees) {
+          sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", nodeIds[n], nodeIds[s]));
+        }
+      }
+
+      foreach (var p in map) {
+        var id1 = nodeIds[p.Key];
+        var id2 = nodeIds[p.Value];
+
+        sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->,color=gray] ({0}) edge[bend left,dashed] ({1});" + Environment.NewLine, id1, id2));
+      }
+      sb.Append("\\end{tikzpicture}" + nl +
+                "\\end{document}" + nl);
+      return sb.ToString();
+    }
+
+    private static string EscapeLatexString(string s) {
+      return s.Replace("\\", "\\\\").Replace("{", "\\{").Replace("}", "\\}").Replace("_", "\\_");
+    }
   }
 }