Information Technology Reference
In-Depth Information
“1” at given position. For example, consider a schema
H
= *11*0** with length
of 7. Let string A=0111000, then
A
is a representation of
H
;
H
can match
A
at the
2,3,5-th positions.
There are 3
l
schemas with length of
. In general, if alphabet contains k letters,
there are totally (k+1)
l
schemas with length of l. The order of a schema is defined
as the number of the symbol which is not equal to “*” in the schema, denoted by
o(
l
). For a binary string, its order is equal to the number of 1 and 0. For example,
the order of schema 011*1** is equal to 4, denoted by o(011*1**) = 4;
o(0******) =1.
As the number of the symbol which is not equal to “*” in the schema,
denoted by o(
H
). For a binary string, its order is equal to the number of 1 and 0.
For example, the order of schema 011*1** is equal to 4, denoted by o(011*1**)
= 4; o(0******) =1.
Definition length of a schema is the distance between the first determining
position and the last determining position in the schema, denoted by delta(
H
H
). For
example, Let H=011*1**, then delta(
)=4. This is because that the first
determining position in this schema is 1, while the last determining position is 5,
and then the distance between them is 5-1=4.
Suppose at the moment
H
t
, schema H has M representations, which are
contained in population B(
). At reproduction stage,
every string is reproduced according to its fitness value. String
t
), denoted by
M
= M(
H
t
B
i
's reproduction
probability is
f
i
p
i
=
(13.17)
Ã
n
f
j
j
=
1
) is replaced with population consisting of n strings which
are not superposed, we hope that there are M(
After population
B
(
t
H
t
+1) representations of schema
H
in population
B
(
t
+1) at the moment
t
. This can be calculated by the following
equation:
f
(
H
)
M(H
t
+1) = M(Ht)· n ·
(13.18)
Ã
n
f
j
j
=
1
where
f
(
H
) denotes average fitness value of strings of schema H at the moment
t
.
Because the average fitness value of the whole population can be written as
f
n
=
Ã
,
j
f
(13.19)
n
j
=
1
the reproduction growth equation of schema can be expressed by
