Semantic similarity crossover

HeuristicLab-Trac-Bot commented 12 years ago

Issue migrated from trac ticket # 1683

milestone: HeuristicLab 3.3.7 | component: Problems.DataAnalysis.Symbolic | priority: medium | resolution: done

2011-11-15 14:14:10: @foolnotion created the issue

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,,1,, and S,,2,, are considered similar if SSD(S,,1,,,S,,2,,) 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

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-22 13:32:01: @foolnotion changed status from new to assigned

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-22 13:32:01: @foolnotion changed owner from bburlacu to mkommend

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-22 13:32:01: @foolnotion commented

r7036: Added SymbolicDataAnalysisExpressionSemanticSimilarityCrossover operator.

r7106: Implemented the SemanticSimilarityCrossover.

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-22 13:32:01: @foolnotion

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-30 17:24:07: @foolnotion changed status from assigned to reviewing

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-20 13:03:45: @mkommend commented

r7488: Minor code improvements in SemanticSimilarityCrossover.

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-20 13:06:43: @mkommend commented

Reviewing comments:

selection of cutpoints results in duplicates

superfluous swap method

default values for the similarity interval?

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-20 13:06:43: @mkommend changed owner from mkommend to bburlacu

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-20 13:06:43: @mkommend changed status from reviewing to assigned

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-21 11:03:17: @foolnotion commented

r7496: Simplified selection of cut points and allowed branches.

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-21 14:39:39: @foolnotion changed owner from bburlacu to mkommend

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-21 14:39:39: @foolnotion changed status from assigned to reviewing

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-21 14:41:40: @mkommend changed milestone from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.7

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-23 16:06:43: @mkommend changed owner from mkommend to bburlacu

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-23 16:06:43: @mkommend changed status from reviewing to readytorelease

HeuristicLab-Trac-Bot commented 12 years ago

2012-07-08 04:36:06: @gkronber removed resolution

HeuristicLab-Trac-Bot commented 12 years ago

heal-research / HeuristicLab