Information Technology Reference
In-Depth Information
f
(
H
f
)
M(
H
t
+1) = M(
H
t
)
(13.20)
This shows that the size of a particular schema is directly proportional to the
ratio of the average fitness of the schema to that of population. In other words,
the schema whose average fitness value is higher than that of population can
generate more representation strings in next generation, while the representation
strings of a schema with lower average fitness will reduce in next generation.
Suppose that schema
H
's average fitness value is greater than that of population
c
f
by value
, where
c
is constant,
then growth equation of a schema is
f
+
c f
M
(
H
t
+1) =
M
(
H
t
)
= (1+c)· M(
H
t
)
(13.21)
f
Further, we can conclude that
)
t
(13.22)
Expression (13.22) shows that the representation strings of a schema whose
average fitness is higher than that of population will grow exponentially with
generation; on the contrary, for the schema whose average fitness is lower than
that of population, its representation strings will reduce at an exponentially
decaying rate.
m
(
H
t
) =
m
(
H
0) · (1+
c
13.6.3
Crossover operation
Crossover operation is a process of information exchange among structural
random strings. Suppose that population
) is a set of schemas, where historical
information is expressed in the form of instances, which are saved in B(t).
Crossover operation is to generate new instances of the existing schemas. At the
same time, new schemas are also generated. A simple crossover operation can be
divided into three steps:
B
(
t
(1) Select two strings from population
B
(
t
):
a
=
s
1
s
2
··· s
l
a' = s'
1
s'
2
··· s'
l
(2) Randomly select a integer
-1}
(3) Exchange the elements on the left of the position
x
∈
{12
···
l
x
in
a
and
a
', and then
generate two pieces of new strings:
s
1
··· s
x
s'
x+1
··· s'
l
and
s'
1
··· s'
x
s
x+1
··· S
l
If each string is endowed with intensity
S
(
C
j
,
T
), then genetic algorithm is
described as follows:
