Opened 11 years ago

Closed 11 years ago

Last modified 11 years ago

#890 closed feature request (done)

Operators for RealVector encoding

Reported by: gkronber Owned by: abeham
Priority: high Milestone: HeuristicLab 3.3.0
Component: Encodings.RealVectorEncoding Version: 3.3
Keywords: Cc:

Description


Change History (25)

comment:1 Changed 11 years ago by abeham

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

comment:2 Changed 11 years ago by abeham

Added polynomial mutation as described by Deb in r2920. Polynomial mutation allows specifying whether changes should be more local or more global by changing the shape of the probability density function from which the mutation strength is drawn (this is not the normal distribution). A maximum manipulation parameter specifies the maximum absolute change that should ever occur.

Deb's implementation described in Deb and Goyal 1996 unfortunately mix mutation and crossover such that mutation is performed only on the crossed genes and then with the given mutation probability. Because in many of our algorithms we decouple crossover and mutation, I have implemented two variants: one that performs the manipulation on a single gene and another that performs it on all genes.

If we also want to have exactly Deb's implementation of his mixed real-coded/binary-coded GA a single operator would need to be implemented that combines the simulated binary crossover (SBX) and the polynomial mutation.

comment:3 Changed 11 years ago by abeham

The simulated binary crossover (SBX) from Deb and Agrawal 1995 was added in r2918:2919. It stems from analyzing the search power of the single point crossover for binary encoding. Deb and Agrawal derived a real coded crossover that produces changes with a similar probability to the single point crossover. Changes that produce very different offspring are not as likely than changes that produce more similar offspring. The shape of this probability function can be adjusted through the contiguity parameter.

comment:4 Changed 11 years ago by abeham

Michalewicz's non-uniform mutation was ported in r2915 also in two variants: one position and all positions. This operator changes the mutation strength depending on the ratio of currentGeneration / maximumGeneration.

A test project was added in r2914, as well as a unit test for the blend alpha crossover (BLX-a).

Operators that were ported in r2913: blend alpha crossover (BLX-a), blend alpha beta crossover (BLX-a-b), and single point crossover. Also in r2913 the uniform one position manipulator was ported.

comment:5 Changed 11 years ago by abeham

updated documentation in r2921

comment:6 Changed 11 years ago by swagner

  • Version changed from 3.2 to 3.3

comment:7 Changed 11 years ago by abeham

Fixed a bug in SBX in r2927. When no crossover is taking place in a dimension, the value in the first parent is taken instead.

comment:8 Changed 11 years ago by abeham

Several changes, please discuss:

  1. I would like to remove the UniformAllPositionsManipulator. It is not a mutation operator in the sense of mutation being a small change to an individual. It randomly reinitializes a whole vector and thus creates a completely new individual (which is why the code is the same as in the UniformRandomRealVectorCreator).
  2. The ContinuousCrossover and CompleteContinuousCrossover in my opinion are not well known by that name. Instead I would suggest implementing the UniformAllPositionsArithmeticCrossover and UniformSomePositionsArithmeticCrossover described by Michalewicz (GA + DS = EP) which include the case of an average crossover. Unfortunately they are only defined for 2 parents. So another operator would be an explicitely named AverageCrossover which calculates the exact average between n parents (there I will reference the IntermediateRecombination described in ES). Do we need an all positions and some positions variant here as well?

comment:9 Changed 11 years ago by abeham

Oh, and another point:

  1. what to do with the SelfAdaptive stuff

comment:10 Changed 11 years ago by abeham

Added DiscreteCrossover in r2928

comment:11 Changed 11 years ago by abeham

Added and removed operators as described above in r2964

comment:12 Changed 11 years ago by abeham

fixed SBX in r3172

comment:13 Changed 11 years ago by abeham

  • Priority changed from major to critical

added bounds check in r3182

comment:14 Changed 11 years ago by abeham

Added move to real vector encoding and test functions in r3187

comment:15 Changed 11 years ago by abeham

Added some move operators for tabu search in r3192

comment:16 Changed 11 years ago by abeham

added normal distributed additive move generator in r3197

comment:17 Changed 11 years ago by abeham

changed some operators (move generators and `SelfAdaptiveNormalAllPositionsManipulator) in r3207

comment:18 Changed 11 years ago by abeham

r3450

  • renamed operators for strategy parameters

comment:19 Changed 11 years ago by abeham

r3520

  • forbid changing some operator names in the GUI

comment:20 Changed 11 years ago by abeham

r3675

  • changed SinglePointCrossover to work with vectors of length 2
  • updated unit tests

comment:21 Changed 11 years ago by abeham

r3677

  • updated MichalewiczNonUniform(All|One)PositionsManipulator to default to "Generations" and added better explanation of one of the parameters

comment:22 Changed 11 years ago by abeham

r3691

  • fixed NormalAllPositionsManipulator to work with GA out of the box

comment:23 Changed 11 years ago by abeham

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

Operators for real vector encoding have been checked against the literature and implemented accordingly.

comment:24 Changed 11 years ago by swagner

  • Milestone changed from Iteration 4 to Current

Milestone Iteration 4 deleted

comment:11 Changed 11 years ago by swagner

  • Milestone changed from Current to HeuristicLab 3.3.0

Milestone Current deleted

Note: See TracTickets for help on using tickets.