Opened 3 years ago

Closed 2 years ago

#2164 closed enhancement (done)

Tree matching functionality for symbolic expression trees

Reported by: bburlacu Owned by: jkarder
Priority: medium Milestone: HeuristicLab 3.3.11
Component: Problems.DataAnalysis.Symbolic Version: 3.3.9
Keywords: Cc:


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.

Change History (11)

comment:1 Changed 3 years ago by bburlacu

  • Status changed from new to accepted

r10562: Committed initial version of the tree matching functionality.

comment:2 Changed 3 years ago by bburlacu

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

comment:3 Changed 3 years ago by bburlacu

  • Milestone changed from HeuristicLab 3.3.10 to HeuristicLab 3.3.x Backlog

comment:4 Changed 3 years ago by 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.

Last edited 3 years ago by bburlacu (previous) (diff)

comment:5 Changed 2 years ago by bburlacu

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

comment:6 Changed 2 years ago by 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.

comment:7 Changed 2 years ago by 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.

comment:8 Changed 2 years ago by bburlacu

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.11
  • Owner changed from bburlacu to jkarder
  • Status changed from accepted to reviewing
  • Version changed from 3.3.9 to 3.3.11

comment:9 Changed 2 years ago by bburlacu

  • Version changed from 3.3.11 to 3.3.9

comment:10 Changed 2 years ago by jkarder

  • Status changed from reviewing to readytorelease

comment:11 Changed 2 years ago by jkarder

  • Resolution set to done
  • Status changed from readytorelease to closed

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

Note: See TracTickets for help on using tickets.