Information Technology Reference
In-Depth Information
Odd-2 (XOR)
Odd-3
Odd-4
A
A
A
O
N
O
N
O
N
a
c
b
A
Odd2
A
Odd3
d
A
a
c
b
Odd2
Odd3
d
Odd-5
Odd-6
A
A
O
N
O
N
e
Odd4
A
Odd5
f
A
e
f
Odd4
Odd5
Figure 4.9.
Finding patterns to design parsimonious solutions to odd-
n
-parity
functions. Note that the simple structure that emerges here can be used to design
parsimonious solutions to any odd-parity function.
of the function. The second reason is also related to the proportion of 0's and
1's in the output bits, more specifically, with the fact that the proportion of 0's
increases exponentially according to the rule
y
= 2
n
-
n
. And this poses a real
problem not only in terms of measuring the fitness of the individuals, but also
in finding ways out of local optima in solution space.
Consider, for instance, the 6-exactly-one-on function with a total of 64
transition states. In this case, only six cases are of the type “1”, whereas 58
belong to the class “0”. So, the possibilities are immense for candidate solu-
tions that are good at realizing all this excess of “0” cases, but unfortunately
that won't help our cause. Indeed, fitness functions based on the number of
hits are unable to get populations out of local optima, but a fitness function
based on the sensitivity/specificity indicators can, as it tends to minimize the
number of false negatives. Indeed, such fitness functions are the key to deal-
ing with such unbalanced sets of fitness cases, be it in logic synthesis or
