Transcript Genetic Algorithm - Chiang Mai University

EE459
Introduction to Artificial Intelligence
Genetic Algorithms
Practical Issues:
Representations
Simple Binary
In the standard GA, a binary encoding is used
to represent each variable being optimised
(x,y) requires two binary variables
If we are working over a range that requires an
exact number of binary bits, this is easy
for example, maximising the function (x) = x2, with
x being an integer over the range 0 to 31
0 to 31 requires 5 binary bits (because 25 = 32)
00000 = 0
00001 = 1
…
11111 = 31
More Complex Cases
If required, we can add an offset as well
e.g. x  [1 32] or x  [145 176] still require only 5
bits
x  [1 32]
 x  [0 31] + 1
x  [145 176]
 x  [0 31] + 145
00000 = 145
00001 = 146
…
11111 = 176
But what if the range is not an exact power of
2?
e.g. in the biscuit example: x, y  [1,9]
nine numbers to represent, so four bits are required
Clipping
If the number to be represented varies from M
to N, for example from 1 to 9
the first N-M (8) bit patterns represent M to N-1 (1 to
8)
the rest represent N (9)
0000 = 1
1000 = 9
0001 = 2
1001 = 9
…
…
0111 = 8
1111 = 9
Clipping has one bit pattern for each number
apart from the last, which can cause problems
the last number is more likely to occur than others
Scaling
Scaling (partially) solves this problem
for x in the range M to N, using L bits
use x = INT(b * ((N-M) / (2L - 1))) + M
where b is the normal binary equivalent of the encoding
e.g. for x  [1 9]; x = INT(b * (8/15)) + 1
0000 = 1
0001 = 1
0010 = 2
0011 = 2
0100 = 3
0101 = 3
0110 = 4
0111 = 4
1000 = 5
1001 = 5
1010 = 6
1011 = 6
1100 = 7
1101 = 7
1110 = 8
1111 = 9
Fitness Penalty
The last alternative is to just let the variable
vary over the full range of the binary
representation, but to set the fitness function to
zero for all values outside the allowable range,
e.g.

quality( xb  1, yb  1) xb , yb  0 8
f ( x, y)  
xb , yb  9 15
0


Note: this does not work in all cases
assumes ‘roulette’ selection with fitness > 0
Approximate Floating-Point
If the exact precision of the figures is not too
important, then just divide a binary range of the
appropriate size into intervals
for example, to maximise (x) = x2 to 3 decimal
places, with x over the range 0.000 to 31.999
3 decimal places requires 1000 numbers
nearest power of 2 is 1024 ( = 210 )
10 bits required for decimal point + 5 bits required for range
15 bits gives a number between 0 and 32767
x = xb / 1024 gives x to approx. 3 d.p.s
Exact Floating-Point
If an ‘exact’ floating-point precision is required,
then probably a method similar to binary
scaling is the best option
For example to represent (exactly) the
numbers
0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9
use the same coding scheme as shown for the
scaling example previously, including using an ‘INT’
function to remove fractions, and then divide by ten
Think carefully about the representation used
remember that floating-points are not exact!
Gray Code
With a standard binary representation, it is
difficult for a GA to add (subtract) 1 from certain
numbers
e.g. 00111111 (63) to 01000000 (64) requires seven
changes to the bit pattern
this can cause the binary GA to get ‘stuck’
One solution is to use a new coding scheme in
which each successive number is represented
by a bit pattern which is only one bit different
from the previous number
such coding schemes are call gray codes
Gray Code Example
Gray
Binary
0000 = 0
0001 = 1
0010 = 2
0011 = 3
0100 = 4
0101 = 5
0110 = 6
0111 = 7
1000 = 8
1001 = 9
1010 = 10
1011 = 11
1100 = 12
1101 = 13
1110 = 14
1111 = 15
0000 = 0
0001 = 1
0011 = 2
0010 = 3
0110 = 4
0111 = 5
0101 = 6
0100 = 7
1100 = 8
1101 = 9
1111 = 10
1110 = 11
1010 = 12
1011 = 13
1001 = 14
1000 = 15
Gray code: flip the rightmost bit that generates
a pattern that is different from all the previous
ones
Generating Gray Code
To generate a gray code from a binary code
assume the binary code is N bits long
bits are numbered 1 to N, where 1 is the leftmost bit
looping method
gray(1)= binary(1);
for i = 2:N
gray(i)=
binary(i-1) XOR binary(i);
end
binary(1)= gray(1);
for i = 2:N
binary(i)=
binary(i-1) XOR gray(i);
end
matrix method (e.g. 8 bits)
A = [ 1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1 ];
gray= (A * binary) MOD 2;
binary= (INV(A) * gray) MOD 2;