Digital Signal Processing Reference
In-Depth Information
into the generation. The mutation probability of a bit
p
m
is very small,
usually
p
m
1%. For practical applications, we normally choose
p
m
close to 0.01. Mutation changes the bit values, and produces a nearly
identical copy with some components of the string altered. Selection,
recombination, and mutation operators are applied to each population
in each generation. The GA stops either when a satisfactory solution is
found or after a predefined number of iterations.
The algorithmic description of a GA is given below.
Generate the initial population randomly for the strings
a
i
:
Π=
{
a
i
}
,
i
=1
,
···
,n
.
for
i
1
to Numberofgenerations
do
Initialize mating set
M
←
← ∅
and Offspring
O
for
j
1
to n
do
Add
f
(
a
i
)
/ f
copies from
a
i
to
M
.
end
for
j
←
1
to n/
2
do
Choose two parents
a
j
and
a
k
from
M
and perform with
the probability
p
c
O
=
O
←
∪
Crossover
(
a
j
,a
k
).
end
for
i
←
1
to n
do
for
j
1
to d
do
Mutate with the probability
p
m
the
j
-th bit from
a
i
∈
←
O
end
end
Update the population Π
←
combine(Π
,O
).
end
It is extremely important to mention that the theoretical basis for
convergence of the GA toward the global maximum is based on the
schema theorem
. The formation and preservation of a schema which
is a local optimal pattern should happen at rates acceptable for solving
problems in practice. While we have been dealing so far with only binary
strings, schemas represent bit patterns based on a ternary alphabet: 0,
1, and
(do not care). Thus, a crossover operation enables information
sharing between two optimal schemas such that new and better solutions
are generated.
∗
Search WWH ::
Custom Search