Genetic Algorithm Example

Problem: Find a test vector to detect the fault Y stuck-at 0.

Approach: Use a genetic algorithm (GA) to find a test vector that excites the fault and propagates the fault effects to the primary output. Characters in the GA individual represent values to be applied to the primary inputs of the circuit.

Use a simple GA with the following parameters:

Fault excitation requires ones on lines A through J, and fault propagation requires zeros on lines K through S. Use a fitness function which favors vectors that excite the fault or have more noncontrolling values on inputs A through J and K through S.

Fitness = (1 if fault is excited or 0 otherwise) +
                  (fraction of inputs on gate Y with noncontrolling values) +
                  (fraction of inputs on gate Z with noncontrolling values)

GA Population by Generation:
    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

    Best Individuals by Generation:
    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Generation Vector Fitness
0 0011010111000001000 1.48889
1100011101100000100 1.37778
1101111111111010010 1.34444
1 0101011111000000000 1.7
1100111111110000000 1.57778
0010001111001001000 1.27778
2 1111111111101000000 2.77778
1101110111000001000 1.68889
1101010111000001000 1.58889
3 1111111111100001100 2.66667
1110011111100000000 1.68889
1101010111000001000 1.58889
4 1111111111000000011 2.77778
1110111110000000000 1.8
1101011111000000001 1.68889
5 1111111110000000000 1.9
1101111011000000000 1.8
1101111111000001000 1.78889
6 1101111011000000000 1.8
0111011111000000000 1.8
1110011111000000000 1.8
7 1111111111000000000 3 <-- Solution! Total vectors evaluated = 243
1111111111110001001 2.55556
1111111111101110000 2.55556
8 1111111111000000000 3
1111111111000000000 3
1111111111001110000 2.66667
9 1111111111000000000 3
1111111111000000000 3
1111111111000000000 3
10 1111111111000000000 3
1111111111000010000 2.88889
1111111111001010000 2.77778
11 1111111111000000000 3
1111111111000000000 3
1111111111000001000 2.88889
12 1111111111000000000 3
1111111111000000000 3
1111111111000000000 3
13 1111111111000000000 3
1111111111000000000 3
1111111111000000000 3
14 1111111111000000000 3
1111111111000000000 3
1111111111000000000 3
15 1111111111000000000 3
1111111111000000000 3
1111111111000000000 3

Last updated May 21, 1996.
Send any questions to liz@crhc.uiuc.edu
Back to IGATE