search

heal-research / HeuristicLab

HeuristicLab - An environment for heuristic and evolutionary optimization
https://dev.heuristiclab.com
GNU General Public License v3.0
39 stars 16 forks source link

Probabilistic functional crossover #1682

Closed HeuristicLab-Trac-Bot closed 12 years ago

HeuristicLab-Trac-Bot commented 12 years ago

Issue migrated from trac ticket # 1682

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

2011-11-15 11:57:16: @foolnotion created the issue

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

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-22 13:30:05: @foolnotion changed status from new to assigned

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-22 13:30:05: @foolnotion changed owner from bburlacu to mkommend

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-22 13:30:05: @foolnotion commented

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.

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-22 13:30:05: @foolnotion

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-22 13:30:05: @foolnotion

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-22 13:30:05: @foolnotion

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-28 14:58:11: @foolnotion changed owner from mkommend to bburlacu

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-30 17:22:31: @foolnotion changed status from assigned to reviewing

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-30 17:22:31: @foolnotion changed owner from bburlacu to mkommend

HeuristicLab-Trac-Bot commented 12 years ago

2011-12-05 09:42:50: @foolnotion commented

r7119: Implemented the MultiSymbolicDataAnalysisExpressionCrossover

HeuristicLab-Trac-Bot commented 12 years ago

2011-12-16 09:43:33: @foolnotion commented

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

HeuristicLab-Trac-Bot commented 12 years ago

2012-01-10 15:24:17: @foolnotion commented

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

HeuristicLab-Trac-Bot commented 12 years ago

2012-01-17 16:27:02: @foolnotion commented

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.

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-16 10:22:14: @foolnotion commented

r7474 (not migrated): Deleted old branch.

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-16 10:35:26: @mkommend commented

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

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-16 13:54:14: @foolnotion commented

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

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-17 14:24:04: @mkommend changed status from reviewing to assigned

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-17 14:24:10: @mkommend changed status from assigned to accepted

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-17 14:26:26: @mkommend commented

r7481: Corrected gp-crossover code.

  • Changed ISymbolicExpressionTreeCrossover
  • Corrected SubtreeCrossover
  • Updated MultiSymbolicDataAnalysisCrossover
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-20 10:28:00: @mkommend commented

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

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-20 10:55:05: @mkommend commented

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.
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-20 10:55:05: @mkommend changed owner from mkommend to bburlacu

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-20 10:55:05: @mkommend changed status from accepted to assigned

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-20 10:55:16: @mkommend changed milestone from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.7

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-20 13:53:50: @mkommend commented

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

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-20 15:12:40: @mkommend commented

r7490: Set range values of DepthConstrainedCrossover to read only.

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-21 10:59:00: @foolnotion commented

r7494:

  • Moved Swap method into base class
  • Simplified selection of allowed branches
  • Replaced while loop with a more simple reversed for loop
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-21 11:09:53: @foolnotion commented

r7497:

  • Added names and detailed descriptions to all crossover operators
  • Minor code improvements (selection of allowed branches and cutpoints)
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-21 11:13:22: @foolnotion commented

r7498: SubtreeCrossover: Minor improvement inside the SelectCrossoverPoint method.

HeuristicLab-Trac-Bot commented 12 years ago

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

HeuristicLab-Trac-Bot commented 12 years ago

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

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-23 16:06:16: @mkommend commented

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

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-23 16:15:03: @mkommend commented

r7507: Forgot to commit two files.

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-23 17:43:46: @mkommend commented

r7508: Added performance unit tests for new GP crossovers.

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-24 15:50:16: @mkommend commented

r7521: Forbid name changes in new gp crossovers

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-27 15:39:50: @mkommend changed owner from mkommend to gkronber

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-28 09:54:41: @mkommend commented

r7533 (not migrated): Removed already integrated branch HeuristcLab.Crossovers.

HeuristicLab-Trac-Bot commented 12 years ago

2012-07-03 15:50:35: @gkronber commented

r8203: minor improvements for semantic crossovers

HeuristicLab-Trac-Bot commented 12 years ago

2012-07-03 15:55:03: @gkronber commented

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!

HeuristicLab-Trac-Bot commented 12 years ago

2012-07-03 15:55:03: @gkronber changed status from reviewing to readytorelease

HeuristicLab-Trac-Bot commented 12 years ago

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

HeuristicLab-Trac-Bot commented 12 years ago

2012-07-08 04:36:18: @gkronber changed status from readytorelease to closed