Opened 12 months ago

Last modified 5 weeks ago

#3067 reviewing enhancement

Crossover probability for SubtreeCrossover

Reported by: gkronber Owned by: mkommend
Priority: medium Milestone: HeuristicLab 3.3.17
Component: Encodings.SymbolicExpressionTreeEncoding Version: trunk
Keywords: Cc:

Description

Some genetic programming variants allow a copy operation where neither crossover nor mutation are applied to selected parent trees.

This is helpful for certain problem instances using a multi-tree representation (via MultiEncoding) where we want to prevent that a crossover event causes crossover for all trees.

One way to add this is to add a crossover rate to the general genetic algorithm variations that we are using in HL for GP.

Another and easier way is to implement this in the crossover operator using a crossover probability.

Attachments (2)

bestquality.jpg (19.3 KB) - added by gkronber 5 weeks ago.
evaluatedsolutions.jpg (20.9 KB) - added by gkronber 5 weeks ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 12 months ago by gkronber

r17490: add crossover probability for subtree crossover and initialized it to 100%

This change breaks reproduceability of old experiments because we added a call to the random number generator.

comment:2 Changed 12 months ago by gkronber

r17491: fix reproducability by calling the PRNG only when probability is < 1

comment:3 Changed 12 months ago by gkronber

  • Status changed from new to accepted
  • Version set to trunk

comment:4 Changed 12 months ago by gkronber

r17492: adapted unit test to compile with r17490

comment:5 Changed 9 months ago by gkronber

  • Owner changed from gkronber to mkommend
  • Status changed from accepted to reviewing

comment:6 Changed 8 weeks ago by mkommend

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

Reviewed r17490, r17491, and r17492.

I have two comments that should be addressed:

  • Why have you chosen to use a DoubleValue instead of a PercentValue? The latter is displayed more nicely, in line with InternalCrossoverPointProbability (which is also a PercentValue) and can be restricted to [0,1].
  • What is the reason for randomly selecting a parent if no crossover is performed? I would have expected that the first parent (parent0) is always returned. Similarly to the fallback if no valid crossover points in the parents can be chosen.

comment:7 Changed 5 weeks ago by gkronber

r17871:17872: changed CrossoverProbabilityParameter to PercentValue and return parent0 when no crossover is performed.

Last edited 5 weeks ago by gkronber (previous) (diff)

comment:8 Changed 5 weeks ago by gkronber

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

Changed 5 weeks ago by gkronber

Changed 5 weeks ago by gkronber

comment:9 Changed 5 weeks ago by gkronber

For OSGPC and the Pagie-1 problem we have:

No big effect for symbolic regression problems with a single tree (higher execution time is caused by resampling in OS). The effect is expected to be more critical with problem encodings made up of several trees.

Note: See TracTickets for help on using tickets.