Opened 13 months ago

Closed 42 hours ago

#3067 closed enhancement (done)

Crossover probability for SubtreeCrossover

Reported by: gkronber Owned by: gkronber
Priority: medium Milestone: HeuristicLab 3.3.17
Component: Encodings.SymbolicExpressionTreeEncoding Version:
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 2 months ago.
evaluatedsolutions.jpg (20.9 KB) - added by gkronber 2 months ago.

Download all attachments as: .zip

Change History (15)

comment:1 Changed 13 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 13 months ago by gkronber

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

comment:3 Changed 13 months ago by gkronber

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

comment:4 Changed 13 months ago by gkronber

r17492: adapted unit test to compile with r17490

comment:5 Changed 10 months ago by gkronber

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

comment:6 Changed 3 months 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 2 months ago by gkronber

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

Version 0, edited 2 months ago by gkronber (next)

comment:8 Changed 2 months ago by gkronber

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

Changed 2 months ago by gkronber

Changed 2 months ago by gkronber

comment:9 Changed 2 months 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.

comment:10 Changed 4 weeks ago by mkommend

Reviewed r17871, r17872.

Thank you for providing this feature.

We should think about including the same functionality in other crossovers or generally in the algorithms themselves.

comment:11 Changed 4 weeks ago by mkommend

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

comment:12 Changed 2 days ago by gkronber

r17975: merged r17490:17492 and r17871:17872 from trunk to stable

Last edited 2 days ago by gkronber (previous) (diff)

comment:13 Changed 42 hours ago by gkronber

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version trunk deleted
Note: See TracTickets for help on using tickets.