Context Navigation

#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 14 years ago by abeham

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

comment:2 Changed 14 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 14 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 14 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 14 years ago by abeham

updated documentation in r2921

comment:6 Changed 14 years ago by swagner

Version changed from 3.2 to 3.3

comment:7 Changed 14 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 14 years ago by abeham

Several changes, please discuss:

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).
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?