Opened 11 years ago

Closed 11 years ago

Last modified 10 years ago

#470 closed enhancement (done)

More flexibility in crossover

Reported by: abeham Owned by: swagner
Priority: low Milestone: HeuristicLab 3.3.0
Component: ZZZ OBSOLETE: Evolutionary Version: 3.2
Keywords: Cc:

Description

We've been discussing about the way crossover works in HL3. Currently it is efficient, but missing some flexibility:

  1. It's difficult to apply multiple crossover operators on a population during a generation. One crossover operator is always applied on the whole population.
  2. It's only possible to cross the parameter which the crossover is defined for. Other parameters in the scope get lost. If additional parameters should be crossed as well a separate crossover operator has to be implemented. This can lead to a wild range of crossover operators that call each other's static apply methods.

The second property is limiting the flexibility to a certain degree. For example if one has an object vector and a strategy vector in the scope, one has to write a new crossover that combines the object as well as the strategy vector, because it has to be done in the same step. Even if the crossover would work independently on each of them. Additionally, one has to do so for every possible combinations of such crossovers (e.g. discrete / discrete, intermediate / discrete, discrete / intermediate and intermediate / intermediate). It would be better to have the crossover merge its parameters in a new scope, but let the parents live to allow another crossover independently to do the same with different parameters.

The way we propose a change look as follows: Crossover would have 3 different steps: Preparation, Crossing and optionally Cleanup.

Preparation: Would work on the population scope after selection. It would create new child scopes, based on the number of parents and parents per children which are added to the population scope. The parent scopes for each child are then append to the child as subscopes. Now, below the population scope, there'll be several empty child scopes, each with their parents as subscopes.

Crossover: The actual crossover (or crossovers) will be applied on each child scope and merge the parameters from its parent into the child scope. Now, the child scope would contain the merged parameters from the parent scope.

Cleanup (optional): Cleanup would simply remove all the parent scopes.

This would also make the application of offspring selection easier. If cleanup is not performed, the offspring selection operator can read the fitness of the parents right out of the child's subscopes. So, the offspring selection operator would perform the cleanup.

If no cleanup is done at all, one automatically gets the whole anchestor tree. This would be absolutely great for further analysis, although of course memory requirements would be huge.

Execution speed would suffer slightly, but should not be that much. The overhead are multiple calls to the crossover operator, as it has to be done per new child now.

Attachments (1)

hl3_crossover.png (38.6 KB) - added by abeham 11 years ago.
A drawing of the actual and proposed working of crossover

Download all attachments as: .zip

Change History (12)

Changed 11 years ago by abeham

A drawing of the actual and proposed working of crossover

comment:1 Changed 11 years ago by swagner

I like this idea very much and I will implement it as soon as possible.

If anybody else needs it more quickly, please feel free to implement it yourself. However, in that case let's have a discussion about some details and naming first.

comment:2 Changed 11 years ago by abeham

  • Owner changed from swagner to abeham
  • Status changed from new to assigned

comment:3 Changed 11 years ago by abeham

  • Resolution set to fixed
  • Status changed from assigned to closed

implemented the changes in r1159 updated the workbenches and libraries in r140

comment:4 Changed 11 years ago by swagner

  • Milestone changed from 3.2 to Iteration 0

Milestone 3.2 deleted

comment:5 Changed 11 years ago by swagner

  • Milestone changed from Iteration 0 to Iteration 1

comment:6 Changed 11 years ago by swagner

  • Resolution fixed deleted
  • Status changed from closed to reopened

Due to these changes, the parameter scope is no longer needed in the Cross method of CrossoverBase and MultiCrossoverBase. Furthermore, two different base classes for crossing two and for crossing more parents is not reasonable. MultiCrossoverBase should be merged into CrossoverBase.

comment:7 Changed 11 years ago by swagner

  • Owner changed from abeham to swagner
  • Status changed from reopened to new

comment:8 Changed 11 years ago by swagner

  • Status changed from new to assigned

comment:9 Changed 11 years ago by swagner

  • Resolution set to fixed
  • Status changed from assigned to closed

Finished refactoring of crossover operators in r1218.

comment:10 Changed 10 years ago by swagner

  • Milestone changed from Iteration 1 to Current

Milestone Iteration 1 deleted

comment:11 Changed 10 years ago by swagner

  • Milestone changed from Current to HeuristicLab 3.3.0

Milestone Current deleted

Note: See TracTickets for help on using tickets.