source: branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Tests/BottomUpSimilarityCalculatorTest.cs @ 11221

Last change on this file since 11221 was 11221, checked in by bburlacu, 8 years ago

#2215: Fixed incorrect namespace of the BottomUpSimilarityCalculator. Changed signature of ComputeBottomMapping method to take tree nodes as arguments rather than trees, because we should be able to compute the bottom-up distance for any two subtrees. Added internal diversity calculator based on the bottom-up distance, which computes the average diversity of all the nodes inside a tree individual.

File size: 7.3 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4using System.Drawing;
5using System.Globalization;
6using System.Linq;
7using System.Text;
8using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
9using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
10using HeuristicLab.Random;
11using Microsoft.VisualStudio.TestTools.UnitTesting;
12
13namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Tests {
14  [TestClass]
15  public class BottomUpSimilarityCalculatorTest {
16    private readonly BottomUpSimilarityCalculator busCalculator;
17    private readonly SymbolicExpressionImporter importer;
18
19    private const int N = 100;
20    private const int Rows = 1;
21    private const int Columns = 10;
22
23    public BottomUpSimilarityCalculatorTest() {
24      busCalculator = new BottomUpSimilarityCalculator();
25      importer = new SymbolicExpressionImporter();
26    }
27
28    [TestMethod]
29    [TestCategory("Problems.DataAnalysis.Symbolic")]
30    [TestProperty("Time", "short")]
31    public void TestBottomUpMatching() {
32      TestMatchedNodes("(+ 1 2)", "(+ 2 1)", 5);
33      TestMatchedNodes("(- 2 1)", "(- 1 2)", 2);
34      TestMatchedNodes("(* (variable 1 X1) (variable 1 X2))", "(* (+ (variable 1 X1) 1) (+ (variable 1 X2) 1))", 2);
35
36      TestMatchedNodes("(* (variable 1 X1) (variable 1 X2))", "(* (+ (variable 1 X1) 1) (variable 1 X2))", 2);
37
38      TestMatchedNodes("(+ (variable 1 a) (variable 1 b))", "(+ (variable 1 a) (variable 1 a))", 1);
39      TestMatchedNodes("(+ (+ (variable 1 a) (variable 1 b)) (variable 1 b))", "(+ (* (+ (variable 1 a) (variable 1 b)) (variable 1 b)) (+ (+ (variable 1 a) (variable 1 b)) (variable 1 b)))", 5);
40
41      TestMatchedNodes(
42        "(* (+ 2.84 (exp (+ (log (/ (variable 2.0539 X5) (variable -9.2452e-1 X6))) (/ (variable 2.0539 X5) (variable -9.2452e-1 X6))))) 2.9081)",
43        "(* (- (variable 9.581e-1 X6) (+ (- (variable 5.1491e-1 X5) 1.614e+1) (+ (/ (variable 2.0539 X5) (variable -9.2452e-1 X6)) (log (/ (variable 2.0539 X5) (variable -9.2452e-1 X6)))))) 2.9081)",
44        9);
45
46      TestMatchedNodes("(+ (exp 2.1033) (/ -4.3072 (variable 2.4691 X7)))", "(/ 1 (+ (/ -4.3072 (variable 2.4691 X7)) (exp 2.1033)))", 6);
47      TestMatchedNodes("(+ (exp 2.1033) (/ -4.3072 (variable 2.4691 X7)))", "(/ 1 (+ (/ (variable 2.4691 X7) -4.3072) (exp 2.1033)))", 4);
48    }
49
50    private void TestMatchedNodes(string expr1, string expr2, int expected) {
51      var t1 = importer.Import(expr1);
52      var t2 = importer.Import(expr2);
53
54      var mapping = busCalculator.ComputeBottomUpMapping(t1.Root, t2.Root);
55      var c = mapping.Count;
56
57      if (c != expected) {
58        throw new Exception("Match count " + c + " is different than expected value " + expected);
59      }
60    }
61
62    [TestMethod]
63    [TestCategory("Problems.DataAnalysis.Symbolic")]
64    [TestProperty("Time", "long")]
65    public void TestBottomUpSimilarityCalculatorPerformance() {
66      var grammar = new TypeCoherentExpressionGrammar();
67      grammar.ConfigureAsDefaultRegressionGrammar();
68      var twister = new MersenneTwister(31415);
69      var ds = Util.CreateRandomDataset(twister, Rows, Columns);
70      var trees = Util.CreateRandomTrees(twister, ds, grammar, N, 1, 100, 0, 0);
71
72      double s = 0;
73      var sw = new Stopwatch();
74
75      sw.Start();
76      for (int i = 0; i < trees.Length - 1; ++i) {
77        for (int j = i + 1; j < trees.Length; ++j) {
78          s += busCalculator.CalculateSolutionSimilarity(trees[i], trees[j]);
79        }
80      }
81      sw.Stop();
82      Console.WriteLine("Elapsed time: " + sw.ElapsedMilliseconds / 1000.0 + ", Avg. similarity: " + s);
83      Console.WriteLine(N * (N + 1) / (2 * sw.ElapsedMilliseconds / 1000.0) + " similarity calculations per second.");
84    }
85
86    private static string FormatMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) {
87      var symbolNameMap = new Dictionary<string, string>
88    {
89      {"ProgramRootSymbol", "Prog"},
90      {"StartSymbol","RPB"},
91      {"Multiplication", "$\\times$"},
92      {"Division", "$\\div$"},
93      {"Addition", "$+$"},
94      {"Subtraction", "$-$"},
95      {"Exponential", "$\\exp$"},
96      {"Logarithm", "$\\log$"}
97    };
98
99      var sb = new StringBuilder();
100      var nodeIds = new Dictionary<ISymbolicExpressionTreeNode, string>();
101      int offset = 0;
102      var layoutEngine = new ReingoldTilfordLayoutEngine<ISymbolicExpressionTreeNode>(x => x.Subtrees);
103      var nodeCoordinates = layoutEngine.CalculateLayout(t1.Root).ToDictionary(n => n.Content, n => new PointF(n.X, n.Y));
104
105      double ws = 0.5;
106      double hs = 0.5;
107
108      var nl = Environment.NewLine;
109      sb.Append("\\documentclass[class=minimal,border=0pt]{standalone}" + nl +
110                 "\\usepackage{tikz}" + nl +
111                 "\\begin{document}" + nl +
112                 "\\begin{tikzpicture}" + nl +
113                 "\\def\\ws{1}" + nl +
114                 "\\def\\hs{0.7}" + nl +
115                 "\\def\\offs{" + offset + "}" + nl);
116
117      foreach (var node in t1.IterateNodesBreadth()) {
118        var id = Guid.NewGuid().ToString();
119        nodeIds[node] = id;
120        var coord = nodeCoordinates[node];
121        var nodeName = symbolNameMap.ContainsKey(node.Symbol.Name) ? symbolNameMap[node.Symbol.Name] : node.ToString();
122        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)));
123      }
124
125      foreach (ISymbolicExpressionTreeNode t in t1.IterateNodesBreadth()) {
126        var n = t;
127        foreach (var s in t.Subtrees) {
128          sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", nodeIds[n], nodeIds[s]));
129        }
130      }
131
132      nodeCoordinates = layoutEngine.CalculateLayout(t2.Root).ToDictionary(n => n.Content, n => new PointF(n.X, n.Y));
133
134      offset = 20;
135      sb.Append("\\def\\offs{" + offset + "}" + nl);
136      foreach (var node in t2.IterateNodesBreadth()) {
137        var id = Guid.NewGuid().ToString();
138        nodeIds[node] = id;
139        var coord = nodeCoordinates[node];
140        var nodeName = symbolNameMap.ContainsKey(node.Symbol.Name) ? symbolNameMap[node.Symbol.Name] : node.ToString();
141        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)));
142      }
143
144      foreach (ISymbolicExpressionTreeNode t in t2.IterateNodesBreadth()) {
145        var n = t;
146        foreach (var s in t.Subtrees) {
147          sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", nodeIds[n], nodeIds[s]));
148        }
149      }
150
151      foreach (var p in map) {
152        var id1 = nodeIds[p.Key];
153        var id2 = nodeIds[p.Value];
154
155        sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->,color=gray] ({0}) edge[bend left,dashed] ({1});" + Environment.NewLine, id1, id2));
156      }
157      sb.Append("\\end{tikzpicture}" + nl +
158                "\\end{document}" + nl);
159      return sb.ToString();
160    }
161
162    private static string EscapeLatexString(string s) {
163      return s.Replace("\\", "\\\\").Replace("{", "\\{").Replace("}", "\\}").Replace("_", "\\_");
164    }
165  }
166}
Note: See TracBrowser for help on using the repository browser.