276
D. Irawan and B. Naujoks
Fig. 8.7 Example of the
creep mutation with uniform
distribution. The initial point,
i.e., the parent, is located at
x 0 ; after creep mutation it
could take any point between
x
min and x
max with equal
probability. Without creep
mutation, the probability
density is spread over x min
and x max instead
generations. If the old individuals are always kept, there are chances that the
population will return to an older state through recombination, thus regressing
instead of progressing to a better state.
The solution to these problems is to truncate (cut off) the population. However,
a new question arises, “which individuals should be kept and which should be
removed?” The answer to this question is defined in the selection operator. Selection
operator will foster progress by removing individuals which are considered to be bad
and will increase the chance to create better offspring.
We may want to keep all the “best” individuals, but, actually, selection operators
should not always favor the most fit individuals as it would easily lead to stagnation
[15, 44]. So, basically, the selection operator has multiple purposes: prevent
stagnation, foster progress, and avoid making the population too large. Also note
that the population does not have to be at a constant size, some algorithms do use a
varying or adaptive population size such as the GAVaPS [3], or the growing SMSEMOA [23].
The population on which the selection is conducted is determined by the selection
scheme. There are two selection schemes: the plus and comma schemes. The plus
scheme is where both the parents and offspring are considered to be kept, while the
comma scheme disregards the parents [15, 17], i.e., the parents are always discarded.
The schemes are usually written as (μ + λ) and (μ, λ) for the plus and comma
schemes, respectively, where μ is the number of parents and λ is the number of
offspring.
After choosing the selection scheme, then the rule on how to select the individuals need to be decided (known as the selection mechanism [15, 17]). Examples of
selection mechanism are tournament selection [44], fitness-proportional selection
[5, 44], and non-dominated sorting [12].
D. Irawan and B. Naujoks
Fig. 8.7 Example of the
creep mutation with uniform
distribution. The initial point,
i.e., the parent, is located at
x 0 ; after creep mutation it
could take any point between
x
min and x
max with equal
probability. Without creep
mutation, the probability
density is spread over x min
and x max instead
generations. If the old individuals are always kept, there are chances that the
population will return to an older state through recombination, thus regressing
instead of progressing to a better state.
The solution to these problems is to truncate (cut off) the population. However,
a new question arises, “which individuals should be kept and which should be
removed?” The answer to this question is defined in the selection operator. Selection
operator will foster progress by removing individuals which are considered to be bad
and will increase the chance to create better offspring.
We may want to keep all the “best” individuals, but, actually, selection operators
should not always favor the most fit individuals as it would easily lead to stagnation
[15, 44]. So, basically, the selection operator has multiple purposes: prevent
stagnation, foster progress, and avoid making the population too large. Also note
that the population does not have to be at a constant size, some algorithms do use a
varying or adaptive population size such as the GAVaPS [3], or the growing SMSEMOA [23].
The population on which the selection is conducted is determined by the selection
scheme. There are two selection schemes: the plus and comma schemes. The plus
scheme is where both the parents and offspring are considered to be kept, while the
comma scheme disregards the parents [15, 17], i.e., the parents are always discarded.
The schemes are usually written as (μ + λ) and (μ, λ) for the plus and comma
schemes, respectively, where μ is the number of parents and λ is the number of
offspring.
After choosing the selection scheme, then the rule on how to select the individuals need to be decided (known as the selection mechanism [15, 17]). Examples of
selection mechanism are tournament selection [44], fitness-proportional selection
[5, 44], and non-dominated sorting [12].