Tree matching functionality for symbolic expression trees

[bburlacu]

A useful feature to have would be the possibility to compare and identify common sequences (building blocks, parts of a formula, etc) between symbolic tree-based solution representations.

This functionality was already present (somewhat unpolished) in the tracking branch, as it was used to identify genetic fragments. It should provide equality and comparison methods for symbolic trees and nodes.

[bburlacu]

r10562: Committed initial version of the tree matching functionality.

[bburlacu]

r10563: Fixed storable and cloning constructor access level (from private to protected)

[bburlacu]

r11384: Added license header to SymbolicExpressionTreeMatching.cs. Added a Difference method for calculating the difference between two trees T1 and T2. From a set theory perspective, this method calculates the relative complement of T2 in T1, which is the subtree by which T1 differs from T2. The Difference method is not symmetric, therefore it has been implemented as an extension method.

[bburlacu]

r11392: Corrected Difference method. The way the differing nodes were collected was wrong.

[ascheibe]

Is there a way or would it make sense to integrate e.g. SymbolicExpressionTreeMatching with the ISolutionSimilarityCalculator; so either use this interface or create a new SimilarityCalculator that uses SymbolicExpressionTreeMatching? This would be nice because then we could use symreg also for algorithms that need diversity information and we could also use the SingleObjectivePopulationDiversityAnalyzer for GP.

[bburlacu]

Yes, the functionality you are looking for is available in #2215. Both bottom-up and max common subtree similarity calculators extend SingleObjectiveSolutionSimilarityCalculator in the HeuristicLab.BottomUpTreeDistance branch.

[jkarder]

r11943: merged r10562, r10563, r11384 and r11392 into stable