Opened 5 years ago

Closed 5 years ago

#1683 closed feature request (done)

Semantic similarity crossover

Reported by: bburlacu Owned by: bburlacu
Priority: medium Milestone: HeuristicLab 3.3.7
Component: Problems.DataAnalysis.Symbolic Version: 3.3.7
Keywords: Cc: mkommend

Description

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 S1 and S2 are considered similar if SSD(S1,S2) 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

Change History (9)

comment:1 Changed 5 years ago by bburlacu

  • Owner changed from bburlacu to mkommend
  • Status changed from new to assigned

r7036: Added SymbolicDataAnalysisExpressionSemanticSimilarityCrossover operator.

r7106: Implemented the SemanticSimilarityCrossover.

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

comment:2 Changed 5 years ago by bburlacu

  • Status changed from assigned to reviewing

comment:3 Changed 5 years ago by mkommend

r7488: Minor code improvements in SemanticSimilarityCrossover.

comment:4 Changed 5 years ago by mkommend

  • Owner changed from mkommend to bburlacu
  • Status changed from reviewing to assigned

Reviewing comments:

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

comment:5 Changed 5 years ago by bburlacu

r7496: Simplified selection of cut points and allowed branches.

comment:6 Changed 5 years ago by bburlacu

  • Owner changed from bburlacu to mkommend
  • Status changed from assigned to reviewing

comment:7 Changed 5 years ago by mkommend

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

comment:8 Changed 5 years ago by mkommend

  • Owner changed from mkommend to bburlacu
  • Status changed from reviewing to readytorelease

comment:9 Changed 5 years ago by gkronber

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from branch to 3.3.7
Note: See TracTickets for help on using tickets.