|
![](/images/dotclear.gif) |
[an error occurred while processing this directive]
5.2.1 Coding
The second step is to give meaning to the strings. Each bit string must represent a complete solution to the problem; our problem is to select values for two parameters, m and b, so that the equation f(x)=mx + b best fits the data. Thus, each string must be coded so that it represents both parameters. We will use a method called concatenated, binary, linear mapping in which a portion of the bits in each string represent the first parameter, m, and the remaining bits represent the second parameter, b. We will simply divide the bit strings equally so that the first four bits in each string represent m and the last four bits represent b. We will interpret each four-bit substring as a binary number. For those of you who have forgotten your binary, or never actually learned it, Table 5.2 contains the binary to base 10 conversions.
Table 5.2 Binary to base 10 conversions are used in many GA encoding schemes.
binary
| base 10
| binary
| base 10
|
0000
| 0
| 1001
| 9
|
0001
| 1
| 1010
| 10
|
0010
| 2
| 1011
| 11
|
0011
| 3
| 1100
| 12
|
0100
| 4
| 1101
| 13
|
0101
| 5
| 1110
| 14
|
0110
| 6
| 1111
| 15
|
0111
| 7
|
Thus, using Table 5.2, we can convert a substring from a bit representation into a base 10 value. However, if that is all we do, then each parameter would have an integer value between 0 and 15. It is highly unlikely that our values of m and b are well represented by an integer. In fact, we know for this problem that our precise values are m=1.057 and b=-0.059. Thus, we need to map the values from binary to decimal within a restricted and different range. We can look at the data in our particular problem and see that the values of m and b are probably going to be somewhere between mmin = 0.5, mmax = 1.5, bmin = -0.5, and bmax = 0.5. There is nothing in the GA theory that helps the user select these values; they are dependent solely on the particular problem being solved and must be supplied by the user. Once, however, these values are selected, the binary strings can be mapped according to the formula:
![](images/05-01d.jpg)
where bin is the binary value of the substring and p is the length of the substring. Thus, with the minimum and maximum values provided, the value of m represented by string number 1 in Figure 5.1 (0011) is
![](images/05-02d.jpg)
The value of b represented by string number 1 is
![](images/05-03d.jpg)
Thus, string number 1 in our initial population represents a potential solution of m=0.7 and b=0.1. Each parameter, m and b, represented by different binary numbers all have a value that is mapped linearly between the minimum and maximum values selected by the user. Table 5.3 shows the values of the parameters associated with the possible substrings in the coding as it has been defined and demonstrated in Table 5.1. Furthermore, Table 5.4 is an expanded version of Table 5.2 in which the parameter values associated with the strings in the initial population have now been included.
Table 5.3 The parameter values are mapped linearly between mmin = 0.5, mmax = 1.5, bmin = -0.5, and bmax = 0.5.
binary
| base 10
| m-value
| b-value
|
0000
| 0
| 0.500
| -0.500
|
0001
| 1
| 0.567
| -0.433
|
0010
| 2
| 0.634
| -0.366
|
0011
| 3
| 0.701
| -0.300
|
0100
| 4
| 0.767
| -0.234
|
0101
| 5
| 0.834
| -0.167
|
0110
| 6
| 0.900
| -0.100
|
0111
| 7
| 0.967
| -0.034
|
1000
| 8
| 1.034
| 0.032
|
1001
| 9
| 1.101
| 0.099
|
1010
| 10
| 1.167
| 0.166
|
1011
| 11
| 1.233
| 0.232
|
1100
| 12
| 1.300
| 0.300
|
1101
| 13
| 1.367
| 0.366
|
1110
| 14
| 1.433
| 0.433
|
1111
| 15
| 1.500
| 0.500
|
Table 5.4 The initial population of strings for a GA in the least-squares problem with the parameter values obtained using the particular coding described above.
string number
| string
| m
| b
|
1
| 00111001
| 0.701
| 0.099
|
2
| 11011110
| 1.367
| 0.433
|
3
| 11100101
| 1.433
| -0.167
|
4
| 10000110
| 1.034
| -0.100
|
5
| 01000110
| 0.767
| -0.100
|
|