Opened 6 years ago

Closed 5 years ago

#1682 closed feature request (done)

Probabilistic functional crossover

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

Description

This crossover operator increases the probability of a beneficial recombination event by (probabilistically) weighting the nodes in the genome based on their behavioral rather than structural similarity.

The main idea is that when a node i is randomly chosen from the first parent, the second parent is scanned to find the node j that has the closest range to that of the chosen node in the first parent, based on a sort of behavioral distance that takes into account the minimum and maximum values computed by the two nodes during computation.

However, instead of being greedy (the case for the deterministic functional crossover), the procedure (which involves computing all distances between node i and every node k from the second parent) assigns a probability for each node in the second parent to be selected as the second cross point, based on the inverted normalized value of the behavioral distance (so the lower the distance, the higher the probability).

J.C. Bongard in [1] claims that this method outperforms genetic programming without crossover, random crossover, and a deterministic form of the crossover operator in the symbolic regression domain.

[1] A Probabilistic Functional Crossover Operator for Genetic Programming, Proceeding, GECCO '10 Proceedings of the 12th annual conference on Genetic and Evolutionary Computation

Change History (31)

comment:1 Changed 6 years ago by bburlacu

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

r7035: Added base class SymbolicDataAnalysisExpressionCrossover for data analysis crossovers (crossovers that also perform evaluation for computing distance metrics). Made adjustments to other classes to accommodate the new crossovers (some methods became more general and were moved), changes affect CutPoint.cs, SubtreeCrossover.cs, SymbolicExpressionTreeNode.cs and others.

r7072: New versions of crossover (work-in-progress)

r7075: Updated crossovers

r7105: Implemented the ProbabilisticFunctionalCrossover.

r7086: Added crossover discovery code.

r7089: Fixed a bug affecting all new crossovers.

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

comment:2 Changed 6 years ago by bburlacu

  • Owner changed from mkommend to bburlacu

comment:3 Changed 6 years ago by bburlacu

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

comment:4 Changed 6 years ago by bburlacu

r7119: Implemented the MultiSymbolicDataAnalysisExpressionCrossover

comment:5 Changed 6 years ago by bburlacu

r7193: Overhauled the crossover operators, fixed bug in the DeterministicBestCrossover.

comment:6 Changed 5 years ago by bburlacu

r7303: Override of the CanChangeName property, added friendly names for the crossover operators.

comment:7 Changed 5 years ago by bburlacu

r7343, r7344, r7346, r7348: Switched to a new branch in the new branch format, removed unnecessary and misplaced files, updated license information, removed redundant inheritance from ISymbolicDataAnalysisExpressionCrossover.

comment:8 Changed 5 years ago by bburlacu

r7474: Deleted old branch.

comment:9 Changed 5 years ago by mkommend

r7475: Corrected crossover branch (assembly references, prebuild command).

comment:10 Changed 5 years ago by bburlacu

r7477: Added missing files (that were previously incorrectly referencing the old branch), added unit tests, recommitted lost changes.

comment:11 Changed 5 years ago by mkommend

  • Status changed from reviewing to assigned

comment:12 Changed 5 years ago by mkommend

  • Status changed from assigned to accepted

comment:13 Changed 5 years ago by mkommend

r7481: Corrected gp-crossover code.

  • Changed ISymbolicExpressionTreeCrossover
  • Corrected SubtreeCrossover
  • Updated MultiSymbolicDataAnalysisCrossover

comment:14 Changed 5 years ago by mkommend

r7486: Added forgotten AfterDeserializationHook in the SymbolicDataAnalysisExpressionTreeInterpreter to add the EvaluatedSolutionsParameter if it is not present.

comment:15 Changed 5 years ago by mkommend

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

Reviewing comments:

  • ProbabilisticFunctionalCrossover
    • Line 71 - 76 selects allowed branches multiple times
    • Line 108 - 118 would be better as a for-loop iterating backwards
  • DeterministicBestCrossover
    • Line 71 - 76 selects allowed branches multiple times
    • swap method exists in several crossovers and should be moved to a base class
    • Method names should start with a capitol letter, e.g. Swap instead of swap.

comment:16 Changed 5 years ago by mkommend

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

comment:17 Changed 5 years ago by mkommend

r7489: Improved DepthConstrainedCrossover and removed readonly attribute from the operators collection in the MultiCrossover.

comment:18 Changed 5 years ago by mkommend

r7490: Set range values of DepthConstrainedCrossover to read only.

comment:19 Changed 5 years ago by bburlacu

r7494:

  • Moved Swap method into base class
  • Simplified selection of allowed branches
  • Replaced while loop with a more simple reversed for loop

comment:20 Changed 5 years ago by bburlacu

r7497:

  • Added names and detailed descriptions to all crossover operators
  • Minor code improvements (selection of allowed branches and cutpoints)

comment:21 Changed 5 years ago by bburlacu

r7498: SubtreeCrossover: Minor improvement inside the SelectCrossoverPoint method.

comment:22 Changed 5 years ago by bburlacu

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

comment:23 Changed 5 years ago by mkommend

r7506: Integrated new gp crossovers into the trunk and corrected the parameter wiring.

comment:24 Changed 5 years ago by mkommend

r7507: Forgot to commit two files.

comment:25 Changed 5 years ago by mkommend

r7508: Added performance unit tests for new GP crossovers.

comment:26 Changed 5 years ago by mkommend

r7521: Forbid name changes in new gp crossovers

comment:27 Changed 5 years ago by mkommend

  • Owner changed from mkommend to gkronber

comment:28 Changed 5 years ago by mkommend

r7533: Removed already integrated branch HeuristcLab.Crossovers.

comment:29 Changed 5 years ago by gkronber

r8203: minor improvements for semantic crossovers

comment:30 Changed 5 years ago by gkronber

  • Status changed from reviewing to readytorelease

The code is well documented, reusable, easily understandable, well structured, adheres to the coding guidelines, and does not contain any obvious mistakes in cloning, event registration or parameter name mapping.

Thanks for implementing these crossover operators!

comment:31 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.