Semantic similarity crossover

[bburlacu]

This type of crossover works under the assumption that the exchange of subtrees is most likely to be beneficial if they are not semantically identical, but also not too different.

The semantic similarity of two subtrees is determined by comparing them on a set of points in the solution space and taking the average absolute difference as a similarity measure. This measure is denoted sampling semantic distance (SSD) and it depends on the number of points as well as on the strategy of choosing those points (random or heuristic-based).

Two trees S₁ and S₂ are considered similar if SSD(S₁,S₂) lies within the bounds of a so-called syntactic sensitivity interval between two predefined constants. In general, the best values for these semantic sensitivity bounds are problem dependent.

In their papers, [1], [2], Uy et al. show that improving semantic locality significantly improves GP performance, reduces code bloat, and substantially enhances generalization.

References:

[1] ​Semantic similarity based crossover in GP: the case for real-valued function regression, EA'09 Proceedings of the 9th international conference on Artificial Evolution

[2] ​The role of syntactic and semantic locality of crossover in genetic programming, PPSN'10 Proceedings of the 11th international conference on Parallel problem solving from nature: Part II

[bburlacu]

r7036: Added SymbolicDataAnalysisExpressionSemanticSimilarityCrossover operator.

r7106: Implemented the SemanticSimilarityCrossover.

[mkommend]

r7488: Minor code improvements in SemanticSimilarityCrossover.

[mkommend]

Reviewing comments:

• selection of cutpoints results in duplicates
• superfluous swap method
• default values for the similarity interval?

[bburlacu]

r7496: Simplified selection of cut points and allowed branches.