1 | #region License Information |
---|
2 | /* HeuristicLab |
---|
3 | * Copyright (C) 2002-2019 Heuristic and Evolutionary Algorithms Laboratory (HEAL) |
---|
4 | * |
---|
5 | * This file is part of HeuristicLab. |
---|
6 | * |
---|
7 | * HeuristicLab is free software: you can redistribute it and/or modify |
---|
8 | * it under the terms of the GNU General Public License as published by |
---|
9 | * the Free Software Foundation, either version 3 of the License, or |
---|
10 | * (at your option) any later version. |
---|
11 | * |
---|
12 | * HeuristicLab is distributed in the hope that it will be useful, |
---|
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
---|
15 | * GNU General Public License for more details. |
---|
16 | * |
---|
17 | * You should have received a copy of the GNU General Public License |
---|
18 | * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>. |
---|
19 | */ |
---|
20 | #endregion |
---|
21 | |
---|
22 | using System; |
---|
23 | using System.Collections.Generic; |
---|
24 | using System.Globalization; |
---|
25 | using System.Linq; |
---|
26 | using HeuristicLab.Common; |
---|
27 | using HeuristicLab.Core; |
---|
28 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding; |
---|
29 | using HeuristicLab.Optimization.Operators; |
---|
30 | using HEAL.Attic; |
---|
31 | |
---|
32 | using NodeMap = System.Collections.Generic.Dictionary<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>; |
---|
33 | |
---|
34 | namespace HeuristicLab.Problems.DataAnalysis.Symbolic { |
---|
35 | [StorableType("63ACB7A4-137F-468F-BE42-A4CA6B62C63B")] |
---|
36 | [Item("SymbolicExpressionTreeBottomUpSimilarityCalculator", "A similarity calculator which uses the tree bottom-up distance as a similarity metric.")] |
---|
37 | public class SymbolicExpressionTreeBottomUpSimilarityCalculator : SolutionSimilarityCalculator { |
---|
38 | private readonly HashSet<string> commutativeSymbols = new HashSet<string> { "Addition", "Multiplication", "Average", "And", "Or", "Xor" }; |
---|
39 | |
---|
40 | public SymbolicExpressionTreeBottomUpSimilarityCalculator() { } |
---|
41 | protected override bool IsCommutative { get { return true; } } |
---|
42 | |
---|
43 | public bool MatchConstantValues { get; set; } |
---|
44 | public bool MatchVariableWeights { get; set; } |
---|
45 | |
---|
46 | [StorableConstructor] |
---|
47 | protected SymbolicExpressionTreeBottomUpSimilarityCalculator(StorableConstructorFlag _) : base(_) { |
---|
48 | } |
---|
49 | |
---|
50 | protected SymbolicExpressionTreeBottomUpSimilarityCalculator(SymbolicExpressionTreeBottomUpSimilarityCalculator original, Cloner cloner) |
---|
51 | : base(original, cloner) { |
---|
52 | } |
---|
53 | |
---|
54 | public override IDeepCloneable Clone(Cloner cloner) { |
---|
55 | return new SymbolicExpressionTreeBottomUpSimilarityCalculator(this, cloner); |
---|
56 | } |
---|
57 | |
---|
58 | #region static methods |
---|
59 | private static ISymbolicExpressionTreeNode ActualRoot(ISymbolicExpressionTree tree) { |
---|
60 | return tree.Root.GetSubtree(0).GetSubtree(0); |
---|
61 | } |
---|
62 | |
---|
63 | public static double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool strict = false) { |
---|
64 | return CalculateSimilarity(ActualRoot(t1), ActualRoot(t2), strict); |
---|
65 | } |
---|
66 | |
---|
67 | public static double CalculateSimilarity(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2, bool strict = false) { |
---|
68 | var calculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator { MatchConstantValues = strict, MatchVariableWeights = strict }; |
---|
69 | return CalculateSimilarity(n1, n2, strict); |
---|
70 | } |
---|
71 | |
---|
72 | public static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool strict = false) { |
---|
73 | return ComputeBottomUpMapping(ActualRoot(t1), ActualRoot(t2), strict); |
---|
74 | } |
---|
75 | |
---|
76 | public static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2, bool strict = false) { |
---|
77 | var calculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator { MatchConstantValues = strict, MatchVariableWeights = strict }; |
---|
78 | return calculator.ComputeBottomUpMapping(n1, n2); |
---|
79 | } |
---|
80 | #endregion |
---|
81 | |
---|
82 | public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) { |
---|
83 | return CalculateSimilarity(t1, t2, out Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map); |
---|
84 | } |
---|
85 | |
---|
86 | public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, out NodeMap map) { |
---|
87 | if (t1 == t2) { |
---|
88 | map = null; |
---|
89 | return 1; |
---|
90 | } |
---|
91 | map = ComputeBottomUpMapping(t1, t2); |
---|
92 | return 2.0 * map.Count / (t1.Length + t2.Length - 4); // -4 for skipping root and start symbols in the two trees |
---|
93 | } |
---|
94 | |
---|
95 | public override double CalculateSolutionSimilarity(IScope leftSolution, IScope rightSolution) { |
---|
96 | if (leftSolution == rightSolution) |
---|
97 | return 1.0; |
---|
98 | |
---|
99 | var t1 = leftSolution.Variables[SolutionVariableName].Value as ISymbolicExpressionTree; |
---|
100 | var t2 = rightSolution.Variables[SolutionVariableName].Value as ISymbolicExpressionTree; |
---|
101 | |
---|
102 | if (t1 == null || t2 == null) |
---|
103 | throw new ArgumentException("Cannot calculate similarity when one of the arguments is null."); |
---|
104 | |
---|
105 | var similarity = CalculateSimilarity(t1, t2); |
---|
106 | if (similarity > 1.0) |
---|
107 | throw new Exception("Similarity value cannot be greater than 1"); |
---|
108 | |
---|
109 | return similarity; |
---|
110 | } |
---|
111 | |
---|
112 | public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) { |
---|
113 | return ComputeBottomUpMapping(t1.Root.GetSubtree(0).GetSubtree(0), t2.Root.GetSubtree(0).GetSubtree(0)); |
---|
114 | } |
---|
115 | |
---|
116 | public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) { |
---|
117 | var compactedGraph = Compact(n1, n2); |
---|
118 | |
---|
119 | IEnumerable<ISymbolicExpressionTreeNode> Subtrees(ISymbolicExpressionTreeNode node, bool commutative) { |
---|
120 | var subtrees = node.IterateNodesPrefix(); |
---|
121 | return commutative ? subtrees.OrderBy(x => compactedGraph[x].Hash) : subtrees; |
---|
122 | } |
---|
123 | |
---|
124 | var nodes1 = n1.IterateNodesPostfix().OrderByDescending(x => x.GetLength()); // by descending length so that largest subtrees are mapped first |
---|
125 | var nodes2 = (List<ISymbolicExpressionTreeNode>)n2.IterateNodesPostfix(); |
---|
126 | |
---|
127 | var forward = new NodeMap(); |
---|
128 | var reverse = new NodeMap(); |
---|
129 | |
---|
130 | foreach (ISymbolicExpressionTreeNode v in nodes1) { |
---|
131 | if (forward.ContainsKey(v)) |
---|
132 | continue; |
---|
133 | |
---|
134 | var kv = compactedGraph[v]; |
---|
135 | var commutative = v.SubtreeCount > 1 && commutativeSymbols.Contains(kv.Label); |
---|
136 | |
---|
137 | foreach (ISymbolicExpressionTreeNode w in nodes2) { |
---|
138 | if (w.GetLength() != kv.Length || w.GetDepth() != kv.Depth || reverse.ContainsKey(w) || compactedGraph[w] != kv) |
---|
139 | continue; |
---|
140 | |
---|
141 | // map one whole subtree to the other |
---|
142 | foreach (var t in Subtrees(v, commutative).Zip(Subtrees(w, commutative), Tuple.Create)) { |
---|
143 | forward[t.Item1] = t.Item2; |
---|
144 | reverse[t.Item2] = t.Item1; |
---|
145 | } |
---|
146 | |
---|
147 | break; |
---|
148 | } |
---|
149 | } |
---|
150 | |
---|
151 | return forward; |
---|
152 | } |
---|
153 | |
---|
154 | /// <summary> |
---|
155 | /// Creates a compact representation of the two trees as a directed acyclic graph |
---|
156 | /// </summary> |
---|
157 | /// <param name="n1">The root of the first tree</param> |
---|
158 | /// <param name="n2">The root of the second tree</param> |
---|
159 | /// <returns>The compacted DAG representing the two trees</returns> |
---|
160 | private Dictionary<ISymbolicExpressionTreeNode, GraphNode> Compact(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) { |
---|
161 | var nodeMap = new Dictionary<ISymbolicExpressionTreeNode, GraphNode>(); // K |
---|
162 | var labelMap = new Dictionary<string, GraphNode>(); // L |
---|
163 | |
---|
164 | var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F |
---|
165 | var graph = new List<GraphNode>(); |
---|
166 | |
---|
167 | IEnumerable<GraphNode> Subtrees(GraphNode g, bool commutative) { |
---|
168 | var subtrees = g.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]); |
---|
169 | return commutative ? subtrees.OrderBy(x => x.Hash) : subtrees; |
---|
170 | } |
---|
171 | |
---|
172 | foreach (var node in nodes) { |
---|
173 | var label = GetLabel(node); |
---|
174 | |
---|
175 | if (node.SubtreeCount == 0) { |
---|
176 | if (!labelMap.ContainsKey(label)) { |
---|
177 | labelMap[label] = new GraphNode(node, label); |
---|
178 | } |
---|
179 | nodeMap[node] = labelMap[label]; |
---|
180 | } else { |
---|
181 | var v = new GraphNode(node, label); |
---|
182 | bool found = false; |
---|
183 | var commutative = node.SubtreeCount > 1 && commutativeSymbols.Contains(label); |
---|
184 | |
---|
185 | var vv = Subtrees(v, commutative); |
---|
186 | |
---|
187 | foreach (var w in graph) { |
---|
188 | if (v.Depth != w.Depth || v.SubtreeCount != w.SubtreeCount || v.Length != w.Length || v.Label != w.Label) { |
---|
189 | continue; |
---|
190 | } |
---|
191 | |
---|
192 | var ww = Subtrees(w, commutative); |
---|
193 | found = vv.SequenceEqual(ww); |
---|
194 | |
---|
195 | if (found) { |
---|
196 | nodeMap[node] = w; |
---|
197 | break; |
---|
198 | } |
---|
199 | } |
---|
200 | if (!found) { |
---|
201 | nodeMap[node] = v; |
---|
202 | graph.Add(v); |
---|
203 | } |
---|
204 | } |
---|
205 | } |
---|
206 | return nodeMap; |
---|
207 | } |
---|
208 | |
---|
209 | private string GetLabel(ISymbolicExpressionTreeNode node) { |
---|
210 | if (node.SubtreeCount > 0) |
---|
211 | return node.Symbol.Name; |
---|
212 | |
---|
213 | if (node is ConstantTreeNode constant) |
---|
214 | return MatchConstantValues ? constant.Value.ToString(CultureInfo.InvariantCulture) : constant.Symbol.Name; |
---|
215 | |
---|
216 | if (node is VariableTreeNode variable) |
---|
217 | return MatchVariableWeights ? variable.Weight + variable.VariableName : variable.VariableName; |
---|
218 | |
---|
219 | return node.ToString(); |
---|
220 | } |
---|
221 | |
---|
222 | private class GraphNode { |
---|
223 | private GraphNode() { } |
---|
224 | |
---|
225 | public GraphNode(ISymbolicExpressionTreeNode node, string label) { |
---|
226 | SymbolicExpressionTreeNode = node; |
---|
227 | Label = label; |
---|
228 | Hash = GetHashCode(); |
---|
229 | Depth = node.GetDepth(); |
---|
230 | Length = node.GetLength(); |
---|
231 | } |
---|
232 | |
---|
233 | public int Hash { get; } |
---|
234 | public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode { get; } |
---|
235 | public string Label { get; } |
---|
236 | public int Depth { get; } |
---|
237 | public int SubtreeCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } } |
---|
238 | public int Length { get; } |
---|
239 | } |
---|
240 | } |
---|
241 | } |
---|