Opened 5 years ago

Closed 5 years ago

#1693 closed feature request (done)

Context-aware 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

Given a randomly selected subtree from one parent, context-aware crossover will always find the best location to place the subtree in the other parent.

In their paper ([1]), Majeed and Ryan suggest that using standard crossover in the initial part of the run and then switching to context-aware crossover yields the best performance. They show that, across a range of standard GP benchmark problems, context-aware crossover produces a higher best fitness as well as a higher mean fitness, and even manages to solve the 11-bit multiplexer problem without ADFs. At the same time, the individuals produced this way are much smaller than standard GP, and far fewer individual evaluations are required, so GP achieves a higher fitness by evaluating fewer and smaller individuals.

The authors hypothesize that the order in which crossover operators are applied (for instance the standard and the context-aware ones) and the time of their application can have a big impact on the experiments outcome.

[1] Using Context-aware Crossover to Improve the Performance of GP, Proceeding, GECCO '06, Proceedings of the 8th annual conference on Genetic and evolutionary computation, ACM New York, NY, USA ©2006.

Change History (10)

comment:1 Changed 5 years ago by bburlacu

  • Version changed from 3.3.5 to branch

comment:2 Changed 5 years ago by bburlacu

  • Status changed from new to assigned

r7109: Implemented the context-aware crossover.

comment:3 Changed 5 years ago by bburlacu

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

comment:4 Changed 5 years ago by bburlacu

r7110: Submitted another variant of the context-aware crossover, called the DeterministicBestCrossover. This one selects a random crossover point and finds the best node from the other parent to be inserted there.

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

comment:5 Changed 5 years ago by mkommend

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

Reviewing comments:

  • selection of cutpoints
  • reorder criteria for cutpoint selection
  • swap method
  • do not set the operator name in the default ctor as this is done by the ItemAttribute automatically
  • improve descriptions

comment:6 Changed 5 years ago by bburlacu

r7495: Simplified selection of cutpoints and reordered criteria for cutpoint selection

comment:7 Changed 5 years ago by bburlacu

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

comment:8 Changed 5 years ago by mkommend

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

comment:9 Changed 5 years ago by mkommend

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

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