Page 974 - The Mechatronics Handbook

0066_Frame_C32.fm Page 24 Wednesday, January 9, 2002 7:54 PM

TABLE 32.1 Initial Population
String Decimal Variable Function Fraction
Number String Value Value Value of Total
1 101101 45 1.125 0.0633 0.2465
2 101000 40 1.000 0.0433 0.1686
3 010100 20 0.500 0.0004 0.0016
4 100101 37 0.925 0.0307 0.1197
5 001010 10 0.250 0.0041 0.0158
6 110001 49 1.225 0.0743 0.2895
7 100111 39 0.975 0.0390 0.1521
8 000100 4 0.100 0.0016 0.0062
Total 0.2568 1.0000

of Table 32.1. Note that to use this approach, our objective function should always be positive. If it is
not, the proper normalization should be introduced at first.

Reproduction
The numbers in the last column of Table 32.1 show the probabilities of reproduction. Therefore, most
likely members numbers 3 and 8 will not be reproduced, and members 1 and 6 may have two or more
copies. Using a random reproduction process, the following population, arranged in pairs, could be
generated:

101101 → 45 110001 → 49 100101 → 37 110001 → 49
100111 → 39 101101 → 45 110001 → 49 101000 → 40

If the size of the population from one generation to another is the same, two parents should generate
two children. By combining two strings, two other strings should be generated. The simplest way to do
this is to split in half each of the parent strings and exchange substrings between parents. For example,
from parent strings 010100 and 100111, the following child strings will be generated: 010111 and 100100.
This process is known as the crossover. The resultant children are

101111 → 47 110101 → 53 100001 → 33 110000 → 48
100101 → 37 101001 → 41 110101 → 53 101001 → 41

In general, the string need not be split in half. It is usually enough if only selected bits are exchanged
between parents. It is only important that bit positions are not changed.

Mutation
In the evolutionary process, reproduction is enhanced with mutation. In addition to the properties
inherited from parents, offspring acquire some new random properties. This process is known as muta-
tion. In most cases mutation generates low-ranked children, which are eliminated in the reproduction
process. Sometimes, however, the mutation may introduce a better individual with a new property. This
prevents the process of reproduction from degeneration. In genetic algorithms, mutation usually plays
a secondary role. For very high levels of mutation, the process is similar to random pattern generation,
and such a searching algorithm is very inefficient. The mutation rate is usually assumed to be at a level
well below 1%. In this example, mutation is equivalent to the random bit change of a given pattern. In
this simple case, with short strings and a small population, and with a typical mutation rate of 0.1%,
the patterns remain practically unchanged by the mutation process. The second generation for this
example is shown in Table 32.2.

©2002 CRC Press LLC