Information Technology Reference
In-Depth Information
Algorithm 13.4 Genetic algorithm with Intensity
1. At the moment
t
, randomly generate population
B
(
t
) with the number of
M
. Calculate
the average fitness of this population, denoted by
v
(
t
), and then endow each string in
B
(
t
) with the standardizing value
S
(C
j
t
)/
v
(
t
).
2. Endow each string in
B
(
t
) with a probability value, which is directly proportional to
the standardizing value. Then, select n pairs of strings from
B
(
t
) based on probability,
n
<<
M
, and reproduce them.
3. For every pair of replicated strings, cross one string with the other, such forming 2n
new strings.
4. Use newly generated 2n strings in step (3) to replace 2n strings with the smallest
intensities in
where
B
(
t
).
5. Let
t=t
+1, goto step (1).
To show how the above genetic algorithm works, we give a simple example
as follows(Fig. 13.9). In this example, there are 8 strings which constitute a
population.
&
Ă
Å
&
Ă
Å
&
Ă
Å
&
Ă
Å
&
Ă
Å
&
Ă
Å
&
Ă
Å
&
Ă
Å
where the value on the right of arrowhead is intensity of corresponding string
C
i
in B(
t
). The strings
C
2
,C
3
,C
6
are all the instances of schema ******1*0*…*,
denoted by
H
1
; the strings
C
3
C
5
C
8
are the instances of schema *00*1**…*,
denoted by
H
2
. Calculate each schema's average intensity:
(H
1
) =
0
+
2
+
2
v
= 1.33
3
(H
2
) =
2
+
2
+
1
v
= 1.67
3
(H) and
then with a probability value according to the standardizing value. Select 3 pairs
of strings for crossover based on probability distribution. When crossing, select a
position at random and then exchange the elements on the left of the position.
This simple operation may lead to subtle influence. Fig. 13.9 shows the whole
Then, we endow each string
C
i
with the standardizing value
S
(
C
)/
v
