Information Technology Reference
In-Depth Information
14.3.5 Crossover
The two individuals selected, called
parents
, are used to generate two
offspring
.The
probability of crossover
p
c
is the probability that they are crossed. It is generally
above 80%, and remains constant throughout the algorithm. If the crossover does
not occur, the offspring are identical to the parents, but if crossover takes place, the
two offspring are obtained by:
o
1
=
α
p
1
+
(
1
−
α)
p
2
(14.23)
o
2
=
α
p
2
+
(
1
−
α)
p
1
where
o
i
are the offspring,
p
i
the parents and
a random vector with elements in
the range from 0 to 1. The products are element-wise.
α
14.3.6 Mutation
Some of the genes in the offspring are randomly changed, that is, a random number
(positive or negative) is added. The probability of change in a gene is called prob-
ability of mutation
p
m
. It is generally constant and very small, below 2%, because
otherwise the search would be completely random. However, in this work
p
m
is a
linearly decreasing parameter throughout the algorithm, from 1 in the first genera-
tion, to 0 in the last one. In this way, the search is fully random in first generations,
so all the regions in the solution space are explored. However, in the last genera-
tions, mutations almost never occur, so the crossover dominates the search, and the
algorithm can converge to the best regions previously found.
Then, the two offspring are added to the new population, and the algorithm returns
to step 4, until the number of elements in this newpopulation equals that of the present
one.
14.3.7 Evaluation of the Population
Each individual in the new population is evaluated as in step 2.
14.3.8 Stop Condition
If the stop condition is not met, the present population is replaced by the new popu-
lation, and the algorithm returns to step 3. Otherwise, it ends, and the best individual
in the new population is taken as the final solution.
Different stop conditions can be used. The most commons being to reach a max-
imum number of generations, a minimum cost, a number of generations without
Search WWH ::
Custom Search